Congregating and market formation

ABSTRACT

Agents in a multiagent system are not typically entirely self-sufficient; instead, they frequently need to enlist other agents to perform tasks for them or to exchange goods or services with them. This creates a problem: how can an agent efficiently locate other agents to work or trade with? As the number of agents grows, the cost of this computation can become prohibitively large. One solution to this is for the system to self-organize into smaller groups of agents. In this paper, we apply the idea of congregating to a model of an information economy. We illustrate how participants in this economy can self-organize into a set of markets such that agents are able to find suitable partners while retaining low computational costs. We show how congregating can help allocation problems scale to large populations by allowing agents to interact locally.

REFERENCES

• 1: S. P. Anderson, A. de Palma, and J.-F. Thisse. Discrete Choice Theory of Product Differentiation. MIT Press, Cambridge, Massachusetts, 1992.
• 2: Christopher H. Brooks , Edmund H. Durfee, Congregation Formation in Multiagent Systems, Autonomous Agents and Multi-Agent Systems, v.7 n.1-2, p.145-170, July-September 2003 [doi>10.1023/A:1024133006761]
• 3: Aaron Armstrong, An Introduction to Congregating in Multiagent Systems, Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), p.79, July 10-12, 2000
• 4: Christopher H. Brooks , Edmund H. Durfee , Rajarshi Das, Price wars and niche discovery in an information economy, Proceedings of the 2nd ACM conference on Electronic commerce, p.95-106, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352882]
• 5: Christopher H. Brooks , Scott Fay , Rajarshi Das , Jeffrey K. MacKie-Mason , Jeffrey O. Kephart , Edmund H. Durfee, Automated strategy searches in an electronic goods market: learning and complex price schedules, Proceedings of the 1st ACM conference on Electronic commerce, p.31-40, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337000]
• 6: R. Davis and R. G. Smith. Negotiation as a metaphor for distributed problem solving. Artificial Intelligence, 20:63--109, 1983.
• 7: Edmund H. Durfee , Tracy Mullen , Sunju Park , José M. Vidal , Peter Weinstein, The Dynamics of the UMDL Service Market Society, Proceedings of the Second International Workshop on Cooperative Information Agents II, Learning, Mobility and Electronic Commerce for Information Discovery on the Internet, p.55-78, July 04-07, 1998
• 8: M. Fenster, S. Kraus, and J. Rosenschein. Coordination without communication: An experimental validation of focal point techniques. In Proceedings of the First International Conference on Multi-Agent Systems, pages 102--116, San Francisco, California, 1995.
• 9: Tuomas Sandholm, Algorithm for optimal winner determination in combinatorial auctions, Artificial Intelligence, v.135 n.1-2, p.1-54, 02/01/2002 [doi>10.1016/S0004-3702(01)00159-X]
• 10: T. C. Schelling. The Strategy of Conflict. Harvard University, 1960.
• 11: Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]
• 12: M. Tambe. Toward flexible teamwork. Journal of Artificial Intelligence Research, 7:83--124, 1997.
• 13: M. P. Wellman, W. E. Walsh, P. R. Wurman, and J. K. MacKie-Mason. Auction protocols for decentralized scheduling. Games and Economic Behavior, 35(1/2):271--303, 2001.
• 14: D. S. Wilson. Natural Selection of Populations and Communities. Benjamin/Cummings, Menlo Park, California, 1980.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Coherence and coordination

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

General Terms:
Design, Economics, Performance