Geia se olous,
Auth thn Paraskeuh epistrefoume
me omilhtria thn Katia Papakonstantinopoulou, apo to Panepisthmio Athinwn.
Stis 4, sthn A36.
Akolouthei titlos kai abstract
Title: Contention issues in congestion games
Abstract:
Communication networks, due to the competitive nature of their users, are widely studied using Game Theory. A key tool in analyzing such networks, modeled as games, is the study of their stable states, that is, their equilibria. Understanding the properties of equilibria can provide insights into the effectiveness of economic policies, engineering decisions, etc.
Among the communication networks of interest, there is an important class in which the players can time their participation in the game with the hope that fewer players will compete for the same resources. Motivated by these games, we study time-dependent strategies for playing congestion games. In this talk I will discuss some recent advances.
I will first present the two models we introduce: (i) the boat model, in which the latency of a player is influenced only by the players that start at the same time, and (ii) the conveyor belt model, in which the latency of a player is affected by the players that share the system, even if they started earlier or later.
Then the structural properties of the games of both models will be described. I will show that the games of the boat model are themselves congestion games. The same is true for the games of two players for the conveyor belt model; however, for this model the games of three or more players are not in general congestion games and may not have pure equilibria.
Consequently, the boat games do possess pure Nash equilibria and the exact topology (the order of the edges in the paths) of the network does not affect the latency of the players, while the conveyor belt games the network topology does matter and they may not have pure Nash equilibria for three or more players.
Finally I will characterize the symmetric Nash equilibria and optimal solutions of boat games of networks of parallel links with affine latencies and conveyor belt games of two players on parallel links with arbitrary latency functions, and give bounds on their price of anarchy and stability.
This is joint work with Elias Koutsoupias.
----------------------------------------------------------------
Exei prokupsei mia allagh sthn wra twn parousiasewn,
H omilia tha einai thn Paraskeuh stis 5 sthn aithousa A36 kai oxi stis 4,
Katia Papakonstantinopoulou, University of Athens,
Title: Contention issues in congestion games
Abstract:
Communication networks, due to the competitive nature of their users, are widely studied using Game Theory. A key tool in analyzing such networks, modeled as games, is the study of their stable states, that is, their equilibria. Understanding the properties of equilibria can provide insights into the effectiveness of economic policies, engineering decisions, etc.
Among the communication networks of interest, there is an important class in which the players can time their participation in the game with the hope that fewer players will compete for the same resources. Motivated by these games, we study time-dependent strategies for playing congestion games. In this talk I will discuss some recent advances.
I will first present the two models we introduce: (i) the boat model, in which the latency of a player is influenced only by the players that start at the same time, and (ii) the conveyor belt model, in which the latency of a player is affected by the players that share the system, even if they started earlier or later.
Then the structural properties of the games of both models will be described. I will show that the games of the boat model are themselves congestion games. The same is true for the games of two players for the conveyor belt model; however, for this model the games of three or more players are not in general congestion games and may not have pure equilibria.
Consequently, the boat games do possess pure Nash equilibria and the exact topology (the order of the edges in the paths) of the network does not affect the latency of the players, while the conveyor belt games the network topology does matter and they may not have pure Nash equilibria for three or more players.
Finally I will characterize the symmetric Nash equilibria and optimal solutions of boat games of networks of parallel links with affine latencies and conveyor belt games of two players on parallel links with arbitrary latency functions, and give bounds on their price of anarchy and stability.
This is joint work with Elias Koutsoupias.
