跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv: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
arXiv ↗PDF ↗

摘要

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 ε\varepsilon-approximate coarse correlated equilibria, constant approximation is possible with support O(log⁡N/ε2)O(\log N/\varepsilon^2) in N×NN\times N games. For correlated equilibria, the best known upper bound was O(log⁡2N/ε4)O(\log^2 N/\varepsilon^4) [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 1≤k≤N1/21\leq k\leq N^{1/2} the worst-case correlated-equilibrium gap achievable by a distribution supported on at most kk pure profiles is Θ(min⁡{1,log⁡Nk1/4}), Θ\left( \min\left\{1,\frac{\sqrt{\log N}}{k^{1/4}}\right\} \right), which implies a Θ(log⁡2N/ε4)Θ(\log^2 N/\varepsilon^4) worst-case support bound. The proof builds on a probabilistic-method construction based on random sign matrices.

作者备注:Innovations in Theoretical Computer Science (ITCS), 2027

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 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 ε\varepsilon-approximate coarse correlated equilibria, constant approximation is possible with support O(log⁡N/ε2)O(\log N/\varepsilon^2) in N×NN\times N games. For correlated equilibria, the best known upper bound was O(log⁡2N/ε4)O(\log^2 N/\varepsilon^4) [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 1≤k≤N1/21\leq k\leq N^{1/2} the worst-case correlated-equilibrium gap achievable by a distribution supported on at most kk pure profiles is Θ(min⁡{1,log⁡Nk1/4}), Θ\left( \min\left\{1,\frac{\sqrt{\log N}}{k^{1/4}}\right\} \right), which implies a Θ(log⁡2N/ε4)Θ(\log^2 N/\varepsilon^4) worst-case support bound. The proof builds on a probabilistic-method construction based on random sign matrices.

查看此版本解读 →查看此版本原文 ↗