Equilibrium Computation: Theory and Practice

Tutorial at AAMAS 2010: Morning, May 11

Brief description of the tutorial

This tutorial provides a broad introduction to the recent literature on the computation of equilibria of simultaneous-move games, weaving together both theoretical and applied viewpoints. It is aimed at members of the AAMAS community with an interest in understanding recent results about the complexity of equilibrium computation and on representation and reasoning methods for compactly represented games. It will also be suitable for those with little experience with game theory (as distinct, e.g., from auction theory). The tutorial will focus on the computational problem of identifying a Nash equilibrium in different game models. We will also more briefly consider approximate equilibria, correlated equilibria, pure-strategy Nash equilibria, and equilibria of two-player zero-sum games.

The tutorial is divided into two parts. The first will focus on normal-form games. It will begin with a brief discussion of game theoretic solution concepts and fundamental computational results. We will then turn to the complexity of equilibrium computation, explaining in detail the result that NASH (the problem of computing a Nash equilibrium) is PPAD-complete. We will end this section by considering the complexity of approximating NASH. The second part considers compact game representations. We will begin by explaining the importance and challenges of compact representation, giving some foundational theoretical results. We will then describe a variety of compact game representations (symmetric, anonymous, congestion, graphical, and action-graph games), illustrating each with motivating examples. Finally, we will survey algorithms for computing the equilibria of compactly-represented games, and conclude by identifying some open research challenges.

Detailed outline of the tutorial

Part I: Equilibrium and Equilibrium Computation in Normal-Form Games

Part I(a): Normal-Form Game Theory, solution concepts, and computational formulations (Kevin)

• Getting our bearings: a quick game theory refresher
• Solution concepts
• Computational formulations

Part I(b): Complexity of NASH (Costis)

• Sperner's Lemma and Nash's proof
• Complexity of epsilon-NASH

Part II: Equilibrium Computation in Compactly-Represented Games

Part II(a) (Costis)

• Background: polynomial type, expected utility problem, ...
• Symmetric games
• Anonymous games

Part II((b) (Kevin)

• Congestion games
• Graphical games
• Action-Graph games