Feb, 2022

(几乎) 嫉妒平衡、比例和高效的不可分混合信物分配

PDF
TL;DR研究如何公平高效地分配不可分割物品给不同的需求者，考虑到嫉妒与比例问题，尝试提出了 Pareto 最优的多项式时间算法，同时维护各种类型的 good/bad 需求和纯商品和混合商品状况下的各项情形。
fairnessefficiencyallocationenvy-freeproportional
发现论文，激发创造
  • 比较嫉妒自由近似松弛

    研究公平分配问题中四种不同的公平度量以及其近似版本之间的联系，并确定它们之间的逼近质量，提供了关于近似公平解质量的深入见解。

    Jun, 2018

  • 不可分割物品的公平分配：改进与概括

    本文研究不可分割物品的公平分配问题，使用最小最大份额范例作为公平性标准，并提出了一种在聚类代理人的集合上使用匹配配分和貪婪演算法获得 3/4 最小最大份额得分的方法，同时将该方法推广到子模，分数次折价及次折价情况，并提出了相应的近似比较与上界。

    Apr, 2017

  • 一般价值情况下的几乎无嫉妒性

    本文研究公平分配中的 “无嫉妒性” 概念，在不能平分的资源分配中，提出了 “去除任意一份资源后，任何玩家都不会愿意交换自己捆绑的价值”（EFX）的公平性条件。使用 Leximin 解决方案证明了在几个情境中都有 EFX 分配的存在性，我们的研究表明，在不同类的玩家估值的不能平分的财产的公平分配中，有着丰富的研究课题。

    Jul, 2017

  • 寻找公平高效的分配

    研究分配一组不可分割商品给一组代理商的公平和高效问题，当代理商对商品具有可加性评估时，存在一种同时满足 EF1 和 PO 的最大 Nash 社会福利目标的分配，并提出了一个类似于假多项式时间算法的方法用于寻找 EF1 和 PO。

    Jul, 2017

  • EFX 的最大纳什福利与其他故事

    研究为具有加法估值函数的代理分配不可分割货物的公平分配问题，并探索两个突出的公平性概念之间的关系：最大纳什福利（MNW）和任何物品的无嫉妒（EFX）。

    Jan, 2020

  • 高纳什福利下任意物品的无嫉妒性：捐赠物品的优势

    本文研究如何在不平等情况下，通过” 捐赠”，实现物品公平且有高效的分配方式，提出了 EFX allocation 的算法，并证明了该算法在市场规模大，且收益较小的情况下非常有效。

    Feb, 2019

  • 三个代理商存在 EFX

    本文研究在具有加性估值的代理之间以公平的方式分配一组不可分割的物品的问题，通过 EFx 公平的概念，我们证明了对于三个代理，总是存在一个 EFx 分配，同时证实了 Caragiannis 等人的猜想，并展示出一个实例，其中对于具有三个代理的部分 EFx 分配（某些物品未分配），其 Nash welfare 比任何完全 EFx 分配的 Nash welfare 要高。

    Feb, 2020

  • 群组资源分配中的几乎无嫉妒

    研究了如何使用 envy-freeness 的松弛，公平地分配不可拆分物品给多组代理人。同时，我们考虑了对代理人估值的不同假设，对于任意单调，响应和可加估值，我们的结果都是具有普遍意义的。此外，我们还引入了一种新模型，其中代理人事先不被划分为不同组，而是与物品分配一起选择划分。

    Jan, 2019

  • 不可分配物品分配中的加权无嫉妒公平性

    本文介绍和分析适用于配有权重的代理商在不可分配的物品的分配中的公平概念。我们提出了两种权重嫉妒自由概念：强权重嫉妒自由和弱权重嫉妒自由。我们证明，满足强权重嫉妒自由和帕累托最优的分配总是存在且可以在伪多项式时间内计算。此外，我们还建立了一个轮换选择算法的泛化版本，可以在多项式时间内为任意数量的代理商产生具有强权重嫉妒自由的分配。最后，我们强调了权重公平分配比其无权重对应更为复杂。

    Sep, 2019

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

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

    May, 2021