Reference : Algorithms for finding coalitions exploiting a new reciprocity condition

	Document type :	Scientific journals : Article
	Discipline(s) :	Engineering, computing & technology : Computer science
	To cite this reference:	http://hdl.handle.net/10993/25169

Title :	Algorithms for finding coalitions exploiting a new reciprocity condition
Language :	English
Author, co-author :	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) >]
Publication date :	20-May-2009
Journal title :	Logic Journal of the IGPL
Publisher :	Oxford University Press
Volume :	17
Issue/season :	3
Pages :	273–297
Peer reviewed :	Yes
Audience :	International
ISSN :	1367-0751
e-ISSN :	1368-9894
City :	Oxford
Country :	United Kingdom
Keywords :	[en] Algorithms ; reciprocity condition ; coalitions exploiting
Abstract :	[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.
Target :	Researchers ; Professionals ; Students ; General public ; Others
Permalink :	http://hdl.handle.net/10993/25169
DOI :	10.1093/jigpal/jzp008
Other URL :	http://jigpal.oxfordjournals.org/content/17/3/273.full.pdf+html

	File(s) associated to this reference
	Fulltext file(s): File Commentary Version Size Access Open access Logic Jnl IGPL-2009-Boella-273-97.pdf Publisher postprint 418.34 kB View/Open

All documents in ORBi^lu are protected by a user license.

 

University of Luxembourg Library |  Feedback |  Legal notices Site Map