Approximate Maximin Share with Subjective Divisibility: Beating the 1/2 Barrier
For researchers in fair division, this work advances the understanding of MMS fairness under subjective divisibility, a less explored model, by providing improved approximation bounds and tight results.
The paper studies maximin share (MMS) fairness under subjective divisibility, where agents differ in both valuations and perceptions of resource divisibility. It proves that the optimal approximation ratio is 2/3 for unary valuations, improves the general approximation guarantee from 1/2 to 5/9, and provides tight 2/3-approximation algorithms for up to four agents.
Maximin share (MMS) stands out as a central notion in fair resource allocation. It is known that exact MMS fairness is not always attainable, especially when agents differ along two dimensions: their valuations and their perceptions of the divisibility of resources. The former case with heterogeneous valuations has been widely studied in the literature. The latter, referred to as subjective divisibility by Bei et al., [Games Econ. Behav. 2025], remains much less explored. We study MMS approximation under subjective divisibility. First, we prove that even in the unary valuation setting, where all items have equal value, the optimal approximation ratio is 2/3. This result is somewhat surprising since in the objective setting, even when agents have heterogeneous valuations, the best possible approximation ratio is at least 7/9 [Huang and Zhou, 2025]. We then address the general case with both valuation heterogeneity and subjective divisibility. Previous work shows the existence of a 1/2-approximate MMS allocation. In this paper, we develop new algorithmic techniques that overcome the difficulties posed by subjective divisibility, and improve the approximation guarantee to 5/9. Finally, we complement this result with small-agent cases. For up to four agents, we give polynomial-time algorithms that compute 2/3-approximate MMS fair allocations. These bounds are tight. Our results deepen the understanding of MMS fairness under heterogeneous valuations and subjective divisibility, and provide a new perspective for this emerging model.