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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    A Generalised Method for Empirical Game Theoretic Analysis


    Beteiligte:
    Tuyls, K (Autor:in) / Perolat, J (Autor:in) / Lanctot, M (Autor:in) / Leibo, JZ (Autor:in) / Graepel, T (Autor:in)

    Erscheinungsdatum :

    2018-07-01


    Anmerkungen:

    In: AAMAS '18: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. (pp. pp. 77-85). ACM: Stockholm, Sweden. (2018)


    Medientyp :

    Paper


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    Bounds and dynamics for empirical game theoretic analysis

    Tuyls, K / Pérolat, J / Lanctot, M et al. | BASE | 2019

    Freier Zugriff

    Tolling at a Frontier: A Game Theoretic Analysis

    Levinson, D. M. | British Library Conference Proceedings | 1999


    A Game Theoretic Analysis on Cloud Manufacturing Model

    Chen, Q.Y. / Wu, Z.H. / Luo, L.C. et al. | British Library Conference Proceedings | 2014


    Game Theoretic Analysis of Adaptive Radar Jamming

    Bachmann, D J / Evans, R J / Moran, B | IEEE | 2011


    A game theoretic approach to search

    Romberg, Harland | AIAA | 2000