On Lower Bounds for Maximin Share Guarantees

We study the problem of fairly allocating a set of indivisible items to a set of agents with additive valuations. Recently, Feige et al. (WINE’21) proved that a maximin share (MMS) allocation exists for all instances with $n$ agents and no more than $n+5$ items. Moreover, they proved that an MMS allocation is not guaranteed to exist for instances with $3$ agents and at least $9$ items, or $n\ge 4$ agents and at least $3n+3$ items. In this work, we shrink the gap between these upper and lower bounds for guaranteed existence of MMS allocations. We prove that for any integer $c>0$, there exists a number of agents $n_c$ such that an MMS allocation exists for any instance with $n\ge n_c$ agents and at most $n+c$ items, where $n_c\le \lfloor {0.6597}^c\cdot c!\rfloor$ for allocation of goods and $n_c\le \lfloor {0.7838}^c\cdot c!\rfloor$ for chores. Furthermore, we show that for $n\mathrm{\ne }3$ agents, all instances with $n+6$ goods have an MMS allocation.