Average Envy-freeness for Indivisible Items
Average Envy-freeness for Indivisible Items
复制标题
不可分割物品的平均无嫉妒度
DOI：
10.1145/3617694.3623229
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Xia, Lirong
中科院分区：
文献类型：
--
作者：
Han, Qishen;Tao, Biaoshuai;Xia, Lirong
在公平分配应用中，代理人可能有不平等的权利，反映他们不同的贡献。此外，代理人的贡献可能取决于分配本身。以前的公平性概念设计的代理人具有相等或预先确定的权利，这些合作分配scenaries.We提出了一个新的公平性概念的平均无嫉妒（AEF），其中嫉妒的代理人定义的平均值的项目在捆绑。平均无嫉妒提供了一个合理的比较代理人之间的基础上，他们收到的项目，并反映了他们的权利。我们研究了寻找AEF的复杂性及其松弛性，平均无嫉妒度为一项（AEF-1）。虽然决定AEF分配是否存在是NP完全的，但AEF-1分配保证存在并且可以在多项式时间内计算。我们还研究了配额分配，即对捆绑包大小的限制。我们证明，找到一个AEF-1分配满足配额是NP-难的。然而，在代理数量固定的情况下，我们提出了多项式时间算法来找到一个AEF-1分配与配额的二进制估值和近似AEF-1分配与配额的一般估值。
In fair division applications, agents may have unequal entitlements reflecting their different contributions. Moreover, the contributions of agents may depend on the allocation itself. Previous fairness notions designed for agents with equal or pre-determined entitlements fail to characterize fairness in these collaborative allocation scenarios.We propose a novel fairness notion of average envy-freeness (AEF), where the envy of agents is defined on the average value of items in the bundles. Average envy-freeness provides a reasonable comparison between agents based on the items they receive and reflects their entitlements. We study the complexity of finding AEF and its relaxation, average envy-freeness up to one item (AEF-1). While deciding if an AEF allocation exists is NP-complete, an AEF-1 allocation is guaranteed to exist and can be computed in polynomial time. We also study allocation with quotas, i.e. restrictions on the sizes of the bundles. We prove that finding an AEF-1 allocation satisfying quotas is NP-hard. Nevertheless, in the instances with a fixed number of agents, we propose polynomial-time algorithms to find an AEF-1 allocation with quotas for binary valuation and an approximated AEF-1 allocation with quotas for general valuation.
登录
查看更多内容
用于计算帕累托最优且几乎成比例分配的多项式时间算法
DOI：
10.1016/j.orl.2020.07.005
发表时间：
2019
期刊：
Oper. Res. Lett.
影响因子：
--
作者：
H. Aziz;H. Moulin;Fedor Sandomirskiy
通讯作者：
Fedor Sandomirskiy
不可分割杂务的加权 EF1 分配
DOI：
--
发表时间：
2023
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
Xiaowei Wu;Cong Zhang;Shengwei Zhou
通讯作者：
Shengwei Zhou
几乎（加权）按比例分配不可分割的杂务✱✱
DOI：
--
发表时间：
2021
期刊：
The Web Conference
影响因子：
--
作者：
B. Li;Yingkai Li;Xiaowei Wu
通讯作者：
Xiaowei Wu
具有任意权利的代理的公平份额分配
DOI：
--
发表时间：
2021
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
Moshe Babaioff;Tomer Ezra;U. Feige
通讯作者：
U. Feige
DOI：
10.1016/j.artint.2021.103633
发表时间：
2021-11
期刊：
Artif. Intell.
影响因子：
--
作者：
M. Ghodsi;M. Hajiaghayi;Masoud Seddighin;Saeed Seddighin;Hadi Yami
通讯作者：
M. Ghodsi;M. Hajiaghayi;Masoud Seddighin;Saeed Seddighin;Hadi Yami