Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2013 Volume 28
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

Cooperative games and multiagent systems

  • Place du Maréchal de Lattre de Tassigny

More Information
  • Abstract: Forming coalitions is a generic means for cooperation: people, robots, web services, resources, firms; they can all improve their performance by joining forces. The use of coalitions has been successful in domains such as task allocations, sensor networks, and electronic marketplaces. Forming efficient coalitions requires the identification of matching synergies between different entities (finding complementary partners, or similar partners, or partners who add diversity). In addition, the different parties must negotiate a fair repartition of the worth created by the coalition. The first part of this paper is a tutorial on cooperative game theory (also called coalitional games). We then survey the different scenarios and the key issues addressed by the multiagent systems community.
  • 加载中
  • Abdallah S., Lesser V.2004. Organization-based cooperative coalition formation. In Proceedings of the IAT 04, Beijing, China.

    Google Scholar

    Airiau S., Sen S.2009. A fair payoff distribution for myopic rational agents. In Proceedings of the Eighth International Conference on Autonomous Agents and Multiagent Systems (AAMAS-09), Budapest, Hungary.

    Google Scholar

    Airiau S., Sen S.2010. On the stability of an optimal coalition structure. In Proceedings of the 19th European Conference on Artificial Intelligence (ECAI-2010), Lisbon, Portugal, 203–208.

    Google Scholar

    Aknine S., Caillou P.2004. Agreements without disagreements. In Proceedings of the 16th Eureopean Conference on Artificial Intelligence, ECAI'2004, Valencia, Spain, 3–7.

    Google Scholar

    Aknine S., Pinson S., Shakun M. F.2004. A multi-agent coalition formation method based on preference models. Group Decision and Negotiation13(6), 513–538.

    Google Scholar

    Aknine S., Shehory O.2005. Coalition formation: concessions, task relationships and complexity reduction. ArXiv Computer Science e-prints.

    Google Scholar

    Asselin F., Chaib-draa B.2006. Performance of software agents in non-transferable payoff group buying. Journal of Experimental and Theoretical Artificial Intelligence18(1), 1–32.

    Google Scholar

    Aubin J.-P.1979. Mathematical Methods of Game and Economic Theory. North-Holland.

    Google Scholar

    Aumann R. J., Drèze J. H.1974. Cooperative games with coalition structures. International Journal of Game Theory3(4), 217–237.

    Google Scholar

    Aziz H., Brandt F., Harrenstein P.2010. Monotone cooperative games and their threshold versions. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems – Volume 1, AAMAS '10, van der Hoek, W., Kaminka, G. A., Lespérance, Y., Luck, M. & Sen, S. (eds). International Foundation for Autonomous Agents and Multiagent Systems, 1107–1114.

    Google Scholar

    Bachrach Y., Elkind E., Meir R., Pasechnik D., Zuckerman M., Rothe J., Rosenschein J.2009. The cost of stability in coalitional games. In SAGT'09: 2nd International Symposium of Algorithmic Game Theory, Paphos, Cyprus, 122–134.

    Google Scholar

    Bachrach Y., Meir R., Jung K., Kohli P.2010. Coalitional structure generation in skill games. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), Atlanta, Georgia, USA, 703–708.

    Google Scholar

    Bachrach Y., Rosenschein J. S.2008. Coalitional skill games. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-08), Estoril, Portugal, 1023–1030.

    Google Scholar

    Bachrach Y., Rosenschein J.2009. Power in threshold network flow games. Autonomous Agents and Multi-Agent Systems18, 106–13210.1007/s10458-008-9057-6. doi: 10.1007/s10458-008-9057-6

    CrossRef   Google Scholar

    Banerjee B., Kraemer L.2010. Coalition structure generation in multi-agent systems with mixed externalities. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems – Volume 1, AAMAS '10, van der Hoek, W., Kaminka, G. A., Lespérance, Y., Luck, M. & Sen, S. (eds). International Foundation for Autonomous Agents and Multiagent Systems, 175–182.

    Google Scholar

    Belmonte M.-V., Conejo R., de-la Cruz J.-L. P., Ruiz F. T.2002. A stable and feasible payoff division for coalition formation in a class of task oriented domains. In ATAL '01: Revised Papers from the 8th International Workshop on Intelligent Agents VIII, Meyer, J.-J. Ch. & Tambe, M. (eds). Springer-Verlag, 324–334.

    Google Scholar

    Belmonte M.-V., Conejo R., de-la Cruz J.-L. P., Ruiz F. T.2004. A robust deception-free coalition formation model. In Proceedings of the 2004 ACM Symposium on Applied Computing (SAC '04), Haddad, H., Omicini, A., Wainwright, R. L. & Liebrock, L. M. (eds). ACM Press, 469–473.

    Google Scholar

    Blankenburg B., Dash R. K., Ramchurn S. D., Klusch M., Jennings N. R.2005. Trusted kernel-based coalition formation. In Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, Dignum, F., Dignum, V., Koenig, S., Kraus, S., Singh, M. P. & Wooldridge, M. (eds). ACM Press, 989–996.

    Google Scholar

    Blankenburg B., He M., Klusch M., Jennings N. R.2006. Risk-bounded formation of fuzzy coalitions among service agents. In Proceedings of 10th International Workshop on Cooperative Information Agents, Edinburgh, UK.

    Google Scholar

    Blankenburg B., Klusch M.2004. On safe kernel stable coalition forming among agents. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, New York, NY, USA.

    Google Scholar

    Blankenburg B., Klusch M.2005. Bsca-f: efficient fuzzy valued stable coalition forming among agents. In Proceedings of the IEEE International Conference on Intelligent Agent Technology (IAT), Skowron, A., Barthès, J.-P. A., Jain, L. C., Sun, R., Morizet-Mahoudeaux, P., Liu, J. & Zhong, N. (eds). IEEE Computer Society Press, 732–738.

    Google Scholar

    Blankenburg B., Klusch M., Shehory O.2003. Fuzzy kernel-stable coalitions between rational agents. In Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-03), Rosenschein, J. S., Wooldridge, M., Sandholm, T. & Yokoo, M. (eds). ACM Press, 9–16.

    Google Scholar

    Bloch F.2003. Non-cooperative models of coalition formation in games with spillover. In The Endogenous Formation of Economic Coalitions, Carraro, C. (ed.). Edward Elgar, chapter 2, 35–79.

    Google Scholar

    Bogomolnaia A., Jackson M. O.2002. The stability of hedonic coalition structures. Games and Economic Behavior38(2), 201–230.

    Google Scholar

    Brânzei S., Larson K.2009a. Coalitional affinity games. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-09), 1319–1320.

    Google Scholar

    Brânzei S., Larson K.2009b. Coalitional affinity games. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), Budapest, Hungary, 79–84.

    Google Scholar

    Breban S., Vassileva J.2002. A coalition formation mechanism based on inter-agent trust relationships. In AAMAS '02: Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems, Gini, M., Ishida, T., Castelfranchi, C. & Lewis Johnson, W. (eds). ACM Press, 306–307.

    Google Scholar

    Brooks C. H., Durfee E. H.2003. Congregation formation in multiagent systems. Autonomous Agents and Multi-Agent Systems7(1–2), 145–170.

    Google Scholar

    Caillou P., Aknine S., Pinson S.2002. A multi-agent method for forming and dynamic restructuring of pareto optimal coalitions. In AAMAS '02: Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems, Gini, M., Ishida, T., Castelfranchi, C. & Lewis Johnson, W. (eds). ACM Press, 1074–1081.

    Google Scholar

    Chalkiadakis G., Boutilier C.2004. Bayesian reinforcement learning for coalition formation under uncertainty. In Proceedings of the third International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'04), New York, NY, USA.

    Google Scholar

    Chalkiadakis G., Boutilier C.2008. Sequential decision making in repeated coalition formation under uncertainty. In Proceedings of the 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-08), Estoril, Portugal.

    Google Scholar

    Chalkiadakis G., Boutilier C.2012. Sequentially optimal repeated coalition formation under uncertainty. Autonomous Agents and Multi-Agent Systems 24(3), 441–484.

    Google Scholar

    Chalkiadakis G., Elkind E., Jennings N. R.2009. Simple coalitional games with beliefs. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, Boutilier, C. (ed.). Morgan Kaufmann Publishers Inc., 85–90.

    Google Scholar

    Chalkiadakis G., Elkind E., Markakis E., Jennings N. R.2008. Overlapping coalition formation. In Proceeedings of the 4th International Workshop on Internet and Network Economics (WINE2008), Shanghai, China, 307–321.

    Google Scholar

    Chalkiadakis G., Elkind E., Markakis E., Jennings N. R.2010. Cooperative games with overlapping coalitions. Journal of Artificial Intelligence Research39, 179–216.

    Google Scholar

    Coleman J. S.1970. The benefits of coalition. Public Choice8, 45–61.

    Google Scholar

    Conitzer V., Sandholm T.2003. Complexity of determining nonemptiness of the core. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Acapulco, Mexico.

    Google Scholar

    Conitzer V., Sandholm T.2004. Computing shapley values, manipulating value division schemes, and checking core membership in multi-issue domains. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-04), San Jose, CA, USA, 219–225.

    Google Scholar

    Contreras J., Klusch M., Shehory O., Wu F.1997. Coalition formation in a power transmission planning environment. In Proceedings of the Second International Conference on Practical Applications of Multi-Agent Systems, PAAM97, London, UK.

    Google Scholar

    Contreras J., Klusch M., Yen J.1998. Multi-agent coalition formation in power transmission planning: a bilateral shapley value approach. In Proceedings of the Fourth International Conference on Artificial Intelligence Planning Systems, Pittsburgh, PA, USA.

    Google Scholar

    Cornforth D., Kirley M., Bossomaier T.2004. Agent heterogeneity and coalition formation: investigating market-based cooperative problem solving. In Proceedings of the third International Joint Conference on Autonomous Agents and Multiagent Systems(AAMAS'04), New York, NY, USA.

    Google Scholar

    Dang V. D., Dash R. K., Rogers A., Jennings N. R.2006. Overlapping coalition formation for efficient data fusion in multi-sensor networks. In Proceedings of the Twenty-First Conference on Artificial Intelligence (AAAI-06), Boston, USA, 635–640.

    Google Scholar

    Dang V. D., Jennings N. R.2004. Generating coalition structures with finite bound from the optimal guarantees. In Proceedings of the third International Joint Conference on Autonomous Agents and Multiagent Systems(AAMAS'04), New York, NY, USA.

    Google Scholar

    Davis M., Maschler M.1965. The kernel of a cooperative game. Naval Research Logistics Quarterly12, 223–259.

    Google Scholar

    Deng X., Fang Q., Sun X.2006. Finding nucleolus of flow game. In SODA '06: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm. ACM Press, 124–131.

    Google Scholar

    Deng X., Papadimitriou C. H.1994. On the complexity of cooperative solution concepts. Mathematical Operation Research19(2), 257–266.

    Google Scholar

    de Keijzer B., Klos T., Zhang Y.2010. Enumeration and exact design of weighted voting games. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2010), Toronto, Canada, 391–398.

    Google Scholar

    Dieckmann T., Schwalbe U.2002. Dynamic coalition formation and the core. Journal of Economic Behavior & Organization49(3), 363–380.

    Google Scholar

    Elkind E., Goldberg L. A., Goldberg P., Wooldridge M.2007. Computational complexity of weighted threshold games. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (AAAI-07), Vancouver, Canada, 718–723.

    Google Scholar

    Elkind E., Pasechnik D.2009. Computing the nucleolus of weighted voting games. In SODA'09: 20th ACM-SIAM Symposium on Discrete Algorithms, New York, NY, USA, 327–335.

    Google Scholar

    Elkind E., Wooldridge M.2009. Hedonic coalition nets. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-09), Budapest, Hungary, 417–424.

    Google Scholar

    Gillies D. B.1953. Some Theorems on n-Person Games. PhD thesis, Department of Mathematics, Princeton University.

    Google Scholar

    Greco G., Malizia E., Palopoli L., Scarcello F.2009. On the complexity of compact coalitional games. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, Boutilier, C. (ed.). Morgan Kaufmann Publishers Inc., 147–152.

    Google Scholar

    Griffiths N., Luck M.2003. Coalition formation through motivation and trust. In Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS '03), Rosenschein, J. S., Wooldridge, M., Sandholm, T. & Yokoo, M. (eds). ACM Press.

    Google Scholar

    Hart S., Kurz M.1983. Endogenous formation of coalitions. Econometrica51(4), 1047–1064.

    Google Scholar

    Horling B., Lesser V.2004. A survey of multi-agent organizational paradigms. The Knowledge Engineering Review19, 281–316.

    Google Scholar

    Horling B., Vincent R., Mailler R., Shen J., Becker R., Rawlins K., Lesser V.2001. Distributed sensor network for real time tracking. In Proceedings of the Fifth International Conference on Autonomous Agents (Agents'01), André, E., Sen, S., Frasson, C. & Müller, J. P. (eds). ACM Press, 417–424.

    Google Scholar

    Ieong S., Shoham Y.2005. Marginal contribution nets: a compact representation scheme for coalitional games. In EC ‘05: Proceedings of the 6th ACM Conference on Electronic Commerce, Riedl, J., Kearns, M. & Reiter, M. (eds). ACM Press, 193–202.

    Google Scholar

    Ieong S., Shoham Y.2008. Bayesian coalitional games. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence (AAAI-08), Chicago, IL, USA, 95–100.

    Google Scholar

    Kahan J. P., Rapoport A.1984. Theories of Coalition Formation. Lawrence Erlbaum Associates.

    Google Scholar

    Kalai E., Xemel E.1982. Totally balanced games and games of flow. Mathematics of Operations Research7, 476–478.

    Google Scholar

    Ketchpel S. P.1994a. The formation of coalitions among self-interested agents. In Proceedings of the Eleventh National Conference on Artificial Intelligence, Seattle, Washington, 414–419.

    Google Scholar

    Ketchpel S. P.1994b. Forming coalitions in the face of uncertain rewards. In Proceedings of the Eleventh National Conference on Artificial Intelligence, Seattle, Washington, 414–419.

    Google Scholar

    Klusch M., Shehory O.1996a.Coalition formation among rational information agents. In Seventh European Workshop on Modelling Autonomous Agents in a Multi-Agent World, van Hoe, R. (ed.). Eindhoven, The Netherlands, 204–217.

    Google Scholar

    Klusch M., Shehory O.1996b. A polynomial kernel-oriented coalition algorithm for rational information agents. In Proceedings of the Second International Conference on Multi-Agent Systems, Rosenschein, J. S., Wooldridge, M., Sandholm, T. & Yokoo, M. (eds). AAAI Press, 157–164.

    Google Scholar

    Kraus S., Shehory O., Taase G.2003. Coalition formation with uncertain heterogeneous information. In Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems, Rosenschein, J. S., Wooldridge, M., Sandholm, T. & Yokoo, M. (eds). ACM Press, 1–8.

    Google Scholar

    Kraus S., Shehory O., Taase G.2004. The advantages of compromising in coalition formation with incomplete information. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'04), New York, NY, USA.

    Google Scholar

    Kuipers J., Faigle U., Kern W.2001. On the computation of the nucleolus of a cooperative game. International Journal of Game Theory30(1), 79–98.

    Google Scholar

    Larson K. S., Sandholm T. W.2000. Anytime coalition structure generation: an average case study. Journal of Experimental & Theoretical Artificial Intelligence12(1), 23–42.

    Google Scholar

    Lau H. C., Zhang L.2003. Task allocation via multi-agent coalition formation: taxonomy, algorithms and complexity. In Proceedings of the 15th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2003), Sacramento, CA, USA, 346–350.

    Google Scholar

    Lerman K., Shehory O.2000. Coalition formation for large-scale electronic markets. In Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), Durfee, E. (ed.). IEEE Computer Society, 167–174.

    Google Scholar

    Li C., Rajan U., Chawla S., Sycara K.2003. Mechanisms for coalition formation and cost sharing in an electronic marketplace. In ICEC '03: Proceedings of the 5th International Conference on Electronic Commerce, Sadeh, N., Dively, M. J., Kauffman, R., Labrou, Y., Shehory, O., Telang, R. & Cranor, L. (eds). ACM Press, 68–77.

    Google Scholar

    Li C., Sycara K.2002. Algorithm for combinatorial coalition formation and payoff division in an electronic marketplace. In Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS '02), Gini, M., Ishida, T., Castelfranchi, C. & Lewis Johnson, W. (eds). ACM Press, 120–127.

    Google Scholar

    Manisterski E., David E., Kraus S., Jennings N. R.2006. Forming efficient agent groups for completing complex tasks. In Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems AAMAS-06, Hakodate, Japan.

    Google Scholar

    Mares M.2001. Fuzzy cooperative games: cooperation with vague expectations, volume 72 of Studies in Fuzziness and Soft Computing. Physica Verlag.

    Google Scholar

    Mérida-Campos C., Willmott S.2004. Modelling coalition formation over time for iterative coalition games. In Proceedings of the third International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS'04), New York, NY, USA.

    Google Scholar

    Mérida-Campos C., Willmott S.2006. The effect of heterogeneity on coalition formation in iterated request for proposal scenarios. In Proceedings of the Fourth European Workshop on Multi-Agent Systems (EUMAS 06), Lisbon, Portugal.

    Google Scholar

    Michalak T., Dowell A., McBurney P., Wooldridge M.2008. Optimal coalition structure generation in partition function games. In Proceeding of the 2008 Conference on ECAI 2008, Ghallab, M., Spyropoulos, C. D., Fakotakis, N. & Avouris, N. (eds). IOS Press, 388–392.

    Google Scholar

    Michalak T., Rahwan T., Marciniak D., Szamotulski M., Jennings N. R.2010. Computational aspects of extending the shapley value to coalitional games with externalities. In Proceedings of the 2010 Conference on ECAI 2010: 19th European Conference on Artificial Intelligence, Coelho, H., Studer, R. & Wooldridge, M. (eds). IOS Press, 197–202.

    Google Scholar

    Michalak T., Rahwan T., Marciniak D., Szamotulski M., McBurney P., Jennings N. R.2010. A logic-based representation for coalitional games with externalities. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems – Volume 1, AAMAS '10. International Foundation for Autonomous Agents and Multiagent Systems, 125–132.

    Google Scholar

    Michalak T., Rahwan T., Sroka J., Dowell A., Wooldridge M., McBurney P., Jennings N. R.2009. On representing coalitional games with externalities. In Proceedings of the 10th ACM Conference on Electronic Commerce 09 (EC'09), Stanford, CA, USA.

    Google Scholar

    Myerson R. B.1977. Graphs and cooperation in games. Mathematics of Operations Research2, 225–229.

    Google Scholar

    Nishizaki I., Sakawa M.2001. Fuzzy and multiobjective games for conflict resolution, volume 64 of Studies in Fuzziness and Soft Computing. Physica Verlag.

    Google Scholar

    Ohta N., Conitzer V., Satoh Y., Iwasaki A., Yokoo M.2009. Anonimity-proof shapley value: extending shapley value for coalitional games in open environments. In Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-09), Budapest, Hungary.

    Google Scholar

    Osborne M. J., Rubinstein A.1994. A Course in Game Theory. The MIT Press.

    Google Scholar

    Owen G.1977. Values of games with a priori unions. In Mathematical Economics and Game Theory: Essays in Honor of Oskar Morgenstern, Hein, O. M. R. (ed.). Springer, 77–88.

    Google Scholar

    Pěchouček M, Mařík V., Bárta J.2002. A knowledge-based approach to coalition formation. IEEE Intelligent Systems17(3), 17–25.

    Google Scholar

    Pěchouček M., Mařík V., čStépánková O.2000. Coalition formation in manufacturing multi-agent systems. In Proceedings of the 11th International Workshop on Database and Expert Systems Applications (DEXA'00), London/Greenwich, UK.

    Google Scholar

    Peleg B., Sudhölter P.2007. Introduction to the theory of cooperative cooperative games, 2nd editionSpringer.

    Google Scholar

    Plaza E., Ontañón S.2006. Learning collaboration strategies for committees of learning agents. Journal of Autonomous Agents and Multi-Agent Systems13(3), 429–461.

    Google Scholar

    Poon A. S. Y., Yeung C. S. K., Wu F. F.1999. Game theoretical multi-agent modeling of coalition formation for multilateral trades. IEEE Transactions on Power Systems4(3), 929–934.

    Google Scholar

    Procaccia A. D., Rosenschein J. S.2006. The communication complexity of coalition formation among autonomous agents. In Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems AAMAS-06, Hakodate, Japan.

    Google Scholar

    Rahwan T., Jennings N. R.2007. An algorithm for distributing coalitional value calculations among cooperating agents. Artificial Intelligence171(8–9), 535–567.

    Google Scholar

    Rahwan T., Jennings N. R.2008a. Coalition structure generation: Dynamic programming meets anytime optimization. In Proceedings of the 23rd Conference on Artificial Intelligence (AAAI-08), Chicago, IL, USA, 156–161.

    Google Scholar

    Rahwan T., Jennings N. R.2008b. An improved dynamic programming algorithm for coalition structure generation. In Proceedings of the 7th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS-08), Estoril, Portugal.

    Google Scholar

    Rahwan T., Michalak T., Jennings N. R., Wooldridge M., McBurney P.2009. Coalition structure generation in multi-agent systems with positive and negative externalities. In Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI-09), Pasadena, CA, USA.

    Google Scholar

    Rahwan T., Ramchurn S. D., Dang V. D., Giovannucci A., Jennings N. R.2007a. Anytime optimal coalition structure generation. In Proceedings of the Twenty-Second Conference on Artificial Intelligence (AAAI-07), Vancouver, Canada, 1184–1190.

    Google Scholar

    Rahwan T., Ramchurn S. D., Dang V. D., Jennings N. R.2007b. Near-optimal anytime coalition structure generation. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI'07), Hyderabad, India, 2365–2371.

    Google Scholar

    Rahwan T., Ramchurn S. D., Jennings N. R., Giovannucci A.2009. An anytime algorithm for optimal coalition structure generation. Journal of Artificial Intelligence Research34, 521–567.

    Google Scholar

    Ray D., Vohra R.1999. A theory of endogenous coalition structures. Games and Economic Behavior26, 286–336.

    Google Scholar

    Sandholm T., Lesser V. R.1997. Coalitions among computationally bounded agents. AI Journal94(1–2), 99–137.

    Google Scholar

    Sandholm T. W., Larson K. S., Andersson M., Shehory O., Tohmé F.1999. Coalition structure generation with worst case guarantees. Artificial Intelligence111(1–2), 209–238.

    Google Scholar

    Sarne D., Kraus S.2003. The search for coalition formation in costly environments. In Cooperative Information Agents VII, 7th International Workshop, CIA 2003, Helsinki, Finland, August 27–29, 2003, Proceedings, Lecture Notes in Computer Science 2782, Springer.

    Google Scholar

    Sarne D., Kraus S.2005. Cooperative exploration in the electronic marketplace. In Proceedings of the Twentieth National Conference on Artificial Intelligence, Veloso, M. & Kambhampati, S. (eds). AAAI Press/The MIT Press, 158–163.

    Google Scholar

    Schmeidler D.1969. The nucleolus of a characteristic function game. SIAM Journal of Applied Mathematics17, 1163–1170.

    Google Scholar

    Sen S., Dutta P. S.2000. Searching for optimal coalition structures. In ICMAS ‘00: Proceedings of the Fourth International Conference on MultiAgent Systems (ICMAS-2000), Durfee, E. (ed.). IEEE Computer Society, 287.

    Google Scholar

    Service T., Adams J.2010. Approximate coalition structure generation. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), Atlanta, Georgia, USA, 854–859.

    Google Scholar

    Service T. C., Adams J. A.2011. Constant factor approximation algorithms for coalition structure generation. Autonomous Agents and Multi-Agent Systems23(1), 1–17.

    Google Scholar

    Shapley L.1953. A value for n-person games. In Contributions to the Theory of Games, Kuhn, H. & Tucker, A. (eds). Princeton University Press, vol. 2, 307–317.

    Google Scholar

    Shehory O., Kraus S.1998. Methods for task allocation via agent coalition formation. Artificial Intelligence101(1–2), 165–200.

    Google Scholar

    Shehory O., Kraus S.1999. Feasible formation of coalitions among autonomous agents in nonsuperadditve environments. Computational Intelligence15, 218–251.

    Google Scholar

    Sims M., Goldman C. V., Lesser V.2003. Self-organization through bottom-up coalition formation. In Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS03), Rosenschein, J. S., Wooldridge, M., Sandholm, T. & Yokoo, M. (eds). ACM Press, 867–874.

    Google Scholar

    Soh L.-K., Tsatsoulis C., Sevay H.2003. A satisficing, negotiated, and learning coalition formation architecture. In Distributed Sensor Networks, Victor, L., Charles O. Jr. & Milind, T. (eds). Springer, 109–138.

    Google Scholar

    Soh L.-K., Tsatsoulis C.2002. Satisficing coalition formation among agents. In AAMAS '02: Proceedings of the First International Joint Conference on Autonomous Agents and Multiagent Systems. ACM Press, 1062–1063.

    Google Scholar

    Stearns R. E.1968. Convergent transfer schemes for n-person games. Transactions of the American Mathematical Society134(3), 449–459.

    Google Scholar

    Thrall R. M., Lucas W. F.1963. N-person games in partition function form. Naval Research Logistics Quarterly10(1), 281–298.

    Google Scholar

    Tohmé F., Sandholm T.1999. Coalition formation processes with belief revision among bounded-rational self-interested agents. Journal of Logic and Computation9(6), 793–815.

    Google Scholar

    Tsvetovat M., Sycara K. P., Chen Y., Ying J.2001. Customer coalitions in electronic markets. In Agent-Mediated Electronic Commerce III, Current Issues in Agent-Based Electronic Commerce Systems (includes revised papers from AMEC 2000 Workshop), Dignum, F. & Cortès, U. (eds). Springer-Verlag, 121–138.

    Google Scholar

    Ueda S., Iwasaki A., Yokoo M., Silaghi M. C., Hirayama K., Matsui T.2010. Coalition structure generation based on distributed constraint optimization. In Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI-10), Atlanta, Georgia, USA, 197–203.

    Google Scholar

    Vassileva J., Breban S., Horsch M.2002. Agent reasoning mechanism for making long-term coalitions based on decision making and trust. Computational Intelligence18(4), 583–595.

    Google Scholar

    Wooldridge M.2009. An Introduction to MultiAgent Systems, 2nd edition, Wiley.

    Google Scholar

    Wu L.S.-Y.1977. A dynamic theory for the class of games with nonempty cores. SIAM Journal on Applied Mathematics32(2), 328–338.

    Google Scholar

    Yamamoto J., Sycara K.2001. A stable and efficient buyer coalition formation scheme for e-marketplaces. In AGENTS '01: Proceedings of the Fifth International Conference on Autonomous Agents, André, E., Sen, S., Frasson, C. & Müller, J. P. (eds). ACM Press, 576–583.

    Google Scholar

    Yokoo M., Conitzer V., Sandholm T., Ohta N., Iwasaki A.2005. Coalitional games in open anonymous environments. In Proceedings of the Twentieth National Conference on Artificial Intelligence, Veloso, M. M. & Kambhampati, S. (eds). AAAI Press AAAI Press/The MIT Press, 509–515.

    Google Scholar

    Yokoo M., Conitzer V., Sandholm T., Ohta N., Iwasaki A.2006. A compact representation scheme for coalitional games in open anonymous environments. In Proceedings of the Twenty First National Conference on Artificial Intelligence, Gil, Y. & Mooney, R. J. (eds). AAAI Press/The MIT Press, 697–702.

    Google Scholar

    Young H. P.1985. Monotonic solutions of cooperative games. International Journal of Game Theory14, 65–72.

    Google Scholar

  • Cite this article

    Stéphane Airiau. 2013. Cooperative games and multiagent systems. The Knowledge Engineering Review 28(4)381−424, doi: 10.1017/S0269888913000106
    Stéphane Airiau. 2013. Cooperative games and multiagent systems. The Knowledge Engineering Review 28(4)381−424, doi: 10.1017/S0269888913000106
    shu
