Scalable Coordination with Chance-Constrained Correlated Equilibria via Reduced-Rank Structure
Jaehan Im, David Fridovich-Keil, Ufuk Topcu · 2026
Read Scalable Coordination with Chance-Constrained Correlated Equilibria via Reduced-Rank Structure by Jaehan Im, David Fridovich-Keil, Ufuk Topcu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-00456.txt.
Introduction
Im and colleagues tackle coordination of rival agents facing uncertain costs. A chance-constrained correlated equilibrium lets such agents coordinate through chance-based incentive guarantees. But computing one directly gets out of hand fast, since joint actions multiply exponentially with scale. The authors prove these equilibria equal mixtures drawn from a limited pool of chance-constrained pure Nash equilibria. That turns an intractable program into a tractable one. In large multi-airline tests, their method slashes compute time and beats current practice on system delay costs.
Catalog record
| CREATOR | Jaehan Im, David Fridovich-Keil, Ufuk Topcu |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28742 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.00456
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Scalable Coordination with Chance-Constrained Correlated Equilibria via Reduced-Rank Structure Jaehan Im, David Fridovich-Keil, Ufuk Topcu Abstract Chance-constrained correlated equilibrium enables coordination of noncooperative agents under cost uncertainty through probabilistic incentive-compatibility guarantees. However, computing such equilibria becomes intractable in large-scale systems due to the exponential growth of the joint action space. We develop an approximation method for computing chance-constrained correlated equilibria by showing that these equilibria admit a representation as convex combinations of a finite set of chance-constrained pure Nash equilibria, enabling tractable computation without solving the full correlated equilibrium program. Numerical experiments on large-scale multi-airline coordination scenarios demonstrate substantial reductions in computation time while achieving lower system delay costs compared to current operational practice. Under cost uncertainty, the proposed method consistently achieves lower deviation rate compared to the full formulation while achieving comparable coordination performance. I Introduction Large-scale multi-agent systems often consist of self-interested agents whose decisions collectively determine system-level outcomes. Designing coordination mechanisms that improve system performance without centralized enforcement remains a fundamental challenge. Correlated equilibrium [ 2 , 1 ] provides a principled framework for such coordination by enabling a coordinator to recommend actions that agents have no incentive to deviate from. In many practical settings, however, agents’ cost structures are uncertain due to modeling errors, operational variability, or private information [ 10 , 11 , 14 , 15 ] . This undermines the incentive-compatibility guarantees of nominal correlated equilibrium, as agents may benefit from deviating when realized costs differ from their nominal estimates. To address this issue, recent work has introduced the chance-constrained correlated equilibrium (CC-CE) by requiring incentive compatibility to hold with a prescribed confidence level, providing robustness against cost uncertainty [ 15 , 14 ] . Despite its modeling advantages, computing CC-CE remains challenging in large-scale systems. The joint action space grows exponentially with the number of agents and their action sets, rendering direct computation intractable. Reduced-rank correlated equilibrium (RRCE) has been proposed to mitigate this issue by representing equilibria as convex combinations of a finite set of pure Nash equilibria [ 16 ] . However, extending this approach to the chance-constrained setting is nontrivial, as the presence of probabilistic incentive constraints alters the structure of the feasible set. We show that CC-CE admits a reduced-rank representation that enables scalable computation. Specifically, we approximate the CC-CE feasible set using convex combinations of a finite set of chance-constrained pure Nash equilibria, thereby avoiding explicit enumeration of the full joint action space. We further characterize the class of equilibria required for this representation and develop an algorithm that scales to large problem instances. Fig. 1 : Illustrative example of a coordination scenario inspired by airport virtual queueing systems. A central coordinator recommends which aircraft to release \raisebox{-.9pt}{1}⃝ but does not enforce aircraft-level decisions directly. Released aircraft contribute to shared congestion c(t) ( \raisebox{-.9pt}{2}⃝ – \raisebox{-.9pt}{3}⃝ ) and to queueing delay \delta_{f}(t) \raisebox{-.9pt}{4}⃝ , while departures are governed by runway service rates \mu_{r} \raisebox{-.9pt}{5}⃝ . Airlines retain autonomy over whether to follow the recommendations \raisebox{-.9pt}{6}⃝ , creating a noncooperative coordination problem. We demonstrate the effectiveness of the proposed approach on coordination problems motivated by virtual queueing systems, where large-scale coordination under uncertainty is required. Numerical results show that the reduced-rank method achieves substantial computational gains while maintaining comparable coordination performance. The contributions of this paper are threefold. First, we establish a reduced-rank representation of chance-constrained correlated equilibria via convex combinations of chance-constrained pure Nash equilibria, enabling scalable computation. Second, we develop a scalable algorithm that avoids enumeration of the full joint action space. Third, we validate the approach on large-scale coordination instances inspired by virtual queueing systems. II Related Work The correlated equilibrium concept [ 2 , 1 ] has been widely studied as a mechanism for coordinating noncooperative agents, as it allows a coordinator to recommend actions while preserving each agent’s autonomy [ 16 , 21 , 10 , 9 , 14 ] . However, correlated equilibrium recommendations can be sensitive to uncertainty in the underlying payoff structure, such as estimation errors or stochastic perturbations [ 10 , 11 ] . Existing approaches handling uncertainty in correlated equilibria include Bayes correlated equilibria [ 7 ] , robust and distributionally robust formulations [ 3 , 13 , 19 , 18 ] , and bounded-rationality models such as quantal response equilibria [ 23 , 6 ] . While these approaches offer complementary perspectives, none provides explicit probabilistic guarantees on incentive compatibility under stochastic cost perturbations. Recent work has introduced chance-constrained formulations of correlated equilibria to address this gap [ 15 , 14 ] . Computing correlated equilibria is known to be intractable as the joint action space grows exponentially with the number of agents [ 16 ] . Prior work has addressed this through learning dynamics [ 12 , 20 ] and approximation methods [ 17 ] , though these do not allow targeted equilibrium selection. The reduced-rank correlated equilibrium framework [ 16 ] approximates the correlated equilibrium set via convex combinations of Nash equilibria, enabling tractable computation while preserving coordination quality. However, whether such reduced-rank representations extend to uncertainty-aware equilibrium formulations remains unclear. III Preliminaries We introduce the correlated equilibrium concept and its use as a coordination mechanism. These form the foundation for the chance-constrained extension developed in Section IV . Consider a finite strategic game with agent set \mathcal{N}=\{1,\ldots,n\} . Each agent i\in\mathcal{N} selects an action from a finite set \mathcal{X}_{i} , and the joint action space is \mathcal{X}:=\prod_{i\in\mathcal{N}}\mathcal{X}_{i} . Let J_{i}:\mathcal{X}\rightarrow\mathbb{R} denote the cost of agent i . We define the deviation cost for agent i as \Delta J_{i}(x_{i},x_{i}^{\prime},x_{-i}):=J_{i}(x_{i},x_{-i})-J_{i}(x_{i}^{\prime},x_{-i}), (1) where x_{-i}\in\prod_{j\neq i}\mathcal{X}_{j} denotes the actions of all agents except i . This quantity captures the cost change that agent i would experience by deviating from a recommended action x_{i} to an alternative x_{i}^{\prime} , given that other agents play x_{-i} . Definition 1 (Correlated equilibrium [ 2 , 1 ] ) A distribution z\in\Delta(\mathcal{X}) is a correlated equilibrium (CE) if \mathbb{E}_{x_{-i}\sim z(\cdot|x_{i})}[\Delta J_{i}(x_{i},x_{i}^{\prime},x_{-i})]\leq 0,\quad\forall i,\ \forall x_{i},\ \forall x_{i}^{\prime}\neq x_{i}. (2) In a CE, a coordinator samples a joint action from z and privately recommends each agent its corresponding component. Since each CE constraint in Equation 2 is linear in z and \Delta(\mathcal{X}) is convex, the CE set forms a convex polytope. Intuitively, once an agent receives a recommendation, following it is individually rational as no unilateral deviation reduces its expected cost. III-A Coordination via correlated equilibrium The goal of coordination is to select, among all feasible CEs, one that leads to a desirable system-level outcome. Let J_{\mathrm{sys}}:\Delta(\mathcal{X})\rightarrow\mathbb{R} denote a system-level cost. The coordination task reduces to the following equilibrium selection problem: \min_{z\in\Delta(\mathcal{X})}\ J_{\mathrm{sys}}(z)\quad\text{s.t. }z\text{ satisfies~\lx@cref{creftypecap\lx@tilde refnum}{eq:ce}}. (3) Since both the objective and constraints are linear in z , Equation 3 is a linear program. This formulation enables the coordinator to steer self-interested agents toward system-efficient outcomes while preserving their autonomy. Example 1 (Coordination via correlated equilibrium) Consider a scenario where two drivers approach an intersection and choose either Go (G) or Stop (S). Their costs are given by \begin{array}[]{c|cc}&G&S\\ \hline\cr G&(5,5)&(-1,1)\\ S&(1,-1)&(1,1)\end{array} (4) where rows correspond to Driver 1 and columns to Driver 2. If both go, they incur a large penalty (5,5). If both stop, both incur a mild delay (1,1). If exactly