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. In settings with indivisible goods, such allocations are not guaranteed to 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. This improves upon the algorithm of Procaccia and Wang, which also produces a 2/3-approximation but runs in polynomial time only for a constant number of agents. We then investigate the intriguing case of 3 agents, for which it is already known that exact maximin share allocations do not always exist. We provide a 6/7-approximation algorithm for this case, improving on the currently known ratio of 3/4. Finally, we undertake a probabilistic analysis. We prove that in randomly generated instances, with high probability there exists a maximin share allocation. This can be seen as a justification of the experimental evidence reported in , that maximin share allocations exist almost always.
展开▼
