Algorithms for Max-Min Share Fair Allocation of Indivisible Chores

H. Aziz, G. Rauchecker, G. Schryen, T. Walsh, in: Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), 2017, pp. 1–7.

Download
OA 732.00 KB
Conference Paper | English
Author
; ; ;
Abstract
We consider Max-min Share (MmS) fair allocations of indivisible chores (items with negative utilities). We show that allocation of chores and classical allocation of goods (items with positive utilities) have some fundamental connections but also differences which prevent a straightforward application of algorithms for goods in the chores setting and viceversa. We prove that an MmS allocation does not need to exist for chores and computing an MmS allocation - if it exists - is strongly NP-hard. In view of these non-existence and complexity results, we present a polynomial-time 2-approximation algorithm for MmS fairness for chores. We then introduce a new fairness concept called optimal MmS that represents the best possible allocation in terms of MmS that is guaranteed to exist. We use connections to parallel machine scheduling to give (1) a polynomial-time approximation scheme for computing an optimal MmS allocation when the number of agents is fixed and (2) an effective and efficient heuristic with an ex-post worst-case analysis.
Publishing Year
Proceedings Title
Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)
Page
1-7
LibreCat-ID

Cite this

Aziz H, Rauchecker G, Schryen G, Walsh T. Algorithms for Max-Min Share Fair Allocation of Indivisible Chores. In: Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17). ; 2017:1-7.
Aziz, H., Rauchecker, G., Schryen, G., & Walsh, T. (2017). Algorithms for Max-Min Share Fair Allocation of Indivisible Chores. In Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17) (pp. 1–7).
@inproceedings{Aziz_Rauchecker_Schryen_Walsh_2017, title={Algorithms for Max-Min Share Fair Allocation of Indivisible Chores}, booktitle={Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)}, author={Aziz, Haris and Rauchecker, Gerhard and Schryen, Guido and Walsh, Toby}, year={2017}, pages={1–7} }
Aziz, Haris, Gerhard Rauchecker, Guido Schryen, and Toby Walsh. “Algorithms for Max-Min Share Fair Allocation of Indivisible Chores.” In Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), 1–7, 2017.
H. Aziz, G. Rauchecker, G. Schryen, and T. Walsh, “Algorithms for Max-Min Share Fair Allocation of Indivisible Chores,” in Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), 2017, pp. 1–7.
Aziz, Haris, et al. “Algorithms for Max-Min Share Fair Allocation of Indivisible Chores.” Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), 2017, pp. 1–7.
Main File(s)
Access Level
OA Open Access
Last Uploaded
2018-12-13T15:06:42Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar