Bounds and dynamics for empirical game theoretic analysis

Tuyls, Karl, Perolat, Julien, Lanctot, Marc, Hughes, Edward, Everett, Richard, Leibo, Joel Z, Szepesvari, Csaba and Graepel, Thore (2020) Bounds and dynamics for empirical game theoretic analysis. AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS, 34 (1). p. 7.

Text
Tuyls2019_Article_BoundsAndDynamicsForEmpiricalG.pdf - Published version
Download (2MB) | Preview

Official URL: http://dx.doi.org/10.1007/s10458-019-09432-y

Abstract

<jats:title>Abstract</jats:title><jats:p>This paper provides several theoretical results for empirical game theory. Specifically, we introduce bounds for empirical game theoretical analysis of complex multi-agent interactions. In doing so we provide insights in the empirical meta game showing that a Nash equilibrium of the estimated meta-game is an approximate Nash equilibrium of the true underlying meta-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 evolutionary dynamics analysis of meta-games using heuristic payoff tables (HPTs) to asymmetric games. The state-of-the-art has only considered evolutionary dynamics of symmetric HPTs 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<jats:italic>AlphaGo</jats:italic>algorithm (symmetric), the dynamics of the Colonel Blotto game played by human players on Facebook (symmetric), the dynamics of several teams of players in the capture the flag game (symmetric), and an example of a meta-game in Leduc Poker (asymmetric), generated by the policy-space response oracle multi-agent learning algorithm.</jats:p>

Item Type:	Article
Uncontrolled Keywords:	Empirical games, Asymmetric games, Replicator dynamics
Depositing User:	Symplectic Admin
Date Deposited:	28 Feb 2020 11:37
Last Modified:	18 Jan 2023 23:59
DOI:	10.1007/s10458-019-09432-y
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3077039