research-article

Planning against fictitious players in repeated normal form games

Authors:

Nicholas R. JenningsAuthors Info & Claims

AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1

Pages 1073 - 1080

Published: 10 May 2010 Publication History

Get Access

Abstract

Planning how to interact against bounded memory and unbounded memory learning opponents needs different treatment. Thus far, however, work in this area has shown how to design plans against bounded memory learning opponents, but no work has dealt with the unbounded memory case. This paper tackles this gap. In particular, we frame this as a planning problem using the framework of repeated matrix games, where the planner's objective is to compute the best exploiting sequence of actions against a learning opponent. The particular class of opponent we study uses a fictitious play process to update her beliefs, but the analysis generalizes to many forms of Bayesian learning agents.

Our analysis is inspired by Banerjee and Peng's AIM framework, which works for planning and learning against bounded memory opponents (e.g an adaptive player). Building on this, we show how an unbounded memory opponent (specifically a fictitious player) can also be modelled as a finite MDP and present a new efficient algorithm that can find a way to exploit the opponent by computing in polynomial time a sequence of play that can obtain a higher average reward than those obtained by playing a game theoretic (Nash or correlated) equilibrium.

References

[1]

M. Babes, E. Munoz de Cote, and M. L. Littman. Social reward shaping in the prisoner's dilemma. In Proceedings of the International Joint Conference on Autonomous Agents and Multi Agent Systems (AAMAS), pages 1389--1392, 2008.

Digital Library

Google Scholar

[2]

B. Banerjee and J. Peng. Efficient learning of multi-step best response. In Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, pages 60--66, The Netherlands, 2005. ACM.

Digital Library

Google Scholar

[3]

G. Brown. Iterative solutions of games by fictitious play. Activity Analysis of Production and Allocation, pages 374--376, 1951.

Google Scholar

[4]

D. Chakraborty and P. Stone. Online multiagent learning against memory bounded adversaries. In Proceedings of the 2008 European Conference on Machine Learning and Knowledge Discovery in Databases - Part I, pages 211--226, Antwerp, Belgium, 2008. Springer-Verlag.

Crossref

Google Scholar

[5]

Y.-H. Chang and L. P. Kaelbling. Playing is believing: the role of beliefs in multi-agent learning. In Advances in Neural Information Processing Systems (NIPS) 14, pages 1483--1490, 2001.

Google Scholar

[6]

D. Fudenberg and J. Tirole. Game Theory. The MIT Press, Cambridge, MA, USA, 1991.

Google Scholar

[7]

S. Hart and A. Mas-Colell. Uncoupled dynamics do not lead to nash equilibrium. American Economic Review, 93(5):1830--1836, December 2003.

Crossref

Google Scholar

[8]

D. A. Levin, Y. Peres, and E. L. Wilmer. Markov Chains and Mixing Times. American Mathematical Society, 2009.

Google Scholar

[9]

M. L. Littman and P. Stone. Implicit Negotiation in Repeated Games, pages 393--404. LNCS. Springer, 2002.

Digital Library

Google Scholar

[10]

L. Panait and S. Luke. Cooperativemulti-agent learning: The state of the art. Autonomous Agents and Multi-Agent Systems, 11(3):387--434, 2005.

Digital Library

Google Scholar

[11]

M. L. Puterman. Markov Decision Processes---Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, 1994.

Digital Library

Google Scholar

[12]

C. J. Watkins and P. Dayan. Q-learning. Machine Learning, 8:279--292, 1992.

Digital Library

Google Scholar

[13]

H. P. Young. The evolution of conventions. Econometrica, 61(1):57--84, Jan 1993.

Crossref

Google Scholar

Cited By

View all

Damer SGini MLarson KWinikoff MDas SDurfee E(2017)Safely Using Predictions in General-Sum Normal Form GamesProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems10.5555/3091125.3091257(924-932)Online publication date: 8-May-2017
https://dl.acm.org/doi/10.5555/3091125.3091257
Hernandez-Leal PZhan YTaylor MSucar LMunoz De Cote E(2017)An exploration strategy for non-stationary opponentsAutonomous Agents and Multi-Agent Systems10.1007/s10458-016-9347-331:5(971-1002)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s10458-016-9347-3
Fang FStone PTambe M(2015)When security games go greenProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832581.2832611(2589-2595)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832581.2832611
Show More Cited By

Index Terms

Planning against fictitious players in repeated normal form games

Recommendations

Deep Fictitious Play for Games with Continuous Action Spaces
AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems

Fictitious play has been a classic algorithm to solve two-player adversarial games with discrete action spaces. In this work we develop an approximate extension of fictitious play to two-player games with high-dimensional continuous action spaces. We use ...
Fictitious Play in Markov Games with Single Controller
EC '22: Proceedings of the 23rd ACM Conference on Economics and Computation

Certain but important classes of strategic-form games, including zero-sum and identical-interest games, have thefictitious-play-property (FPP), i.e., beliefs formed in fictitious play dynamics always converge to a Nash equilibrium (NE) in the repeated ...
Repeated Games with Bonuses

This paper deals with 2-player zero-sum repeated games in which player 1 receives a bonus at stage t if he repeats the action he played at stage t 1. We investigate the optimality of simple strategies for player 1. A simple strategy for player 1 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

AAMAS '10: Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems: volume 1 - Volume 1

May 2010

1578 pages

ISBN:9780982657119

General Chairs:
Michael Luck
King's College London, UK
,
Sandip Sen
University of Tulsa

In-Cooperation

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 10 May 2010

Check for updates

Author Tags

Qualifiers

Research-article

Conference

AAMAS '10

Sponsor:

AAMAS '10: The Ninth International Conference on Autonomous Agents and Multiagent Systems

May 10 - 14, 2010

Toronto, Canada

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
65
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Damer SGini MLarson KWinikoff MDas SDurfee E(2017)Safely Using Predictions in General-Sum Normal Form GamesProceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems10.5555/3091125.3091257(924-932)Online publication date: 8-May-2017
https://dl.acm.org/doi/10.5555/3091125.3091257
Hernandez-Leal PZhan YTaylor MSucar LMunoz De Cote E(2017)An exploration strategy for non-stationary opponentsAutonomous Agents and Multi-Agent Systems10.1007/s10458-016-9347-331:5(971-1002)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s10458-016-9347-3
Fang FStone PTambe M(2015)When security games go greenProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832581.2832611(2589-2595)Online publication date: 25-Jul-2015
https://dl.acm.org/doi/10.5555/2832581.2832611
Fang FStone PTambe MWeiss GYolum PBordini RElkind E(2015)Defender Strategies In Domains Involving Frequent Adversary InteractionProceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems10.5555/2772879.2773374(1663-1664)Online publication date: 4-May-2015
https://dl.acm.org/doi/10.5555/2772879.2773374
Lewenberg YRabinovich ZRosenschein JGini MShehory OIto TJonker C(2013)Ishikawa playProceedings of the 2013 international conference on Autonomous agents and multi-agent systems10.5555/2484920.2485020(627-634)Online publication date: 6-May-2013
https://dl.acm.org/doi/10.5555/2484920.2485020
Sykulski AChapman AMunoz de Cote EJennings N(2010)EA2Proceedings of the 2010 conference on ECAI 2010: 19th European Conference on Artificial Intelligence10.5555/1860967.1861009(209-214)Online publication date: 4-Aug-2010
https://dl.acm.org/doi/10.5555/1860967.1861009

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Deep Fictitious Play for Games with Continuous Action Spaces

Fictitious Play in Markov Games with Single Controller

Repeated Games with Bonuses