Download PDF

Article Metrics

Article views(24) PDF downloads(227)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Cooperative games and multiagent systems

  • Place du Maréchal de Lattre de Tassigny

  • Published online: 03 May 2013
The Knowledge Engineering Review  28,  2013, 28(4): 381−424  |  Cite this article

Abstract: Abstract: Forming coalitions is a generic means for cooperation: people, robots, web services, resources, firms; they can all improve their performance by joining forces. The use of coalitions has been successful in domains such as task allocations, sensor networks, and electronic marketplaces. Forming efficient coalitions requires the identification of matching synergies between different entities (finding complementary partners, or similar partners, or partners who add diversity). In addition, the different parties must negotiate a fair repartition of the worth created by the coalition. The first part of this paper is a tutorial on cooperative game theory (also called coalitional games). We then survey the different scenarios and the key issues addressed by the multiagent systems community.

    HTML

    Acknowledgments

    • This article originated from the related work of my dissertation, under the supervision of Sandip Sen. I thank him for reviews and comments about earlier versions of this paper. I also thank Krzysztof R. Apt. for sharing his notes. I also thank Ulle Endriss for his comments. An earlier version of this article has been used as lecture notes for the 12th European Agent Systems Summer School held in Saint-Etienne, France.

    • The formal definition is the following: definition 2.13 (Lexicographic ordering). Let$$\[--><$> (x,y)\, \in \,{{({{{\Bbb R}}^m} )}^2} <$><!--$$. We say that x is greater or equal to y in the lexicographical ordering, and we note$$\[--><$> x\,{{\geq }_{lex}}\,y\,when\,\,\left\{ {\matrix{ {x\, = \,y\,or} \hfill \cr{\exists\, t\,s.\,t.\,1\,\leq \,t\,\leq \,m\,s.\,t.\,\forall i\,s.\,t.\,1\,\leq \,i\, \lt \,t\,{{x}_i}\, = \,{{y}_i}\,and\,{{x}_t}\, \gt \,{{y}_t}} \hfill \\\end{}} \right. <$><!--$$

    • We introduce this class in Section 2.6 about the Shapley value.

    • $$\[--><$>{\scr S}(n,m) <$><!--$$ is the number of ways of partitioning a set of n elements into $$\[--><$> m <$><!--$$ non-empty sets.

    • An earlier version is Chalkiadakis et al. (2008).

    Rights and permissions
    • Copyright © Cambridge University Press 2013 2013Cambridge University Press
References (126)
  • About this article
    Cite this article
    Stéphane Airiau. 2013. Cooperative games and multiagent systems. The Knowledge Engineering Review 28(4)381−424, doi: 10.1017/S0269888913000106
    Stéphane Airiau. 2013. Cooperative games and multiagent systems. The Knowledge Engineering Review 28(4)381−424, doi: 10.1017/S0269888913000106
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return