On the PTAS for Maximin Shares in an Indivisible Mixed Manna
Abstract
We study fair allocation of indivisible items, both goods and chores, under the popular fairness notion of maximin share (MMS). The problem is well-studied when there are only goods (or chores), where a PTAS to compute the MMS values of agents is well-known. In contrast, for the mixed manna, a recent result showed that finding even an approximate MMS value of an agent up to any approximation factor in (0,1] is NP-hard for general instances. In this paper, we complement the hardness result by obtaining a PTAS to compute the MMS value when its absolute value is at least 1/p times either the total value of all the goods or total cost of all the chores, for some constant p valued at least 1.
Cite
Text
Kulkarni et al. "On the PTAS for Maximin Shares in an Indivisible Mixed Manna." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I6.16695Markdown
[Kulkarni et al. "On the PTAS for Maximin Shares in an Indivisible Mixed Manna." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/kulkarni2021aaai-ptas/) doi:10.1609/AAAI.V35I6.16695BibTeX
@inproceedings{kulkarni2021aaai-ptas,
title = {{On the PTAS for Maximin Shares in an Indivisible Mixed Manna}},
author = {Kulkarni, Rucha and Mehta, Ruta and Taki, Setareh},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2021},
pages = {5523-5530},
doi = {10.1609/AAAI.V35I6.16695},
url = {https://mlanthology.org/aaai/2021/kulkarni2021aaai-ptas/}
}