Coalition Formation : Towards Feasible Solutions

• Autorzy: Shehory O.
• Języki publikacji: EN

Abstrakty

EN

Coalition formation research in the last decade has produced an array of coalition formation mechanisms. Although these address a variety of environments and settings, they are usually inadequate for practical applications. The major limitations of the proposed mechanisms that render them inapplicable are a high computational complexity, and unrealistic assumptions regarding the availability of information. In this article we present two recent coalition formation mechanisms that attempt to overcome these limitations. One of the mechanisms introduces a very low complexity, allowing scaling to thousands of agents, and the other mechanism does not assume complete information. Rather, it assumes private, subjective and inaccurate valuation of coalitions. These two mechanisms do not solve all of the problems present in the field, however they point at promising directions that might lead to fully applicable solutions in future research.

Słowa kluczowe

EN

coalition formation; computational complexity; agent; complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 63, nr 2,3
• Strony: 107--124
• Opis fizyczny: Bibliogr. 25 poz., wykr.

Twórcy

autor

Shehory O.

• IBM Research Lab in Haifa, Univ. Mount Carmel, Haifa, 31905 Israel,

Bibliografia

• [1] Axelrod, R., Hamilton,W. D.: The Evolution of Cooperation, Science, 211:1390-1396, 1981.
• [2] Barabasi, A. L., Stanley, H. E.: Fractal Concepts in Surface Growth Cambridge University Press, Cambridge, 1995.
• [3] Blackenburg, B., Klusch, M., Shehory, O.: Fuzzy kernel-stable coalitions between rational agents, Proc. of AAMAS-03, pages 9-16,Melbourne, Australia, 2003.
• [4] Davis, M.,Maschler,M.: The kernel of a cooperative game, Naval Research Logistics Quarterly, 12:223-259, 1965.
• [5] Ephrati, E., Pollack, M., Ur, S.: Deriving multi-agent coordination through filtering strategies, Proc. of IJCAI-95, pages 679-685, Montreal, Quebec, Canada, 1995.
• [6] Guenter, O., Hogg, T., Huberman, B. A.: Learning in Multiagent Control of Smart Matter, AAAI Workshop on Multiagent Learning, 1997.
• [7] Huberman, B. A., Hogg, T.: The Behavior of Computational Ecologies, in: The Ecology of Computation (B. A. Huberman Ed.), Elsevier, North-Holland, 1988.
• [8] Kahan, J. P., Rapoport, A.: Theories of coalition formation, Lawrence Erlbaum Associates, Hillsdale, New Jersey, 1984.
• [9] Ketchpel, S. P.: Forming coalitions in the face of uncertain rewards, Proc. of AAAI-94, pages 414-419, Seattle, Washington, 1994.
• [10] Kraus, S., Shehory, O., Taase, G.: Coalition formation with uncertain heterogeneous information, Proc. of AAMAS-03, pages 1-8, Melbourne, Australia, 2003.
• [11] Klusch, M., Shehory, O.: A polynomial kernel-oriented coalition formation algorithm for rational information agents, Proc. of ICMAS-96, pages 157-164, Kyoto, Japan, 1996.
• [12] Klusch, M., Gerber, A.: Issues of dynamic coalition formation among agents, Proc. of KSCO-02, France, 2002.
• [13] Kwasnica, A.M.: Bayesian Implementable of Efficient and Core Allocations, Penn. State University Working Paper, 2002.
• [14] Lerman, K., Shehory, O.: Coalition formation for large-scale electronic markets, Proc. of ICMAS-00, pages 167-174, Boston, MA, 2000.
• [15] Sandholm, T. W., Lesser, V. R.: Coalition formation among bounded rational agents, Proc. of IJCAI-95, pages 662-669,Montrèal, 1995.
• [16] Sandholm, T. W., Larson, K., Andersson, M., Shehory, O., Tohme, F.: Coalition structure generation with worst-case guarantees, Artificial Intelligence, 1999.
• [17] Schaerf, A., Shoham, Y., Tennenholtz, M.: Adaptive Load Balancing: A Study in Multi-Agent Learning, Journal of Artificial Intelligence Research, 2:475-500, 1995.
• [18] Sen, S., Sekaran, M., Hale, J.: Learning to Coordinate without sharing information, Proc. 1st International Conference on Multi-Agent Systems, MIT Press, 1995.
• [19] Sen, S.: Reciprocity: A foundational principle for promoting cooperative behavior among self-interested agents, Proc. 1st International Conference on Multi-Agent Systems, MIT Press, 1995.
• [20] Shehory, O., Kraus, S.: Coalition formation among autonomous agents: Strategies and complexity, in: Lecture Notes in Artificial Intelligence No. 957, From Reaction to Cognition (C. Castelfranchi and J. P. Muller, eds.), pages 57-72. Berlin: Springer-Verlag, 1993.
• [21] Shehory, O., Kraus, S.: Methods for task allocation via agent coalition formation, Artificial Intelligence, 101(1-2):165-200, 1998.
• [22] Shehory, O., Kraus, S.: Feasible formation of coalitions among autonomous agents in non-super-additive environments, Computational Intelligence, 15(3):218-251, 1999.
• [23] Shehory, O., Kraus, S., Yadgar, O.: Emergent cooperative goal satisfaction in large-scale automated-agent systems, Artificial Intelligence, 1999.
• [24] Vohra, R.: Incomplete information, incentive compatibility and the Core, Economic Theory, 86:123-147, 1999.
• [25] Zlotkin, G., Rosenschein, J.: Coalition, cryptography, and stability: Mechanisms for coalition formation in task oriented domains, Proc. of AAAI-94, pages 432-437, Seattle, Washington, 1994.