Algorithms for finding coalitions exploiting a new reciprocity condition (bibtex)
by Guido Boella, Luigi Sauro, Leendert W. N. van der Torre
Abstract:
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.
Reference:
Algorithms for finding coalitions exploiting a new reciprocity condition (Guido Boella, Luigi Sauro, Leendert W. N. van der Torre), In Logic Journal of the IGPL, volume 17, 2009.
Bibtex Entry:
@Article{Boella2009f,
  Title                    = {Algorithms for finding coalitions exploiting a new reciprocity condition},
  Author                   = {Guido Boella and Luigi Sauro and Leendert W. N. van der Torre},
  Journal                  = {Logic Journal of the IGPL},
  Year                     = {2009},
  Number                   = {3},
  Pages                    = {273-297},
  Volume                   = {17},

  Abstract                 = {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.},
  Affiliation              = {icr},
  Bdsk-url-1               = {http://jigpal.oxfordjournals.org/cgi/reprint/jzp008?ijkey=9alKpgJ9lYP8fHr&keytype=ref},
  Bibsource                = {DBLP, http://dblp.uni-trier.de},
  Date-modified            = {2011-09-25 17:32:41 +0200},
  Ee                       = {http://dx.doi.org/10.1093/jigpal/jzp008},
  Timestamp                = {2013.07.26},
  Url                      = {http://jigpal.oxfordjournals.org/cgi/reprint/jzp008?ijkey=9alKpgJ9lYP8fHr&keytype=ref}
}
Powered by bibtexbrowser