Publikationsserver der RWTH Aachen University
Nash equilibria and improvement dynamics in congestion games
Abstract
dc:descriptionCommunication infrastructures and markets are maintained and used by millions of entities each of them facing a private objective. The vast number of participants in conjunction with their individual goals to choose the best alternative gave rise to study such scenarios in the framework of game theory as it is rather unrealistic to assume that a centrally computed solution can be implemented. In this thesis, we follow this line of research and study congestion games as introduced by Rosenthal in 1973 and several modifications of his original approach. Congestion games model scenarios in which a finite number of players individually strives to allocate resources maximizing their utility. Here, the resources can correspond to quite different types of objects, e.g. to edges in a network or to machines processing tasks. Given a set of resources a player's goal is to select a feasible subset of the resources, subsequently named a strategy, that minimizes the sum of the latencies of the resources in the set. Thereby, a subset is feasible if it possesses a predefined combinatorial structure, e.g., corresponds to a path or a tree in a network. The latency of a resource depends on the number of players sharing that resource, i.e., the congestion, as it increases the more player allocate the resource. Since the seminal presentation of this notion of games several modifications including weighted and player-specific congestion games have been proposed. In a weighted congestion game, the congestion on a resource depends on the weighted number of players, whereas players compute their latencies with respect to player-specific payoff functions in a player-specific congestion game. Note that congestion games lie at the intersection of game theory and combinatorial optimization as from a global perspective we are concerned with a game, whereas from the local perspective of individual players we are concerned with a combinatorial optimization problem. Among others, one goal of this thesis is to apply results from combinatorial optimization in order to gain new insights into congestion games. At first, we study the existence of Nash equilibria in weighted and in player-specific congestion games as every standard game without these additional requirements possesses a Nash equilibrium. We characterize those games with respect to the combinatorial structure of the players' strategy spaces in which a Nash equilibrium is guaranteed to exist. Namely, we show that the matroid property, i.e., if the strategy space of each player is the set of bases of a matroid, is the maximal property that guarantees the existence of Nash equilibria. If this property, however, is not satisfied we cannot guarantee the existence of Nash equilibrium without taking additional properties of the game into account. We also study dynamics that arise if players actually play a congestion game and consider the time until they terminate at a stable configuration in which none of the players can improve its latency. In best response dynamics we assume that players sequentially switch to the best available strategy given fixed choices of the others. In case of standard congestion games, we show that the matroid property is the maximal property on the combinatorial structure of the players' strategy spaces that guarantees polynomial time convergence. In case of weighted and player-specific congestion games, however, we provide analytical and experimental evidence that even in singleton games, best response dynamics do not terminate quickly. Note that in singleton games, each strategy is a singleton set. In case of standard congestion games, we also study concurrent imitation dynamics that arise if players imitate each other on the basis of a protocol we propose. We motivate to study such dynamics as the assumption that players have complete knowledge, which is usually applied when considering Nash equilibria, is likely not to be true in many real world applications. The protocol we propose guarantees pseudo-polynomial time convergence to an imitation-stable state in a monotonic fashion, that is, undesirable overshooting effects do not occur. We can also prove that an approximate equilibrium in which only a small fraction of the players sustains latency significantly above or below the average is reached quickly. Finally, we propose to study a modification of player-specific singleton congestion games in which the resources can assign priorities to the players in order to foster some of them. In our model only the players with the highest priority gain access to a resource whereas the others are locked out. We analyze the existence of Nash equilibria in this class of games and discuss relationships to other existing models.
Degree
thesis:*- Grantor dc:publisher
- Publikationsserver der RWTH Aachen University
- Year dc:date
- 2009
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Ackermann, Heiner
- Contributors dc:contributor
-
- Vöcking, Berthold
Subjects
dc:subject × 8Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- eng