Metraipolis › archive › dc_767147c8a1f1

Subquadratic Subsidies for Nonnegative or Nonpositive Valuations — arXiv:2609.08272

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.08272
License (as archived)
CC0-1.0
Archived
2026-10-16T13:30:10.640Z
SHA-256 of the archived text
e664f136ac274888e0c100e7a0ea02254a2eeec4ac11585c50bd34d0e8d50d65
Stable URL of this page
https://metraipolis.com/documento/dc_767147c8a1f1

How to cite

Subquadratic Subsidies for Nonnegative or Nonpositive Valuations — arXiv:2609.08272 — arXiv (en), https://arxiv.org/abs/2609.08272 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_767147c8a1f1 (Metraipolis archive dc_767147c8a1f1, sha256 e664f136ac274888e0c100e7a0ea02254a2eeec4ac11585c50bd34d0e8d50d65)
BibTeX
@misc{dc767147c8a1f1,
  title = {Subquadratic Subsidies for Nonnegative or Nonpositive Valuations — arXiv:2609.08272},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.08272},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_767147c8a1f1; sha256 e664f136ac274888e0c100e7a0ea02254a2eeec4ac11585c50bd34d0e8d50d65},
  year = {2026}
}

Archived text

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

We study envy-freeness with subsidies for indivisible items beyond additive valuations. Assuming that every single-item marginal value lies in $[-1,1]$, we prove that a total subsidy of $O(n^{3/2}\sqrt{\log n})$ suffices to achieve envy-freeness among $n$ agents whenever all agents assign nonnegative values to every bundle or all assign nonpositive values to every bundle. These valuation classes include monotone goods and monotone chores, respectively, but do not require monotonicity. Our result establishes the first subquadratic total-subsidy bound for general monotone valuations that holds for every number of agents.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-09 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2609.08272 — 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-16T13:06:09.179Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).