Metraipolis › archive › dc_44aa4370dca1

Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations — arXiv:2611.05073

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05073
License (as archived)
CC0-1.0
Archived
2026-11-04T21:46:24.352Z
SHA-256 of the archived text
8f5f8520058f4987c4efee74ed72021dc6669a2d47073adf87b6db60f6bed5c2
Stable URL of this page
https://metraipolis.com/documento/dc_44aa4370dca1

How to cite

Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations — arXiv:2611.05073 — arXiv (en), https://arxiv.org/abs/2611.05073 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_44aa4370dca1 (Metraipolis archive dc_44aa4370dca1, sha256 8f5f8520058f4987c4efee74ed72021dc6669a2d47073adf87b6db60f6bed5c2)
BibTeX
@misc{dc44aa4370dca1,
  title = {Toward Constant-Factor Maximin Share Guarantees for Subadditive Valuations — arXiv:2611.05073},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05073},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_44aa4370dca1; sha256 8f5f8520058f4987c4efee74ed72021dc6669a2d47073adf87b6db60f6bed5c2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05073. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

For $n$ agents and $m$ indivisible goods, an agent's maximin share (MMS) is the largest minimum bundle value she can obtain by partitioning the goods into $n$ bundles. Constant MMS approximations are known for additive, submodular, or XOS valuations, but whether such a guarantee exists for general subadditive valuations remains open. We advance this question in two directions. For general subadditive valuations, we exponentially improve the guarantee from $\Omega(1/\log\log n)$ to $\Omega(1/\log^* n)$, where $\log^* n$ is the iterated logarithm. We then seek constant MMS guarantees under additional structure on subadditive valuations by studying $q$-partitioning valuations: every partition of a bundle into at most $q$ groups admits nonnegative group prices that sum to the bundle's value and whose sum on any collection of groups is at most the value of their union. This hierarchy ranges from subadditivity at $q=2$ to XOS for $q\ge m$. We give the first study of MMS in the intermediate classes and prove constant guarantees whenever $q/n$ has a fixed positive lower bound, including $1/6$ for $q\ge n$ and $1/4$ for $q\ge2n$. For XOS valuations, we further improve the universal guarantee from $4/17\approx 0.2353$ to $5/16=0.3125$. For subadditive valuations, we prove a bidding amplification theorem that gives an exponential bound on each agent's probability of receiving less than half her MMS, while satisfying her budget in every outcome. For $q$-partitioning valuations, we give a scalar criterion that converts bounds on the value lost from disjoint deletions within a bundle into bounds on potential losses, even when an agent contributes zero below the target bundle value. For XOS valuations, we prove a reservation theorem that selects goods for integral assignment together with auxiliary additive valuations and accounts for the loss in rounding.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2611.05073 — 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-11-04T21:37:19.377Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).