Dynamics of Profit-Sharing Games

John Augustine, Ning Chen, Edith Elkind, Angelo Fanelli, Nick Gravin, Dmitry ShiryaevInternet Math 2015 · DOI

Introduction

In multiagent systems, the formation of coalitions is a fundamental process for achieving complex goals. While traditional cooperative game theory provides a robust framework for identifying stable team structures, it often lacks a dynamic perspective. Specifically, it rarely accounts for the process by which agents—who may be selfish and myopic—actually converge to these stable states. This research addresses the gap between static equilibrium theory and the dynamic reality of agents making local, short-sighted decisions to maximize their immediate payoffs.

Modeling Selfish Cooperation

The core of this study lies in analyzing how agents partition themselves into teams when profits are distributed based on individual contributions. The researchers focus on submodular profit functions, which characterize environments with "diminishing returns." In such settings, an agent's marginal contribution is greater when joining a smaller group than a larger one.

The paper evaluates three distinct profit-sharing mechanisms:

  1. Fair-Value Games: Payoffs are determined by an agent's current marginal utility to their team.
  2. Labor Union Games: Payoffs incorporate the history of the team, protecting "seniority." An agent's payoff is based on their contribution at the time of joining and is guaranteed not to decrease as long as they remain on that team.
  3. Shapley Games: A hybrid model where payoffs represent the expected marginal contribution across all possible arrival sequences (the classic Shapley value).

Theoretical Framework: Potential and Stability

To analyze these dynamics, the authors introduce the concept of perfect $\beta$-nice games. This framework allows for a unified analysis of convergence and efficiency across different game types. A critical finding is that all three models are "potential games." This mathematical property ensures that a Nash equilibrium—a state where no individual agent can improve their payoff by switching teams—always exists. Furthermore, it guarantees that any sequence of selfish moves will eventually lead to such an equilibrium, preventing the system from descending into infinite cycles of team-switching.

Efficiency and Convergence Results

The research provides strong theoretical guarantees regarding the performance of these decentralized systems:

  • Price of Anarchy (PoA) $\le 2$: Even in the worst-case stable state reached through selfish behavior, the total profit generated is at least 50% of the theoretical social optimum.
  • Price of Stability (PoS) = 1: For Fair-Value and Labor Union games, the best possible stable state is identical to the socially optimal configuration.
  • Rapid Convergence: The system reaches near-optimal states (within a factor of 2 of the optimum) in a polynomial number of steps. Notably, in Labor Union games starting from an empty state, a stable Nash equilibrium is reached in exactly $n$ moves, where $n$ is the number of players.

Conclusion and Future Directions

This work demonstrates that central planning is not a prerequisite for efficiency in multiagent systems. Simple, myopic dynamics driven by individual incentives can lead to highly productive and stable outcomes, provided the underlying profit functions exhibit submodularity. The property of diminishing returns acts as a natural stabilizer, preventing any single team from becoming an unstoppable "black hole" for players and maintaining an efficient distribution of talent.

Future research may explore "succinct" representations of these games to handle the exponential data requirements of complex real-world scenarios. Additionally, investigating environments with "increasing returns" (supermodular functions) remains a significant open challenge, as the stabilizing effect of diminishing returns would no longer be present.

Summary updated

BibTeX
@article{augustine2015dynamics,
  author = {John Augustine and Ning Chen and Edith Elkind and Angelo Fanelli and Nick Gravin and Dmitry Shiryaev},
  title = {{Dynamics of Profit-Sharing Games}},
  journal = {Internet Math.},
  year = {2015},
  doi = {10.1080/15427951.2013.830164},
}
Figure