← 研踪 PaperTrailarXiv:2611.20362 · v1
Settling the Support Complexity of Correlated Equilibria
首次提交 2026-11-16 08:41
版本更新 2026-11-16 08:41
雷达观测 2026-11-17 17:12
摘要
We study the support complexity of approximate correlated equilibria (CE) in two-player games, that is, the minimum number of pure action profiles that must be assigned positive probability to approximate a correlated equilibrium of a two-player matrix game. For -approximate coarse correlated equilibria, constant approximation is possible with support in games. For correlated equilibria, the best known upper bound was [Babichenko et al., 2014, 2017], but whether this bound was tight remained open. We establish a matching lower bound, resolving the open question of Ko and Schvartzman [2017]. Specifically, we show that, already for two-player zero-sum games, for every the worst-case correlated-equilibrium gap achievable by a distribution supported on at most pure profiles is which implies a worst-case support bound. The proof builds on a probabilistic-method construction based on random sign matrices.
作者备注:Innovations in Theoretical Computer Science (ITCS), 2027
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-16 08:41 · 最新观测版本
Settling the Support Complexity of Correlated Equilibria
We study the support complexity of approximate correlated equilibria (CE) in two-player games, that is, the minimum number of pure action profiles that must be assigned positive probability to approximate a correlated equilibrium of a two-player matrix game. For -approximate coarse correlated equilibria, constant approximation is possible with support in games. For correlated equilibria, the best known upper bound was [Babichenko et al., 2014, 2017], but whether this bound was tight remained open. We establish a matching lower bound, resolving the open question of Ko and Schvartzman [2017]. Specifically, we show that, already for two-player zero-sum games, for every the worst-case correlated-equilibrium gap achievable by a distribution supported on at most pure profiles is which implies a worst-case support bound. The proof builds on a probabilistic-method construction based on random sign matrices.
查看此版本解读 →查看此版本原文 ↗