有限正规式博弈中纳什均衡算法调查
本文介绍了博弈论中最常用的平衡概念 Nash 均衡存在的缺陷,从计算机科学角度考虑,解决方案概念试图解决 Nash 均衡的弱点,例如不足的鲁棒性,处理联盟的不足,不考虑计算成本以及游戏中参与者不知晓所有方面的情况等。
Jun, 2008
AI 在数学领域以一种建设性的方式处理数学问题,使推理自动化、减少劳动力和降低错误率。本研究首次提供了一个自动化方法,用于理论计算机科学中一个经过深入研究的问题:计算两人博弈中的近似纳什均衡。我们观察到,这样的算法可以被重新表述为搜索混合范式,其中包括搜索阶段和混合阶段。通过这样做,我们能够完全自动化设计和分析混合阶段的过程。例如,我们演示了如何使用我们的方法来分析文献中所有算法的近似界限。这些近似界限是无需任何手写证明计算的。我们的自动化方法严重依赖近似纳什均衡中的 LP 松弛结构。由于许多近似算法和在线算法采用了 LP 松弛,我们的方法可能被扩展用于自动化分析其他算法。
Oct, 2023
通过发展更高效和可扩展的算法,使用稀疏迭代方法的行为扰动来解决不完全信息博弈中的纳什均衡问题,从而实现最优均衡,但不排除博弈树中未到达的子树中存在次优策略。 通过使用平滑方法,能够计算出一个近似的 extensive-form 完美均衡,以解决经典的纳什均衡算法中存在的精度问题。
May, 2017
通过采样策略和马尔科夫蒙特卡罗方法,提出了一种基于多项式更新算法的广义博弈相关均衡计算方法,用于在多智能体系统中更高效的计算关于社会福利的均衡。
May, 2012
本研究介绍了多人博弈图模型和 Nash 平衡的计算算法,特别是在树形图的情况下,我们提出了高效的局部消息传递算法,它只涉及到与相邻节点的交互以及相对较少的全局交互,从而使得该算法可以被分布式实施。
Jan, 2013
我们引入了神经均衡求解器,它利用特殊的等变神经网络体系结构来近似解决具有固定形状、购买速度和决定性的所有游戏空间,并定义了一个灵活的均衡选择框架,该框架能够唯一选择最小化相对熵或最大化福利的均衡,该网络的训练无需生成任何监督训练数据,展示了在更大的游戏中惊人的零样本泛化能力。这样的网络是许多可能的多主体算法的强大组成部分。
Oct, 2022
本文研究了基于局部知识来学习研究各种类型的博弈及其均衡求解的复杂度,探讨了计算学习模型和对于各种博弈的查询复杂度,着重研究了对称网络拥塞博弈,并通过仅查询少量的纯策略来学习成本函数。
Feb, 2013
本文研究网络玩家的公共物品博弈,其中每个玩家具有二进制行动,并针对这类博弈的算法方面进行了研究,包括纯策略纳什均衡的存在性检测,限制条件下的可计算性以及启发式算法的提出与实验测试。
Nov, 2019