Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
Algorithmic Game Theory (Tutorial)
| pdf-format: |
|
Abstract
Game theory studies mathematical models of interactions amongst self-interested entities. A "solution concept" means a description of the outcome of a game, and it is important that it should be defined in such a way that a solution always exists (every game should have an outcome). Nash's famous theorem that mixed-strategy equilibria are guaranteed to exist, resulted in Nash equilibrium being the most prominent solution concept in game theory.As a result, computational challenges of the form "given a game, find a solution", have the property that we are searching for something whose existence is guaranteed (they are total search problems). Moreover, these solutions belong to the complexity class NP, since it is usually straightforward to check whether a proposed solution is correct (an incorrect one will admit a profitable deviation by one or more of the players, and this is usually easy to find). However, in versions of the problem that appear to be computationally hard, we cannot apply NP-completeness, due to a result of Megiddo saying that total search problems cannot be NP-complete unless NP is equal to co-NP.
In this tutorial, which is intended for people familiar with NP-completeness, I give an overview of the alternative notions of computational hardness that apply to game-theoretic solution concepts. I discuss the complexity class PPAD (introduced by Papadimitriou) which captures the computational complexity of various classes of games that don’t seem to be solvable in polynomial time. I also mention the complexity classes PLS and FIXP, and the kinds of games that they apply to.
Suppose, alternatively, that we have a polynomial-time algorithm that applies to some given class of games. A follow-up question is whether there exist algorithms that find a solution via processes that reflect decentralised selfish behaviour. This is because a solution concept arguably remains unrealistic if it can be efficiently computed, but only using a highly centralised algorithm. In the second half of the tutorial I present some results on learning dynamics for equilibrium computation, and mention recent work on communication complexity and query complexity.
I discuss some research directions and open problems, such as the following. What are the prospects for proving that PPAD is as hard as NP? How about algorithms that find improved approximate Nash equilibria? 2-player games are easy to solve in practice, using the Lemke-Howson algorithm, so is there a satisfying mathematical sense in which 2-player games are easy to solve? (For example, a sense in which Lemke-Howson works "most of the time"?)
BibTeX - Entry
@InProceedings{goldberg:LIPIcs:2015:4960,
author = {Paul W. Goldberg},
title = {{Algorithmic Game Theory (Tutorial)}},
booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
pages = {20--20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-78-1},
ISSN = {1868-8969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4960},
URN = {urn:nbn:de:0030-drops-49606},
doi = {10.4230/LIPIcs.STACS.2015.20},
annote = {Keywords: equilibrium, non-cooperative games, computational complexity}
}
| Keywords: | equilibrium, non-cooperative games, computational complexity | |
| Statistics: |
 Number of document requests |
|
| Collection: | 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) | |
| Issue Date: | 2015 | |
| Date of publication: | 26.02.2015 |
