Introduction
In classical coalitional game theory, specifically games with Transferable Utilities (TU), the focus is typically on static snapshots: determining a "fair" distribution of a fixed reward (the "core") so that no group of players has an incentive to defect. However, real-world cooperative scenarios—such as supply chain logistics or network resource sharing—are inherently dynamic. The value generated by a coalition may fluctuate over time due to market volatility or shifting demand.
This paper addresses the challenge of maintaining stability in these dynamic environments. The authors model the game's value as a bounded mean ergodic process, meaning that while instantaneous values are noisy and unpredictable, they possess a stable long-term average. The goal is to design robust allocation rules that drive rewards toward the core despite this uncertainty.
Methodology: Flow Transformation and Stability
The core innovation of this research is the transformation of a game-theoretic problem into a robust control problem. This is achieved through several key steps:
- Flow Transformation: The coalitional game is represented as a hypergraph. In this model, edges represent players and vertices represent coalitions. Reward allocations are treated as "flows," while coalition values act as "demands" at the vertices.
- Excess Dynamics: A state variable termed "excess" is defined as the difference between the cumulative reward a coalition has received and the value it has generated. The objective of the central planner is to maintain non-negative excess for all coalitions.
- Lyapunov Stochastic Stability: To guarantee convergence, the authors employ Lyapunov functions. They demonstrate that under the proposed allocation rules, the system's deviation from the core behaves as a supermartingale, eventually decaying to zero with probability one.
The authors explore two primary information scenarios. In the Full Observation case, the planner knows the exact excess values and can target a specific point in the core. In the Partial Observation case, the planner only knows the sign of the excess (whether a coalition is currently overpaid or underpaid), using an "oracle-based" approach akin to cutting-plane methods in optimization.
Key Insights
The research highlights several critical properties of these dynamic systems:
- Coalitional Patience: The model assumes coalitions are "patient," willing to accept short-term underpayment if the allocation rule guarantees long-term fairness.
- Robustness through Ignorance: The rules do not require knowledge of the underlying probability distribution of the noise, only that it is bounded and has a stable mean.
- Geometric Convergence: By linking the problem to Blackwell’s Approachability Theory, the authors show that staying in the core is equivalent to a reward vector approaching a target set in multi-dimensional space.
Results and Validation
The theory was validated using numerical simulations of a 3-player coalitional game. By running 100,000 random selections over 5,000 allocation epochs, the authors demonstrated that error terms consistently vanish. Both full and partial information rules were proven to converge "with probability one" (almost surely). In the full-information case, the planner successfully targeted a specific "nominal" point in the core, ensuring a desired distribution of wealth.
Conclusion and Future Work
While the results are promising, the model currently relies on a centralized planner and a priori knowledge of the "nominal" average game. Future research could explore decentralized versions of these rules or incorporate learning phases to estimate the game's mean values in real-time. Additionally, addressing the exponential growth of coalitions ($2^n - 1$) as the number of players ($n$) increases remains a significant computational challenge.
Summary updated