A Coupled Optimization Framework for Correlated Equilibria in Normal-Form Games

In competitive multi-player interactions, simultaneous optimality is a key requirement for establishing strategic equilibria. This property is explicit when the game-theoretic equilibrium is the simultaneously optimal solution of coupled optimization problems. However, no such optimization problems exist for the correlated equilibrium, a strategic equilibrium where the players can correlate their actions. We address the lack of a coupled optimization framework for the correlated equilibrium by introducing an unnormalized game-an extension of normal-form games in which the player strategies are lifted to unnormalized measures over the joint actions. We show that the set of fully mixed generalized Nash equilibria of this unnormalized game is a subset of the correlated equilibria of the normal-form game. Furthermore, we introduce an entropy regularization to the unnormalized game and prove that the entropy-regularized generalized Nash equilibrium is a sub-optimal correlated equilibrium where the degree of sub-optimality depends on the magnitude of regularization. We derive a closed form solution for an entropy-regularized generalized Nash equilibrium and verify via simulation its computational complexity.