Competition Versus Complexity in Multiple-Selection Prophet Inequalities
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914346672586752 |
|---|---|
| author | Cruz-Ossa, Eugenio Perez-Salazar, Sebastian Verdugo, Victor |
| author_facet | Cruz-Ossa, Eugenio Perez-Salazar, Sebastian Verdugo, Victor |
| contents | Competition complexity formalizes a compelling intuition: rather than refining the mechanism, how much additional competition is sufficient for a simple mechanism to compete with an optimal one? We begin the study of this question in multi-unit pricing for welfare maximization using prophet inequalities. An online decision-maker observes $m \geq k$ nonnegative values drawn independently from a known distribution, may select up to $k$ of them, and aims to maximize the expected sum of selected values. The benchmark is a prophet who observes a sequence of length $n \geq k$ and selects the $k$ largest values. We focus on the widely adopted class of single-threshold algorithms and fully characterize their $(1-\varepsilon)$-competition complexity. Notably, our results reveal a sharp competition-induced phase transition: in the absence of competition, single-threshold algorithms are fundamentally limited to a $1-1/\sqrt{2kπ}$ fraction of the prophet value, whereas even a $1\%$ multiplicative increase beyond $n$ observations suffices to achieve a $1-\exp(-Θ(k))$ fraction. Another notable result happens when $k=1$: we show that the $(1-\varepsilon)$-competition complexity is exactly $\ln(1/\varepsilon)$, fully resolving an open question by Brustle et al. [Math. Oper. Res. 2024]. Our analysis is based on infinite-dimensional linear programming and duality arguments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_20398 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Competition Versus Complexity in Multiple-Selection Prophet Inequalities Cruz-Ossa, Eugenio Perez-Salazar, Sebastian Verdugo, Victor Computer Science and Game Theory Optimization and Control Competition complexity formalizes a compelling intuition: rather than refining the mechanism, how much additional competition is sufficient for a simple mechanism to compete with an optimal one? We begin the study of this question in multi-unit pricing for welfare maximization using prophet inequalities. An online decision-maker observes $m \geq k$ nonnegative values drawn independently from a known distribution, may select up to $k$ of them, and aims to maximize the expected sum of selected values. The benchmark is a prophet who observes a sequence of length $n \geq k$ and selects the $k$ largest values. We focus on the widely adopted class of single-threshold algorithms and fully characterize their $(1-\varepsilon)$-competition complexity. Notably, our results reveal a sharp competition-induced phase transition: in the absence of competition, single-threshold algorithms are fundamentally limited to a $1-1/\sqrt{2kπ}$ fraction of the prophet value, whereas even a $1\%$ multiplicative increase beyond $n$ observations suffices to achieve a $1-\exp(-Θ(k))$ fraction. Another notable result happens when $k=1$: we show that the $(1-\varepsilon)$-competition complexity is exactly $\ln(1/\varepsilon)$, fully resolving an open question by Brustle et al. [Math. Oper. Res. 2024]. Our analysis is based on infinite-dimensional linear programming and duality arguments. |
| title | Competition Versus Complexity in Multiple-Selection Prophet Inequalities |
| topic | Computer Science and Game Theory Optimization and Control |
| url | https://arxiv.org/abs/2602.20398 |