TY - GEN
T1 - On the PTAS for Maximin Shares in an Indivisible Mixed Manna
AU - Kulkarni, Rucha
AU - Mehta, Ruta
AU - Taki, Setareh
N1 - Publisher Copyright:
Copyright © 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85116115044&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85116115044&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85116115044
T3 - 35th AAAI Conference on Artificial Intelligence, AAAI 2021
SP - 5523
EP - 5530
BT - 35th AAAI Conference on Artificial Intelligence, AAAI 2021
PB - Association for the Advancement of Artificial Intelligence
T2 - 35th AAAI Conference on Artificial Intelligence, AAAI 2021
Y2 - 2 February 2021 through 9 February 2021
ER -