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
Restricted aziz_rauchecker_schryen_walsh.pdf 732.00 KB
OA 10582-Article Text-14110-1-2-20201228.pdf 738.75 KB
Conference Paper | English
Author
Aziz, Haris; Rauchecker, Gerhard; Schryen, GuidoLibreCat; Walsh, Toby
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)
Volume
31
Issue
1
Page
1-7
Conference
Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)
Conference Location
San Francisco, CA, USA
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). Vol 31. ; 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) (Vol. 31, pp. 1–7). San Francisco, CA, USA.
@inproceedings{Aziz_Rauchecker_Schryen_Walsh_2017, title={Algorithms for Max-Min Share Fair Allocation of Indivisible Chores}, volume={31}, number={1}, 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), 31: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), San Francisco, CA, USA, 2017, vol. 31, no. 1, 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), vol. 31, no. 1, 2017, pp. 1–7.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
aziz_rauchecker_schryen_walsh.pdf 732.00 KB
Access Level
Restricted Closed Access
Last Uploaded
2021-08-13T13:55:29Z
Access Level
OA Open Access
Last Uploaded
2021-08-13T13:55:14Z


Export

Marked Publications

Open Data LibreCat

Search this title in

Google Scholar