Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey
Abstract
Fair allocation of indivisible goods is a central topic in many AI applications. Unfortunately, the corresponding problems are known to be NP-hard for many fairness concepts, so unless P = NP, exact polynomial-time algorithms cannot exist for them. In practical applications, however, it would be highly desirable to find exact solutions as quickly as possible. This motivates the study of algorithms that—even though they only run in exponential time—are as fast as possible and exactly solve such problems. We present known complexity results for them and give a survey of important techniques for designing such algorithms, mainly focusing on four common fairness notions: max-min fairness, maximin share, maximizing Nash social welfare, and envy-freeness. We also highlight the most challenging open problems for future work.
Cite
Text
Nguyen and Rothe. "Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey." International Joint Conference on Artificial Intelligence, 2023. doi:10.24963/IJCAI.2023/754Markdown
[Nguyen and Rothe. "Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey." International Joint Conference on Artificial Intelligence, 2023.](https://mlanthology.org/ijcai/2023/nguyen2023ijcai-complexity/) doi:10.24963/IJCAI.2023/754BibTeX
@inproceedings{nguyen2023ijcai-complexity,
title = {{Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey}},
author = {Nguyen, Trung Thanh and Rothe, Jörg},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2023},
pages = {6732-6740},
doi = {10.24963/IJCAI.2023/754},
url = {https://mlanthology.org/ijcai/2023/nguyen2023ijcai-complexity/}
}