Coalition structure generation is the problem of partitioning the agents of a given environment into disjoint and exhaustive coalitions so that the whole available worth is maximized. While this problem has been classically studied in settings where all coalitions are allowed to form, it has been recently reconsidered in the literature moving from the observation that environments often forbid the formation of certain coalitions. By following this latter perspective, a model for coalition structure generation is proposed where constraints of two different kinds can be expressed simultaneously. Indeed, the model is based on the concept of valuation structure, which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. It is shown that valuation structures can be used to model a number of relevant problems arising in real-world application domains. Then, the complexity of coalition structure generation over valuation structures is studied, by assuming that the functions associating each coalition with its worth are given as input according to some compact encoding—rather than explicitly listing all exponentially-many associations. In particular, islands of tractability are identified based on the topological properties of the underlying interaction graphs and on suitable algebraic properties of the given worth functions. Finally, stability issues over valuation structures are studied too, by considering the core as the prototypical solution concept.

Constrained coalition formation on valuation structures: Formal framework, applications, and islands of tractability

GRECO, Gianluigi;GUZZO, Antonella
2017

Abstract

Coalition structure generation is the problem of partitioning the agents of a given environment into disjoint and exhaustive coalitions so that the whole available worth is maximized. While this problem has been classically studied in settings where all coalitions are allowed to form, it has been recently reconsidered in the literature moving from the observation that environments often forbid the formation of certain coalitions. By following this latter perspective, a model for coalition structure generation is proposed where constraints of two different kinds can be expressed simultaneously. Indeed, the model is based on the concept of valuation structure, which consists of a set of pivotal agents that are pairwise incompatible, plus an interaction graph prescribing that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. It is shown that valuation structures can be used to model a number of relevant problems arising in real-world application domains. Then, the complexity of coalition structure generation over valuation structures is studied, by assuming that the functions associating each coalition with its worth are given as input according to some compact encoding—rather than explicitly listing all exponentially-many associations. In particular, islands of tractability are identified based on the topological properties of the underlying interaction graphs and on suitable algebraic properties of the given worth functions. Finally, stability issues over valuation structures are studied too, by considering the core as the prototypical solution concept.
Complex networks; Coalition formations
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.11770/134257
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 11
  • ???jsp.display-item.citation.isi??? 7
social impact