Metraipolis › archive › dc_05217db12455
Online Stochastic Allocation with Increasing Returns — arXiv:2609.34121
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.34121
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T23:06:55.026Z
- SHA-256 of the archived text
620f6dde4d2b3003328d7a04c88711ae61cd264804b01b56850d100e0271079c- Stable URL of this page
https://metraipolis.com/documento/dc_05217db12455
How to cite
Online Stochastic Allocation with Increasing Returns — arXiv:2609.34121 — arXiv (en), https://arxiv.org/abs/2609.34121 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_05217db12455 (Metraipolis archive dc_05217db12455, sha256 620f6dde4d2b3003328d7a04c88711ae61cd264804b01b56850d100e0271079c)
BibTeX
@misc{dc05217db12455,
title = {Online Stochastic Allocation with Increasing Returns — arXiv:2609.34121},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.34121},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_05217db12455; sha256 620f6dde4d2b3003328d7a04c88711ae61cd264804b01b56850d100e0271079c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.34121. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Online resource allocation is a fundamental problem in revenue management, sponsored search, and platform operations. Most prior work assumes nonincreasing assignment rewards, capturing diminishing returns. We instead study increasing returns, where assigning more customers to the same product can unlock larger value through scale, visibility, or network effects. We consider capacity-limited products assigned to sequentially arriving customers, where the reward of each product depends on the total number of customers assigned to it. We focus on full compatibility, where every product can be assigned to every customer. The number of customers is unknown to the online algorithm. We show that representative classical approaches, such as online greedy algorithm and LP-based independent rounding, can perform arbitrarily bad in this setting, even when products share a common bonus function. For homogeneous bonus functions, we give a simple polynomial-time algorithm that achieves a tight $1/2$-competitive ratio. For arbitrary heterogeneous bonus functions, we show that no constant competitive ratio independent of the number of products is possible: for $m$ products, the optimal competitive can be as small as $\Theta\left({1}/{\sqrt m}\right)$. This shows that heterogeneous delayed rewards can force any online algorithm to guess the realized arrival counts. We then identify a structured heterogeneous regime that restores a constant guarantee. When each bonus function is nonnegative, nondecreasing, and discrete concave, we design an intermediate target repair algorithm with a deterministic pathwise guarantee of $0.2466$. The algorithm repeatedly computes an offline target for a larger demand level and repairs the current allocation toward it using a prefix-robust assignment order. This coordinates buildup while remaining robust to early stopping and yields a distribution-free guarantee.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.OC).
Categorie arXiv: Data Structures and Algorithms (cs.DS) ; Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.34121 — 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-07T22:42:39.317Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).