An improved approximation algorithm for maximin shares

摘要

Fair division is a fundamental problem in various multi-agent settings, where the goal is to divide a set of resources among agents in a fair manner. We study the case where m indivisible items need to be divided among n agents with additive valuations using the popular fairness notion of maximin share (MMS). An MMS allocation provides each agent a bundle worth at least her maximin share. While it is known that such an allocation need not exist [1], [2], a series of remarkable work [1], [3], [4], [5], [6] provided approximation algorithms for a 23-MMS allocation in which each agent receives a bundle worth at least 23 times her maximin share. More recently, Ghodsi et al. [7] showed the existence of a 34-MMS allocation and a PTAS to find a (34−ϵ)-MMS allocation for an ϵ>0. Most of the previous works utilize intricate algorithms and require agents' approximate MMS values, which are computationally expensive to obtain.