公平分配:可行性,主导和激励
研究针对代理人与物体之间的离散分配问题,使用分数或随机分配的随机支配关系系统地定义了不同的比例公正和不嫉妒的概念,提出了多个公正概念并设计了多项式时间算法,扩展到不平等权利的情况,并且提出了一些公正概念,其中最优比例和最优弱比例是可取的。
Dec, 2013
本文研究了在 n 个代理人中公平分配不可分性商品的问题,提出了比最小限度份额更强的公平性概念:团体最小限度份额保证。我们证明,在特定情况下,总是存在 GMMS 分配,在加性估值模型下存在近似 GMMS 分配,并提出了一个多项式时间算法来找到这样的分配。此外,我们表明 GMMS 可能导致近似无嫉妒的分配。
Nov, 2017
本论文主要研究如何在给定的特定限制条件下,实现资源公平配置问题,提出了一种有效的算法来计算两个中心公平概念,即 EF1和MMS,在满足限制条件的状态下,特别地,证明了在所有代理具有相同加性估值的情况下,即使存在限制条件,仍然可以有效地计算出 EF1 分配。
Apr, 2018
研究对不可分割物品的公平分配的查询复杂度。 发现对于两个代理人和任意单调效用的情况,可以使用对数数量的查询计算满足envy-freeness最多一个good (EF1)的分配,并且这个logarithmic查询复杂性界限也适用于具有可加性效用的三个代理人,但是需要使用polylogarithmic界限来满足单增效用的情况。同时,证明即使只有两个代理人具有相同可加效用时,计算满足envy-freeness和EFX(envy-freeness up to any good)之一的分配需要线性数量的查询。
Jul, 2018
本论文提出了一种以人口为基础的近似公平性概念,重点研究了最大最小份额的分配,并证明了在9个代理人以内,可以使用多项式时间算法来分配最大最小份额的$rac{2}{3} $,从而提高了现有的保证值,并在合成数据上进行了实证实验。
May, 2021
本文研究了将不可拆分物品分配给具有加法偏好的代理人的基本问题。我们考虑 eliciting 每个代理人仅排名她最喜欢的 $k$ 个物品,而不是她的完整基数估值。我们表征了实现嫉妒 -自由度高达一个良好且近似最大值共享保证的 $k$ 值。我们还分析了由于缺乏完整信息而产生的社会福利的乘法损失,无论是否满足公平要求。
May, 2021
研究如何公平高效地分配不可分割物品给不同的需求者,考虑到嫉妒与比例问题,尝试提出了 Pareto 最优的多项式时间算法,同时维护各种类型的good/bad需求和纯商品和混合商品状况下的各项情形。
Feb, 2022
研究基于 matroid rank 值的不可分配物品的公平分配问题,提出了基于 Yankee Swap 方法的算法,该算法能够计算出可证明的公平和有效的 Lorenz 支配分配,相比于现有的多项式时间算法,该方法具有易于理解和可扩展的优势,有助于向任何实际的公平分配场景的应用。
Jun, 2022
研究在具有双值次模估值的代理人之间公平分配不可分割物品的问题,并提出了一种基于Yankee Swap机制的简单顺序算法框架,可用于计算多种解决方案概念,包括leximin,max Nash welfare(MNW)和$p$-mean welfare最大化分配,当$a$除以$b$时;对于两个公认的特性-羡慕无阻和最大收益份额保证,我们进一步检查leximin和MNW分配。
Feb, 2023