Abstract
In a web-based review platform, papers from various research fields must be assigned to a group of reviewers. Each paper has an inherent cost, which represents the effort required for reading and evaluating it (e.g., the paper's length). Reviewers can bid on papers they are interested in, and if they are assigned a paper they have bid on, no cost is incurred. Otherwise, the inherent cost $c(e)$ for paper $e$ applies. We capture this with a model of restricted additive costs: every item $e$ has a cost $c(e)$, and each agent either incurs $0$ or $c(e)$ for $e$. In this work, we study how to allocate such chores fairly and efficiently. We propose an algorithm for computing allocations that are both EFX and MMS. Furthermore, we show that our algorithm achieves a $2$-approximation of the optimal social cost, and the approximation ratio is optimal. We also show that slightly weaker fairness guarantees can be obtained if one requires the algorithm to run in polynomial time.
Introduction
Fair division research often focuses on "goods"—items that agents desire. However, many real-world scenarios involve "chores"—unpleasant tasks that must be distributed among a group. Examples include assigning peer reviews to researchers or server maintenance tasks to engineers. The goal is to find an allocation that is both fair and efficient.
The gold standard for fairness in indivisible item allocation is Envy-Freeness (EF), where no agent prefers another's bundle to their own. Since EF allocations do not always exist for indivisible items, researchers turn to relaxations:
- EFX (Envy-Free up to any item): An agent does not envy another after removing any chore from their own bundle. This is often considered the strongest relaxation of envy-freeness.
- MMS (Maximin Share): An agent receives a bundle with a cost no greater than what they could guarantee themselves if they were the one to partition all chores into $n$ bundles and then received the worst one.
This paper investigates these properties within the restricted additive cost model. In this setting, each chore $e$ has a base cost $c(e)$, and for each agent $i$, the cost of chore $e$ is either $c(e)$ or $0$.
The Zero-Cost Trap and Efficiency
A key insight of this work is the "Zero-Cost Trap." In the restricted additive model, if an agent receives a chore they value at $0$, the EFX requirement becomes significantly stricter. Because removing a zero-cost item does not decrease the agent's perceived total cost, they must essentially be fully envy-free toward others to satisfy the "up to any item" condition.
Furthermore, the paper demonstrates a fundamental tension between EFX and Pareto Optimality (PO). In some instances, maintaining EFX requires assigning a chore to an agent who finds it difficult, even if another agent could perform it for free. This leads to the concept of the "Price of EFX"—the ratio of the social cost of a fair allocation to the minimum possible social cost. The authors prove this price is exactly 2 in the restricted additive setting, and their algorithm achieves this bound.
Algorithmic Framework
The authors propose a three-phase algorithm to achieve simultaneous EFX and MMS guarantees:
- Phase 1: Identical Costs. The algorithm first considers chores that everyone finds costly ($M^+$). It starts with an MMS partition and iteratively reallocates chores from high-cost bundles to low-cost bundles until the partition is EFX. This is proven to terminate using a potential function argument.
- Phase 2: Zero-Cost Integration. Chores that some agents find "free" ($M^0$) are then integrated. Agents take turns adding these to their preferred bundles, a process that requires careful management to avoid violating the stricter EFX conditions triggered by zero-cost items.
- Phase 3: Matching. Finally, the algorithm uses a matching-based approach to assign the resulting bundles to agents, ensuring that every agent receives a bundle they find both EFX and MMS-feasible.
Key Results and Complexity
The primary contribution is the proof that an allocation that is both EFX and MMS always exists for restricted additive chores. The proposed algorithm achieves a 2-approximation of the optimal social cost, which is shown to be the best possible ratio.
Recognizing that finding an optimal MMS partition is NP-hard, the authors also provide a polynomial-time variant. By utilizing a "Longest Processing Time First" (LPT) scheduling approach in Phase 1, they obtain an allocation that is EFX and a 4/3-approximation of MMS. Additionally, they show that if the fairness requirement is relaxed to EF1 (Envy-Free up to one item), full Pareto Optimality and MMS can be achieved simultaneously in polynomial time.
Conclusion
This work provides the first algorithm to simultaneously guarantee EFX and MMS for chores in the restricted additive setting while maintaining optimal efficiency bounds. Future research remains open regarding the existence of EFX for general additive costs and the dual problem of allocating goods under similar restricted valuations.
Summary updated