{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T08:16:22Z","timestamp":1770538582625,"version":"3.49.0"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,12,4]],"date-time":"2019-12-04T00:00:00Z","timestamp":1575417600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,12,4]],"date-time":"2019-12-04T00:00:00Z","timestamp":1575417600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Auton Agent Multi-Agent Syst"],"published-print":{"date-parts":[[2020,4]]},"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>","DOI":"10.1007\/s10458-019-09432-y","type":"journal-article","created":{"date-parts":[[2019,12,4]],"date-time":"2019-12-04T16:03:12Z","timestamp":1575475392000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Bounds and dynamics for empirical game theoretic analysis"],"prefix":"10.1007","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7929-1944","authenticated-orcid":false,"given":"Karl","family":"Tuyls","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Julien","family":"Perolat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Lanctot","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edward","family":"Hughes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Everett","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joel Z.","family":"Leibo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba","family":"Szepesv\u00e1ri","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thore","family":"Graepel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,12,4]]},"reference":[{"key":"9432_CR1","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1007\/s00199-009-0449-x","volume":"42","author":"D Avis","year":"2010","unstructured":"Avis, D., Rosenberg, G., Savani, R., & von Stengel, B. (2010). Enumeration of nash equilibria for two-player games. Economic Theory, 42, 9\u201337.","journal-title":"Economic Theory"},{"key":"9432_CR2","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1080\/09540091.2015.1039492","volume":"27","author":"D Bloembergen","year":"2015","unstructured":"Bloembergen, D., Hennes, D., McBurney, P., & Tuyls, K. (2015). Trading in markets with noisy information: An evolutionary analysis. Connection Science, 27, 253\u2013268.","journal-title":"Connection Science"},{"key":"9432_CR3","doi-asserted-by":"publisher","first-page":"659","DOI":"10.1613\/jair.4818","volume":"53","author":"D Bloembergen","year":"2015","unstructured":"Bloembergen, D., Tuyls, K., Hennes, D., & Kaisers, M. (2015). Evolutionary dynamics of multi-agent learning: A survey. Journal of Artificial Intelligence Research (JAIR), 53, 659\u2013697.","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"key":"9432_CR4","doi-asserted-by":"crossref","unstructured":"Borel, E. (1921). La th\u00e9orie du jeu les \u00e9quations int\u00e9grales \u00e0 noyau sym\u00e9trique. comptes rendus de l\u2019acad\u00e9mie, 173, 1304\u20131308. english translation by savage, l.: The theory of play and integral equations with skew symmetric kernels. Econometrica 21, 97\u2013100 (1953).","DOI":"10.2307\/1906946"},{"key":"9432_CR5","unstructured":"Brinkman, E., & Wellman, M. (2016). Shading and efficiency in limit-order markets. In Proceedings of the IJCAI-16 workshop on algorithmic game theory."},{"key":"9432_CR6","volume-title":"Multi-Agent-Based Simulation XIII, Lecture Notes in Computer Science","author":"BA Cassell","year":"2013","unstructured":"Cassell, B. A., & Wellman, M. (2013). EGTAOnline: An experiment manager for simulation-based game studies. In F. Giardini & F. Amblard (Eds.), Multi-Agent-Based Simulation XIII, Lecture Notes in Computer Science (Vol. 7838). Berlin: Springer."},{"key":"9432_CR7","doi-asserted-by":"crossref","unstructured":"Coulom, R. (2008). Whole-history rating: A Bayesian rating system for players of time-varying strength. In Computers and games, 6th international conference, CG 2008, Beijing, China, September 29\u2013October 1, 2008. Proceedings (pp. 113\u2013124).","DOI":"10.1007\/978-3-540-87608-3_11"},{"key":"9432_CR8","volume-title":"The rating of chess players, past and present","author":"AE Elo","year":"1978","unstructured":"Elo, A. E. (1978). The rating of chess players, past and present. Bronx: Ishi Press International."},{"issue":"7","key":"9432_CR9","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.artint.2007.01.001","volume":"171","author":"I Erev","year":"2007","unstructured":"Erev, I., & Roth, A. E. (2007). Multi-agent learning and the descriptive value of simple models. Artificial Intelligence, 171(7), 423\u2013428.","journal-title":"Artificial Intelligence"},{"key":"9432_CR10","doi-asserted-by":"publisher","DOI":"10.2307\/j.ctvcm4gjh","volume-title":"Game theory evolving","author":"H Gintis","year":"2009","unstructured":"Gintis, H. (2009). Game theory evolving (2nd ed.). Princeton, NJ: University Press.","edition":"2"},{"key":"9432_CR11","unstructured":"Hennes, D., Claes, D., & Tuyls, K. (2013). Evolutionary advantage of reciprocity in collision avoidance. In Proceedings of the AAMAS 2013 workshop on autonomous robots and multirobot systems (ARMS 2013)"},{"key":"9432_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139173179","volume-title":"Evolutionary games and population dynamics","author":"J Hofbauer","year":"1998","unstructured":"Hofbauer, J., & Sigmund, K. (1998). Evolutionary games and population dynamics. Cambridge: Cambridge University Press."},{"key":"9432_CR13","unstructured":"Jaderberg, M., Czarnecki, W. M., Dunning, I., Marris, L., Lever, G., Castaneda, A. G., Beattie, C., Rabinowitz, N. C., Morcos, A. S., Ruderman, A., et\u00a0al. (2018). Human-level performance in first-person multiplayer games with population-based deep reinforcement learning. arXiv preprint arXiv:1807.01281."},{"key":"9432_CR14","unstructured":"Jecmen, S., Brinkman, E., & Sinha, A. (2018). Bounding regret in simulated games. In: ICML workshop on exploration in RL."},{"key":"9432_CR15","first-page":"249","volume":"1","author":"L Julian Schvartzman","year":"2009","unstructured":"Julian Schvartzman, L., & Wellman, M. P. (2009). Stronger CDA strategies through empirical game-theoretic analysis and reinforcement learning. AAMAS, 1, 249\u2013256.","journal-title":"AAMAS"},{"key":"9432_CR16","doi-asserted-by":"crossref","unstructured":"Kaisers, M., Tuyls, K., Thuijsman, F., & Parsons, S. (2008). Auction analysis by normal form game approximation. In Proceedings of the 2008 IEEE\/WIC\/ACM international conference on intelligent agent technology, Sydney, NSW, Australia, December 9\u201312, 2008 (pp. 447\u2013450).","DOI":"10.1109\/WIIAT.2008.261"},{"key":"9432_CR17","doi-asserted-by":"crossref","unstructured":"Kohli, P., Kearns, M., Bachrach, Y., Herbrich, R., Stillwell, D., & Graepel, T. (2012). Colonel blotto on facebook: the effect of social relations on strategic interaction. In Web science 2012, WebSci \u201912, Evanston, IL, USA, June 22\u201324, 2012 (pp. 141\u2013150).","DOI":"10.1145\/2380718.2380738"},{"key":"9432_CR18","first-page":"4190","volume-title":"Advances in neural information processing systems 30","author":"M Lanctot","year":"2017","unstructured":"Lanctot, M., Zambaldi, V., Gruslys, A., Lazaridou, A., Tuyls, K., Perolat, J., et al. (2017). A unified game-theoretic approach to multiagent reinforcement learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, & R. Garnett (Eds.), Advances in neural information processing systems 30 (pp. 4190\u20134203). Berlin: Springer."},{"key":"9432_CR19","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1038\/246015a0","volume":"246","author":"J Maynard Smith","year":"1973","unstructured":"Maynard Smith, J., & Price, G. R. (1973). The logic of animal conflicts. Nature, 246, 15\u201318.","journal-title":"Nature"},{"key":"9432_CR20","doi-asserted-by":"crossref","unstructured":"Nguyen, T., Wright, M., Wellman, M., & Singh, S. (2017). Multi-stage attack graph security games: Heuristic strategies, with empirical game-theoretic analysis. In Proceedings of the fourth ACM workshop on moving target defense.","DOI":"10.1145\/3140549.3140562"},{"issue":"4","key":"9432_CR21","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1109\/TCIAIG.2012.2210424","volume":"4","author":"P Nijssen","year":"2012","unstructured":"Nijssen, P., & Winands, M. H. (2012). Monte carlo tree search for the hide-and-seek game scotland yard. IEEE Transactions on Computational Intelligence and AI in Games, 4(4), 282\u2013294.","journal-title":"IEEE Transactions on Computational Intelligence and AI in Games"},{"key":"9432_CR22","unstructured":"Phelps, S., Cai, K., McBurney, P., Niu, J., Parsons, S., & Sklar, E. (2007). Auctions, evolution, and multi-agent learning. In Adaptive agents and multi-agent systems III. Adaptation and multi-agent learning, 5th, 6th, and 7th European symposium, ALAMAS 2005-2007 on adaptive and learning agents and multi-agent systems, Revised Selected Papers (pp. 188\u2013210)."},{"key":"9432_CR23","unstructured":"Phelps, S., Parsons, S., & McBurney, P. (2004). An evolutionary game-theoretic comparison of two double-auction market designs. In Agent-mediated electronic commerce VI, theories for and engineering of distributed mechanisms and systems, AAMAS 2004 Workshop, AMEC 2004, New York, NY, USA, July 19, 2004, Revised Selected Papers (pp. 101\u2013114)."},{"issue":"1","key":"9432_CR24","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/j.entcom.2009.09.002","volume":"1","author":"M Ponsen","year":"2009","unstructured":"Ponsen, M., Tuyls, K., Kaisers, M., & Ramon, J. (2009). An evolutionary game-theoretic analysis of poker strategies. Entertainment Computing, 1(1), 39\u201345.","journal-title":"Entertainment Computing"},{"key":"9432_CR25","doi-asserted-by":"crossref","unstructured":"Prakash, A., & Wellman, M. (2015). Empirical game-theoretic analysis for moving target defense. In Proceedings of the second ACM workshop on moving target defense","DOI":"10.1145\/2808475.2808483"},{"key":"9432_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-01578-6","volume-title":"Predicting human decision-making: From prediction to action. Synthesis lectures on artificial intelligence and machine learning","author":"A Rosenfeld","year":"2018","unstructured":"Rosenfeld, A., & Kraus, S. (2018). Predicting human decision-making: From prediction to action. Synthesis lectures on artificial intelligence and machine learning. San Rafael: Morgan & Claypool Publishers."},{"issue":"7587","key":"9432_CR27","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1038\/nature16961","volume":"529","author":"D Silver","year":"2016","unstructured":"Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., et al. (2016). Mastering the game of go with deep neural networks and tree search. Nature, 529(7587), 484\u2013489.","journal-title":"Nature"},{"key":"9432_CR28","unstructured":"Southey, F., Bowling, M., Larson, B., Piccione, C., Burch, N., Billings, D., & Rayner, C. (2005). Bayes\u2019 bluff: Opponent modelling in poker. In Proceedings of the twenty-first conference on uncertainty in artificial intelligence (UAI-05)."},{"issue":"1","key":"9432_CR29","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1006\/ijhc.1997.0162","volume":"48","author":"P Stone","year":"1998","unstructured":"Stone, P., & Veloso, M. (1998). Towards collaborative and adversarial learning: A case study in robotic soccer. International Journal of Human-Computer Studies, 48(1), 83\u2013104.","journal-title":"International Journal of Human-Computer Studies"},{"issue":"7","key":"9432_CR30","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/j.artint.2007.01.004","volume":"171","author":"K Tuyls","year":"2007","unstructured":"Tuyls, K., & Parsons, S. (2007). What evolutionary game theory tells us about multiagent learning. Artificial Intelligence, 171(7), 406\u2013416.","journal-title":"Artificial Intelligence"},{"key":"9432_CR31","unstructured":"Tuyls, K., P\u00e9rolat, J., Lanctot, M., Leibo, J. Z., & Graepel, T. (2018). A generalised method for empirical game theoretic analysis. In International foundation for autonomous agents and multiagent systems (AAMAS), Richland, SC, USA\/ACM (pp. 77\u201385)."},{"issue":"1","key":"9432_CR32","doi-asserted-by":"publisher","first-page":"1015","DOI":"10.1038\/s41598-018-19194-4","volume":"8","author":"K Tuyls","year":"2018","unstructured":"Tuyls, K., Perolat, J., Lanctot, M., Savani, R., Leibo, J., Ord, T., et al. (2018). Symmetric decomposition of asymmetric games. Scientific Reports, 8(1), 1015.","journal-title":"Scientific Reports"},{"key":"9432_CR33","doi-asserted-by":"crossref","unstructured":"Tuyls, K., Verbeeck, K., & Lenaerts, T. (2003). A selection-mutation model for q-learning in multi-agent systems. In The second international joint conference on autonomous agents & multiagent systems, AAMAS 2003, July 14\u201318, 2003, Melbourne, Victoria, Australia, Proceedings (pp. 693\u2013700).","DOI":"10.1145\/860575.860687"},{"issue":"3","key":"9432_CR34","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/1842713.1842719","volume":"20","author":"Y Vorobeychik","year":"2010","unstructured":"Vorobeychik, Y. (2010). Probabilistic analysis of simulation-based games. ACM Transactions on Modeling and Computer Simulation, 20(3), 16. https:\/\/doi.org\/10.1145\/1842713.1842719.","journal-title":"ACM Transactions on Modeling and Computer Simulation"},{"key":"9432_CR35","unstructured":"Vorobeychik, Y., & Wellman, M. P. (2008). Stochastic search methods for nash equilibrium approximation in simulation-based games. In Proceedings of the seventh international conference on autonomous agents and multiagent systems (AAMAS) (pp. 1055\u20131062)."},{"key":"9432_CR36","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s10994-007-0715-8","volume":"67","author":"Y Vorobeychik","year":"2007","unstructured":"Vorobeychik, Y., Wellman, M. P., & Singh, S. (2007). Learning payoff functions in infinite games. Machine Learning, 67, 145\u2013168.","journal-title":"Machine Learning"},{"key":"9432_CR37","doi-asserted-by":"crossref","unstructured":"Wah, E., Hurd, D., & Wellman, M. (2015). Strategic market choice: Frequent call markets vs. continuous double auctions for fast and slow traders. In Proceedings of the third EAI conference on auctions, market mechanisms, and their applications.","DOI":"10.4108\/eai.8-8-2015.2260356"},{"key":"9432_CR38","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1613\/jair.5360","volume":"59","author":"E Wah","year":"2017","unstructured":"Wah, E., Wright, M., & Wellman, M. (2017). Welfare effects of market making in continuous double auctions. Journal of Artificial Intelligence Research, 59, 613\u2013650.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"9432_CR39","unstructured":"Walsh, W. E., Das, R., Tesauro, G., & Kephart, J. (2002). Analyzing complex strategic interactions in multi-agent games. In AAAI-02 workshop on game theoretic and decision theoretic agents, 2002."},{"key":"9432_CR40","unstructured":"Walsh, W. E., Parkes, D. C., & Das, R. (2003). Choosing samples to compute heuristic-strategy nash equilibrium. In Proceedings of the fifth workshop on agent-mediated electronic commerce."},{"key":"9432_CR41","doi-asserted-by":"crossref","unstructured":"Wang, X., Vorobeychik, Y., & Wellman, M. (2018). A cloaking mechanism to mitigate market manipulation. In Proceedings of the 27th international joint conference on artificial intelligence (pp. 541\u2013547).","DOI":"10.24963\/ijcai.2018\/75"},{"key":"9432_CR42","volume-title":"Evolutionary game theory","author":"J Weibull","year":"1997","unstructured":"Weibull, J. (1997). Evolutionary game theory. Cambridge: MIT Press."},{"key":"9432_CR43","unstructured":"Wellman, M., Kim, T., & Duong, Q. (2013). Analyzing incentives for protocol compliance in complex domains: A case study of introduction-based routing. In Proceedings of the 12th workshop on the economics of information security."},{"key":"9432_CR44","unstructured":"Wellman, M. P. (2006). Methods for empirical game-theoretic analysis. In Proceedings, The twenty-first national conference on artificial intelligence and the eighteenth innovative applications of artificial intelligence conference July 16\u201320, 2006, Boston, Massachusetts, USA (pp. 1552\u20131556)."},{"key":"9432_CR45","unstructured":"Wiedenbeck, B., Cassell, B. A., & Wellman, M. P. (2014). Bootstrap statistics for empirical games. In Proceedings of the 2014 international conference on Autonomous agents and multi-agent systems (pp. 597\u2013604). International Foundation for Autonomous Agents and Multiagent Systems."},{"key":"9432_CR46","unstructured":"Wiedenbeck, B., & Wellman, M. (2012). Scaling simulation-based game analysis through deviation-preserving reduction. In Proceedings of the eleventh international conference on autonomous agents and multiagent systems (AAMAS)."},{"key":"9432_CR47","unstructured":"Wright, M. (2016). Using reinforcement learning to validate empirical game-theoretic analysis: A continuous double auction study. CoRR arXiv:1604.06710."},{"key":"9432_CR48","doi-asserted-by":"crossref","unstructured":"Wright, M., Venkatesan, S., Albenese, M., & Wellman, M. (2016). Moving target defense against DDoS attacks: An empirical game-theoretic analysis. In Proceedings of the third ACM workshop on moving target defense.","DOI":"10.1145\/2995272.2995279"},{"key":"9432_CR49","unstructured":"Wright, M., & Wellman, M. P. (2018). Evaluating the stability of non-adaptive trading in continuous double auctions. AAMAS, 614\u2013622."},{"key":"9432_CR50","doi-asserted-by":"crossref","unstructured":"Zeeman, E. C., (1980). Population dynamics from game theory. In Global theory of dynamical systems, Springer, Berlin, Heidelberg (pp. 471\u2013497).","DOI":"10.1007\/BFb0087009"},{"key":"9432_CR51","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/0022-5193(81)90311-8","volume":"89","author":"E Zeeman","year":"1981","unstructured":"Zeeman, E. (1981). Dynamics of the evolution of animal conflicts. Theoretical Biology, 89, 249\u2013270.","journal-title":"Theoretical Biology"}],"container-title":["Autonomous Agents and Multi-Agent Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-019-09432-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10458-019-09432-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10458-019-09432-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,7]],"date-time":"2022-10-07T17:51:27Z","timestamp":1665165087000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10458-019-09432-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,4]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["9432"],"URL":"https:\/\/doi.org\/10.1007\/s10458-019-09432-y","relation":{},"ISSN":["1387-2532","1573-7454"],"issn-type":[{"value":"1387-2532","type":"print"},{"value":"1573-7454","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,12,4]]},"assertion":[{"value":"4 December 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"7"}}