拓扑博弈中纳什均衡的复杂性问题
本文提出了一种新的 N 人动态路由博弈模型,研究交通流量的基本图表并介绍了明确的拥堵动态学;然而,由于 Nash 均衡计算是 PPAD 完全的,因此提出了相应的均值场游戏,该方法在交通动力学建模方面取得了成功。
Oct, 2021
我们研究了不完全信息博弈中分布式学习近似相关均衡的迭代复杂度,我们证明了在广义形式博弈中,假设 PPAD 不属于 TIME (n^polylog (n)),任何多项式时间学习算法至少需要 2^log_2^{1-o (1)}(|I|) 次迭代才能收敛于 ε- 近似相关均衡集合,同时我们给出了无耦合动态的方法,在对数次迭代中达到 ε- 近似相关均衡的贝叶斯博弈,无需考虑类型的数量。
Jun, 2024
证明了寻找 Nash 均衡在 P 平等辩论(有向版本)中完备,且矩阵 Bimatrix 不存在全面多项式时间逼近方案,这表明了在非合作博弈中计算均衡与计算固定点等价的复杂性,并且对数学经济学和运筹学具有广泛的复杂性影响。
Apr, 2007
本研究通过提出 CongestEXP 算法来解决在线拥塞博弈问题,通过在设施级别上维护权重,创新性地规避了指数级依赖于可能的设施集合大小的遗憾界,并且适用于任何个体玩家,并在存在严格纳什均衡时,能以近似指数速度收敛至纳什策略。
Jun, 2023
本文提出了一种新的算法方法来解决优化一些目标(如社会福利)的相关均衡问题,并且给出了一种适用于所有紧凑表示的足够条件,同时利用该算法方法将最优 CE 问题转化为调整偏差的社会福利问题,这个框架可以识别出新的类别的博弈,其中包括基于树图的图形多项式博弈。同样使用类似的方法,我们导出了一种足够的条件来处理最优粗糙相关均衡问题,并使用其证明了单例拥塞博弈的可跟踪性。
Sep, 2011
本文研究在连续价值分布和离散竞标空间的第一价格拍卖中计算贝叶斯 - 纳什均衡的问题,并证明当投标人对其他竞标人的价值分布有独立的主观先验信念时,计算该拍卖的 ε- 均衡是 PPAD - 完全的,而计算精确均衡是 FIXP - 完全的。此外,我们还提供了一个有效的算法来解决该问题的特殊情况,即有固定数量的投标人和可用的报价。
Mar, 2021
本文介绍了一种松弛的 Nash 平衡概念,即 σ 平滑的 Nash 平衡,通过使用随机化算法和多项式时间确定性算法,在常数参数范围内,可以更有效地找到近似的 σ 平滑的 Nash 平衡。
Sep, 2023
通过研究不完全记忆下的最优决策问题,我们分析了广义形式博弈中多个解概念(纳什均衡、基于证据决策理论的多个自体以及基于因果决策理论的多个自体)下,在多人情景中寻找均衡的计算复杂性,同时关注精确和近似解的计算。我们将单人游戏、两人零和游戏与最小最大值以及没有外在随机性(几率节点)的游戏作为特例,并将这些问题与复杂性类 P、PPAD、PLS、Σ₂ᴾ、∃R 和∃∀R 联系起来。
Jun, 2024
该论文研究了在有界凸多面体域上通过梯度下降解决的搜索问题,并表明该类等于两个众所周知的类的交集:PPAD 和 PLS。同时证明了在区间 [0,1] x [0,1] 上计算连续可微函数的 Karush-Kuhn-Tucker(KKT)点是 PPAD 和 PLS 完全的第一个非人工问题。该研究结果还表明,Daskalakis 和 Papadimitriou 定义的 CLS 类(连续局部搜索) - 它是 PPAD 和 PLS 的更 “自然” 对应物,其中包含许多有趣的问题 - 本身等于 PPAD 和 PLS。
Nov, 2020