Logic Journal of IGPL Advance Access originally published online on May 20, 2009
Logic Journal of IGPL 2009 17(3):273-297; doi:10.1093/jigpal/jzp008
Algorithms for finding coalitions exploiting a new reciprocity condition
Università di Torino, Italy.
E-mail: guido{at}di.unito.it
Università di Napoli, Italy.
E-mail: sauro{at}na.infn.it
University of Luxembourg, Luxembourg.
E-mail: leon.vandertorre{at}uni.lu
We introduce a reciprocity criterion for coalition formation among goal-directed agents, which we call the indecomposable do-ut-des property. It refines an older reciprocity property, called the do-ut-des or give-to-get property by considering the fact that agents prefer to form coalitions whose components cannot be formed independently. A formal description of this property is provided as well as an analysis of algorithms and their complexity. We provide an algorithm to decide whether a coalition has the desired property, and we show that the problem to verify whether a single coalition satisfies the property is tractable. Moreover, we provide an algorithm to search all the sub-coalitions of a given coalition satisfying the new property. Even if this problem is not computationally tractable, we show that in several cases, also the complexity of this problem may decrease considerably.
Received for publication 17 October 2008.
References
-
[1] Alur R, Henzinger TA, Mang FYC, Qadeer S, Rajamani SK, Tasiran S. Mocha: Modularity in model checking. (1998) 521–525. In Proceedings of the 10th International Conference on Computer Aided Verification, (CAV '98), volume 1427 of Lecture Notes in Computer Science.
[2] Alur R, Henzinger TA, Kupferman O. Alternating-time temporal logic. Journal of ACM (2002) 49(5):672–713.[CrossRef]
[3] Aumann RJ. The core of a cooperative game without side payments. Transaction of the American Mathematical Society (1961) 98:539–552.[CrossRef]
[4] Boella G, Sauro L, van der Torre L. Power and dependence relations in groups of agents. (2004) Beijin, Cina. In Procs. of 2004 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT'04).
[5] Boella G, Sauro L, van der Torre L. Admissible agreements among goal-directed agents. (2005) Paris, France. In Procs. of 2005 IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT'05).
[6] Boella G, Sauro L, van der Torre L. Strengthening admissible coalitions. In: Procs. of ECAI'06 (2006) Riva del Garda.
[7] Boella G, Sauro L, van der Torre L. From social power to social importance. Web Intelligence and Agent Systems Journal (2007) 5(4):393–404.
[8] Bonzon E, Lagasquie-Schiex M, Lang J. Dependencies between players in boolean games. In: ECSQARU 2007 (2007) 743–754.
[9] Bonzon E, Lagasquie-Schiex M, Lang J, Zanuttini B. Boolean games revisited. (2006) Springer-Verlag. 265–269. In 17th European Conference on Artificial Intelligence (ECAI'06).
[10] Bulling N, Chesnevar CI, Dix J. Modelling coalitions: Atl + argumentation. In: AAMAS 2008 (2008) 681–688.
[11] Castelfranchi C. Founding agents' "autonomy" on dependence theory. (2000) Berlin, Germany. 353–357. In Proceedings of the 14th European Conference on Artificial Intelligence (ECAI'00).
[12] Castelfranchi C. The Micro-Macro Constitution of Power. ProtoSociology (2003) 18–19.
[13] Conte R, Sichman J. Multi-Agent Dependence by Dependence Graphs. (2002) Bologna, Italy. 483–490. In Proceedings of The First International Joint Conference on Autonomous Agents & Multiagent Systems (AAMAS'02).
[14] Conte R, Sichman JS. Dependence graphs: Dependence within and between groups. Computational & Mathematical Organization Theory (2002) 8(2):87–112.[CrossRef]
[15] Cormen T, Rivest C Leiserson R. Introduction to Algorithms (1990) MIT Press.
[16] Dang D, Jennings N. Generating coalition structures with finite bound from the optimal guarantees. (2004) New York, USA. 564–571. In Proceedings of The Third International Joint Conference on Autonomous Agents & Multiagent Systems (AAMAS'04).
[17] d'Inverno M, Luck M. A formal view of social dependence networks. (1996) Camberra, Australia. In Proceedings of First Australian Workshop on Distributed Artificial Intelligence (DAI'95), volume 1087 of Lecture Notes in Computer Science.
[18] Dunne PE, Wooldridge M. Preferences in qualitative coalitional games. In: Proceedings of the sixth Workshop on Game Theoretic and Decision Theoretic Agents (GTDT'04) (2004) July. New York, USA. 29–38.
[19] Durfee EH, Rosenschein JS. Distributed problem solving and multi-agent systems: Comparisons and examples. In: The Thirteenth International Distributed Artificial Intelligence Workshop (1994) Seattle, Washington. 94–104.
[20] Goranko V, van Drimmelen G. Decidability and complete axiomatization of the alternating-time temporal logic. In: Theoretical Computer Science. to appear.
[21] Grosz B, Kraus S, Talman S, Stossel B, Havlin M. The influence of social dependencies on decision-making: Initial investigation with a new game. (2004) New York, USA. 782–789. In Proceedings of The Third International Joint Conference on Autonomous Agents & Multiagent Systems (AAMAS'04).
[22] Harel D, Kozen D, Tiuryn J. Dynamic logic. In: Handbook of Philosophical Logic Volume II — Extensions of Classical Logic—Gabbay D, Guenther F, eds. (1984) Dordrecht, The Netherlands: D. Reidel Publishing Company. 497–604.
[23] Harrenstein P. Logic in Conflict (2004) Utrecht University. PhD thesis.
[24] Harrenstein P, van der Hoek W, Meyer J, Witteveen C. Boolean games. In: TARK 2001 (2001) 287–298.
[25] Kraus S, Plotkin T. Algorithms of distributed task allocation for cooperative agents. Theoretical Computer Science (2000) 242(1–2):1–27.[CrossRef][Web of Science]
[26] McMillan KL. Symbolic Model Checking (1992) CMU University. PhD thesis.
[27] Pauly M. A Modal Logic for Coalitional Power in Games. Journal of Logic and Computation (2002) 12:146–166.
[28] Rosental RW. Cooperative games in effectiveness form. Journal of Economic Theory (1972) 5:88–101.[CrossRef][Web of Science]
[29] Sandholm T, Larson K, Andersson M, Shehory O, Tohm F. Coalition structure generation with worst case guarantees. Artificial Intelligence (1999) 111(1–2):209–238.[CrossRef][Web of Science]
[30] Sandholm T, Lesser V. Coalitions among computationally bounded agents. Artificial Intelligence (1997) 94(1):99–137.[CrossRef][Web of Science]
[31] Sauro L. Formalizing Admissibility Criteria in Coalition Formation Among Goaldirected Agents (2006) PhD thesis.
[32] Sauro L. Qualitative criteria of admissibility for enforced agreements. Computational & Mathematical Organization Theory (2006) October;12(2–3):147–168.[CrossRef]
[33] Shapley LS, Shubik M. Pure competition, coalitional power and fair division. International Economic Review (1969) 10(3):337–362.[CrossRef]
[34] Shehory O, Kraus S. Methods for Task Allocation via Agent Coalition Formation. Artificial Intelligence (1998) 101(1–2):165–200.[CrossRef][Web of Science]
[35] Sichman JS, Demazeau Y. On social reasoning in multi-agent systems. Revista Iberoamericana de Inteligencia Artificial (2001) 13:68–84.
[36] Tarjan R. Depth-first search and linear graph algorithms. SIAM Journal of Computation (1972) 1(2):146–160.[CrossRef]
[37] van der Hoek W, Wooldridge M. Cooperation, knowledge, and time: Alternatingtime temporal epistemic logic and its applications. Studia Logica (2003) 75(1):125–157.[CrossRef]
[38] von Neumann J, Morgensten O. Theory of Games and Economic Behavior (1944) John Wiley and Sons.
[39] Wooldridge M, Dunne PE. On the computational complexity of qualitative coalitional games. Artificial Intelligence (2004) 158(1):27–73.[CrossRef][Web of Science]
[40] Wooldridge M, Jennings J. Towards a theory of cooperative problem solving. (1994) Odense, Denmark, Springer. 40–53. Proceedings of the Sixth European Workshop on Modelling Autonomous Agents in Multi-Agent Worlds (MAAMAW-94), volume 1069 of Lecture Notes in Computer Science.
[41] Zlotkin G, Rosenschein JS. Mechanism design for automated negotiation, and its application to task oriented domains. Artificial Intelligence (1996) 86(2):195–244.[CrossRef][Web of Science]
CiteULike 
Connotea 
Del.icio.us What's this?
| ||||||||||||||||||||||||||||||||||||||||||||||||