Metraipolis › archive › dc_754d05ba9fa5

Online Fair Division Against an Oblivious Adversary — arXiv:2609.28333

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.28333
License (as archived)
CC0-1.0
Archived
2026-10-08T10:08:13.138Z
SHA-256 of the archived text
a554fe2926ada07b27e0b06c002057ed53eb6c0660cadc6ca556ed9ddd6317fa
Stable URL of this page
https://metraipolis.com/documento/dc_754d05ba9fa5

How to cite

Online Fair Division Against an Oblivious Adversary — arXiv:2609.28333 — arXiv (en), https://arxiv.org/abs/2609.28333 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_754d05ba9fa5 (Metraipolis archive dc_754d05ba9fa5, sha256 a554fe2926ada07b27e0b06c002057ed53eb6c0660cadc6ca556ed9ddd6317fa)
BibTeX
@misc{dc754d05ba9fa5,
  title = {Online Fair Division Against an Oblivious Adversary — arXiv:2609.28333},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.28333},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_754d05ba9fa5; sha256 a554fe2926ada07b27e0b06c002057ed53eb6c0660cadc6ca556ed9ddd6317fa},
  year = {2026}
}

Archived text

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

We study the online allocation of indivisible goods among $n$ agents, where each good must be allocated immediately and irrevocably upon arrival. Against an adaptive adversary, Neoh and Teh [2026] proved that no algorithm can guarantee a positive approximation to proportionality up to one good (PROP1) that is independent of the number of goods, and the same holds for proportionality up to $k$ goods (PROP$k$) for any fixed $k$. We instead consider an oblivious adversary, which fixes the input in advance. Choo et al. [2026] showed that the uniformly random allocation returns a $\Theta(1/\log(n/\delta))$-PROP1 allocation with probability at least $1-\delta$. We improve this to $\Omega(1/\log\log(n/\delta))$; our algorithm does not take $\delta$ as input, so the same algorithm achieves this bound for every $\delta\in(0,1)$. Moreover, with the same probability, a variant of our algorithm gives every agent almost her bundle, and even without adding any good when no single good is too valuable relative to this share. In contrast, for envy-freeness up to one good (EF1), we show that, for every $\alpha\in(0,1]$, every randomized algorithm has an input on which its probability of returning an $\alpha$-EF1 allocation is at most $e^{-\Omega(n)}$. For envy-freeness up to any good (EFX), this probability is at most $1/n!$ with only $n+1$ goods, a bound that is optimal within a factor of $(n+1)/2$. For the maximin share (MMS), this probability is at most $5/6$, however small $\alpha$ is. Allowing more removals gives a positive envy-freeness guarantee: allocating each good to a uniformly random agent among those with positive values achieves, with high probability, an approximation factor arbitrarily close to one for envy-freeness up to logarithmically many goods, and logarithmically many goods are necessary for this rule.

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