Tuyls, K;
Pérolat, J;
Lanctot, M;
Hughes, E;
Everett, R;
Leibo, JZ;
Szepesvári, C;
(2019)
Bounds and dynamics for empirical game theoretic analysis.
Autonomous Agents and Multi-Agent Systems
, 34
, Article 7. 10.1007/s10458-019-09432-y.
Preview |
Text
Tuyls2019_Article_BoundsAndDynamicsForEmpiricalG.pdf - Published Version Download (2MB) | Preview |
Abstract
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 AlphaGo 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.
| Type: | Article |
|---|---|
| Title: | Bounds and dynamics for empirical game theoretic analysis |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1007/s10458-019-09432-y |
| Publisher version: | https://doi.org/10.1007/s10458-019-09432-y |
| Language: | English |
| Additional information: | This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10091328 |
Archive Staff Only
 |
View Item |
