A Strongly Polynomial-Time 7/9-Approximation Algorithm for Maximin Share Allocations
The goal is to find allocations of indivisible goods under additive valuations that give every agent a large fraction of her maximin share (MMS). The previous best guarantee was 10/13, achieved only up to epsilon by a PTAS.
The algorithm works on ordered instances and proceeds in rounds through pair, triple and bag-filling branches with reduction rules. The analysis keeps a private witness allocation for each agent, using solid and fluid items, and tracks it through three stages. Strong polynomiality comes from iteratively lowering threshold estimates of MMS values based on comparisons in failed runs. The main results are formalized and verified in Lean 4.
A strongly polynomial-time 7/9-MMS algorithm is obtained, making O(n^5 m^4) calls to the core routine and running in O(n^7 m^5) time. This improves the prior 10/13 guarantee.
| Paper | Existence | Algorithmic |
|---|---|---|
| [22] | 3/4 | (3/4-ε) PTAS |
| [26] | 3/4+1/(12n) | 3/4 strongly polynomial |
| [27] | 10/13 | (10/13-ε) PTAS |
| This paper | 7/9 | 7/9 strongly polynomial |
