Chance-Constrained Correlated Equilibria for Robust Noncooperative Coordination

Jaehan Im, Ufuk Topcu, David Fridovich-Keil · 2026

Read Chance-Constrained Correlated Equilibria for Robust Noncooperative Coordination by Jaehan Im, Ufuk Topcu, David Fridovich-Keil (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-2603-14141.txt.

Introduction

Im, Topcu, and Fridovich-Keil study correlated equilibria when agents' costs are known only with uncertainty. A coordinator suggests moves that no agent wants to defy, but wrong cost data can break that promise. Their chance-constrained version keeps the promise with a set confidence level. Sensitivity results price the value of cutting each source of uncertainty. Higher confidence is not always better, since it trades against system efficiency. In tests, the method cuts realized coordination costs by up to 35 percent.

Catalog record

CREATORJaehan Im, Ufuk Topcu, David Fridovich-Keil
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32887
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.14141

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Chance-Constrained Correlated Equilibria for Robust Noncooperative Coordination Jaehan Im, Ufuk Topcu, David Fridovich-Keil Abstract 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 that the proposed framework maintains coordination performance in uncertain environments and are consistent with the theoretical insights developed in the analysis. I Introduction Multi-agent systems often consist of self-interested agents whose decisions collectively determine system-level outcomes. In such environments, agents optimize their own objectives independently, which often leads to inefficient outcomes at equilibrium. As a result, designing coordination mechanisms that improve system-level performance without requiring cooperation remains a central challenge in decentralized decision-making systems. The correlated equilibrium concept [ 4 , 3 ] provides a coordination mechanism that can improve outcomes in noncooperative games. In this mechanism, a coordinator samples a joint action from a probability distribution and privately recommends an action to each player. If the distribution satisfies the correlated equilibrium conditions, no player can reduce its cost by unilaterally deviating from the recommendation. This incentive-compatibility property enables a coordinator to influence the behavior of self-interested agents while respecting their autonomy. The correlated equilibrium concept has been widely studied as a coordination tool in various multi-agent systems [ 16 , 20 , 13 , 15 , 12 ] , as illustrated in the air mobility coordination example in Figure 1 . However, in many practical applications, the coordinator may not have accurate knowledge of the players’ cost structures [ 7 , 12 , 1 , 2 ] . Under such uncertainty, the incentive compatibility conditions derived from the nominal cost model may no longer hold. Consequently, players may have incentives to deviate from the recommended actions, which undermines the effectiveness of the correlated equilibrium. 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. We study a chance-constrained correlated equilibrium (CC-CE) that explicitly accounts for uncertainty in agents’ costs. In CC-CE, the incentive compatibility conditions are required to hold with a user-specified confidence level. By incorporating uncertainty directly into the equilibrium constraints, CC-CE generates recommendations that remain incentive-compatible under cost uncertainty with quantifiable confidence. Our recent work has explored the use of CC-CE for coordination under uncertainty [ 15 ] , primarily focusing on empirical performance. However, the theoretical role of uncertainty in shaping coordination outcomes and incentive constraints remains largely unexplored. The contributions of this paper are threefold. First, we derive sensitivity results that quantify the value of information in individual incentive constraints and identify the constraints that act as information bottlenecks in coordination. Second, we analyze how the confidence level used in CC-CE affects system performance, revealing a tradeoff between robustness and efficiency. Third, we provide numerical experiments that illustrate how these theoretical insights explain the coordination behavior observed in practice. II Related work The correlated equilibrium concept [ 4 , 3 ] 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 , 20 , 13 , 12 , 15 ] . However, correlated equilibrium recommendations can be sensitive to uncertainty in the underlying payoff structure, such as estimation errors or stochastic perturbations [ 13 , 20 ] . Existing work addressing uncertainty in correlated equilibria largely follows two directions. One line of research studies Bayes correlated equilibria , which model payoff uncertainty through states and information structures [ 10 ] . In this framework, agents face incomplete information about payoff-relevant states, and incentive compatibility is defined in expectation with respect to players’ beliefs [ 10 , 9 , 19 ] . Another line of work incorporates uncertainty directly into agents’ cost functions through robust or distributionally robust formulations [ 5 , 14 , 18 , 17 ] . These approaches enforce worst-case guarantees over admissible uncertainty sets. While this framework provides strong robustness, it often leads to nonconvex optimization problems [ 18 , 17 ] and can become overly conservative when uncertainty reflects stochastic fluctuations around nominal costs. A different perspective appears in bounded-rationality models such as quantal response equilibria and their correlated variants [ 23 , 8 ] . These models introduce stochastic response rules and define equilibrium as a fixed point of noisy best responses. Here, randomness arises from the response mechanism rather than from explicit reliability constraints on deviation incentives that arise in the setting of correlated equilibrium problems with uncertain agent objectives. III Preliminaries III-A Correlated equilibrium Consider a finite strategic game with agent set N=\{1,\dots,n\} . Each agent i\in N chooses an action from a finite action set X_{i} . The joint action space is defined as \mathcal{X}:=\prod_{i\in N}X_{i} . Let z\in\Delta(\mathcal{X}) denote a joint probability distribution over action profiles. A correlated equilibrium can be interpreted as a coordination device that recommends actions to agents according to the distribution z . Upon receiving a recommendation, each agent decides whether to follow it or deviate to another action. Let J_{i}:\mathcal{X}\to\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}X_{j} denotes the joint actions of all agents except i . This quantity represents the cost change experienced by agent i if the recommended action x_{i} is replaced with a deviation x_{i}^{\prime} while other agents play x_{-i} . Given a recommendation x_{i} , the conditional expected deviation margin under z is \displaystyle\mathbb{E}_{x_{-i}\sim z(\cdot|x_{i})} \displaystyle[\Delta J_{i}(x_{i},x_{i}^{\prime},x_{-i})] (2) \displaystyle=\textstyle{\sum_{x_{-i}}z(x_{-i}|x_{i})\Delta J_{i}(x_{i},x_{i}^{\prime},x_{-i})}. This expectation measures whether the deviation is profitable on average when recommendations are drawn from the joint distribution. We recall the classical definition of correlated equilibrium [ 4 , 3 ] . Definition 1 (Correlated equilibrium) A distribution z\in\Delta(\mathcal{X}) is a correlated equilibrium 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, (3) for all suggestions x_{i} , and for all deviations x_{i}^{\prime}\neq x_{i} . Intuitively, once an agent receives a recommendation, no unilateral deviation yields a lower expected cost. Therefore following the recommendation is rational. III-B Coordination via correlated equilibrium The objective of coordination is to select a feasible equilibrium that leads to

Read the complete text