Mar, 2014

随机优先权及其扩展下的单边匹配社会福利

PDF
TL;DR研究了在代理人对有限物品具有不受限制的基数偏好时，近似社会福利最大化（无货币）的问题，在此问题中随机优先级是一个非常著名的期望真实机制，证明了随机优先级的近似比率是 Θ（n ^ {-1 / 2}），而没有期望真实机制可以实现比 O（n^{-1/2}）更好的近似比率。此外，证明了所有序数（不一定是期望真实的）机制的近似比率都是 O（n^{-1/2}），表明随机优先级是问题的渐近最好的期望真实机制和最好的序数机制。
发现论文，激发创造
  • 无货币的单边配对市场中的社会福利

    本文研究了在没有货币支付的情况下，将 N 个物品分配给 N 个拥有完整、私有偏好列表和单位需求的代理的社会福利。研究了两个自然社会福利的度量方式，并分析了两种常见的匹配机制，即随机串独裁和概率串行机制，给出了这些机制的效能保证。

    Apr, 2011

  • 区间投票的真实近似

    研究机制设计的基本问题，即在无货币的情况下，考虑有限数量的备选方案和一般记数偏好下的近似社会福利最大化问题，并提出一种随机的期望真实序数机制来实现其预期社会福利至少是社会最优方案社会福利的 1/m^(3/4)。此外，对于足够多的代理和任何期望真实序数机制，存在一种评估配置文件，其中机制在预期上达到最优社会福利的 O (m^(-2/3)) 分数，对于 m=3 的自然特殊情况，可以获得更紧的界限，并获得有关实用期望真实机制可达到近似比率的自然受限类别的分离结果。

    Jul, 2013

  • 盲目、贪婪和随机：用于匹配和聚类的序数近似算法

    研究了匹配和其他相关问题，提出一种只使用有限的偏序信息设计近似算法的模型，并证明当隐含权重满足度量不等式时，可以实现 1.6 倍近似度的匹配，以及利用匹配算法的黑箱设计了其他多个近似算法，推动了该问题的研究。

    Dec, 2015

  • 具有独立偏好的分配问题的平均情况分析

    本文研究了基本的分配问题，提出了一种新的机制来最大化效益，即当提供自利智能体对不可分割项目的私人偏好时，我们提出了一种新的机制：随机优先级机制，并且发现这种机制的效率损失具有常数界 。

    Jun, 2019

  • 没有效用函数的效益主义者：仅使用序数偏好最大化图问题的社会福利 - 全版

    通过对经验偏好信息的分析，研究了多智能体系统中的最大效用解计算问题，该问题考虑了代理连接效用的多样性和约束性质，并证明基于有限的偏序信息可以实现接近于最优的解，特别地，最大生成树、最大权重平面子图、最佳旅行商问题和各种匹配问题都可以实现 2 - 近似度的计算。

    Nov, 2017

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

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

    May, 2021

  • 二元估值的公平诚实机制

    设计了一种分配机制，基于私有偏好，旨在通过将不可分割物品分配给玩家来实现高效和公平；使用具有二分边缘概率的估值，并且它是公证的，它生成的分配满足许多所需的公平性质。

    Feb, 2020

  • 贪心算法求解纳什社会福利最大化问题

    研究公平地将一组不可分割的物品在代理商之间进行分配的问题，通过​​加法估值来衡量分配的公平程度，即代理商对其组合的估值的几何平均数，研究了特定情况下简单贪婪算法的有效性，其中代理的估值不同或是二元估值。

    Jan, 2018

  • 广义均值福利的通用紧致在线算法

    该研究针对在线情况下可分配商品的公平高效分配问题，提出了一种基于平均值的算法框架来最大化每个成员获得的价值。该框架可以用于范围各异的福利函数，通过特定的阈值，得到了统一的与个性化竞争保证，并实现了比现有算法更好的效果。

    Sep, 2021

  • 私人匹配与分配

    本文研究了在私有约束下如何进行资源分配问题，可以从最大权重匹配、联合差分隐私和总代用品假设等方面来考虑。通过研究分析发现，这种问题在不同隐私条件下的解决方案存在明显差异，提出了适用于差分联合隐私的解决方案来保障社会福利最大化。

    Nov, 2013