Advertisement
Published in:
2017 | OriginalPaper | Chapter
Approximation Algorithms for Computing Maximin Share Allocations
Authors : Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, Amin Saberi
Published in: Extended Abstracts Summer 2015
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We study the problem of computing maximin share guarantees, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of a single agent is the best that she can guarantee to herself, if she would be allowed to partition the goods in any way she prefers, into n bundles, and then receive her least desirable bundle. The objective then in our problem is to find a partition, so that each agent is guaranteed her maximin share. Our main result is a 2∕3-approximation, that runs in polynomial time for any number of agents, improving upon recent results in the literature.