On the complexity of equilibria in games with succinct representation

Algorithmic game theory studies computational and algorithmic questions arising from the behavior of players in strategic situations. The computational aspects of game theory became subject to closer scrutiny in the last two decades. One reason for this is certainly the advent of large scale communication networks – most prominently the Internet. Modern technology allows to monitor, evaluate, and influence the behavior of interacting agents in large systems. One may think of many (future) applications including distribution of goods and services in auctions, allocation of resources, routing of data packages, or regulation of vehicle traffic. One of the main contributions of game theory is the ability to predict how these games will be played. The most commonly used solution concepts are equilibrium concepts that describe which strategies will be adopted by players. One of the central challenges in algorithmic game theory is to characterize the computational complexity of such equilibria. Results in this direction yield important indicators if game-theoretic solution concepts are plausible outcomes of competitive environments in practice. Furthermore, computational complexity is of practical importance if one desires to predict or influence the outcome of a strategic situation in a large-scale environment. In this work, we answer fundamental complexity theoretic questions about several equilibrium concepts. We investigate the complexity of problems regarding the existence, recognition, and computation of Nash equilibria, strong equilibria, and sink equilibria. Probably the most prominent solution concept in (non-cooperative) game theory is the Nash equilibrium – a strategy profile, from which no player can profitably unilaterally deviate. A refinement of Nash equilibria is the concept of strong equilibrium – a strategy profile, from which no coalition wants to jointly deviate. We also study the dynamics that emerge when players iteratively play best responses. That is, in each time step one of the players chooses his optimal strategy given that strategies of the other players are fixed. We identify games in which this process converges to an equilibrium and study the duration of this process. For games in which the best response dynamics does not converge, the concept of sink equilibrium was proposed. Intuitively, a sink equilibrium is the set of strategy profiles on which the aforementioned best response dynamics eventually ends up without leaving this set again. a strongly connected component without outgoing arcs of the A sink equilibrium is guaranteed to exist in every finite game. We study the complexity of two basic questions related to sink equilibria – whether a given strategy profile belongs to a sink equilibrium and whether a game has a sink equilibrium that consists of more than one strategy profile. We study these equilibrium concepts in games that have a succinct representation. Unlike games in normal form, in which the utilities or payoffs for the players are given explicitly for every possible strategy profile of the game, we consider games that have a certain underlying combinatorial structure which allows for a compact description of the game: That is, the description size of the game grows only polynomial with natural parameters such as the number of players or the number of strategies. A well studied class of succinct games are congestion games. They are an elegant model to adress the effects of resource usage and congestion with strategic agents and have been used frequently to model competitive network routing scenarios. We also consider two generalizations of the class of congestion games, namely weighted and player-specific congestion games, and a variation in form of bottleneck congestion games. In addition, we study the class of anonymous games with a constant number of actions. Here, a player's payoff does not depend on the identities of others players, which allows to represent the game in polynomial space. Finally, we question the assumption of selfish players and consider a scenario in which players are partly altruistic. We study the existence and the complexity of equilibria in congestion games with such players. Some of our results can be extended to a class of general potential games and social cost functions, and we study a number of prominent examples. In addition to these results for uncoordinated dynamics, we consider a scenario with a central altruistic institution that can set incentives for the agents to adopt favorable behavior.

Grantor dc:publisher

Publikationsserver der RWTH Aachen University

Year dc:date

2010

Author dc:creator

• Skopalik, Alexander

Contributors dc:contributor

• Vöcking, Berthold

• info:eu-repo/classification/ddc/004
• Gleichgewichtspunkt <Spieltheorie>
• Berechnungskomplexität
• Informatik
• complexity
• game theory
• equilibrium

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

https://publications.rwth-aachen.de/search?p=id:%22RWTH-CONV-124654%22

OAI identifier oai:identifier

oai:publications.rwth-aachen.de:63207