Chance-Constrained Correlated Equilibria for Robust Noncooperative Coordination
Authors: Jaehan Im, Ufuk Topcu, David Fridovich-Keil
Organizations: Department of Aerospace Engineering and Engineering Mechanics, The University of Texas at Austin · The Oden Institute for Computational Engineering and Sciences, The University of Texas at Austin
Correlated equilibria enable a coordinator to influence the self-interested agents by recommending actions that no player has an incentive to deviate from. However, the effectiveness of this mechanism relies on accurate knowledge of the agents' cost structures. When cost parameters are uncertain, the recommended actions may no longer be incentive compatible, allowing agents to benefit from deviating from them. We study a chance-constrained correlated equilibrium problem formulation that accounts for uncertainty in agents' costs and guarantees incentive compatibility with a prescribed confidence level. We derive sensitivity results that quantify how uncertainty in individual incentive constraints affects the expected coordination outcome. In particular, the analysis characterizes the value of information by relating the marginal benefit of reducing uncertainty to the dual sensitivities of the incentive constraints, providing guidance on which sources of uncertainty should be prioritized for information acquisition. The results further reveal that increasing the confidence level is not always beneficial and can introduce a tradeoff between robustness and system efficiency. Numerical experiments demonstrate this tradeoff: CC-CE reduces realized coordination cost by up to 35% at intermediate confidence levels, while the proposed information-gain metric consistently identifies effective uncertainty sources to reduce.
Figures & tables
Fig. 1: Illustration of the vertiport occupancy coordination scenario. Aircraft arrive through multiple approach queues, where each queue represents a self-interested agent that dispatches aircraft and determines which combination of vertiports to occupy or yield. A central coordinator broadcasts correlated recommendations that suggest vertiport usage while preserving agents’ autonomy. The interaction forms a noncooperative coordination game in which agents may follow or deviate from the recommended actions.
Fig. 2: Conceptual illustration of CC-CE feasible-set contraction in the decision space z∈Δ(X) for two constraints c∈{1,2} . Uncertainty contracts the nominal deviation constraints mc(z) by the weighted margin q(α)σi(c)πc , yielding the effective chance-constrained boundaries gc(z;α,σi(c)) . Constraint c=1 (blue) has a relatively small uncertainty contribution, while constraint c=2 (red) has a larger relative contribution from uncertainty-induced contraction. In this illustration, the optimal solution z∗ lies at the intersection where both constraints are active, with dual sensitivities λ1 and λ2 . This highlights that the value of reducing uncertainty depends jointly on the dual sensitivity, the uncertainty level, and recommendation likelihood.
Fig. 3: Effect of the confidence level α on coordination performance for the congestion parameter γ=2.0 . Increasing α contracts the CC-CE feasible region and increases nominal cost, but reduces the deviation rate toward zero. The realized cost exhibits a non-monotonic trend, reflecting the effect of reduced deviations and increased conservativeness. Note that costs are normalized by their corresponding Naive-CE values, so nominal and realized costs should not be directly compared.
Fig. 4: Information-acquisition performance across congestion regimes with α=0.9 . Each strategy selects five deviation constraints whose uncertainty margins are removed before resolving the CC-CE problem. Nominal costs are normalized by the baseline CC-CE cost for each γ . The proposed InfoGain strategy achieves the lowest normalized cost across all γ values, with larger gains in higher-congestion regimes.
Cooperative equilibria are fragile. When agents learn alongside each other rather than in a fixed environment, the process of learning destabilizes the cooperation they are trying to sustain: every gradient step an agent takes shifts the distribution of actions its partner will play, turning a cooperative partner into a source of stochastic noise precisely where the cooperation decision is most sensitive. We study how this co-learning noise propagates through the structure of coordination games, and find that the cooperative equilibrium, even when strongly Pareto-dominant, is exponentially unstable under standard risk-neutral learning, collapsing irreversibly once partner noise crosses the game's critical cooperation threshold. The natural response to apply distributional robustness to hedge against partner uncertainty makes things strictly worse: risk-averse return objectives penalize the high-variance cooperative action relative to defection, widening the instability region rather than shrinking it, a paradox that reveals a fundamental mismatch between the domains where robustness is applied and instability originates. We resolve this by showing that robustness should target the policy gradient update variance induced by partner uncertainty, not the return distribution. This distinction yields an algorithm whose gradient updates are modulated by an online measure of partner unpredictability, provably expanding the cooperation basin in symmetric coordination games. To unify stability, sample complexity, and welfare consequences of this approach, we introduce the Price of Paranoia as the structural dual of the Price of Anarchy. Together with a novel Cooperation Window, it precisely characterizes how much welfare learning algorithms can recover under partner noise, pinning down the optimal degree of robustness as a closed-form balance between equilibrium stability and sample efficiency.
Deep Kumar Ganguly, Chandradithya S Jonnalagadda, Pratham Chintamani +1
Technical University of Munich (TU Munich) · Brown University · Indian Institute of Technology Tirupati (IIT Tirupati)
Collaborative virtual queueing has been proposed as a mechanism to mitigate airport surface congestion while preserving airline autonomy over aircraft-level pushback decisions. A central coordinator can regulate aggregate pushback capacity but cannot directly control which specific aircraft are released, limiting its ability to steer system-level performance. We propose a noncooperative coordination mechanism for collaborative virtual queueing based on the correlated equilibrium concept, which enables the coordinator to provide incentive-compatible recommendations on aircraft-level pushback decisions without overriding airline autonomy. To account for uncertainty in airlines' internal cost assessments, we introduce chance constraints into the correlated equilibrium formulation. This formulation provides explicit probabilistic guarantees on incentive compatibility, allowing the coordinator to adjust the confidence level with which airlines are expected to follow the recommended actions. We further propose a scalable algorithm for computing chance-constrained correlated equilibria by exploiting a reduced-rank structure. Numerical experiments demonstrate that the proposed method scales to realistic traffic levels up to 210 eligible pushbacks per hour, reduces accumulated delay by up to approximately 8.9% compared to current first-come-first-served schemes, and reveals a trade-off between confidence level, deviation robustness, and achievable cost efficiency.
Jaehan Im, David Fridovich-Keil, Ufuk Topcu
Department of Aerospace Engineering, The University of Texas at Austin, Austin, Texas, USA
In many multi-agent applications, tasks yield rewards only when executed by a coalition meeting an unknown size threshold; otherwise, feedback is fully censored. This censorship creates an identifiability problem: agents cannot distinguish stochastic failure from insufficient coordination. We formalize this setting as the Threshold-Activated Cooperative Multi-Armed Bandit (TAC-MAB) and analyze it under both centralized and decentralized coordination. We show that a centralized algorithm (C-TAC) achieves cumulative regret O(log T), decomposed into a structural-search term that captures the cost of resolving feasibility under censored feedback and a statistical-monitoring term for value estimation. We then introduce D-TAC, a decentralized event-triggered protocol in which agents synchronize only when their structural beliefs change. Empirically, D-TAC achieves a 23x reduction in communication relative to the centralized baseline while preserving feasibility alignment under conservative belief fusion. These results characterize the coordination cost of learning under censored feedback and show that near-centralized communication efficiency is achievable without continuous synchronization.