Metraipolis › archive › dc_7a1fedce63a6

Optimal Prophet Inequalities for Gain from Trade — arXiv:2609.30742

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.30742
License (as archived)
CC0-1.0
Archived
2026-10-08T02:56:34.651Z
SHA-256 of the archived text
3fe07531818d415f29b4d404a5becb0d542db42b84237a04fda4638ae7e3f769
Stable URL of this page
https://metraipolis.com/documento/dc_7a1fedce63a6

How to cite

Optimal Prophet Inequalities for Gain from Trade — arXiv:2609.30742 — arXiv (en), https://arxiv.org/abs/2609.30742 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7a1fedce63a6 (Metraipolis archive dc_7a1fedce63a6, sha256 3fe07531818d415f29b4d404a5becb0d542db42b84237a04fda4638ae7e3f769)
BibTeX
@misc{dc7a1fedce63a6,
  title = {Optimal Prophet Inequalities for Gain from Trade — arXiv:2609.30742},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.30742},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7a1fedce63a6; sha256 3fe07531818d415f29b4d404a5becb0d542db42b84237a04fda4638ae7e3f769},
  year = {2026}
}

Archived text

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

We initiate the study of prophet trading, an online trading model in which a trader interacts with sellers and buyers who arrive in a uniformly random order and whose prices are drawn independently from a common known distribution. The trader aims to maximize the expected gain from trade (GFT), with performance measured against an omniscient prophet that knows the realized arrival order and all prices in advance. Unlike the classical prophet inequality problem, the trader must make both purchasing and selling decisions while managing the inventory, which makes both the prophet benchmark and the analysis of online algorithms substantially more intricate. For arbitrary numbers of buyers and sellers, we propose a simple threshold-based algorithm and prove a distribution-free competitive ratio of~2, which is the best possible. Our main technical contribution is an exact characterization of the inventory process induced by threshold trading. By expressing the algorithm's expected GFT in terms of the cumulative holding probability at buyer arrivals, we derive an exact formula for this inventory term, which serves as the foundation of our analysis and yields sharper guarantees in several important special cases. For balanced trading (with $n$ sellers and $n$ buyers), we improve the competitive ratio to $(2n^2-n)/((n+4^{-n}-1)(n+1))$, which is strictly less than 2 for every $n>1$. For the single-seller case, we sharpen the analysis of the fixed-threshold algorithm to obtain an asymptotic competitive ratio of $2e^2/(e^2+1)\approx1.76$. Furthermore, by exploiting the additional structure of this setting, we design an adaptive-threshold algorithm whose competitive ratio approaches $e/(e-1)\approx 1.58$. Due to a symmetry property of our general algorithmic idea, the same $1.76$-competitive guarantee also holds for the single-buyer case.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-28 in math.OC).
Categorie arXiv: Optimization and Control (math.OC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.30742 — 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-08T02:20:09.725Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).