Feb, 2015

概率串行规则下的均衡

PDF
TL;DR研究了使用 PS 规则的平衡问题，首先展示了 Nash 偏离的可能和纯策略 Nash 平衡的存在性，接着证明了验证给定档案是否为纯策略 Nash 平衡是 coNP - 完全的，计算纯策略 Nash 平衡是 NP 困难的。最后，使用实验验证了纯策略 Nash 平衡下的社会福利大多数至少与诚实档案相当。
probabilistic serial rulenash equilibriumstrategyproofnp-hardsocial welfare
发现论文，激发创造
  • 操纵概率串联规则

    通过研究概率排序规则，本文探讨了代理商操纵的计算复杂性问题，提出了计算最佳响应的算法，并在两个代理商的情况下，证明了即使是最佳期望效用，也可以用多项式时间计算得出。

    Jan, 2015

  • 序贯配置的均衡

    本研究探讨了序贯配置下的策略性行为，特别是考虑到 Nash 均衡、纯策略 均衡的计算和 Pareto 最优。研究表明，即使对于两个代理人，更好的应对也可以循环。研究结果提供了一个在纯 Nash 均衡下的结果，并且可以通过 “bluff profile” 的形式实现。此外，研究还展示了针对两个代理人的最佳 Stackelberg 策略的动态规划。

    May, 2017

  • 关于策略无懈可击和公正选取序列的研究：第一位玩家不可全选

    研究机制，序列式独裁，分配，社会福利和代理人影响的影响

    Jan, 2023

  • 公平混合：二分偏好的情况

    讨论了三个优秀的投票规则，其中条件功利规则是一个策略性稳健且容易计算的规则，其最坏和平均效率在代理人数量较小时都是低的，而效率最高的 Nash Max Product 规则虽然可以实现任何联盟的最强福利保障，但不符合排斥策略性稳健性，而有效的平等主义规则保护个体代理人但不保护联盟。

    Dec, 2017

  • 可观测完美均衡

    本文定义了一种名为可观测完美均衡的平衡改进概念，它在公开可见的动作概率上是鲁棒的，并证明了它总是保证存在的。该概念被证明在具有重要不完美信息的游戏中是有用的。

    Oct, 2022

  • 安全均衡

    提出一种新的解决方案概念 —— 安全均衡，用概率描述对手的理性行为，存在于所有战略形式博弈中，是 PPAD-hard 问题，同时提出了准确算法和可伸缩的近似算法。

    Jan, 2022

  • 光滑纳什均衡：算法与复杂性

    本文介绍了一种松弛的 Nash 平衡概念，即 σ 平滑的 Nash 平衡，通过使用随机化算法和多项式时间确定性算法，在常数参数范围内，可以更有效地找到近似的 σ 平滑的 Nash 平衡。

    Sep, 2023

  • 社会福利最优顺序分配程序

    通过简单的顺序分配程序，共享不可分割的物品，当代理人采取轮流选择物品时，预计可以计算每个代理人的效用到多项式时间复杂度，而当代理人行为策略变化时，预期 utilitarian social welfare 时最大化的。

    Apr, 2013

  • 行为到稀疏图游戏：均衡状态的高效恢复

    本文研究了通过玩家联合行动的噪声观察准确恢复图形游戏的纯策略纳什均衡（PSNE）集的问题。我们提出了一种基于 L1 正则化的逻辑回归算法，用于精确恢复 PSNE 集，并进行了验证。此算法在计算上高效，而且具有对数样本复杂度。

    Jul, 2016

  • 不可分割物品的公平分配

    本文讨论了如何公平地将不可分割的物品分配给一组代理，并给出了一种多项式时间近似算法，最大化了 Nash 社会福利，计算出的配置是帕累托最优且近似无嫉妒。

    May, 2018