Learning in the time-dependent minority game

ABSTRACT

We study learning in the time-dependent Minority Game (MG). The MG is a repeated conflicting interest game involving a large number of agents. So far, the learning mechanisms studied were rather naive and involved only exploitation of the best strategy so far at the expense of exploring new strategies. Instead, we use a reinforcement learning method called Q-learning and show how it improves the results on MG extensions of increasing difficulty.

REFERENCES

• 1: W.B. Arthur. Inductive reasoning and bounded rationality (the el farol problem). Am. Econ. Rev., 84:406--411, 1994.
• 2: D. Challet, M. Marsili, and Y.-C. Zhang. Minority Games. Oxford University Press, 2005.
• 3: D. Challet and Y.-C. Zhang. Emergence of cooperation and organization in an evolutionary game. Physica A, 246:407, 1997.
• 4: D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
• 5: Aram Galstyan , Karl Czajkowski , Kristina Lerman, Resource Allocation in the Grid Using Reinforcement Learning, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.1314-1315, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.232]
• 6: Aram Galstyan , Shashikiran Kolar , Kristina Lerman, Resource allocation games with changing resource capacities, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860599]
• 7: A. Galstyan and K. Lerman. Adaptive boolean networks and minority games with time-dependent capacities. Phys. Rev. E, 66:015103, 2002.
• 8: A. Galstyan and K. Lerman. Minority games and distributed coordination in non-stationary environments. In Proc. of Int. Joint Conf. on Neural Networks, 2002.
• 9: W. Kets and M. Voorneveld. Congestion, equilibrium and learning: The minority game. Discussion Paper 2007-61, Tilburg University, Center for Economic Research, 2007.
• 10: E. Moro. The minority game: an introductory guide, 2004.
• 11: R.B. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
• 12: Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007
• 13: R. Savit, R. Manuca, and R. Riolo. Adaptive competition, market efficiency, and phase transitions. Phys. Rev. Lett., 82(10):2203--2206, Mar 1999.
• 14: Y. Shoham and K. Leyton-Brown. Multiagent Systems. Cambridge University Press, 2008.
• 15: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 16: Christopher J. C. H. Watkins , Peter Dayan, Technical Note: $\backslash cal\; Q$-Learning, Machine Learning, v.8 n.3-4, p.279-292, May 1992 [doi>10.1007/BF00992698]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Scheduling

General Terms:
Performance

Keywords:
minority games, multi-agent, reinforcement learning