Weighted EF1 Allocations for Indivisible Chores
Xiaowei Wu, Cong Zhang, Shengwei Zhou
Abstract
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.