Fischer, Felix (2009): Complexity results for some classes of strategic games. Dissertation, LMU München: Faculty of Mathematics, Computer Science and Statistics 

PDF
Fischer_Felix.pdf 1MB 
Abstract
Game theory is a branch of applied mathematics studying the interaction of selfinterested entities, socalled agents. Its central objects of study are games, mathematical models of realworld interaction, and solution concepts that single out certain outcomes of a game that are meaningful in some way. The solutions thus produced can then be viewed both from a descriptive and from a normative perspective. The rise of the Internet as a computational platform where a substantial part of today's strategic interaction takes place has spurred additional interest in game theory as an analytical tool, and has brought it to the attention of a wider audience in computer science. An important aspect of realworld decisionmaking, and one that has received only little attention in the early days of game theory, is that agents may be subject to resource constraints. The young field of algorithmic game theory has set out to address this shortcoming using techniques from computer science, and in particular from computational complexity theory. One of the defining problems of algorithmic game theory concerns the computation of solution concepts. Finding a Nash equilibrium, for example, i.e., an outcome where no single agent can gain by changing his strategy, was considered one of the most important problems on the boundary of P, the complexity class commonly associated with efficient computation, until it was recently shown complete for the class PPAD. This rather negative result for general games has not settled the question, however, but immediately raises several new ones: First, can Nash equilibria be approximated, i.e., is it possible to efficiently find a solution such that the potential gain from a unilateral deviation is small? Second, are there interesting classes of games that do allow for an exact solution to be computed efficiently? Third, are there alternative solution concepts that are computationally tractable, and how does the value of solutions selected by these concepts compare to those selected by established solution concepts? The work reported in this thesis is part of the effort to answer the latter two questions. We study the complexity of wellknown solution concepts, like Nash equilibrium and iterated dominance, in various classes of games that are both natural and practically relevant: ranking games, where outcomes are rankings of the players; anonymous games, where players do not distinguish between the other players in the game; and graphical games, where the wellbeing of any particular player depends only on the actions of a small group other players. In ranking games, we further compare the payoffs obtainable in Nash equilibrium outcomes with those of alternative solution concepts that are easy to compute. We finally study, in general games, solution concepts that try to remedy some of the shortcomings associated with Nash equilibrium, like the need for randomization to achieve a stable outcome.
Item Type:  Thesis (Dissertation, LMU Munich) 

Keywords:  Algorithmic game theory, Normalform games, Solution concepts, Computational complexity 
Subjects:  600 Natural sciences and mathematics > 510 Mathematics 600 Natural sciences and mathematics 
Faculties:  Faculty of Mathematics, Computer Science and Statistics 
Language:  English 
Date Accepted:  3. July 2009 
1. Referee:  Hofmann, Martin 
Persistent Identifier (URN):  urn:nbn:de:bvb:19103593 
MD5 Checksum of the PDFfile:  cc3cc9f9d1dd060147f603b30b47af97 
Signature of the printed copy:  0001/UMC 17908 
ID Code:  10359 
Deposited On:  27. Jul 2009 11:57 
Last Modified:  16. Oct 2012 08:29 