Yankee Swap:用于矩阵排名估值的快速、简单且公平的分配机制
研究针对代理人与物体之间的离散分配问题,使用分数或随机分配的随机支配关系系统地定义了不同的比例公正和不嫉妒的概念,提出了多个公正概念并设计了多项式时间算法,扩展到不平等权利的情况,并且提出了一些公正概念,其中最优比例和最优弱比例是可取的。
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
本文介绍和分析适用于配有权重的代理商在不可分配的物品的分配中的公平概念。我们提出了两种权重嫉妒自由概念:强权重嫉妒自由和弱权重嫉妒自由。我们证明,满足强权重嫉妒自由和帕累托最优的分配总是存在且可以在伪多项式时间内计算。此外,我们还建立了一个轮换选择算法的泛化版本,可以在多项式时间内为任意数量的代理商产生具有强权重嫉妒自由的分配。最后,我们强调了权重公平分配比其无权重对应更为复杂。
Sep, 2019
本论文提出了一种以人口为基础的近似公平性概念,重点研究了最大最小份额的分配,并证明了在9个代理人以内,可以使用多项式时间算法来分配最大最小份额的$rac{2}{3} $,从而提高了现有的保证值,并在合成数据上进行了实证实验。
May, 2021
研究如何公平高效地分配不可分割物品给不同的需求者,考虑到嫉妒与比例问题,尝试提出了 Pareto 最优的多项式时间算法,同时维护各种类型的good/bad需求和纯商品和混合商品状况下的各项情形。
Feb, 2022
研究了无货币转移的情况下,将一组不可分割物品公平地分配给 n 个权利平等的代理商,其中每个代理商都有一个来自某个估值函数类的估值。研究表明,适当的“份额”是可以实现的,需要将其定义为可行实现的问题,并确定计算可行最大收益份额的算法。
May, 2022
研究在具有双值次模估值的代理人之间公平分配不可分割物品的问题,并提出了一种基于Yankee Swap机制的简单顺序算法框架,可用于计算多种解决方案概念,包括leximin,max Nash welfare(MNW)和$p$-mean welfare最大化分配,当$a$除以$b$时;对于两个公认的特性-羡慕无阻和最大收益份额保证,我们进一步检查leximin和MNW分配。
Feb, 2023
通过学习,设计公平分配机制,以比例公平性为基准,解决了一次性分配机制的学习问题,同时提出了可行的方法来度量机制的可利用性,并通过数据控制公平性和可利用性之间的权衡,提出了两种近似比例公平机制,分别是ExPF-Net和ExS-Net,通过大量的数值模拟验证了这些机制的有效性和鲁棒性。
Nov, 2023