← All papers
First page of A Strongly Polynomial-Time 7/9-Approximation Algorithm for Maximin Share Allocations

A Strongly Polynomial-Time 7/9-Approximation Algorithm for Maximin Share Allocations

Xin Huang, Shengwei Zhou

cs.GT Nov 17, 2025 · v3 cs.DS
The main 7/9-MMS approximation guarantee and the polynomial-time algorithm results are formalized and verified in Lean 4, with accompanying code.
We study maximin share (MMS) allocations of indivisible goods under nonnegative additive valuations. We give a strongly polynomial-time algorithm that allocates to every agent a bundle worth at least $7/9$ of her MMS, improving the previous $10/13$ guarantee of Heidari et al. (SODA 2026). Our analysis uses a dynamic witness-allocation framework that tracks the remaining goods from each agent's perspective throughout the allocation process. We obtain the computational result by iteratively refining upper bounds on MMS values, using only polynomially many runs of the allocation algorithm. Finally, we formalize and verify our main results in Lean 4.

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.

PaperExistenceAlgorithmic
[22]3/4(3/4-ε) PTAS
[26]3/4+1/(12n)3/4 strongly polynomial
[27]10/13(10/13-ε) PTAS
This paper7/97/9 strongly polynomial
Selected MMS guarantees for additive goods (subset)