Research Repository

Approximation Algorithms for Computing Maximin Share Allocations

Amanatidis, Georgios and Markakis, Evangelos and Nikzad, Afshin and Saberi, Amin (2017) 'Approximation Algorithms for Computing Maximin Share Allocations.' ACM Transactions on Algorithms, 13 (4). ISSN 1549-6325

journal-mms_acm_alt.pdf - Accepted Version

Download (671kB) | Preview


We study the problem of computing maximin share allocations, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of an agent is the best she can guarantee to herself, if she is allowed to partition the goods in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then is to find a partition, where each agent is guaranteed her maximin share. Such allocations do not always exist, hence we resort to approximation algorithms. Our main result is a 2/3-approximation that runs in polynomial time for any number of agents and goods. This improves upon the algorithm of Procaccia and Wang (2014), which is also a 2/3-approximation but runs in polynomial time only for a constant number of agents. To achieve this, we redesign certain parts of the algorithm in Procaccia and Wang (2014), exploiting the construction of carefully selected matchings in a bipartite graph representation of the problem. Furthermore, motivated by the apparent difficulty in establishing lower bounds, we undertake a probabilistic analysis. We prove that in randomly generated instances, maximin share allocations exist with high probability. This can be seen as a justification of previously reported experimental evidence. Finally, we provide further positive results for two special cases arising from previous works. The first is the intriguing case of three agents, where we provide an improved 7/8-approximation. The second case is when all item values belong to {0, 1, 2}, where we obtain an exact algorithm

Item Type: Article
Divisions: Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Elements
Date Deposited: 07 Apr 2020 12:34
Last Modified: 21 Apr 2020 12:15

Actions (login required)

View Item View Item