AAAI2013

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

1. [game model] [15 minutes -- Nicola]

* definition of finite game

* example rock-paper-scissors

* matrix representation (bimatrix for 2-player)

* definition of strategies

* definition of expected utility


2. [solution concepts] [30 minutes -- Nicola]

* non-equilibrium: dominance, iterated dominance, minmax/maxmin

* equilibrium: Nash, Nash refinements (perfect), Nash relaxations (correlated), leader-follower


3. [computing a Nash equilibrium] [75 minutes -- Nicola]

* matrix game (minmax/maxmin derivation)

* bimatrix game (LH, MILP, support enumeration)

* correlated (LP)

* leader follower (LP)


4. [computational complexity] [30 minutes -- Troels]

* why NASH is not NP-complete

* PPAD computational complexity class

* other complexity results (e.g., searching for an optimal equilibrium, verification complexity)


5. [extensive form] [30 minutes -- Troels]

* game model definition (trees, perfect vs. imperfect information)

* strategies in extensive form (behavioral vs. plans)

* normal-form of an extensive-form

* sequence form


6. [refinements ] [30 minutes -- Troels]

* subgame perfect equilibrium

* sequential equilibrium

* normal-form perfect

* quasi perfect and extensive-form perfect equilibria

* normal-form proper


7. [extensive form algorithms] [30 minutes -- Troels]

* Lemke algorithm for sequence form

* Counter factual regret minimization





Tutors

Nicola Gatti is currently Assistant Professor with tenure at the Politecnico di Milano, Italy. His research topics are artificial intelligence, multiagent systems, and specifically algorithmic game theory. Currently, he is lecturer of Informatics Systems (BSc course), Internet Monetization (MSc course), Algorithmic Game Theory (PhD course), and assistant of the graduate courses of Artificial Intelligence and of Autonomous Agents and Multiagent Systems in computer engineering, at Politecnico di Milano.

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 noncooperative game theory. He is currently a postdoctoral associate at Duke University.