In this paper, we consider how to fairly allocate $m$ indivisible chores to a set of $n$ (asymmetric) agents. As exact fairness cannot be guaranteed, motivated by the extensive study of EF1, EFX and PROP1 allocations, we propose and study {\em proportionality up to any item} (PROPX), and show that a PROPX allocation always exists. We argue that PROPX might be a more reliable relaxation for proportionality in practice than the commonly studied maximin share fairness (MMS) by the facts that (1) MMS allocations may not exist even with three agents, but PROPX allocations always exist even for the weighted case when agents have unequal obligation shares; (2) any PROPX allocation ensures 2-approximation for MMS, but an MMS allocation can be as bad as $\Theta(n)$-approximation to PROPX. We propose two algorithms to compute PROPX allocations and each of them has its own merits. Our first algorithm is based on a recent refinement for the well-known procedure -- envy-cycle elimination, where the returned allocation is simultaneously PROPX and $4/3$-approximate MMS. A by-product result is that an exact EFX allocation for indivisible chores exists if all agents have the same ordinal preference over the chores, which might be of independent interest. The second algorithm is called bid-and-take, which applies to the weighted case. Furthermore, we study the price of fairness for (weighted) PROPX allocations, and show that the algorithm computes allocations with the optimal guarantee on the approximation ratio to the optimal social welfare without fairness constraints.


翻译:在本文中,我们考虑如何公平地将美元不可分割的杂务分配到一组美元(非对称)代理商。由于对EF1、EFX和PROP1分配进行广泛研究的动机无法保证准确的公平性,我们提议并研究PROPX分配比例与任何项目的相称性(PROPX),并表明PROPX分配总是存在的。我们认为,PROPX在实际中比通常研究的“最大分享公平性(MMS)”更可靠地放松相称性,因为以下事实:(1)即使在三个代理商中,MMS分配的公平性也可能不存在,但PROPX分配的公平性即使在代理人有不平等的债务份额的情况下,即使加权案件也总是存在PROPX分配分配;(2)任何PROPX分配确保MS分配的2比额接近2,但MMS分配的比值可能不如$Theta(n)$-appormission。 我们建议两种算法来计算PROPX分配,而每一项都有其自身的优点。我们的第一次算法基于最近对众所周知的程序的改进 -- 嫉妒-循环消除,在其中,即回分配是PRO-周期内, ROX分配是PX的比值比值比值,如果回分配是PROX的比值比值比值比价的比值比值比值比值比值比值比值比值比值比值比价比值,那么的比值比值比值比值比值比值比值比值比值比值比值比值比值比值比值比值比值比值比值比值比值是所有。

0
下载
关闭预览

相关内容

【2020新书】Python文本分析,104页pdf
专知会员服务
98+阅读 · 2020年12月23日
专知会员服务
123+阅读 · 2020年9月8日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【推荐】(Keras)LSTM多元时序预测教程
机器学习研究会
24+阅读 · 2017年8月14日
Arxiv
0+阅读 · 2021年5月14日
Arxiv
0+阅读 · 2021年5月14日
Arxiv
0+阅读 · 2021年5月13日
Arxiv
0+阅读 · 2021年5月13日
Arxiv
0+阅读 · 2021年5月13日
VIP会员
相关VIP内容
【2020新书】Python文本分析,104页pdf
专知会员服务
98+阅读 · 2020年12月23日
专知会员服务
123+阅读 · 2020年9月8日
深度强化学习策略梯度教程,53页ppt
专知会员服务
178+阅读 · 2020年2月1日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
151+阅读 · 2019年10月12日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
revelation of MONet
CreateAMind
5+阅读 · 2019年6月8日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【推荐】(Keras)LSTM多元时序预测教程
机器学习研究会
24+阅读 · 2017年8月14日
相关论文
Top
微信扫码咨询专知VIP会员