本研究探讨匿名博弈的均衡计算，通过先进行具有适应性的问题到博弈的支付函数计算的算法处理。讨论研究的主题是查询复杂度，即计算精确或近似纳什均衡所需的查询数量。研究发现不能通过查询有效算法找到精确均衡，但可以通过假设效用函数的进一步对称性或关注近似均衡来获得更好的查询复杂度界限。研究涉及的匿名游戏的子类是匿名博弈的相似研究，结论为使用随机算法可以在相应的复杂度下查询到一个近似的纳什均衡，此外也证明了一定数量次的查询才能找到任何 ϵ- 好支持纳什平衡，即使采用随机算法也需要 Ω(n log n) 的复杂度。

Dec, 2014

在大量玩家的二元行动博弈中，查询复杂度与 ε- 支持纳什均衡的关系是指数级的，并导致自适应动态收敛到近似纳什均衡的速度指数级下降。

Jun, 2013

本文介绍一种新的算法，该算法可以在多项式时间内计算任意常数 δ 大于 0 的（1/3+δ）- 纳什均衡策略。我们通过扩展策略集来解决旧的算法中的瓶颈情况，超过了过去 15 年来由 Tsaknakis 和 Spirakis 提出的算法，得到的最佳近似保证为（0.3393+δ）。

Apr, 2022

本文研究了基于局部知识来学习研究各种类型的博弈及其均衡求解的复杂度，探讨了计算学习模型和对于各种博弈的查询复杂度，着重研究了对称网络拥塞博弈，并通过仅查询少量的纯策略来学习成本函数。

Feb, 2013

通过引入一种新的算法层次结构中的 Optimistic Matrix Multiplicative Weights Update (OMMWU) 算法，本研究在计算量子零和博弈中的 ε-Nash 均衡方面取得了二次速度提升，并为量子游戏理论中的主要议题提供了新的基准。

Nov, 2023

提出量子计算的次线性时间的算法，基于 LP 问题和量子 SDP 求解器，用有效的 Gibbs 采样方法计算二人零和游戏的 Nash 均衡点。

Apr, 2019

本文提出两种新算法：平衡在线镜像下降和平衡对策后悔最小化，通过整合平衡探索策略到它们的经典对应物算法，解决学习不完美信息的广义零和游戏的近似 Nash 均衡问题。同时，将结果推广到学习多人游戏的粗略相关均衡。

Feb, 2022

该论文研究了在一个允许算法在纯策略配置上查询玩家收益的模型中寻找 $n$ 个玩家博弈的相关均衡的复杂性，结果表明随机规避后悔的动态算法可以高效地得出近似相关均衡，但确切相关均衡需要更多的回报查询（随机算法瓶颈）并无法使用高效的确定性算法（因为查询次数下限）。

May, 2013

针对二人 NxN 游戏的 epsilon-Nash 均衡和 n 人二元动作游戏的 epsilon 弱近似 Nash 均衡，我们证明了通信复杂度的下限是多项式 N 和指数级 n。

Aug, 2016

这篇研究论文探讨了具有噪声的两人零和矩阵博弈中，识别纯策略纳什均衡（PSNE）的样本复杂度。研究人员设计了一个接近最优的算法，其样本复杂度与已知的下界相匹配，同时解决了纯探索问题和 dueling bandits 问题，且结果与最优边界相匹配。

Oct, 2023