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).