Metraipolis › archive › dc_6ff339d535aa
Residual Maximin Share: Exact Finite-Agent Frontier, Sparse Extremizers, and Threshold Cuts — arXiv:2608.30257
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.30257
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T08:19:27.687Z
- SHA-256 of the archived text
efea37466ddd4efa6c6c12a91271da3a65ab1dce59e7dbd22bff859e7dda6dde- Stable URL of this page
https://metraipolis.com/documento/dc_6ff339d535aa
How to cite
Residual Maximin Share: Exact Finite-Agent Frontier, Sparse Extremizers, and Threshold Cuts — arXiv:2608.30257 — arXiv (en), https://arxiv.org/abs/2608.30257 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6ff339d535aa (Metraipolis archive dc_6ff339d535aa, sha256 efea37466ddd4efa6c6c12a91271da3a65ab1dce59e7dbd22bff859e7dda6dde)
BibTeX
@misc{dc6ff339d535aa,
title = {Residual Maximin Share: Exact Finite-Agent Frontier, Sparse Extremizers, and Threshold Cuts — arXiv:2608.30257},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.30257},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6ff339d535aa; sha256 efea37466ddd4efa6c6c12a91271da3a65ab1dce59e7dbd22bff859e7dda6dde},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.30257. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Residual maximin share (RMMS) is the largest share threshold that remains guaranteeable throughout dynamic allocation processes, even after previously allocated, lower-valued bundles are removed from the item pool. For additive valuations, recent density-balance analyses established finite-agent lower bounds comparing RMMS with the classical maximin share (MMS). In this paper, we prove that these finite-agent lower bounds are exact. Specifically, if $d_n$ denotes the largest odd integer at most $n$, the worst-case ratio satisfies $\inf_{M,v:\operatorname{MMS}>0}\frac{\operatorname{RMMS}(M,v,n)}{\operatorname{MMS}(M,v,n)}=\frac{2d_n}{3d_n-1}$. Consequently, the exact additive frontier forms consecutive odd-even plateaus and converges monotonically to $2/3$. We then investigate the combinatorial structure of extremal instances. While naive witnesses require $\Theta(n^2)$ items, we construct an explicit three-valued family achieving the exact boundary with only linear support: $(5n-3)/2$ items for odd $n$ and $(5n-4)/2$ items for even $n$. Its low-valued block supports two exact partitions that simultaneously certify the MMS benchmark and the residual obstruction. By modeling these dual partitions as a bipartite transportation graph, we prove that this block attains the absolute minimum support $q+d-1=3q$. At minimum support, any two-valued filler is uniquely rigid up to relabeling. Finally, we establish structural characterizations of RMMS. A general min--max representation applies to all finite monotone valuations. For integer additive valuations, we prove that a threshold $T$ is residual self-feasible if and only if every subset cut satisfies a packing-covering condition. Because RMMS is pointwise maximal among residual self-feasible shares, these exact constants establish a tight limitation on the fairness guarantees achievable by share-based lone-divider algorithms.
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-01 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2608.30257 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T08:08:10.913Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).