Approximation Algorithms for Computing Maximin Share Allocations

20^th May 2015, 13:00 Ashton Lecture Theater
Prof Vangelis Markakis
Department of Informatics
Athens University of Economics and Business
Greece

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 he can guarantee to himself, if he partitions the goods into n bundles and receives his least desirable bundle. The objective then is to find a partition, so that each player is guaranteed his maximin share.
In the presence of indivisible goods, such allocations are not guaranteed to exist, hence, we resort to approximation algorithms.
Our main result is a 2/3-approximation algorithm, which runs in polynomial time for any number of agents and goods, improving upon previous results in the literature. We also investigate some special cases and provide better approximation guarantees. Finally, we provide a probabilistic analysis, showing that maximin share allocations exist in most cases (i.e., with probability 1-o(1) on randomly generated instances). This is in accordance with the apparent difficulty reported in previous works, for obtaining impossibility results.