Resource allocation games with changing resource capacities

ABSTRACT

In this paper we study a class of resource allocation games which are inspired by the El Farol Bar problem. We consider a system of competitive agents that have to choose between several resources characterized by their time dependent capacities. The agents using a particular resource are rewarded if their number does not exceed the resource capacity, and punished otherwise. Agents use a set of strategies to decide what resource to choose, and use a simple reinforcement learning scheme to update the accuracy of strategies. A strategy in our model is simply a lookup table that suggests to an agent what resource to choose based on the actions of its neighbors at the previous time step. In other words, the agents form a social network whose connectivity controls the average number of neighbors with whom each agent interacts. This statement of the adaptive resource allocation problem allows us to fully parameterize it by a small set of numbers. We study the behavior of the system via numeric simulations of 100 to 5000 agents using one to ten resources. Our results indicate that for a certain range of parameters the system as a whole adapts effectively to the changing capacity levels and results in very little under- or over-utilization of the resources.

REFERENCES

• 1: W. B. Arthur. Inductive reasoning and bounded rationality. American Economic Review, 84:406--411, 1994.
• 2: R. Axelrod and W. D. Hamilton. The evolution of cooperation. Science, 211:1390--1396, 1981.
• 3: Craig Boutilier , Moisés Goldszmidt , Bikash Sabata, Sequential Auctions for the Allocation of Resources with Complementarities, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.527-523, July 31-August 06, 1999
• 4: A. Cavagna. Irrelevance of memory in the minority game. Phys. Rev. E, 59:R3783, 1999.
• 5: D. Challet and M. Marsili. Phase transition and symmetry breaking in the minority game. Phys. Rev. E, 60:R6271, 1999.
• 6: D. Challet and Y.-C. Zhang. Emergence of cooperation and organization in an evolutionary game. Physica A, page 407, 1997.
• 7: D. Challet and Y.-C. Zhang. On the minority game: Analytical and numerical studies. Physica A, 256:514, 1998.
• 8: Anthony Chavez , Alexandros Moukas , Pattie Maes, Challenger: a multi-agent system for distributed resource allocation, Proceedings of the first international conference on Autonomous agents, p.323-331, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267736]
• 9: 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
• 10: D. Fudenberg and D. K. Levine. The Theory of Learning in Games. MIT Press, Cambridge, MA, 1998.
• 11: A. Galstyan and K. Lerman. Adaptive boolean networks and minority games with time-dependent capacities. Physical Review, E66:015103, 2002.
• 12: N. Johnson, P. Hui, D. Zheng, and C. Tai. Minority game with arbitrary cuttoffs. Physica A, 269:493, 1999.
• 13: Spiros Kapetanakis , Daniel Kudenko, Reinforcement learning of coordination in cooperative multi-agent systems, Eighteenth national conference on Artificial intelligence, p.326-331, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 14: S. A. Kauffman. The Origins of Order. Oxford University Press, New York, 1993.
• 15: James F. Kurose , Rahul Simha, A Microeconomic Approach to Optimal Resource Allocation in Distributed Computer Systems, IEEE Transactions on Computers, v.38 n.5, p.705-717, May 1989 [doi>10.1109/12.24272]
• 16: See http://www.unifr.ch/econophysics/minority/ for an extensive collection of articles and references.
• 17: T. Mullen and M. Wellman. Market-Based Negotiation for Digital Library Services. In Proc. of the 2nd USENIX Workshop on Electronic Commerce, Oakland, CA, Nov. 1996.
• 18: R. W. Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 19: T. Sandholm. Limitations of the Vickrey Auction in Computational Multiagent Systems. In International Conference on Multi-Agent Systems (ICMAS), pages 299--306, Kyoto, Japan, Dec. 1996.
• 20: Tuomas Sandholm, An Algorithm for Optimal Winner Determination in Combinatorial Auctions, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.542-547, July 31-August 06, 1999
• 21: T. Sandholm and S. Suri. Market Clearability. In International Joint Conference on Artificial Intelligence (IJCAI), pages 1145--1151, Seattle, WA, 2001.
• 22: R. Savit, R. Manuca, and R. Riolo. Adaptive competition, market efficiency, phase transition. Phys. Rev. Lett., 82(10):2203, 1999.
• 23: A. Schaerf, Y. Shoham, and M. Tennenholtz. Adaptive load balancing: A study in multi-agent learning. Journal of Artificial Intelligence Research, 2:475--500, 1995.
• 24: Sandip Sen , Mahendra Sekaran , John Hale, Learning to coordinate without sharing information, Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), p.426-431, October 1994, Seattle, Washington, United States
• 25: R. G. Smith. The Contract Net Protocol. IEEE Tranactions on Computers, 29(12):1104--1113, Dec. 1980.
• 26: R. V. Sole, B. Luque, and S. A. Kauffman. Phase Transitions in Random Networks with Multiple States. SFI Working Papers, 00-02-011, 2000.
• 27: M. Tan. Multi-Agents Reinforcement Learning: Independent vs Cooperative agents. In Proceeding of the $10^th$ International Conference on Machine Learning (ICML-93), 1993.
• 28: J. Vidal , E. Durfee, The Moving Target Function Problem in Multi-Agent Learning, Proceedings of the 3rd International Conference on Multi Agent Systems, p.317, July 03-07, 1998
• 29: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ, 1944.
• 30: William E. Walsh , Michael P. Wellman, A Market Protocol for Decentralized Task Allocation, Proceedings of the 3rd International Conference on Multi Agent Systems, p.325, July 03-07, 1998
• 31: C. J. C. H. Watkins. Learning from Delayed Rewards. PhD thesis, Cambridge University, Cambridge, England, 1989.
• 32: Michael P. Wellman, Market-oriented programming: some early lessons, Market-based control: a paradigm for distributed resource allocation, World Scientific Publishing Co., Inc., River Edge, NJ, 1996
• 33: F. Ygge and H. Akkermans. Decentralized Markets versus Central Control: A Comparative Study. Journal of Artificial Intelligence Research, 11:301--333, 1999.

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.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

General Terms:
Algorithms, Design

Keywords:
dynamical systems, game, reinforcement learning