Complexity results for some classes of strategic games

Game theory is a branch of applied mathematics studying the
interaction of self-interested entities, so-called agents. Its
central objects of study are games, mathematical models of
real-world 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 real-world decision-making, 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 well-known 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 well-being 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.