多件公平分割
本文通过随机分配机制在具有多个参与方的背景下研究了公平分配资源的问题,结果表明当所有组包含相同数量的玩家时,最大化幸福感的分配可能是无嫉妒的,而通过随机分配的机制可以满足近似无嫉妒的要求。
Jun, 2017
我们提出了一种离散和有界的无嫉妒协议,可为任何数量的代理找到无嫉妒分配。即使我们没有完全运行我们的协议,我们也可以在至多 $n^3 {(n^2)}^n$ 个查询中找到一个部分分配,以实现比例分配和无嫉妒性。最后,我们还表明,可以在最多 $n^3 {(n^2)}^n$ 个查询中计算一个无嫉妒的部分分配,使得每个代理人都获得至少糕点总价值的 $1 / (3n)$ 的连接块。
Apr, 2016
本文研究了将不可拆分物品分配给具有加法偏好的代理人的基本问题。我们考虑 eliciting 每个代理人仅排名她最喜欢的 $k$ 个物品,而不是她的完整基数估值。我们表征了实现嫉妒 - 自由度高达一个良好且近似最大值共享保证的 $k$ 值。我们还分析了由于缺乏完整信息而产生的社会福利的乘法损失,无论是否满足公平要求。
May, 2021
研究的是蛋糕切割问题的询问复杂度,同时给出了计算近似无嫉妒、完美和公平分配的下限和上限,其中下限在计算 n=3 个玩家之间的连通无嫉妒分配以及 n=2 个玩家之间的完美和公平分配方面非常紧密,还阐明了移动刀具程序的形式化方法,并证明了这个大的子类可以在 Robertson-Webb 的询问模型中以任意小的误差高效地模拟。
May, 2017
本文研究如何在分类任务中实现公平分配,重点是探讨基于小样本能否实现 envy-free classification 并提出了一个新的方案,使用低 Natarajan 维度的确定性分类器的混合模型,可以在高概率下实现几乎 envy-free 分类。
Sep, 2018
本文研究公平分配中的 “无嫉妒性” 概念,在不能平分的资源分配中,提出了 “去除任意一份资源后,任何玩家都不会愿意交换自己捆绑的价值”(EFX)的公平性条件。使用 Leximin 解决方案证明了在几个情境中都有 EFX 分配的存在性,我们的研究表明,在不同类的玩家估值的不能平分的财产的公平分配中,有着丰富的研究课题。
Jul, 2017