1053. Fairness Criteria for Allocating Indivisible Chores: Connections and Efficiencies
Invited abstract in session HE-20: Design and Evaluation of Approximations, cluster Combinatorial Optimization.
Thursday, 16:15-17:45Room: FENH106
Authors (first author is the speaker)
| 1. | Bo Chen
|
| Warwick Business School, University of Warwick | |
| 2. | Ankang Sun
|
| University of Warwick | |
| 3. | Xuan Vinh Doan
|
| Warwick Business School, University of Warwick |
Abstract
We study several fairness notions in allocating indivisible chores (i.e., items with non-positive utilities) to agents, who have additive and submodular cost functions. The fairness criteria are envy-free up to any item (EFX), envy-free up to one item (EF1), maximin share (MMS), and pairwise maximin share (PMMS), proposed as relaxations of envy-freeness. For allocations under each fairness criterion, we establish their approximation guarantee for other fairness criteria. Under the additive setting, our results show strong connections between these fairness criteria and, at the same time, reveal intrinsic differences between allocations of goods (i.e., items with positive utilities) and chores. Strong relationships cannot be inherited by the sub-modular setting, however, where PMMS and MMS are no longer relaxations of envy-freeness, and, even worse, few non-trivial guarantees exist. Furthermore, we investigate efficiency loss under these fairness constraints and establish their prices of fairness.
Keywords
- Agent Systems
- Approximation Algorithms
- Combinatorial Optimization
Status: accepted
Back to the list of papers