Algorithms for finding coalitions exploiting a new reciprocity condition
English
Boella, Guido[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
Sauro, Luigi[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
van der Torre, Leon[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
[en] 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.
Researchers ; Professionals ; Students ; General public ; Others