群组资源分配中的几乎无嫉妒
本文研究公平分配中的 “无嫉妒性” 概念,在不能平分的资源分配中,提出了 “去除任意一份资源后,任何玩家都不会愿意交换自己捆绑的价值”(EFX)的公平性条件。使用 Leximin 解决方案证明了在几个情境中都有 EFX 分配的存在性,我们的研究表明,在不同类的玩家估值的不能平分的财产的公平分配中,有着丰富的研究课题。
Jul, 2017
研究对不可分割物品的公平分配的查询复杂度。 发现对于两个代理人和任意单调效用的情况,可以使用对数数量的查询计算满足 envy-freeness 最多一个 good (EF1) 的分配,并且这个 logarithmic 查询复杂性界限也适用于具有可加性效用的三个代理人,但是需要使用 polylogarithmic 界限来满足单增效用的情况。同时,证明即使只有两个代理人具有相同可加效用时,计算满足 envy-freeness 和 EFX(envy-freeness up to any good)之一的分配需要线性数量的查询。
Jul, 2018
本文通过随机分配机制在具有多个参与方的背景下研究了公平分配资源的问题,结果表明当所有组包含相同数量的玩家时,最大化幸福感的分配可能是无嫉妒的,而通过随机分配的机制可以满足近似无嫉妒的要求。
Jun, 2017
本文研究了将不可拆分物品分配给具有加法偏好的代理人的基本问题。我们考虑 eliciting 每个代理人仅排名她最喜欢的 $k$ 个物品,而不是她的完整基数估值。我们表征了实现嫉妒 - 自由度高达一个良好且近似最大值共享保证的 $k$ 值。我们还分析了由于缺乏完整信息而产生的社会福利的乘法损失,无论是否满足公平要求。
May, 2021
本文研究在具有加性估值的代理之间以公平的方式分配一组不可分割的物品的问题,通过 EFx 公平的概念,我们证明了对于三个代理,总是存在一个 EFx 分配,同时证实了 Caragiannis 等人的猜想,并展示出一个实例,其中对于具有三个代理的部分 EFx 分配(某些物品未分配),其 Nash welfare 比任何完全 EFx 分配的 Nash welfare 要高。
Feb, 2020
本论文主要研究如何在给定的特定限制条件下,实现资源公平配置问题,提出了一种有效的算法来计算两个中心公平概念,即 EF1 和 MMS,在满足限制条件的状态下,特别地,证明了在所有代理具有相同加性估值的情况下,即使存在限制条件,仍然可以有效地计算出 EF1 分配。
Apr, 2018
本文介绍和分析适用于配有权重的代理商在不可分配的物品的分配中的公平概念。我们提出了两种权重嫉妒自由概念:强权重嫉妒自由和弱权重嫉妒自由。我们证明,满足强权重嫉妒自由和帕累托最优的分配总是存在且可以在伪多项式时间内计算。此外,我们还建立了一个轮换选择算法的泛化版本,可以在多项式时间内为任意数量的代理商产生具有强权重嫉妒自由的分配。最后,我们强调了权重公平分配比其无权重对应更为复杂。
Sep, 2019
本文从公平分配的角度出发,讨论了将物品分配给代理人组的问题,并提出了群体嫉妒和群体帕累托效率等新概念,探讨了这些新群体性质的公理化分类和其在不同社会福利下的表现。
Jun, 2020
研究分配一组不可分割商品给一组代理商的公平和高效问题,当代理商对商品具有可加性评估时,存在一种同时满足 EF1 和 PO 的最大 Nash 社会福利目标的分配,并提出了一个类似于假多项式时间算法的方法用于寻找 EF1 和 PO。
Jul, 2017
该研究研究了不可分割商品的分配存在性,并在底层项图中添加约束来确保连通性;当该图是路径并且效用函数是可单调的时,我们证明了最多四个代理商可以获得 EF1 分配,而任意数量的代理商都可以获得 EF2 分配。
Aug, 2018