游到沉没:计算游戏的极限
考虑从严格的行为数据中学习线性影响博弈 (LIGs) 的结构和参数,通过纯策略 Nash 平衡的最大似然估计 (MLE) 将学习问题转化为生成模型的估计,在控制平衡数量的同时捕捉数据中的均衡行为。该方法可以应用于识别大型 (社交) 网络中最有影响力的个体,并支持决策分析和其他普适性的图形游戏。
Jun, 2012
本研究介绍了多人博弈图模型和Nash平衡的计算算法,特别是在树形图的情况下,我们提出了高效的局部消息传递算法,它只涉及到与相邻节点的交互以及相对较少的全局交互,从而使得该算法可以被分布式实施。
Jan, 2013
通过一种启发式的学习方案,我们派生出了一种由惩罚项调整的复制者漂移的新类连续时间学习动态,这种惩罚调节的动态相当于玩家保留他们正在进行的回报的指数折扣总和,然后基于这些表现分数使用平滑最佳响应选择行动。借助这种内在的对偶,所提出的动态满足一种进化博弈理论的民间定理的变体,并且它们以(任意精度的)纳什均衡的逼近收敛于潜在游戏。受到交通工程应用的启发,我们进一步利用这种对偶来设计离散时间的,基于回报的学习算法,该算法具有这些收敛性质,并且仅需要玩家观察他们在游戏中的回报
Mar, 2013
本文研究了通过玩家联合行动的噪声观察准确恢复图形游戏的纯策略纳什均衡(PSNE)集的问题。我们提出了一种基于L1正则化的逻辑回归算法,用于精确恢复PSNE集,并进行了验证。此算法在计算上高效,而且具有对数样本复杂度。
Jul, 2016
本文研究了no-regret动力学中最常被考虑的动态系统之一 - Follow-the-regularized-leader的行为,证明了非严格的纳什均衡对于no-regret学习是不稳定的且不能吸引该动态系统的稳定状态,因此只有严格的纳什均衡是no-regret动力学的稳定限制点。
Oct, 2020
本文研究了一类竞争场景,其中代理和它们玩的游戏都在时间上演化。该系统中的信息论保存定律、泊松回归和 Nash 均衡特征表明,尽管代理和游戏共同演化,但其结果仍然遵循一定的规律。同时,针对这种共同演化的网络游戏提出了预测代理行为的多项式时间算法。
Dec, 2020
本文提出一种基于零阶优化技术、结合平滑梯度估计器和均衡查找动态的方法来解决没有梯度信息的连续行动博弈问题,采用神经网络建模玩家策略,特别是采用随机策略网络来建模混合策略。实验表明,该方法可以快速找到高质量的近似均衡。此外,研究表明,输入噪声的维度对方法的性能至关重要。这是第一篇在未知任何梯度信息的情况下解决了不受限制的连续行动博弈的研究。
Nov, 2022
通过研究正则化的无悔学习方法在有限游戏中的长期行为,我们发现玩家的实际策略如何随时间演变的理解非常有限,同时发现只有严格纳什均衡是稳定吸引的,进而揭示了玩家的日常对策的集合有理性的特性。我们进一步刻画了相应集合的稳定和收敛速率,并表明基于熵正则化的方法以几何速度收敛,而基于投影的方法在有限次迭代内收敛,即使是在带有被动反馈的并发奖励的情况下。
Nov, 2023