Theory of moves learners: towards non-myopic equilibria

ABSTRACT

In contrast to classical game theoretic analysis of simultaneous and sequential play in bimatrix games, Steven Brams has proposed an alternative framework called the Theory of Moves (TOM) where players can choose their initial actions and then, in alternating turns, decide to shift or not from its current action. A backward induction process is used to determine a non-myopic action and equilibrium is reached when an agent, on its turn to move, decides to not change its current action. Brams claims that the TOM framework captures the dynamics of a wide range of real-life non-cooperative negotiations ranging over political, historical, and religious disputes. We believe that his analysis is weakened by the assumption that a player has perfect knowledge of the opponent's payoff. We present a learning approach by which TOM players can learn to converge to Non-Myopic Equilibria (NME) without prior knowledge of its opponent's preferences and by inducing them from past choices made by the opponent. We present experimental results from all structurally distinct 2-by-2 games without a common preferred outcome showing convergence of our proposed learning player to NMEs. We also discuss the relation between equilibriums in sequential games and NMEs of TOM.

REFERENCES

• 1: B. Banerjee, S. Sen, and J. Peng. Fast concurrent reinforcement learners. In Proceedings of the Seventeenth International Joint Conference on Artificial Intelligence, pages 825--830, 2001.
• 2: Multiagent learning using a variable learning rate, Artificial Intelligence, v.136 n.2, p.215-250, April 2002 [doi>10.1016/S0004-3702(02)00121-2]
• 3: S. J. Brams. Theory of Moves. Cambridge University Press, Cambridge: UK, 1994.
• 4: Caroline Claus , Craig Boutilier, The dynamics of reinforcement learning in cooperative multiagent systems, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.746-752, July 1998, Madison, Wisconsin, United States
• 5: V. Conitzer and T. Sandholm. AWESOME: A general multiagent learning algorithm that converges in self-play. In Twentieth International Conference on Machine Learning, pages 83--90, San Francisco, CA, 2003: Morgan Kaufmann.
• 6: Junling Hu , Michael P. Wellman, Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm, Proceedings of the Fifteenth International Conference on Machine Learning, p.242-250, July 24-27, 1998
• 7: Michael L. Littman , Peter Stone, A polynomial-time Nash equilibrium algorithm for repeated games, Decision Support Systems, v.39 n.1, p.55-66, March 2005 [doi>10.1016/j.dss.2004.08.007]
• 8: M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Proceedings of the Eleventh International Conference on Machine Learning, pages 157--163, San Mateo, CA, 1994. Morgan Kaufmann.
• 9: Michael L. Littman, Friend-or-Foe Q-learning in General-Sum Games, Proceedings of the Eighteenth International Conference on Machine Learning, p.322-328, June 28-July 01, 2001
• 10: Michael L. Littman , Peter Stone, Implicit Negotiation in Repeated Games, Revised Papers from the 8th International Workshop on Intelligent Agents VIII, p.393-404, August 01-03, 2001
• 11: R. B. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
• 12: J. F. Nash. Non-cooperative games. Annals of Mathematics, 54:286 -- 295, 1951.
• 13: A. Rapoport and M. Guyer. A taxonomy of 2x2 games. General Systems, 11:203--214, 1966.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
          Subjects: Knowledge acquisition

General Terms:
Experimentation, Performance

Keywords:
bimatrix games, non-myopic equilibrium, theory of moves