Weighted EF1 Allocations for Indivisible Chores
Weighted EF1 Allocations for Indivisible Chores
复制标题
不可分割杂务的加权 EF1 分配
DOI：
--
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Shengwei Zhou
中科院分区：
文献类型：
--
作者：
Xiaowei Wu;Cong Zhang;Shengwei Zhou
我们研究如何公平地分配一组不可分割的家务一组代理，其中每个代理i ∈ N有一个可加性的成本函数ci和一个非负的权重wi，代表其承担家务的义务。我们考虑一个项目（WEF 1）的加权无嫉妒的公平性概念，这要求每个代理i在去除最昂贵的项目e后的加权成本ci（Xi {e}）/wi对于任何其他代理j最多为ci（Xj）/wj。虽然WEF 1分配货物可以在多项式时间内计算（Chakraborty et al. TEAC 2021），但它的存在对于家务仍然是一个悬而未决的问题。在这项工作中，我们肯定地回答了这个开放的问题。我们表明，WEF 1分配家务总是存在的，可以在多项式时间内计算。
We study how to fairly allocate a set of indivisible chores to a group of agents, where each agent i ∈ N has an additive cost function ci and a non-negative weight wi that represents its obligation for undertaking the chores. We consider the fairness notion of weighted envy-freeness up to one item (WEF1), which requires that the weighted cost ci(Xi {e})/wi of each agent i after removing the most costly item e is at most ci(Xj)/wj for any other agent j. While WEF1 allocations for goods can be computed in polynomial time (Chakraborty et al. TEAC 2021), its existence for chores is still an open problem. In this work, we answer this open problem affirmatively. We show that WEF1 allocations for chores always exist and can be computed in polynomial time.
最大纳什福利和有关 EFX 的其他故事
DOI：
10.24963/ijcai.2020/4
发表时间：
2020
期刊：
--
影响因子：
--
作者：
Amanatidis G
通讯作者：
Amanatidis G
DOI：
10.1609/aaai.v36i5.20436
发表时间：
2022
期刊：
Proceedings of the AAAI Conference on Artificial Intelligence
影响因子：
--
作者：
Garg, Jugal;Murhekar, Aniket;Qin, John
通讯作者：
Qin, John
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