Sep, 2019

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

PDF
TL;DR本文介绍和分析适用于配有权重的代理商在不可分配的物品的分配中的公平概念。我们提出了两种权重嫉妒自由概念：强权重嫉妒自由和弱权重嫉妒自由。我们证明，满足强权重嫉妒自由和帕累托最优的分配总是存在且可以在伪多项式时间内计算。此外，我们还建立了一个轮换选择算法的泛化版本，可以在多项式时间内为任意数量的代理商产生具有强权重嫉妒自由的分配。最后，我们强调了权重公平分配比其无权重对应更为复杂。
weighted envy-freenessallocation of indivisible itemspareto optimalityweighted nash social welfareweighted fair division
发现论文，激发创造
  • 信息隐瞒下的公平分配

    研究 “Envy-freeness up to one good” 的公平性，提出一种基于信息隐瞒的新型公平性，通过实验及对算法的分析，验证算法分配的公平性。

    Jul, 2019

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

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

    Jan, 2019

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

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

    Feb, 2019

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

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

    Jul, 2017

  • 寻找公平高效的分配

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

    Jul, 2017

  • 三个代理商存在 EFX

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

    Feb, 2020

  • 不可分割商品的公平代价

    本文研究了如何使用公平价格概念来有效地分配不可分割物品。作者比较了以前研究的公平概念，发现某些实例无法满足这些概念，提出一些新概念并介绍了公平价格和强公平价格的概念。最后，作者在价格公平性和强价格公平性的范围内提供了严格或渐进紧的效率损失限制。

    May, 2019

  • 关于不可分配物品的公平分配中群体无嫉妒和群组帕累托效率

    本文从公平分配的角度出发，讨论了将物品分配给代理人组的问题，并提出了群体嫉妒和群体帕累托效率等新概念，探讨了这些新群体性质的公理化分类和其在不同社会福利下的表现。

    Jun, 2020

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

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

    May, 2018

  • 使用少量查询合理分配多种货物

    研究对不可分割物品的公平分配的查询复杂度。 发现对于两个代理人和任意单调效用的情况，可以使用对数数量的查询计算满足 envy-freeness 最多一个 good (EF1) 的分配，并且这个 logarithmic 查询复杂性界限也适用于具有可加性效用的三个代理人，但是需要使用 polylogarithmic 界限来满足单增效用的情况。同时，证明即使只有两个代理人具有相同可加效用时，计算满足 envy-freeness 和 EFX（envy-freeness up to any good）之一的分配需要线性数量的查询。

    Jul, 2018