Almost (Weighted) Proportional Allocations for Indivisible Chores✱✱
Almost (Weighted) Proportional Allocations for Indivisible Chores✱✱
复制标题
几乎（加权）按比例分配不可分割的杂务✱✱
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Xiaowei Wu
中科院分区：
文献类型：
--
作者：
B. Li;Yingkai Li;Xiaowei Wu
在本文中，我们研究了如何公平地分配一组不可分割的家务，一些（不对称）代理与附加成本函数。我们认为公平的概念（加权）比例的任何项目（PROPX），并表明（加权）PROPX分配总是存在的，可以有效地计算。我们还考虑了部分信息设置，算法只能使用代理的顺序偏好。我们设计的算法，实现2-近似（加权）PROPX，近似比是最佳的。我们通过调查（加权）PROPX和其他公平概念（如最大化份额和AnyPrice份额）之间的关系，并通过强制分配（加权）PROPX来限制社会福利损失，从而补充了算法结果。
In this paper, we study how to fairly allocate a set of indivisible chores to a number of (asymmetric) agents with additive cost functions. We consider the fairness notion of (weighted) proportionality up to any item (PROPX), and show that a (weighted) PROPX allocation always exists and can be computed efficiently. We also consider the partial information setting, where the algorithms can only use agents’ ordinal preferences. We design algorithms that achieve 2-approximate (weighted) PROPX, and the approximation ratio is optimal. We complement the algorithmic results by investigating the relationship between (weighted) PROPX and other fairness notions such as maximin share and AnyPrice share, and bounding the social welfare loss by enforcing the allocations to be (weighted) PROPX.
最大纳什福利和有关 EFX 的其他故事
DOI：
10.24963/ijcai.2020/4
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Amanatidis G
通讯作者：
Amanatidis G
EFX 存在三个代理
DOI：
10.1145/3391403.3399511
发表时间：
2020
期刊：
EC '20: Proceedings of the 21st ACM Conference on Economics and Computation
影响因子：
--
作者：
Chaudhury, Bhaskar R.;Garg, Jugal;Mehlhorn, Kurt
通讯作者：
Mehlhorn, Kurt