A Generalised Method for Empirical Game Theoretic Analysis

By Karl Tuyls, Julien Pérolat, Marc Lanctot, Joel Z. Leibo, Thore Graepel. 2018

60 citations recorded by the source corpus.

This paper provides theoretical bounds for empirical game theoretical analysis of complex multi-agent interactions. We provide insights in the empirical meta game showing that a Nash equilibrium of the meta-game is an approximate Nash equilibrium of the true underlying game. We investigate and show how many data samples are required to obtain a close enough approximation of the underlying game. Additionally, we extend the meta-game analysis methodology to asymmetric games. The state-of-the-art has only considered empirical games in which agents have access to the same strategy sets and the payoff structure is symmetric, implying that agents are interchangeable. Finally, we carry out an empirical illustration of the generalised method in several domains, illustrating the theory and evolutionary dynamics of several versions of the AlphaGo algorithm (symmetric), the dynamics of the Colonel Blotto game played by human players on Facebook (symmetric), and an example of a meta-game in Leduc Poker (asymmetric), generated by the PSRO multi-agent learning algorithm.

Subfields: Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Game & Decision Theory

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “Visualization of Evolutionary and Policy Learning Dynamics One common visualization tool in the multiagent learning literature (especially in games) is a phase portrait that shows a vector field and/or trajectories of particle the depict local changes to the policy under specific update dynamics [64”
Emergent Coordination Through Competition (2019, background): “Survival-of-the-fittest analysis as shown in Al-Shedivat et al. (2017) would lead to a cycle, and agent ranking would depend on when measurements are taken (Tuyls et al., 2018).”
Neural Replicator Dynamics (2019, background): “EGT models the interactions of a population of individuals that have minimal knowledge of opponent strategies or preferences, and has proven vital for not only the analysis and evaluation of MARL agents [45, 50, 66, 67], but also the development of novel algorithms [64].”
Re-evaluating evaluation (2018, methodology): “Empirical game theory has been applied to domains like poker and continuous double auctions, and has recently been extended to asymmetric games [54–58]. von Neumann winners in the dueling bandit setting and NE-regret are related to Nash averaging [59–62].”
Autocurricula and the Emergence of Innovation from Social Interaction: A Manifesto for Multi-Agent Intelligence Research (2019, background): “For example, Tuyls et al. (2018) showed strategic intransitivities between AlphaGo versions and Zen, the previous state-of-the-art Go engine.”
Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (2018, background): “These analyses are common in multiagent learning as they allow visual depiction of the policy changes and how different factors affect the (convergence) behavior [83, 92, 13, 91, 11, 94, 1, 99, 98, 8, 89].”
α-Rank: Multi-Agent Evaluation by Evolution (2019, background): “hods In this section, we concisely outline the game-theoretic concepts and methods necessary to understand the remainder of the paper. For a detailed discussion of the concepts we refer the reader to [8, 13, 30, 31]. We also introduce a novel game-theoretic concept, Markov-Conley chains, which we us”