Fair Division of Indivisible Chores with Weighted and Prioritized Agents
摘要
We consider the problem of fair division of chores with weigh-ted and prioritized agents. The well-known fact that envy-freeness (EF) allocations of indivisible chores may not exist has led to the relaxation of EF known as envy-free up to one item (EF1). Weights can characterize the rights or responsibilities of agents, and Chakraborty et al. [7] extended EF1 to weighted envy-free up to one item (WEF1). “Priority” can compensate for unfairness experienced by agents in previous allocations, and Bu et al. [4] introduced a new fairness notion called \(EF_{PRIOR}\) , which requires that priority agents do not envy non-priority agents, while the entire allocation remains EF1. Recently, Li et al. [13] extended \(EF_{PRIOR}\) to \(WEF_{PRIOR}\) , requiring that priority agents do not envy non-priority agents, while the entire allocation remains WEF1. They studied the existence and computability of \(WEF_{PRIOR}\) in the context of goods allocation. Inspired by this, we investigate the existence of \(WEF_{PRIOR}\) allocations in the context of chore situations. We demonstrate that when agents’ cost functions are additive, the \(WEF_{PRIOR}\) allocation can be computed in polynomial time.