Bounds on the Cost of Stabilizing a Cooperative Game

Yoram Bachrach, Edith Elkind, Enrico Malizia, Reshef Meir, Dmitrii V. Pasechnik, Jeffrey S. Rosenschein, Jörg Rothe, Michael ZuckermanJAIR 2018 · DOI · OpenReview

Introduction

In the realm of cooperative game theory, the "core" represents the gold standard of stability. It is the set of all possible ways to distribute the total value generated by a group such that no sub-group (coalition) has a financial incentive to break away and act independently. However, in many practical applications—ranging from multi-agent systems to corporate mergers—the core is empty. In these cases, no matter how the "loot" is divided, some players will always find it more profitable to defect.

This paper addresses this fundamental instability by introducing the Cost of Stability (CoS). The CoS is defined as the minimum external subsidy required to supplement the game's total value such that the core becomes non-empty. Essentially, it asks: "What is the price of keeping everyone at the table?"

Theoretical Foundations

The authors approach the problem through the lens of the Bondareva–Shapley theorem, which provides necessary and sufficient conditions for a non-empty core based on "balanced collections" of coalitions. By applying linear programming duality, the researchers transform the search for a stable payoff into an optimization problem. This allows them to derive the Cost of Stability as the ratio between the value of the optimal solution to the dual program and the value of the grand coalition.

Analyzing Game Classes

The research provides a comprehensive taxonomy of stability costs across several fundamental classes of games:

1. Weighted Voting Games (WVG)

In a WVG, each player has a weight, and a coalition wins if its total weight meets or exceeds a specific quota. The paper proves that calculating the exact CoS for WVGs is coNP-complete. However, they provide a Fully Polynomial-Time Approximation Scheme (FPTAS) using the ellipsoid method and dynamic programming, making it feasible to estimate subsidies in complex voting scenarios.

2. Anonymous and Superadditive Games

A game is anonymous if the value of a coalition depends only on its size, not the identity of its members. It is superadditive if the union of two disjoint coalitions always produces at least as much value as the sum of their individual values. The authors find that anonymity drastically reduces the cost of stability. For anonymous superadditive games, the multiplicative CoS is at most $2 - \frac{2}{n+1}$, where $n$ is the number of players.

3. Cost-Sharing Games

In scenarios like Steiner tree or set cover games, where players share the cost of a service, the paper establishes that the CoS is bounded by approximately $\ln(n)$. This aligns with known results in combinatorial optimization regarding the integrality gap of certain linear programs.

Key Results: A Hierarchy of Stability

The paper's most significant contribution is a set of tight mathematical bounds on the multiplicative Cost of Stability (the ratio of the subsidized total to the original value):

Game Type Multiplicative Bound
General Monotone $n$ (where $n$ is the number of players)
Superadditive $\sqrt{n}$
Anonymous Superadditive $\approx 2$ (specifically $2 - \frac{2}{n+1}$)
Superadditive WVG $< 2$
Subadditive Cost-Sharing $\approx \ln(n)$

Implications and Future Work

The Cost of Stability serves as more than just a budget estimate; it acts as a formal measure of a game's inherent fragility. While this work focuses on Transferable Utility (TU) games—where value is a fungible resource like money—it opens the door for several extensions:

  • Fairness Constraints: Integrating the CoS with fairness concepts like the Shapley Value to ensure subsidies don't just create stability, but also equity.
  • Restricted Interaction: Examining how stability costs change when players can only form coalitions based on a social or communication network.
  • Non-Transferable Utility: Adapting these bounds for games where payoffs cannot be easily redistributed.

By quantifying the "price of cooperation," this research provides a vital tool for mechanism designers and policy makers tasked with maintaining harmony in competitive environments.

Summary updated

BibTeX
@article{bachrach2018bounds,
  author = {Yoram Bachrach and Edith Elkind and Enrico Malizia and Reshef Meir and Dmitrii V. Pasechnik and Jeffrey S. Rosenschein and Jörg Rothe and Michael Zuckerman},
  title = {{Bounds on the Cost of Stabilizing a Cooperative Game}},
  journal = {J. Artif. Intell. Res.},
  year = {2018},
  doi = {10.1613/jair.1.11270},
}
Figure