Feb, 2016

顺序分配操作的复杂性

PDF
TL;DR该研究通过一个示例，证明了 Bouveret 和 Lang（2014）提出的计算最佳响应的算法在某些情况下无法正确找到最佳响应，并证明了计算最佳响应是一个 NP 完全问题。然而，对于两个 agent 的情况，Bouveret 和 Lang（2014）的一些结论仍然成立。
sequential allocationstrategyproofpolynomial-time algorithmadditively separable utilitiesnp-complete
发现论文，激发创造
  • 序贯配置的均衡

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

    May, 2017

  • 通过顺序机制实现可行和必要的分配

    本文研究了可划分和必需的分配问题，重点关注了一些常用的链式分配机制。对于五个天然的链式分配机制，本文分别给出了平衡、递归平衡、平衡交替、严格交替和所有策略的分配特征，并同时检查了这几个类别中分配问题的计算复杂性。

    Dec, 2014

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

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

    Apr, 2013

  • 操纵概率串联规则

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

    Jan, 2015

  • 加性和响应偏好下的有效再分配

    在多智能体问题中，通过新的资源配置方式实现互惠互利是一个根本性问题。本文探讨了两种不同偏好关系的情况下，如何以不同的限制条件测试 Pareto 最优性。第一部分着重于代理人对物体的加法计数效用的表达方法，提出了计算复杂性结果和多项式时间算法；第二部分假设代理人只表达其对单个对象的偏好，并将其偏好降解为相加的形式，提出了可能和必要 Pareto 最优性的特征和多项式时间算法。

    Apr, 2016

  • 不可分割商品顺序分配机制的福利

    研究顺序分配不可分配物品的机制，探讨其效率和社会福利之间的关系，并研究政策选择对社会福利的影响及相应的计算问题。

    Nov, 2015

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

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

    May, 2016

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

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

    Jan, 2023

  • 半强化反馈下的最优资源分配

    研究一种顺序资源分配问题，包括一个固定数量的重复工作，每次时间步骤经理都应该在工作之间分配可用资源以最大化完成的工作数量的期望值。

    Jun, 2014

  • 具有部分信息的公正而有效的资源分配

    本文研究了将不可拆分物品分配给具有加法偏好的代理人的基本问题。我们考虑 eliciting 每个代理人仅排名她最喜欢的 $k$ 个物品，而不是她的完整基数估值。我们表征了实现嫉妒 - 自由度高达一个良好且近似最大值共享保证的 $k$ 值。我们还分析了由于缺乏完整信息而产生的社会福利的乘法损失，无论是否满足公平要求。

    May, 2021