Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey
Trung Thanh Nguyen, Jörg Rothe
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.
BibTeX
@inproceedings{ijcai2023p754,
title = {Complexity Results and Exact Algorithms for Fair Division of Indivisible Items: A Survey},
author = {Nguyen, Trung Thanh and Rothe, Jörg},
booktitle = {Proceedings of the Thirty-Second International Joint Conference on
Artificial Intelligence, {IJCAI-23}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Edith Elkind},
pages = {6732--6740},
year = {2023},
month = {8},
note = {Survey Track},
doi = {10.24963/ijcai.2023/754},
url = {https://doi.org/10.24963/ijcai.2023/754},
}