TY - GEN
T1 - Guaranteeing Maximin Shares
T2 - 30th International Joint Conference on Artificial Intelligence, IJCAI 2021
AU - Hosseini, Hadi
AU - Searns, Andrew
N1 - Funding Information:
HH acknowledges the support from NSF grant #1850076. We are grateful to Erel Segal-Halevi for his valuable input that improved the proof of Theorem 3.
Publisher Copyright:
© 2021 International Joint Conferences on Artificial Intelligence. All rights reserved.
PY - 2021
Y1 - 2021
N2 - The maximin share (MMS) guarantee is a desirable fairness notion for allocating indivisible goods. While MMS allocations do not always exist, several approximation techniques have been developed to ensure that all agents receive a fraction of their maximin share. We focus on an alternative approximation notion, based on the population of agents, that seeks to guarantee MMS for a fraction of agents. We show that no optimal approximation algorithm can satisfy more than a constant number of agents, and discuss the existence and computation of MMS for all but one agent and its relation to approximate MMS guarantees. We then prove the existence of allocations that guarantee MMS for 2/3 of agents, and devise a polynomial time algorithm that achieves this bound for up to nine agents. A key implication of our result is the existence of allocations that guarantee MMS?3n/2?, i.e., the value that agents receive by partitioning the goods into ?3/2n? bundles, improving the best known guarantee of MMS2n-2. Finally, we provide empirical experiments using synthetic data.
AB - The maximin share (MMS) guarantee is a desirable fairness notion for allocating indivisible goods. While MMS allocations do not always exist, several approximation techniques have been developed to ensure that all agents receive a fraction of their maximin share. We focus on an alternative approximation notion, based on the population of agents, that seeks to guarantee MMS for a fraction of agents. We show that no optimal approximation algorithm can satisfy more than a constant number of agents, and discuss the existence and computation of MMS for all but one agent and its relation to approximate MMS guarantees. We then prove the existence of allocations that guarantee MMS for 2/3 of agents, and devise a polynomial time algorithm that achieves this bound for up to nine agents. A key implication of our result is the existence of allocations that guarantee MMS?3n/2?, i.e., the value that agents receive by partitioning the goods into ?3/2n? bundles, improving the best known guarantee of MMS2n-2. Finally, we provide empirical experiments using synthetic data.
UR - http://www.scopus.com/inward/record.url?scp=85118868168&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85118868168&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:85118868168
T3 - IJCAI International Joint Conference on Artificial Intelligence
SP - 238
EP - 244
BT - Proceedings of the 30th International Joint Conference on Artificial Intelligence, IJCAI 2021
A2 - Zhou, Zhi-Hua
PB - International Joint Conferences on Artificial Intelligence
Y2 - 19 August 2021 through 27 August 2021
ER -