网络公平的蛋糕切分
本文考虑在一个附加约束条件下的不可分割物品的公平分配,该约束条件表示物品之间的关系构成了一张无向图,并且每个代理人所分配的份额必须形成该图的一个连通子图。我们关注具有可加效用的代理人,并考虑几种常见的公平分配解概念,例如比例、不嫉妒性和最小份额保证。尽管在一般情况下按照这些解概念找到好的分配是计算上困难的,但我们设计了对于简单结构的基础图和 / 或代理人数量,或者更宽松地说,代理人种类数量较少的特殊情况下的有效算法。特别地,尽管在一般情况下存在不存在的结果,但我们证明了对于无环图,存在最小份额分配并且可以有效找到。
May, 2017
我们提出了一种离散和有界的无嫉妒协议,可为任何数量的代理找到无嫉妒分配。即使我们没有完全运行我们的协议,我们也可以在至多 $n^3 {(n^2)}^n$ 个查询中找到一个部分分配,以实现比例分配和无嫉妒性。最后,我们还表明,可以在最多 $n^3 {(n^2)}^n$ 个查询中计算一个无嫉妒的部分分配,使得每个代理人都获得至少糕点总价值的 $1 / (3n)$ 的连接块。
Apr, 2016
这篇研究论文主要研究公平地分配一组异质可分资源给具有不同偏好的个体的问题,关注的是资源对应于一张连接图的边缘,每个个体必须被分配一块连通的图形,所考虑的公平概念是经典的无嫉妒性。该问题是 NP 完全的,我们分析了该问题相对于两个自然复杂度度量的复杂性:个体数量和图中边缘的数量。虽然即使对于只有两名个体的实例问题仍然是 NP 困难的,但我们根据图的结构性质给出了当个体数量是常数时该问题复杂性的两分法特征。对于后一种情况,我们设计了一个多项式时间算法,当图形具有常数数量的边时。
Dec, 2023
研究的是蛋糕切割问题的询问复杂度,同时给出了计算近似无嫉妒、完美和公平分配的下限和上限,其中下限在计算 n=3 个玩家之间的连通无嫉妒分配以及 n=2 个玩家之间的完美和公平分配方面非常紧密,还阐明了移动刀具程序的形式化方法,并证明了这个大的子类可以在 Robertson-Webb 的询问模型中以任意小的误差高效地模拟。
May, 2017
本文研究如何在分类任务中实现公平分配,重点是探讨基于小样本能否实现 envy-free classification 并提出了一个新的方案,使用低 Natarajan 维度的确定性分类器的混合模型,可以在高概率下实现几乎 envy-free 分类。
Sep, 2018
本研究在经典的分配问题基础上,研究了基于社交网络的分配问题,目标是通过最小化代理人之间的嫉妒程度来实现公平分配;同时,该研究还贡献了基于图结构的问题结构与计算结果,提出了一个名为 “可分离性” 的概念,可以在某些图结构中实现高效的最优分配算法。
Jan, 2023