Algorithms for finding coalitions exploiting a new reciprocity condition

Logic Journal of the IGPL 17 (3):273-297 (2009)
  Copy   BIBTEX


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



    Upload a copy of this work     Papers currently archived: 91,322

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Complexity Results of STIT Fragments.François Schwarzentruber - 2012 - Studia Logica 100 (5):1001-1045.
A dynamic logic of agency I: Stit, capabilities and powers.Andreas Herzig & Emiliano Lorini - 2010 - Journal of Logic, Language and Information 19 (1):89-121.


Added to PP

14 (#956,614)

6 months
8 (#341,144)

Historical graph of downloads
How can I increase my downloads?