Metraipolis › archive › dc_70c72aaf8a46

Beyond a Single Optimal Design: A Dynamical Systems Characterization of Online Allocation with Convex Costs — arXiv:2609.22651

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.22651
License (as archived)
CC0-1.0
Archived
2026-10-09T06:58:02.169Z
SHA-256 of the archived text
3e5dac3d01515c1eeaa4ba9b52839a1aa136a23a956100ba45a5f679026a3e49
Stable URL of this page
https://metraipolis.com/documento/dc_70c72aaf8a46

How to cite

Beyond a Single Optimal Design: A Dynamical Systems Characterization of Online Allocation with Convex Costs — arXiv:2609.22651 — arXiv (en), https://arxiv.org/abs/2609.22651 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_70c72aaf8a46 (Metraipolis archive dc_70c72aaf8a46, sha256 3e5dac3d01515c1eeaa4ba9b52839a1aa136a23a956100ba45a5f679026a3e49)
BibTeX
@misc{dc70c72aaf8a46,
  title = {Beyond a Single Optimal Design: A Dynamical Systems Characterization of Online Allocation with Convex Costs — arXiv:2609.22651},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.22651},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_70c72aaf8a46; sha256 3e5dac3d01515c1eeaa4ba9b52839a1aa136a23a956100ba45a5f679026a3e49},
  year = {2026}
}

Archived text

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

We study online allocation with convex costs (\OACC), a generalization of limited-supply models in which additional resources can be produced dynamically at convex cost. Prior work largely focuses on constructing a single algorithm that achieves strong competitive guarantees. In contrast, our main contribution is a structural characterization of the optimal design space of reserve functions (i.e., normalized pricing rules) for \OACC, yielding a family of optimal online algorithms. Using a principled dynamical-systems approach, we show that optimal online algorithms arise as solutions of a nonlinear eigenvalue problem: the optimal competitive ratio corresponds to the dominant eigenvalue, and the associated eigenfunction determines the optimal reserve function. This perspective establishes the existence of infinitely many optimal designs attaining the best possible competitive ratio, thereby unifying and generalizing a broad class of prior algorithms. Beyond unification, our characterization uncovers new structural phenomena, including the ability to flexibly mix dynamic and static pricing without loss of optimality and the construction of universally competitive algorithms under unknown or stochastic costs. We further extend the analysis to more structured settings such as supply-oblivious arrivals and hard supply constraints, obtaining sharper guarantees that improve upon previous bounds.

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