Mar, 2015

大型博弈中的混乱代价

PDF
TL;DR本文开发了一个框架，为计算机科学应用中涉及到的包含多个参与者的博弈论模型提供了红利保障，以减小其混沌的程度，实现了对多个经典模型的实例化，包括 “同时出价单项竞拍”、“贪婪组合式拍卖” 和 “路由博弈”，并鉴定了在什么情况下多方博弈的 POA 更好，同时也给出了简单竞拍可以在现实中表现出几乎和最优竞拍一样的效果的新的方面。
game theoryprice of anarchycomputer scienceauctionsrouting games
发现论文，激发创造
  • 拍卖中的混沌代价

    本文提出了一种通用的、模块化的理论来证明竞拍中的平衡近似保证，该理论补充了传统经济技术，着重于精确和最优解决方案，并因此局限于相对简化的设置。我们提出了三个用户友好的分析工具：平滑型不等式、扩展定理和组合定理，将这些工具结合起来，为许多广泛使用的拍卖格式的均衡提供了严格的最坏情况近似保证。

    Jul, 2016

  • 利他博弈的鲁棒性劣解代价

    本文研究了各种类型的博弈中当玩家是（部分）利他主义者时的均衡的低效性，并通过模拟玩家的 “利他” 行为来推导出这些游戏的安定价格的（严格）下限。

    Dec, 2011

  • 拍卖收益的失调代价

    该研究开发了工具，用于分析具有单维代理商的非对称拍卖中的 Bayes-Nash 平衡的福利和收益，分析分离了标准的平稳框架两个不同的部分，得到了关于社会福利和收益的无序价格结果，并为最优福利和最优收益提供了近似结果，同时还给出了同时组合多个拍卖的扩展定理。

    Apr, 2014

  • 交通网络中的混沌成本：效率与最优控制

    通过分析几个主要城市的道路网络的旅行时间，我们评估了无协调驾驶者的乱象代价。我们的模拟表明，不协调的驾驶者可能会浪费相当数量的旅行时间。令人意外的是，简单地封锁某些道路可以部分改善交通状况。我们分析了各种复杂网络，讨论了物理学中类似的悖论可能性。

    Dec, 2007

  • D3C: 多智能体学习中降低混沌代价

    D3C 算法通过引入 Price of anarchy 的不可微上界，使得每个多智能体可以调整其激励机制，从而提高系统的效率。

    Oct, 2020

  • 自私驾驶有多糟糕？限制城市驾驶游戏均衡的低效性

    该研究通过将驾驶游戏建模为拥塞游戏来界定均衡效率，并通过模拟交通拥堵情况对社会成本和个人利益之间的相对权衡进行探究，得出了针对一些问题的 PoA 的改进边界。该研究还通过去中心化多智能体强化学习策略得出了高效均衡状态。

    Oct, 2022

  • 算法理性：代价计算的博弈论

    本文提出了一个关于战略代理进行可能昂贵计算的普适的博弈论框架，利用该框架在一些已研究的博弈中（如有限重复犯罪囚徒困境和剪刀石头布）提供心理学上合理的解释，同时提出了保证博弈中存在均衡的自然条件。

    Dec, 2014

  • 优化原子拥塞的复杂性

    计算系统最优策略的计算复杂性在领域中鲜有研究，本论文通过参数化复杂性范式，确定了问题的可处理边界，并且发现控制问题计算复杂性的结构性参数不是基于顶点分离器，而是基于边分离器。

    Dec, 2023

  • 广义二价定价拍卖中结果低效性的限制

    本文研究了广义第二价格 (GSP) 拍卖中的均衡状态空间，并量化了广泛来源的不确定性和完全信息设置下可能出现的低效均衡状态损失。通过贝叶斯博弈模型，得出了 2.927 的损失因子上限，证明了拍卖参与者关于其他参与者和广告质量因素的部分信息的贝叶斯模型中的效率损失。此外，在完全信息设置中，我们证明了对于三个广告商的情况下，纯纳什均衡的 “惩罚因子” 的上限接近于 1.282，同时我们展示了类似的低上限的结果适用于任何遵循无后悔策略的拍卖结果。

    Jan, 2012

  • 马尔可夫潜势博弈中 Softmax 策略梯度的收敛性和劣质纳什均衡价格保证

    本文研究使用策略梯度方法解决马尔可夫势博弈 (包括完全合作的情况) 的收敛性，在策略参数化方面，包括 tabular 和神经网络等。通过引入 POA 和平滑概念，给出了 POA 边界，并通过实验比较了不同方法的收敛速度和 POA。

    Jun, 2022