寻找任何非平凡的粗糙相关均衡是困难的
本文提出了一种新的算法方法来解决优化一些目标(如社会福利)的相关均衡问题,并且给出了一种适用于所有紧凑表示的足够条件,同时利用该算法方法将最优 CE 问题转化为调整偏差的社会福利问题,这个框架可以识别出新的类别的博弈,其中包括基于树图的图形多项式博弈。同样使用类似的方法,我们导出了一种足够的条件来处理最优粗糙相关均衡问题,并使用其证明了单例拥塞博弈的可跟踪性。
Sep, 2011
该论文研究了在一个允许算法在纯策略配置上查询玩家收益的模型中寻找 $n$ 个玩家博弈的相关均衡的复杂性,结果表明随机规避后悔的动态算法可以高效地得出近似相关均衡,但确切相关均衡需要更多的回报查询(随机算法瓶颈)并无法使用高效的确定性算法(因为查询次数下限)。
May, 2013
我们研究了不完全信息博弈中分布式学习近似相关均衡的迭代复杂度,我们证明了在广义形式博弈中,假设 PPAD 不属于 TIME (n^polylog (n)),任何多项式时间学习算法至少需要 2^log_2^{1-o (1)}(|I|) 次迭代才能收敛于 ε- 近似相关均衡集合,同时我们给出了无耦合动态的方法,在对数次迭代中达到 ε- 近似相关均衡的贝叶斯博弈,无需考虑类型的数量。
Jun, 2024
研究首价单品拍卖中的相关均衡和粗略均衡,证明与 Nash 均衡一样,所有相关均衡都可以实现完全的效率和至少是次高价值的收入;而粗略均衡则可能产生较低的效率和收入,即使没有价格高估。
Jan, 2016
本文研究多人随机博弈中同时学习的问题,通过生成算法获得相关均衡,包括 extensive-form correlated equilibrium 和普通 coarse correlated equilbrium,并提供了一些能够多项式时间内解决的特殊情况。
Oct, 2022
本文探讨了贝叶斯博弈的均衡概念,包括相关均衡、通信均衡,推导出基于均衡对策的博弈稳定状态的实现方法,提出一种满足稳定、高效、优化多个博弈均衡的新均衡概念。
Apr, 2023
本文提出一种针对不完全信息的博弈模式下具有更快学习速度的学习动态方案,并对其进行实验验证。其中,主要技术贡献为通过预测实现加速 Phi-regret 最小化,并通过对于有结构的马尔科夫链的细致扰动分析,表征与之相关的 fixed points 的稳定性。
Feb, 2022
我们研究了多人广义和 Markov 游戏中计算相关均衡的政策优化算法,以往结果在收敛速率上达到了 $O (T^{-1/2})$ 的相关均衡和 $O (T^{-3/4})$ 的粗糙相关均衡的加速收敛速率,本文提出了一种通过组合平滑值更新和乐观正则化领导者算法与对数障碍正则器的两个主要因素构建的解耦政策优化算法,达到了计算相关均衡的几乎最优 $ ilde {O}(T^{-1})$ 的收敛速率。
Jan, 2024