Extensive–form games with heterogeneous populations: solution concepts, equilibria characterization, learning dynamics

Article type: Research Article

Authors: Gatti, Nicola | Panozzo, Fabio^* | Restelli, Marcello

Affiliations: Politecnico di Milano, Piazza Leonardo da Vinci 32 Milano, Italy

Correspondence: [*] Corresponding author: Fabio Panozzo, Politecnico di Milano, Piazza Leonardo da Vinci 32 Milano, Italy. E-mail: Panozzo@elet.polimi.it.

Abstract: The adoption of Nash equilibrium (NE) in real–world settings is often impractical due to its too restrictive assumptions. Game theory and artificial intelligence provide alternative (relaxed) solution concepts. When knowledge about opponents’ utilities and types are not available, the appropriate solution concept for extensive–form games is the self–confirming equilibrium (SCE), which relaxes NE allowing agents to have wrong beliefs off the equilibrium path. In this paper, we provide the first computational and learning study of the situations in which a two–agent extensive–form game is played by heterogeneous populations of individuals that repeatedly match (e.g., eBay): we extend the SCE concept, we study the equilibrium computation problem, and we study how these equilibria affect learning dynamics. We show that SCEs are crucial for characterizing both stable states of learning dynamics and the dynamics themselves.

Keywords: Artificial Intelligence, Multi–agent systems, Algorithms, Economics, Game Theory (cooperative and non-cooperative)

DOI: 10.3233/IA-160092

Journal: Intelligenza Artificiale, vol. 10, no. 1, pp. 19-31, 2016