三个代理商存在 EFX
本文研究如何在不平等情况下,通过” 捐赠”,实现物品公平且有高效的分配方式,提出了 EFX allocation 的算法,并证明了该算法在市场规模大,且收益较小的情况下非常有效。
Feb, 2019
研究为具有加法估值函数的代理分配不可分割货物的公平分配问题,并探索两个突出的公平性概念之间的关系:最大纳什福利(MNW)和任何物品的无嫉妒(EFX)。
Jan, 2020
对于将一组不可分割的货物分配给具有加法估值函数的一组代理人的问题,我们研究了实现近似无嫉妒性(α-EFX)的分配。我们的结果表明,在少于七个代理人、代理人估值函数最多可以取三个值或代理人估值函数可以通过多图表示时,存在 2/3-EFX 分配。因此,我们的结果推动了近似 EFX 分配的存在性和计算的前沿,并为解决精确 EFX 分配的存在性提供了洞察。
Jun, 2024
我们研究公平分配问题和满足公平性准则的 EFX 分配的存在性。通过使用完全不同的技术,我们将这个存在性结果推广到一般的二元估值,并提出了一种多项式时间算法来计算 EFX 分配。
Aug, 2023
本文研究公平分配中的 “无嫉妒性” 概念,在不能平分的资源分配中,提出了 “去除任意一份资源后,任何玩家都不会愿意交换自己捆绑的价值”(EFX)的公平性条件。使用 Leximin 解决方案证明了在几个情境中都有 EFX 分配的存在性,我们的研究表明,在不同类的玩家估值的不能平分的财产的公平分配中,有着丰富的研究课题。
Jul, 2017
研究了如何使用 envy-freeness 的松弛,公平地分配不可拆分物品给多组代理人。同时,我们考虑了对代理人估值的不同假设,对于任意单调,响应和可加估值,我们的结果都是具有普遍意义的。此外,我们还引入了一种新模型,其中代理人事先不被划分为不同组,而是与物品分配一起选择划分。
Jan, 2019
研究分配一组不可分割商品给一组代理商的公平和高效问题,当代理商对商品具有可加性评估时,存在一种同时满足 EF1 和 PO 的最大 Nash 社会福利目标的分配,并提出了一个类似于假多项式时间算法的方法用于寻找 EF1 和 PO。
Jul, 2017
本文介绍和分析适用于配有权重的代理商在不可分配的物品的分配中的公平概念。我们提出了两种权重嫉妒自由概念:强权重嫉妒自由和弱权重嫉妒自由。我们证明,满足强权重嫉妒自由和帕累托最优的分配总是存在且可以在伪多项式时间内计算。此外,我们还建立了一个轮换选择算法的泛化版本,可以在多项式时间内为任意数量的代理商产生具有强权重嫉妒自由的分配。最后,我们强调了权重公平分配比其无权重对应更为复杂。
Sep, 2019
研究对不可分割物品的公平分配的查询复杂度。 发现对于两个代理人和任意单调效用的情况,可以使用对数数量的查询计算满足 envy-freeness 最多一个 good (EF1) 的分配,并且这个 logarithmic 查询复杂性界限也适用于具有可加性效用的三个代理人,但是需要使用 polylogarithmic 界限来满足单增效用的情况。同时,证明即使只有两个代理人具有相同可加效用时,计算满足 envy-freeness 和 EFX(envy-freeness up to any good)之一的分配需要线性数量的查询。
Jul, 2018