On the use of memory and resources in minority games

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the use of memory and resources in minority games

Full text

Pdf (680 KB)

Source

ACM Transactions on Autonomous and Adaptive Systems (TAAS) archive
Volume 4 , Issue 2 (May 2009) table of contents

Article No. 11

Year of Publication: 2009

ISSN:1556-4665

Authors

Ricardo M. Araujo	Institute of Informatics, Federal University of Rio Grande do Sul, Porto Alegre, RS, Brazil
Luis C. Lamb	Institute of Informatics, Federal University of Rio Grande do Sul, Porto Alegre, RS, Brazil

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 18, Downloads (12 Months): 115, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1516533.1516535 What is a DOI?

ABSTRACT

The use of resources in multiagent learning systems is a relevant research problem, with a number of applications in resource allocation, communication and synchronization. Multiagent distributed resource allocation requires that agents act on limited, localized information with minimum communication overhead in order to optimize the distribution of available resources. When requirements and constraints are dynamic, learning agents may be needed to allow for adaptation. One way of accomplishing learning is to observe past outcomes, using such information to improve future decisions. When limits in agents' memory or observation capabilities are assumed, one must decide on how large should the observation window be. We investigate how this decision influences both agents' and system's performance in the context of a special class of distributed resource allocation problems, namely dispersion games. We show by using several numerical experiments over a specific dispersion game (the Minority Game) that in such scenario an agent's performance is non-monotonically correlated with her memory size when all other agents are kept unchanged. We then provide an information-theoretic explanation for the observed behaviors, showing that a downward causation effect takes place.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Andrecut, M. and Ali, M. 2001. Q learning in the minority game. Phys. Rev. E 64, 67--103.
	2	Ricardo M. Araujo , Luis C. Lamb, Towards Understanding the Role of Learning Models in the Dynamics of the Minority Game, Proceedings of the 16th IEEE International Conference on Tools with Artificial Intelligence, p.727-731, November 15-17, 2004 [doi>10.1109/ICTAI.2004.117]
	3	Araújo, R. M. and Lamb, L. C. 2007. A information-theoretic analysis of memory bounds in a distributed resource allocation mechanism. In Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI'07). AAAI Press, 212--217.
	4	Arthur, W. B. 1994. Inductive reasoning and bounded rationality. Am. Econ. Rev. 84, 406--411.
	5	A. Bazzan , G. Andrioti, Wayward Agents in a Commuting Scenario (Personalities in the Minority Game), Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.55, July 10-12, 2000
	6	Eric Bonabeau, Editor's introduction: stigmergy, Artificial Life, v.5 n.2, p.95-96, April 1999 [doi>10.1162/106454699568692]
	7	Eric Bonabeau , Marco Dorigo , Guy Theraulaz, Swarm intelligence: from natural to artificial systems, Oxford University Press, Inc., New York, NY, 1999
	8	J. G. Carbonell, Machine learning: paradigms and methods, Elsevier North-Holland, Inc., New York, NY, 1990
	9	Cavagna, A. 1999. Irrelevance of memory in the minority game. Phys. Rev. E 59, 3783--3786.
	10	Challet, D., Chessa, A., Marsili, M., and Zhang, Y.-C. 2001. From minority games to real markets. Quantit. Finan. 1, 168--176.
	11	Challet, D., Marsili, M., and Zhang, Y.-C. 2004. Minority Games. Oxford University Press.
	12	Challet, D. and Zhang, Y.-C. 1997. Emergence of cooperation and organization in an evolutionary game. Physica A 246. 407--418.
	13	Challet, D. and Zhang, Y.-C. 1998. On the minority game: Analytical and numerical studies. Physica A 256, 514--532.
	14	Chen, Y. and Gazzale, R. S. 2004. When does learning in games generate convergence to Nash equilibria? the role of supermodularity in an experimental setting. Am. Econo. Rev. 94, 5, 1505--1535.
	15	Chow, F. and Chau, H. 2003. Multiple choice minority game. Physica A 319, 601--615.
	16	Jacob W. Crandall , Michael A. Goodrich, Learning to compete, compromise, and cooperate in repeated general-sum games, Proceedings of the 22nd international conference on Machine learning, p.161-168, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102372]
	17	de Cara, A. R., Pla, O., and Guinea, F. 1999. Competition, efficiency and collective behavior in the “El Farol” bar model. Eur. Phys. J. B 10, 187--191.
	18	Dietterich, T. G. 2003. Machine learning. In Nature Encyclopedia of Cognitive Science. Macmillan, London.
	19	Bruce Edmonds , Scott Moss, Modelling Bounded Rationality Using Evolutionary Techniques, Selected Papers from AISB Workshop on Evolutionary Computing, p.31-42, April 07-08, 1997
	20	J. Doyne Farmer, Physicists Attempt to Scale the Ivory Towers of Finance, Computing in Science and Engineering, v.1 n.6, p.26-39, November 1999 [doi>10.1109/5992.906615]
	21	David B. Fogel, Evolutionary computation: toward a new philosophy of machine intelligence, IEEE Press, Piscataway, NJ, 1995
	22	Geisendorf, S. 2000. Modeling bounded rationality by genetic algorithms. In Proceedings of the 24th International Conference of Agricultural Economists (IAAE). 31--42.
	23	Erol Gelenbe , Zhiguang Xu , Esin Seref, Cognitive Packet Networks, Proceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence, p.47, November 08-10, 1999
	24	Trond Grenager , Rob Powers , Yoav Shoham, Dispersion games: general definitions and some specific learning results, Eighteenth national conference on Artificial intelligence, p.398-403, July 28-August 01, 2002, Edmonton, Alberta, Canada
	25	Junling Hu , Michael P. Wellman, Online learning about other agents in a dynamic multiagent system, Proceedings of the second international conference on Autonomous agents, p.239-246, May 10-13, 1998, Minneapolis, Minnesota, United States [doi>10.1145/280765.280839]
	26	Kahneman, D. 2003. Maps of bounded rationality: Psychology for behavioral economics. The Am. Econo. Rev. 93, 5, 1449--1475.
	27	Li, Y., Riolo, R., and Savit, R. 2000. Evolution in minority games II: Games with variable strategy spaces. Physica A 276. 265--283.
	28	Li, Y., VanDeemen, A., and Savit, R. 2000. The minority game with variable payoffs. Physica A 284, 501--503.
	29	David J. C. MacKay, Information Theory, Inference & Learning Algorithms, Cambridge University Press, New York, NY, 2002
	30	Manuca, R., Li, Y., Riolo, R., and Savit, R. 2000. The structure of adaptive competition in minority games. Physica A 282. 559--608.
	31	S Ryszard Michalski , G Jaime Carbonell , M Tom Mitchell, Machine learning an artificial intelligence approach volume II, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1986
	32	Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
	33	Moelbert, S. and Rios, P. D. L. 2002. The local minority game. Physica A 303, 217--225.
	34	Moro, E. 2004. The minority game: an introductory guide. In Advances in Condensed Matter and Statistical Physics, E. Korutcheva and R. Cuerno, Eds. Nova Science Publishers.
	35	Powers, R. and Shoham, Y. 2005. Learning against opponents with bounded memory. In Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI'05). 817--822.
	36	Rubinstein, A. 1998. Modeling Bounded Rationality. Zeuthen Lecture Book Series. The MIT Press, Cambridge, Massachussets.
	37	Savit, R., Manuca, R., and Riolo, R. 1999. Adaptive competition, market efficiency, phase transitions and spin-glasses. Physical Review Letters 82, 2203--2206.
	38	Shoham, Y., Powers, R., and Grenager, T. 2004. On the agenda(s) of research on multi-agent learning. In Proceedings of AAAI Fall Symposium on Artificial Multi-Agent Learning. Technical Report FS-04-02.
	39	Simon, H. 1955. A behavioral model of rational choice. The Quart. J. Econ. 69.
	40	Sysi-Aho, M., Chakraborti, A., and Kasti, K. 2003. Intelligent minority game with genetic-crossover strategies. Eur. Phys. J. B 34, 00234, 373--377.
	41	Guy Theraulaz , Eric Bonbeau, A brief history of stigmergy, Artificial Life, v.5 n.2, p.97-116, April 1999 [doi>10.1162/106454699568700]
	42	Vidal, J. M. and Durfee, E. H. 1997. Agents learning about agents: A framework and analysis. In Proceedings of the 14th National Conference on Artificial Intelligence (AAAI'97), Multiagent Learning Workshop.
	43	Tingting Wang , Jiming Liu, Evaluating the Minority Game strategy in agent role assignments, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082766]
	44	Tingting Wang , Jiming Liu, The Minority Game Strategy in Team Competition: How and When?, Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology, p.587-594, September 19-22, 2005 [doi>10.1109/IAT.2005.131]