May, 2013

理解激励：机制设计转化为算法设计

PDF
TL;DR本文提供了一种从机制设计到算法设计的计算高效的黑盒约简方法，并且在虚拟福利和收益两个问题上进行了探讨，发现在单调子模拟拍卖场景下，这两个问题都无法在多项式时间内进行近似解决。
mechanism designalgorithm designvirtual welfarerevenuecomputational complexity
发现论文，激发创造
  • 多维机制优化设计：将收益降至最小以实现福利最大化

    本文提供了一个从收入最大化到福利最大化的规约，以在具有任意（可能是组合）可行性约束和具有任意（可能是组合）需求约束的多维贝叶斯拍卖中，恰当地将 Myerson 的结果扩展到此设置。我们还展示了每个可行的贝叶斯拍卖都可以实现为虚拟 VCG 分配规则的分布。利用这种表征，我们展示了如何找到并运行仅具有黑箱访问虚拟 VCG 分配规则实现的收入最优拍卖。

    Jul, 2012

  • 对称次模目标的预算可行机制设计

    本文研究了一类采购拍卖问题，涉及到预算约束和非单调子模价值函数。我们提出了可行的机制来最大化拍卖者的估值函数，同时也满足诚实、可行和近似最优的要求，本文所提机制在增加了预算约束的条件下，显著改进了以往的方法。其中以最大割问题为重点，在此问题上，我们的结果显著提高了已知的近似比，同时为只有指数级机制的情况建立了多项式运行时间的结果。

    Apr, 2017

  • 隐含支付计算的诚实机制

    本文介绍了一种简单而通用的规约方法，可将单参数域的单调分配规则转化为随机机制，使得机制期望上是真实的，并且对于每个实现都是独立的。该机制的运行时间复杂度与 Dijkstra 算法相同，可在机制设计的许多问题中应用。

    Apr, 2010

  • 可计算实现的 VCG 机制

    本文分两部分，第一部分研究了将 VCG (Vickrey, Clarke, Groves) 机制应用于复杂问题如组合拍卖时的计算难度，第二部分提出了修改后的 VCG 机制，使得机制更加高效且诚实。

    Sep, 2011

  • 分类任务带部分验证的自动化机制设计

    本文研究了自动机制设计中的部分验证问题，侧重于所有类型在结果上共享相同偏好的环境中的真实机制，并寻找优化确定性真实机制的有效算法，同时将这些结果推广到代价函数为次模的情况。

    Apr, 2021

  • 关于最大化最小份额分配的诚实机制

    本文研究了一种公平分配问题，即计算最大最小份额分配。通过机制设计方法，提出了三种关于机制试图引导玩家了解其偏好的信息模型，并对每个模型进行积极和消极（不可能性）结果的阐述，最后特别关注了两位玩家的情况，提出了挑战性的问题。

    May, 2016

  • 无货币的诚实分配

    研究不使用支付的真实机制的设计，以解决广义分配问题（GAP）及其变体。引入私人估值的模型，并研究了几种 GAP 变体，开发了一个基于 LP 的通用技术，可以将设计真实机制的问题降低到该问题的分数版本，获得了一些近似算法且吻合上下界，这个技术也可用于其他基于 LP 的问题。

    Jan, 2010

  • 机制设计的复杂度

    本研究探讨了在多智能体系统中，通过机制设计实现代理人诚实报告偏好从而选择出（社会）期望结果的问题。我们提出了一种自动创建偏好聚合机制的方法，并发现在无法进行边际支付的情况下，确定性机制的机制设计问题是 NP 完全的，但随机机制则是可计算的。

    May, 2002

  • 动态机制设计中的公平分配

    通过研究动态机制设计问题，我们确定拍卖者在每一轮中向两个买家群体销售一个不可分割的商品的优化分配和付款方式，以最大化他们的折扣总收入并遵守确保每个群体最低平均分配的公平约束。

    May, 2024

  • 通过对偶理论实现次可加买家的简单机制

    该论文提出了在多个项目和多个竞标人设置中的简单又近似最优机制，其中分别提到了简单的确定和支配策略激励兼备的顺序发布价格机制或带进场费的匿名顺序发布价格机制。

    Nov, 2016