AAAIFeb, 2016

树图游戏与其推广的混合策略纳什均衡的 FPTAS

PDF
TL;DR该文提供了第一个完全多项式时间的近似混合策略纳什均衡算法，用于计算树形图多超矩阵博弈中的纳什均衡，并证明当操作数量受到限制时，该算法适用于树状多项式博弈和树形图博弈，并引出了拟多项式时间的近似算法。
fully polynomial time approximation schememixed-strategy nash equilibriumtree-structured graphical multi-hypermatrix gamesgraphical polymatrix gamesppad-complete
发现论文，激发创造
  • 博弈论图形模型

    本研究介绍了多人博弈图模型和 Nash 平衡的计算算法，特别是在树形图的情况下，我们提出了高效的局部消息传递算法，它只涉及到与相邻节点的交互以及相对较少的全局交互，从而使得该算法可以被分布式实施。

    Jan, 2013

  • 行为到稀疏图游戏：均衡状态的高效恢复

    本文研究了通过玩家联合行动的噪声观察准确恢复图形游戏的纯策略纳什均衡（PSNE）集的问题。我们提出了一种基于 L1 正则化的逻辑回归算法，用于精确恢复 PSNE 集，并进行了验证。此算法在计算上高效，而且具有对数样本复杂度。

    Jul, 2016

  • 双矩阵博弈中 1/3 近似纳什均衡的多项式时间算法

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

    Apr, 2022

  • 通过树分解在零和展开式博弈中实现团队相关均衡

    本文针对协作游戏的均衡点发现问题，提出了一种基于树分解的全新算法。该算法不仅能实现多项实践和理论上的突破，而且思路新颖、高效，可以直接描述相关策略的多面体，因此可以免费获取在相关策略下的平衡点。实验结果证明其在标准游戏套件上的性能超越了现有所有竞争算法，唯一的例外是一类特定的基准游戏。

    Sep, 2021

  • 不平等议价权下议价网络的 FPTAS

    本论文研究了 Nash 谈判的扩展概念，研究了不平等谈判力量的可能性，并提供了当存在时的计算方法和快速本地算法。

    Aug, 2010

  • 一种用于结构化博弈中纳什均衡的连续化方法

    本文提出了一种高效的算法来计算包括图形游戏和多智体影响图在内的结构化博弈表示中的纳什均衡，并演示了该算法的强大性能。

    Sep, 2011

  • 有限博弈中虚拟博弈的近似性能

    本文研究了虚拟博弈在寻找二人博弈的纳什均衡时的表现，证明虚拟博弈无法找到一个加法近似保证显著优于 1/2 的解。我们的结论适用于 2 人游戏并且玩家的得分在 [0,1] 范围内。

    Mar, 2011

  • 匿名博弈中的均衡计算

    该研究提出了一种高效的近似算法，适用于在匿名游戏中寻找纳什均衡，其中玩家的效用虽然不同，但在其他玩家之间没有区别，该算法适用于玩家众多但策略较少的游戏，可在多项式时间内计算出近似的 “纯纳什均衡”，此近似值的上限是 O (s^2L)，此外，该研究还表明可以有一个 “PTAS” 算法，可用于寻找 epsilon。

    Oct, 2007

  • 计算两人纳什均衡的复杂性问题

    证明了寻找 Nash 均衡在 P 平等辩论（有向版本）中完备，且矩阵 Bimatrix 不存在全面多项式时间逼近方案，这表明了在非合作博弈中计算均衡与计算固定点等价的复杂性，并且对数学经济学和运筹学具有广泛的复杂性影响。

    Apr, 2007

  • 通过均衡逼近实现对同时行动博弈的树搜索

    通过将自我博弈的树搜索算法应用于同时移动的游戏中，以近似粗略相关均衡为子程序的实际方法，提高了在合作、竞争和混合任务上的性能表现。

    Jun, 2024