相关均衡的查询复杂度
本研究探讨匿名博弈的均衡计算，通过先进行具有适应性的问题到博弈的支付函数计算的算法处理。讨论研究的主题是查询复杂度，即计算精确或近似纳什均衡所需的查询数量。研究发现不能通过查询有效算法找到精确均衡，但可以通过假设效用函数的进一步对称性或关注近似均衡来获得更好的查询复杂度界限。研究涉及的匿名游戏的子类是匿名博弈的相似研究，结论为使用随机算法可以在相应的复杂度下查询到一个近似的纳什均衡，此外也证明了一定数量次的查询才能找到任何 ϵ- 好支持纳什平衡，即使采用随机算法也需要 Ω(n log n) 的复杂度。
Dec, 2014
本文研究了基于局部知识来学习研究各种类型的博弈及其均衡求解的复杂度，探讨了计算学习模型和对于各种博弈的查询复杂度，着重研究了对称网络拥塞博弈，并通过仅查询少量的纯策略来学习成本函数。
Feb, 2013
我们研究了不完全信息博弈中分布式学习近似相关均衡的迭代复杂度，我们证明了在广义形式博弈中，假设 PPAD 不属于 TIME (n^polylog (n))，任何多项式时间学习算法至少需要 2^log_2^{1-o (1)}(|I|) 次迭代才能收敛于 ε- 近似相关均衡集合，同时我们给出了无耦合动态的方法，在对数次迭代中达到 ε- 近似相关均衡的贝叶斯博弈，无需考虑类型的数量。
Jun, 2024
我们研究了多人广义和 Markov 游戏中计算相关均衡的政策优化算法，以往结果在收敛速率上达到了 $O (T^{-1/2})$ 的相关均衡和 $O (T^{-3/4})$ 的粗糙相关均衡的加速收敛速率，本文提出了一种通过组合平滑值更新和乐观正则化领导者算法与对数障碍正则器的两个主要因素构建的解耦政策优化算法，达到了计算相关均衡的几乎最优 $ ilde {O}(T^{-1})$ 的收敛速率。
Jan, 2024
本文研究多人随机博弈中同时学习的问题，通过生成算法获得相关均衡，包括 extensive-form correlated equilibrium 和普通 coarse correlated equilbrium，并提供了一些能够多项式时间内解决的特殊情况。
Oct, 2022
本文研究在任何 n 个玩家和 m 个动作的博弈中，通过对混合策略均衡进行少量取样，可以得到近似均衡。本文研究了三种不同类型的均衡，并且得出了近似均衡的上下限，这些结果表明，我们可以使用少量的样本来测试玩家是否根据近似均衡进行游戏，即使是在大型博弈中。此外，本文的研究结果大幅改进了先前对于大型博弈中近似均衡支持集大小的估计，对于所有三种均衡，我们证明了支持集大小为 polylogarithmic，而以前的最佳上限是多项式的。
Oct, 2013
本文提出了一种新的算法方法来解决优化一些目标（如社会福利）的相关均衡问题，并且给出了一种适用于所有紧凑表示的足够条件，同时利用该算法方法将最优 CE 问题转化为调整偏差的社会福利问题，这个框架可以识别出新的类别的博弈，其中包括基于树图的图形多项式博弈。同样使用类似的方法，我们导出了一种足够的条件来处理最优粗糙相关均衡问题，并使用其证明了单例拥塞博弈的可跟踪性。
Sep, 2011