Synthesis of strategies from interaction traces

ABSTRACT

We describe how to take a set of interaction traces produced by different pairs of players in a two-player repeated game, and combine them into a composite strategy. We provide an algorithm that, in polynomial time, can generate the best such composite strategy. We describe how to incorporate the composite strategy into an existing agent, as an enhancement of the agent's original strategy.

We provide experimental results using interaction traces from 126 agents (most of them written by students as class projects) for the Iterated Prisoner's Dilemma, Iterated Chicken Game, and Iterated Battle of the Sexes. We compared each agent with the enhanced version of that agent produced by our algorithm. The enhancements improved the agents' scores by about 5% in the IPD, 11% in the ICG, and 26% in the IBS, and improved their rank by about 12% in the IPD, 38% in the ICG, and 33% in the IBS.

REFERENCES

• 1: R. Axelrod. The Evolution of Cooperation. Basic Books, 1984.
• 2: Sanjay Bhansali , Mehdi T. Harandi, Synthesis of UNIX Programs Using Derivational Analogy, Machine Learning, v.10 n.1, p.7-55, Jan. 1993 [doi>10.1023/A:1022612610155]
• 3: D. Billings, N. Burch, A. Davidson, R. Holte, and J. Schaeffer. Approximating game-theoretic optimal strategies for full-scale poker. In IJCAI, pages 661--668, 2003.
• 4: Jorg Denzinger , Jasmine Hamdan, Improving Modeling of Other Agents using Tentative Stereotypes and Compactification of Observations, Proceedings of the Intelligent Agent Technology, IEEE/WIC/ACM International Conference, p.106-112, September 20-24, 2004 [doi>10.1109/IAT.2004.71]
• 5: M. Deutsch. The Resolution of Conflict: Constructive and Destructive Processes. Yale University Press, 1973.
• 6: C. Drummond. Accelerating reinforcement learning by composing solutions of automatically identified subtasks. JAIR, 16:59--104, 2002.
• 7: D. Egnor. Iocaine powder explained. ICGA Journal, 23(1):33--35, 2000.
• 8: G. Kendall, X. Yao, and S. Y. Chong. The Iterated Prisoner's Dilemma: 20 Years On. World Scientific, 2007.
• 9: Richard E. Korf, Macro-operators: a weak method for learning, Artificial Intelligence, v.26 n.1, p.35-77, April 1985 [doi>10.1016/0004-3702(85)90012-8]
• 10: J. Li. How to design a strategy to win an IPD tournament. In G. Kendall, X. Yao, and S. Y. Chong, editors, The Iterated Prisoner's Dilemma: 20 Years On, pages 89--104. World Scientific, 2007.
• 11: R. D. Luce and H. Raiffa. Games and Decisions: Introduction and Critical Survey. Wiley, 1957.
• 12: Amy McGovern , Richard S. Sutton, Roles of Macro-actions in Accelerating Reinforcement Learning TITLE2:, University of Massachusetts, Amherst, MA, 1998
• 13: A. Parker, D. Nau, and V. Subrahmanian. Overconfidence or paranoia? search in imperfect-information games. In AAAI, July 2006.
• 14: Doina Precup , Richard S. Sutton , Satinder P. Singh, Theoretical Results on Reinforcement Learning with Temporally Abstract Options, Proceedings of the 10th European Conference on Machine Learning, p.382-393, April 21-23, 1998
• 15: Manuela M. Veloso , Jaime G. Carbonell, Derivational Analogy in PRODIGY: Automating Case Acquisition, Storage, and Utilization, Machine Learning, v.10 n.3, p.249-278, March 1993 [doi>10.1023/A:1022686910523]
• 16: Dajun Zeng , Katia Sycara, Using Case-Based Reasoning as a Reinforcement Learning Framework for Optimization with Changing Criteria, Proceedings of the Seventh International Conference on Tools with Artificial Intelligence, p.56, November 05-08, 1995

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Economics, Experimentation, Performance, Theory

Keywords:
agents, interaction, learning, multi-agent systems, prisoner's dilemma, repeated games