通过研究不完全记忆下的最优决策问题,我们分析了广义形式博弈中多个解概念(纳什均衡、基于证据决策理论的多个自体以及基于因果决策理论的多个自体)下,在多人情景中寻找均衡的计算复杂性,同时关注精确和近似解的计算。我们将单人游戏、两人零和游戏与最小最大值以及没有外在随机性(几率节点)的游戏作为特例,并将这些问题与复杂性类 P、PPAD、PLS、Σ₂ᴾ、∃R 和∃∀R 联系起来。
Jun, 2024
该研究探讨了不完全回忆下的单人博弈理论,比如 “睡美人问题” 和 “健忘的司机游戏”,并找到了与之对应的平面最大化问题的解决方案,从而解决了这些策略计算的复杂性问题。
May, 2023
本文提出两种新算法:平衡在线镜像下降和平衡对策后悔最小化,通过整合平衡探索策略到它们的经典对应物算法,解决学习不完美信息的广义零和游戏的近似 Nash 均衡问题。同时,将结果推广到学习多人游戏的粗略相关均衡。
Feb, 2022
本文定义了一种名为可观测完美均衡的平衡改进概念,它在公开可见的动作概率上是鲁棒的,并证明了它总是保证存在的。该概念被证明在具有重要不完美信息的游戏中是有用的。
Oct, 2022
通过发展更高效和可扩展的算法,使用稀疏迭代方法的行为扰动来解决不完全信息博弈中的纳什均衡问题,从而实现最优均衡,但不排除博弈树中未到达的子树中存在次优策略。 通过使用平滑方法,能够计算出一个近似的 extensive-form 完美均衡,以解决经典的纳什均衡算法中存在的精度问题。
May, 2017
研究表明,通过公开玩家策略,可以从常见的收益游戏中摆脱不完美的信息,但同样的方法不能应用于两人零和游戏,该论文提出利用正则化平衡的方法来解决这个问题,以便计算这些均衡点可以被视为完美信息问题。
Jan, 2023
本研究探讨匿名博弈的均衡计算,通过先进行具有适应性的问题到博弈的支付函数计算的算法处理。讨论研究的主题是查询复杂度,即计算精确或近似纳什均衡所需的查询数量。研究发现不能通过查询有效算法找到精确均衡,但可以通过假设效用函数的进一步对称性或关注近似均衡来获得更好的查询复杂度界限。研究涉及的匿名游戏的子类是匿名博弈的相似研究,结论为使用随机算法可以在相应的复杂度下查询到一个近似的纳什均衡,此外也证明了一定数量次的查询才能找到任何 ϵ- 好支持纳什平衡,即使采用随机算法也需要 Ω(n log n) 的复杂度。
Dec, 2014
本文提出无法完全回忆的游戏中,针对使用 CFR 算法的一般类游戏的第一个遗憾上限及其不适用性,同时证明使用 CFR 在任何抽象类游戏中都适用,且在三种情况下证明不完全回忆可用于交换少量遗憾和显著降低内存。
May, 2012
本文研究如何在大型零和博弈中计算近似纳什均衡,提出两种方法:无悔在线学习和基于凸凹点公式的梯度方法,并尝试将两种方法进行整合。
Nov, 2014
在大量玩家的二元行动博弈中,查询复杂度与 ε- 支持纳什均衡的关系是指数级的,并导致自适应动态收敛到近似纳什均衡的速度指数级下降。
Jun, 2013