In many real-world settings, the structure of the environment constrains the formation of coalitions among agents. These settings can be represented by characteristic function games, also known as coalitional games, equipped with interaction graphs. An interaction graph determines the set of all feasible coalitions, in that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. Our work analyzes stability issues arising in such environments, by focusing on the core as a solution concept, and by considering the coalition structure viewpoint, that is, without assuming that the grand-coalition necessarily forms. The complexity of the coalition structure core is studied over a variety of interaction graph structures of interest, including complete graphs, lines, cycles, trees, and nearly-acyclic graphs (formally, having bounded treewidth). The related stability concepts of the least core and the cost of stability are also studied. Results are derived for the setting of compact coalitional games, i.e., for games that are implicitly described via a compact encoding, and where simple calculations on this encoding are to be performed in order to compute the payoff associated with any coalition. Moreover, specific results are provided for compact games defined via marginal contribution networks, an expressive encoding mechanism that received considerable attention in the last few years.

Characteristic function games with restricted agent interactions: Core-stability and coalition structures

GRECO, Gianluigi;
2016-01-01

Abstract

In many real-world settings, the structure of the environment constrains the formation of coalitions among agents. These settings can be represented by characteristic function games, also known as coalitional games, equipped with interaction graphs. An interaction graph determines the set of all feasible coalitions, in that a coalition C can form only if the subgraph induced over the nodes/agents in C is connected. Our work analyzes stability issues arising in such environments, by focusing on the core as a solution concept, and by considering the coalition structure viewpoint, that is, without assuming that the grand-coalition necessarily forms. The complexity of the coalition structure core is studied over a variety of interaction graph structures of interest, including complete graphs, lines, cycles, trees, and nearly-acyclic graphs (formally, having bounded treewidth). The related stability concepts of the least core and the cost of stability are also studied. Results are derived for the setting of compact coalitional games, i.e., for games that are implicitly described via a compact encoding, and where simple calculations on this encoding are to be performed in order to compute the payoff associated with any coalition. Moreover, specific results are provided for compact games defined via marginal contribution networks, an expressive encoding mechanism that received considerable attention in the last few years.
2016
Coalitional games; Computational complexity; Marginal contribution networks; Solution concepts; Treewidth
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/132551
 Attenzione

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

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 35
  • ???jsp.display-item.citation.isi??? 29
social impact