EQUILIBRIUM COMPUTATION TUTORIAL
EQUILIBRIUM COMPUTATION TUTORIAL
Overview
This tutorial aims at providing a gentle introduction to the computational results for non-cooperative game theory. The tutorial will introduce the basics of non-cooperative game theory: mechanisms in strategic and extensive form and strategies, solution concepts and their motivation, and examples of applications. Then, for the most adopted solution concepts, the computational complexity of verifying a solution, finding an equilibrium, and other advanced results (i.e., searching for optimal equilibria or approximate equilibria) will be discussed and subsequently the main algorithms will be presented with some examples of applications. The tutorial will provide basics, well established results, and recent advancements.
Target audience
Our primary target audience is students and other novices who will benefit from an extensive introduction to one of the most important areas of multi-agent systems research.
Syllabus
A) game theory basics
1. game definition: mechanisms in strategic form and in extensive form and strategies (normal form, agent form, sequence form)
2. non-equilibrium solution concepts for strategic form: dominance and never best response, minmax/maxmin
3. equilibrium solution concepts for strategic form: Nash, perfect Nash, Bayes-Nash, leader-follower, proper, correlated
4. equilibrium solution concepts for extensive form: subgame perfect equilibrium, sequential equilibrium, normal-form/quasi/extensive-form perfect equilibrium
5. advanced concepts: epsilon-approximate Nash, self-confirming equilibria
6. examples of applications for multi autonomous agents
B) computational results for strategic form games
1. computing a minmax/maxmin: LP for two players games and three or more with correlated strategies, NP-hard with three or more non-correlated players
2. computing a Nash equilibrium: PPAD class, completeness, Lemke-Howson algorithm, other formulations (MILP, support enumeration, local search techniques)
3. computing a perfect Nash: computational complexity with two (P) and more (NP-hard) players of verifying a solution, algorithms
4. computing a correlated equilibrium
C) computational results for extensive form games
1. computing a minmax/maxmin: LP for two players and more correlated players
2. computing a Nash equilibrium: Lemke's algorithm
3. refinements: verification (sequential equilibrium, quasi-perfect, proper) and computation
D) computational results with advanced concepts
1. computational complexity of finding an epsilon-approximate Nash equilibrium, anytime versions of Lemke-Howson, MILP, local search
2. algorithms for self-confirming equilibria with two players
Tutors
Nicola Gatti is currently assistant professor with tenure at the Politecnico di Milano, Italy. His research topics are artificial intelligence, multi-agent systems, and specifically algorithmic game theory. Currently, he is lecturer of Informatics Systems (undergraduate course) and Algorithmic Game Theory (PhD course), and assistant of the graduate courses of Artificial Intelligence and of Autonomous Agents and Multi-Agent Systems in Computer Engineering, at Politecnico di Milano. He also delivered the lecture "Automated Negotiations in Electronic Markets" (with Maria Fasli) at EASSS for three years in row (2008-2010) and he delivered the tutorial "Security games" (with Chris Kiekintveld and Manish Jain) at AAMAS2011 and AAAI2011. He has co-authored about 40 papers on algorithmic game theory presented at several international conferences and journals, among them 4 papers at AAAI, 15 papers at AAMAS, 2 papers at AIJ.
Troels Bjerre Sørensen is a Research Fellow at the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick, United Kingdom. His primary research area is the computational aspects of solution concept in non-cooperative game theory. He is currently lecturing "Algorithmic Game Theory" at the University of Warwick.