Abstract
Game theory studies mathematical models of interactions amongst selfinterested 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 mixedstrategy 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 NPcompleteness, due to a result of Megiddo saying that total search problems cannot be NPcomplete unless NP is equal to coNP.
In this tutorial, which is intended for people familiar with NPcompleteness, I give an overview of the alternative notions of computational hardness that apply to gametheoretic 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 polynomialtime algorithm that applies to some given class of games. A followup 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? 2player games are easy to solve in practice, using the LemkeHowson algorithm, so is there a satisfying mathematical sense in which 2player games are easy to solve? (For example, a sense in which LemkeHowson 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 = {2020},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897781},
ISSN = {18688969},
year = {2015},
volume = {30},
editor = {Ernst W. Mayr and Nicolas Ollinger},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/4960},
URN = {urn:nbn:de:0030drops49606},
doi = {10.4230/LIPIcs.STACS.2015.20},
annote = {Keywords: equilibrium, noncooperative games, computational complexity}
}
Keywords: 

equilibrium, noncooperative 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 