Lyapunov stochastic stability and control of robust dynamic coalitional\n games with transferable utilities

Dario Bauso, Puduru Viswanadha Reddy, Tamer Başar

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:

  1. 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.
  2. 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.
  3. 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

Abstract

This paper considers a dynamic game with transferable utilities (TU), where\nthe characteristic function is a continuous-time bounded mean ergodic process.\nA central planner interacts continuously over time with the players by choosing\nthe instantaneous allocations subject to budget constraints. Before the game\nstarts, the central planner knows the nature of the process (bounded mean\nergodic), the bounded set from which the coalitions' values are sampled, and\nthe long run average coalitions' values. On the other hand, he has no knowledge\nof the underlying probability function generating the coalitions' values. Our\ngoal is to find allocation rules that use a measure of the extra reward that a\ncoalition has received up to the current time by re-distributing the budget\namong the players. The objective is two-fold: i) guaranteeing convergence of\nthe average allocations to the core (or a specific point in the core) of the\naverage game, ii) driving the coalitions' excesses to an a priori given cone.\nThe resulting allocation rules are robust as they guarantee the aforementioned\nconvergence properties despite the uncertain and time-varying nature of the\ncoaltions' values. We highlight three main contributions. First, we design an\nallocation rule based on full observation of the extra reward so that the\naverage allocation approaches a specific point in the core of the average game,\nwhile the coalitions' excesses converge to an a priori given direction. Second,\nwe design a new allocation rule based on partial observation on the extra\nreward so that the average allocation converges to the core of the average\ngame, while the coalitions' excesses converge to an a priori given cone. And\nthird, we establish connections to approachability theory and attainability\ntheory.\n
BibTeX
@misc{bauso2011lyapunov,
  author = {Dario Bauso and Puduru Viswanadha Reddy and Tamer Başar},
  title = {{Lyapunov stochastic stability and control of robust dynamic coalitional\textbackslash\{\}n games with transferable utilities}},
  year = {2011},
  eprint = {1106.1933},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1106.1933},
}
Figure