Subsidies, Stability, and Restricted Cooperation in Coalitional Games

Reshef Meir, Jeffrey S. Rosenschein, Enrico MaliziaIJCAI 2011 · DOI

TL;DR

This paper explores how to incentivize self-interested agents to cooperate in "coalitional games" by using external subsidies. The authors quantify the minimum subsidy needed to ensure stable cooperation, comparing it to other stability concepts like the "least core" and analyzing how restricting which coalitions can form affects this cost.

What Problem Does This Paper Address?

In many real-world scenarios, multiple independent agents (companies, individuals, software agents) can achieve greater collective profit or utility by cooperating. However, these agents are often self-interested and will only cooperate if the outcome is stable – meaning no subgroup has an incentive to break away and form their own coalition. This paper tackles the challenge of ensuring such stable cooperation, particularly in situations where the "core" (a standard concept for stable outcomes) might be empty, meaning no stable allocation exists. The authors investigate the use of external subsidies as a mechanism to "buy" stability, aiming to find the most cost-effective way to achieve this. They also examine how limiting the possible coalition structures (e.g., only allowing certain groups to form) can reduce the need for subsidies.

Methods

The paper leverages concepts from coalitional game theory, specifically transferable utility (TU) games, where gains can be freely redistributed among agents.

  • Cost of Stability (CoS): The core contribution is the formalization and analysis of the "Cost of Stability." This is defined as the minimum external subsidy required to make the grand coalition (all agents cooperating) stable. This is achieved by creating a new game, $G(\Delta)$, where the grand coalition's value is increased by a subsidy $\Delta$. The CoS is the smallest $\Delta$ for which $G(\Delta)$ has a non-empty core.
  • Extended Core: The paper defines the "extended core" as the set of all possible stable outcomes achievable with the minimal subsidy (CoS).
  • Least Core: The authors compare CoS with the "least core," which represents the minimal relaxation of coalition demands needed for stability without external subsidies. They analyze the relationship between the CoS and the "strong least core" ($es(G)$) and "weak least core" ($ew(G)$).
  • Restricted Coalitions: A significant part of the work involves analyzing how restricting the set of possible coalitions ($T$) affects the CoS. This includes scenarios where only coalitions of a certain size are allowed, or where agent interactions are constrained by a communication graph.
  • Linear Programming Duality: The paper uses concepts from linear programming duality, particularly the Bondareva-Shapley theorem, to characterize the core and derive bounds for the CoS.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Subsidies as a Stability Tool: External subsidies are a powerful, albeit potentially costly, way to enforce cooperation. The CoS provides a precise measure of this cost.
  • CoS vs. Least Core: The paper establishes a quantitative relationship between the CoS and the least core. This is crucial because it shows how much "cheaper" it might be to subsidize cooperation versus demanding less from deviating coalitions.
  • Restrictions Can Significantly Reduce Costs: Limiting the types of coalitions that can form (e.g., through communication constraints or size limits) can dramatically reduce the required subsidy, sometimes making cooperation stable with minimal or no external intervention.
  • Superadditivity is Key: The paper highlights that superadditive games (where combining coalitions is always at least as good as their individual values) exhibit more stable properties and allow for tighter bounds on CoS.
  • Tight Bounds: The authors derive tight bounds for the ratio between the CoS and the least core, improving upon previous results and providing a more nuanced understanding of their relationship.

Key Results

  • CoS Bounds: For superadditive games, the paper shows $CoS(G) \leq \sqrt{n} \cdot es(G)$ and $CoS(G) \geq \frac{n}{n-1} \cdot es(G)$, where $n$ is the number of agents and $es(G)$ is the strong least core value. These bounds are shown to be tight.
  • Restricted Coalitions Impact:
    • For coalitions of size at most $k$, $RCoS(G|T) \leq \min\{k, \sqrt{n}\}$.
  • For partitions, $RCoS(G|T) < \max_{C \in P} \sqrt{|C|}$.
  • For communication graphs with a single cycle, $RCoS(G|T) < 2$.
  • Weak Least Core Relationship: For any game, $CoS(G) = n \cdot ew(G)$, where $ew(G)$ is the weak least core value. This implies that the weak least core is always contained within the extended core.

Limitations and Future Work

  • Conjecture on Nucleolus: A key open problem is whether the standard nucleolus (a unique solution concept) is always contained within the extended core. The authors conjecture this is true for games where the least core is contained in the extended core.
  • Specific Game Families: While general bounds are provided, exploring the CoS in specific families of TU games (e.g., network flow, graph games) could yield more tailored insights.
  • Expense Sharing Games: The analysis is primarily for profit-sharing games. Extending these results to expense-sharing games is suggested.
  • Non-TU Games: The paper notes that similar analyses could be applied to non-TU games, particularly concerning the "price of anarchy."
  • Coalition Structures: Further investigation into the CoS of coalition structures is proposed.

Summary updated

BibTeX
@inproceedings{meir2011subsidies,
  author = {Reshef Meir and Jeffrey S. Rosenschein and Enrico Malizia},
  title = {{Subsidies, Stability, and Restricted Cooperation in Coalitional Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.5591/978-1-57735-516-8/ijcai11-060},
}
Figure