Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Minimal Subsidies in Expense Sharing Games
verfasst von : Reshef Meir, Yoram Bachrach, Jeffrey S. Rosenschein
Erschienen in: Algorithmic Game Theory
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
A key solution concept in cooperative game theory is the core. The core of an expense sharing game contains stable allocations of the total cost to the participating players, such that each subset of players pays at most what it would pay if acting on its own. Unfortunately, some expense sharing games have an empty core, meaning that the total cost is too high to be divided in a stable manner. In such cases, an external entity could choose to induce stability using an external subsidy. We call the minimal subsidy required to make the core of a game non-empty the
Cost of Stability (CoS)
, adopting a recently coined term for surplus sharing games.
We provide bounds on the CoS for general, subadditive and anonymous games, discuss the special case of
Facility Games
, as well as consider the complexity of computing the CoS of the grand coalition and of coalitional structures.