Arbitration and Stability in Cooperative Games with Overlapping Coalitions

Yair Zick, Evangelos Markakis, Edith Elkind

Abstract

In traditional cooperative game theory, agents are typically restricted to joining a single coalition. Overlapping Coalition Formation (OCF) games relax this constraint, allowing agents to distribute their resources across multiple simultaneous projects. However, defining stability in OCF settings is complex, as it requires modeling how non-deviating players react when others alter their resource commitments. This paper introduces "arbitration functions" as a unified mathematical framework to model these reactions. By characterizing a new family of "arbitrated cores," the authors provide tools to determine the existence of stable resource distributions and introduce the "Sensitive Core" as a novel intermediate stability concept.

Introduction

In many real-world economic and social scenarios, agents do not commit exclusively to one group. Instead, they "multitask," contributing varying fractions of their total resources to different projects. This behavior is formally modeled by Overlapping Coalition Formation (OCF) games. While OCF games offer a more realistic representation of human and organizational cooperation, they introduce a significant challenge: defining the "core," or the set of outcomes where no group of players has an incentive to deviate.

In a standard game, a deviation is simple—players leave and form a new group. In an OCF game, a deviating group might change their resource allocation but still remain involved in shared projects with players who did not deviate. The stability of the system then depends on how these "non-deviators" react. Do they continue to pay the deviators for their remaining contributions, or do they withhold funds as a penalty? Previous research proposed isolated concepts—the conservative, refined, and optimistic cores—but lacked a general theory to handle arbitrary reactions such as legal fines or reputation damage. This paper fills that gap by introducing the Arbitration Function.

The Arbitration Framework

The authors propose the Arbitration Function as a mapping that dictates exactly what a deviating group can expect to receive from their remaining shared projects based on their actions and the current state of the game. This function acts as a mathematical "rule of law" for the game, determining the consequences of breaking an agreement.

Using this framework, the authors define a broad class of solution concepts called Arbitrated Cores. To analyze these cores, they employ Linear Programming (LP) duality. This approach allows them to translate the complex question of whether a stable outcome exists into "balancedness" conditions. This effectively extends the classic Bondareva-Shapley theorem—a cornerstone of traditional game theory—into the overlapping setting, providing a rigorous method for checking the non-emptiness of the core under various arbitration rules.

Key Insights and the Hierarchy of Stability

One of the paper's primary contributions is the identification of a Hierarchy of Stability. The authors demonstrate that different arbitration rules create a nested relationship between core concepts:

$$\text{Conservative} \subseteq \text{Sensitive} \subseteq \text{Refined} \subseteq \text{Optimistic}$$

This hierarchy reveals a counter-intuitive truth: a more "lenient" world, where deviators are allowed to keep more of their shared payoffs, actually makes it easier to find a stable outcome because the resulting core is larger. Conversely, in a "conservative" world where deviators are punished by losing all shared project income, the OCF structure adds little value; these games become mathematically equivalent to standard, non-overlapping games.

However, lenience comes with a "cost of stability." To prevent a player from deviating in a lenient environment, their payments must be more evenly distributed across all their projects. They cannot concentrate their earnings in a few high-value coalitions if they know they can still collect minor payoffs from others even after deviating.

The Sensitive Core

The paper introduces the Sensitive Core, a new intermediate stability concept. In this model, players are neither entirely vindictive nor entirely optimistic. Instead, they only withhold payments if they are personally affected by a deviation. This "middle ground" provides a more nuanced model for agents who prioritize their own project outcomes over general punitive measures, offering a more realistic representation of professional or contractual environments.

Results and Theoretical Advancements

The research yields several significant results:

  • Unified Characterization: The framework encompasses all previously known OCF core concepts, allowing researchers to create and test new arbitration rules within a single mathematical structure.
  • Non-emptiness Conditions: The authors proved a new sufficient condition for the conservative core to be non-empty. This condition is "strictly weaker" than previous state-of-the-art requirements, meaning it is easier to satisfy and applies to a broader range of games.
  • Scaling and Stability: The paper proves that if a game's value function is "homogeneous" (e.g., doubling all resource inputs at least doubles the profit), a stable outcome is guaranteed to exist under the refined arbitration rule.

Limitations and Future Directions

While this work significantly advances the theory of OCF games, it focuses on a static snapshot of cooperation. The authors identify several areas for future exploration:

  1. Additive Deviations: The current model primarily considers players withdrawing or reducing resources. Future work should address "additive" deviations where players attempt to join new projects.
  2. Beyond the Core: While group stability (the core) is vital, other concepts like the "nucleolus" (fairness) or "bargaining sets" (negotiation) remain largely unexplored in the context of arbitration functions.
  3. Dynamic Coalitions: Modeling how coalitions and arbitration reactions evolve over time would move the theory closer to the complexities of real-world dynamic markets.

By providing a unified language for reactions to deviation, this paper moves OCF games from a collection of isolated examples toward a comprehensive theory of flexible, overlapping cooperation.

Summary updated

Abstract

Overlapping Coalition Formation (OCF) games, introduced by Chalkiadakis, Elkind, Markakis, Polukarov and Jennings in 2010, are cooperative games where players can simultaneously participate in several coalitions. Capturing the notion of stability in OCF games is a difficult task:deviating players may continue to contribute resources to joint projects with non-deviators, and the crucial question is what payoffs the deviators expect to receive from such projects. Chalkiadakis et al. introduce three stability concepts for OCF games---the conservative core, the refined core, and the optimistic core---that are based on different answers to this question. In this paper, we propose a unified framework for the study of stability in the OCF setting, which encompasses the stability concepts considered by Chalkiadakis et al. as well as a wide variety of alternative stability concepts. Our approach is based on the notion of arbitration functions, which determine the payoff obtained by the deviators, given their deviation and the current allocation of resources. We provide a characterization of stable outcomes under arbitration. We then conduct an in-depth study of four types of arbitration functions, which correspond to four notions of the core; these include the three notions of the core considered by Chalkiadakis et al. Our results complement those of Chalkiadakis et al. and answer questions left open by their work. In particular, we show that OCF games with the conservative arbitration function are essentially equivalent to non-OCF games, by relating the conservative core of an OCF game to the core of a non-overlapping cooperative game, and use this result to obtain a strictly weaker sufficient condition for conservative core non-emptiness than the one given by Chalkiadakis et al.
BibTeX
@article{zick2014arbitration,
  author = {Yair Zick and Evangelos Markakis and Edith Elkind},
  title = {{Arbitration and Stability in Cooperative Games with Overlapping Coalitions}},
  journal = {J. Artif. Intell. Res.},
  year = {2014},
  doi = {10.1613/jair.4237},
}
Figure