改进无嫉妒匹配算法
研究针对代理人与物体之间的离散分配问题,使用分数或随机分配的随机支配关系系统地定义了不同的比例公正和不嫉妒的概念,提出了多个公正概念并设计了多项式时间算法,扩展到不平等权利的情况,并且提出了一些公正概念,其中最优比例和最优弱比例是可取的。
Dec, 2013
我们提出了一种离散和有界的无嫉妒协议,可为任何数量的代理找到无嫉妒分配。即使我们没有完全运行我们的协议,我们也可以在至多$n^3{(n^2)}^n$个查询中找到一个部分分配,以实现比例分配和无嫉妒性。最后,我们还表明,可以在最多$n^3{(n^2)}^n$个查询中计算一个无嫉妒的部分分配,使得每个代理人都获得至少糕点总价值的$1 / (3n)$ 的连接块。
Apr, 2016
研究对不可分割物品的公平分配的查询复杂度。 发现对于两个代理人和任意单调效用的情况,可以使用对数数量的查询计算满足envy-freeness最多一个good (EF1)的分配,并且这个logarithmic查询复杂性界限也适用于具有可加性效用的三个代理人,但是需要使用polylogarithmic界限来满足单增效用的情况。同时,证明即使只有两个代理人具有相同可加效用时,计算满足envy-freeness和EFX(envy-freeness up to any good)之一的分配需要线性数量的查询。
Jul, 2018
本文介绍和分析适用于配有权重的代理商在不可分配的物品的分配中的公平概念。我们提出了两种权重嫉妒自由概念:强权重嫉妒自由和弱权重嫉妒自由。我们证明,满足强权重嫉妒自由和帕累托最优的分配总是存在且可以在伪多项式时间内计算。此外,我们还建立了一个轮换选择算法的泛化版本,可以在多项式时间内为任意数量的代理商产生具有强权重嫉妒自由的分配。最后,我们强调了权重公平分配比其无权重对应更为复杂。
Sep, 2019
研究如何公平高效地分配不可分割物品给不同的需求者,考虑到嫉妒与比例问题,尝试提出了 Pareto 最优的多项式时间算法,同时维护各种类型的good/bad需求和纯商品和混合商品状况下的各项情形。
Feb, 2022
本研究在经典的分配问题基础上,研究了基于社交网络的分配问题,目标是通过最小化代理人之间的嫉妒程度来实现公平分配;同时,该研究还贡献了基于图结构的问题结构与计算结果,提出了一个名为“可分离性”的概念,可以在某些图结构中实现高效的最优分配算法。
Jan, 2023
这篇研究论文主要研究公平地分配一组异质可分资源给具有不同偏好的个体的问题,关注的是资源对应于一张连接图的边缘,每个个体必须被分配一块连通的图形,所考虑的公平概念是经典的无嫉妒性。该问题是NP完全的,我们分析了该问题相对于两个自然复杂度度量的复杂性:个体数量和图中边缘的数量。虽然即使对于只有两名个体的实例问题仍然是NP困难的,但我们根据图的结构性质给出了当个体数量是常数时该问题复杂性的两分法特征。对于后一种情况,我们设计了一个多项式时间算法,当图形具有常数数量的边时。
Dec, 2023