Correlated equilibrium implementation: Navigating toward social optima with learning dynamics Conference: ; ;

Soumen Banerjee and Yi-Chun Chen and Yifei Sun · 2025

Read Correlated equilibrium implementation: Navigating toward social optima with learning dynamics Conference: ; ; by Soumen Banerjee and Yi-Chun Chen and Yifei Sun (2025) 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-2506-03528.txt.

Introduction

Soumen Banerjee, Yi-Chun Chen, and Yifei Sun designed a game mechanism in 2025 that steers self interested players to a social planner's chosen outcome, even when the players are poor strategists. Classic mechanism design assumes players reason their way to a sharp equilibrium, which real people often cannot do.

Their finite mechanism makes the planner's target the unique correlated outcome of the game. A classic result then says players who simply adjust to cut their regrets will land there anyway. In trade simulations, regret driven players converged to the wanted outcomes without knowing others' tastes or the game's structure. The mechanism avoids the giant number games older designs relied on.

Catalog record

CREATORSoumen Banerjee and Yi-Chun Chen and Yifei Sun
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE65 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-03528

Browse the full library · About the Tower of Babel

Full text

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

Correlated equilibrium implementation: Navigating toward social optima with learning dynamics Conference: ; ; Soumen Banerjee and Yi-Chun Chen and Yifei Sun Abstract . Implementation theory has made significant advances in characterizing which social choice functions can be implemented in Nash equilibrium, but these results typically assume sophisticated strategic reasoning by agents. However, evidence exists to show that agents frequently cannot perform such reasoning. In this paper, we present a finite mechanism which fully implements Maskin-monotonic social choice functions as the outcome of the unique correlated equilibrium of the induced game. Due to the results in ( Hart and Mas-Colell 2000 ) , this yields that even when agents use a simple adaptive heuristic like regret minimization rather than computing equilibrium strategies, the designer can expect to implement the SCF correctly. We demonstrate the mechanism’s effectiveness through simulations in a bilateral trade environment, where agents using regret matching converge to the desired outcomes despite having no knowledge of others’ preferences or the equilibrium structure. The mechanism does not use integer games or modulo games. 1. Introduction Implementation theory has made significant strides in characterizing implementable social choice functions. ( Maskin 1999 ) establishes that any social choice function satisfying monotonicity can be implemented in Nash equilibrium. However, this and many subsequent results rely on agents being able to compute and play Nash equilibria (and indirectly, best responses) - an assumption that has faced increasing scrutiny from both theoretical and empirical perspectives (see for instance ( Goeree and Louis 2021 ) , ( Li 2017 ) ). This has led to a growing interest in implementation under more realistic behavioral assumptions. A particularly promising direction comes from the demonstration in ( Hart and Mas-Colell 2000 ) that simple regret minimization learning leads to correlated equilibria rather than Nash equilibria. 1 1 1 The Pluribus robot designed by researchers at Carnegie Mellon university, which beat the best professional human players at no-limit Texas hold ’em poker also uses a variation of regret minimization, suggesting that the algorithm is not just simple, but also capable. In addition, other adaptive procedures such as calibrated learning (due to ( Foster and Vohra 1997 ) ) and universal conditional consistency (due to ( Fudenberg and Levine 1999 ) ) have also been shown to approach correlated equilibria. 2 2 2 ( Stoltz and Lugosi 2007 ) demonstrate that regret minimization yields correlated equilibria when the strategy sets are convex and compact. These results suggests that correlated equilibrium may be a more natural solution concept for implementation problems, as it emerges from straightforward adaptive behavior rather than requiring sophisticated strategic reasoning. 3 3 3 ( Halpern and Leung 2016 ) and ( Srivastava 2019 ) provide empirical evidence in support of the claim that decision makers perform regret minimization. While we know which social choice functions can be implemented in Nash equilibrium, we lack a characterization of SCFs which can be implemented in correlated equilibria and implementing mechanisms that explicitly target implementation in correlated equilibria. Such mechanisms would be especially valuable as they could achieve desired social outcomes under simple learning dynamics rather than requiring agents to compute equilibria. This paper provides a step forward in resolving this tension between implementation theory and behavioral realism. We show that Maskin-monotonicity characterizes SCFs which are implementable in correlated equilibrium and provide a mechanism which can fully implement such SCFs as the outcome obtained in a unique correlated equilibrium. While there is a voluminous literature on full implementation, our paper offers the first mechanism that implements in adaptive heuristics per ( Hart and Mas-Colell 2000 ) . Previous papers such as ( Cabrales 1999 ) appeal to both integer games and adaptive dynamics where every best response must be played with positive probability, while ( Cabrales and Serrano 2011 ) requires that the agents switch with positive probability to any better or best response. In addition, we demonstrate in a simulation that the mechanism achieves the desirable social choice outcome in a canonical bilateral trade environment when the buyer and seller play the induced game using regret minimization heuristics. Finally, the mechanism does not rely on integer or modulo games, making it a reasonable candidate for practical deployment. 4 4 4 See ( Jackson 1992 ) and ( Moore 1992 ) for a critique of these tail-chasing devices. 2. Mechanism and Proof of Implementation 2.1. Environment Consider a finite set of agents \mathcal{I}=\{1,2,...,I\} with I\geq 2 ; a finite set of possible states \Theta ; and a set of pure alternatives A . We consider an environment with lotteries and transfers. Specifically, we work with the space of allocations/outcomes X\equiv\Delta\left(A\right)\times\mathbb{R}^{I} where \Delta(A) denotes the set of lotteries on A that have a countable support, and \mathbb{R}^{I} denotes the set of transfers to the agents. Each state \theta\in\Theta induces a type \theta_{i}\in\Theta_{i} for each agent i\in\mathcal{I} . Assume that \Theta has no redundancy, i.e., whenever \theta\neq\theta^{\prime} , we must have \theta_{i}\neq\theta_{i}^{\prime} for some agent i . Hence, we can identify a state \theta with its induced type profile \left(\theta_{i}\right)_{i\in\mathcal{I}} and \Theta with a subset of \times_{i=1}^{I}\Theta_{i} . Moreover, we say that a type profile \left(\theta_{i}\right)_{i\in\mathcal{I}} identifies a state \theta^{\prime} if \theta_{i}=\theta_{i}^{\prime} for every i\in\mathcal{I} . Each type \theta_{i}\in\Theta_{i} induces a utility function u_{i}\left(\cdot,\theta_{i}\right):X\rightarrow\mathbb{R} which is quasilinear in transfers and has a bounded expected utility representation on \Delta\left(A\right) . That is, for each x=\left(\ell,\left(t_{i}\right)_{i\in\mathcal{I}}\right)\in X , we have u_{i}\left(x,\theta_{i}\right)=v_{i}(\ell,\theta_{i})+t_{i} for some bounded expected utility function v_{i}(\cdot,\theta_{i}) over \Delta\left(A\right) . That is, we work with an environment with transferable utility (TU) restriction on agents’ preferences which is absent in ( Maskin 1999 ) . As in ( Abreu and Matsushima 1992 ) , we will take for granted that distinct elements of \Theta_{i} induce different preference orderings over \Delta\left(A\right), and also that a player is never indifferent over all elements of A. We focus on a complete information environment in which the state \theta is common knowledge among the agents but unknown to a mechanism designer. Thanks to the complete-information assumption, it is indeed without loss of generality to assume that agents’ values are private. The designer’s objective is specified by a social choice function f:\Theta\rightarrow X , namely, if the state is \theta , the designer would like to implement the social outcome f\left(\theta\right) . We allow an SCF to be defined as a mapping from \Theta to X only so as to keep its consistency with the range of the outcome function used in the implementing mechanism. We can define f:\Theta\rightarrow\Delta\left(A\right) as a special case of SCFs, as long as the designer is still allowed to impose off-the-equilibrium transfers in the implementing mechanism. 2.2. Implementation We denote a mechanism by \mathcal{M}=\left((M_{i},\tau_{i}\right)_{i\in\mathcal{I}},g) where M_{i} is a nonempty set of messages available to agent i ; g:M\rightarrow X (where M\equiv\times_{i=1}^{I}M_{i} ) is the outcome function ; and \tau_{i}:M\rightarrow\mathbb{R} is the transfer rule which specifies the payment to agent i . At each state \theta\in\Theta , the environment and the mechanism together constitute a game with complete information which we denote by \Gamma(\mathcal{M},\theta) . Let \sigma\in\Delta(M) be a probability distribution over M . A strategy profile \sigma is said to be a correlated equilibrium of the game \Gamma(\mathcal{M},\theta) if, for all agents i\in\mathcal{I} and all

Read the complete text