公平分配
我们提出了一种离散和有界的无嫉妒协议,可为任何数量的代理找到无嫉妒分配。即使我们没有完全运行我们的协议,我们也可以在至多 $n^3 {(n^2)}^n$ 个查询中找到一个部分分配,以实现比例分配和无嫉妒性。最后,我们还表明,可以在最多 $n^3 {(n^2)}^n$ 个查询中计算一个无嫉妒的部分分配,使得每个代理人都获得至少糕点总价值的 $1 / (3n)$ 的连接块。
Apr, 2016
这篇研究论文主要研究公平地分配一组异质可分资源给具有不同偏好的个体的问题,关注的是资源对应于一张连接图的边缘,每个个体必须被分配一块连通的图形,所考虑的公平概念是经典的无嫉妒性。该问题是 NP 完全的,我们分析了该问题相对于两个自然复杂度度量的复杂性:个体数量和图中边缘的数量。虽然即使对于只有两名个体的实例问题仍然是 NP 困难的,但我们根据图的结构性质给出了当个体数量是常数时该问题复杂性的两分法特征。对于后一种情况,我们设计了一个多项式时间算法,当图形具有常数数量的边时。
Dec, 2023
本文研究如何在分类任务中实现公平分配,重点是探讨基于小样本能否实现 envy-free classification 并提出了一个新的方案,使用低 Natarajan 维度的确定性分类器的混合模型,可以在高概率下实现几乎 envy-free 分类。
Sep, 2018
研究了如何使用 envy-freeness 的松弛,公平地分配不可拆分物品给多组代理人。同时,我们考虑了对代理人估值的不同假设,对于任意单调,响应和可加估值,我们的结果都是具有普遍意义的。此外,我们还引入了一种新模型,其中代理人事先不被划分为不同组,而是与物品分配一起选择划分。
Jan, 2019
本文研究公平分配中的 “无嫉妒性” 概念,在不能平分的资源分配中,提出了 “去除任意一份资源后,任何玩家都不会愿意交换自己捆绑的价值”(EFX)的公平性条件。使用 Leximin 解决方案证明了在几个情境中都有 EFX 分配的存在性,我们的研究表明,在不同类的玩家估值的不能平分的财产的公平分配中,有着丰富的研究课题。
Jul, 2017
本文研究了将不可拆分物品分配给具有加法偏好的代理人的基本问题。我们考虑 eliciting 每个代理人仅排名她最喜欢的 $k$ 个物品,而不是她的完整基数估值。我们表征了实现嫉妒 - 自由度高达一个良好且近似最大值共享保证的 $k$ 值。我们还分析了由于缺乏完整信息而产生的社会福利的乘法损失,无论是否满足公平要求。
May, 2021
本文通过随机分配机制在具有多个参与方的背景下研究了公平分配资源的问题,结果表明当所有组包含相同数量的玩家时,最大化幸福感的分配可能是无嫉妒的,而通过随机分配的机制可以满足近似无嫉妒的要求。
Jun, 2017