Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.18756 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914342004326400 |
|---|---|
| author | Kong, Jieming Murthy, Karthyek |
| author_facet | Kong, Jieming Murthy, Karthyek |
| contents | We study the i.i.d. $k$-selection prophet inequality problem, where a decision-maker sequentially observes $n$ independent nonnegative rewards and may accept at most $k$ of them without knowledge of future realizations. The objective is to maximize the expected total reward relative to that of a prophet who observes all rewards in advance. This problem captures the performance limits achievable in online resource allocation and underlies posted-price mechanisms in online marketplaces. We characterize the optimal welfare achievable relative to the prophet in terms of $k$ and the extreme value index of the reward distribution, in the asymptotic regime where the number of offers $n$ grows large. This optimal performance ratio turns out to be at least $1-\frac{\log k}{8k}[1+ε]$ for any $ε> 0$ and sufficiently large $k$, improving upon the respective, tight $1 - \frac{1}{\sqrt{2πk}}$ guarantee of static-threshold algorithms. We additionally analyze the certainty-equivalent (CE) heuristic, a widely used online allocation algorithm known to yield optimal regret growth in $n$ when evaluated under the fluid scaling assumption. Even in the absence of the fluid scaling, the CE heuristics's performance improves with $k$ to eventually match the leading order terms of the optimal dynamic program's performance ratio. A finer analysis nevertheless reveals that regret can be divergent and large relative to the optimal dynamic program when $n/k \to \infty$. This highlights the sensitivity in viewing the CE heuristic's performance under the commonly adopted, though subjective, fluid scaling assumption. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18756 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Multiunit I.I.D. Prophet Inequalities via Extreme Value Asymptotics Kong, Jieming Murthy, Karthyek Optimization and Control We study the i.i.d. $k$-selection prophet inequality problem, where a decision-maker sequentially observes $n$ independent nonnegative rewards and may accept at most $k$ of them without knowledge of future realizations. The objective is to maximize the expected total reward relative to that of a prophet who observes all rewards in advance. This problem captures the performance limits achievable in online resource allocation and underlies posted-price mechanisms in online marketplaces. We characterize the optimal welfare achievable relative to the prophet in terms of $k$ and the extreme value index of the reward distribution, in the asymptotic regime where the number of offers $n$ grows large. This optimal performance ratio turns out to be at least $1-\frac{\log k}{8k}[1+ε]$ for any $ε> 0$ and sufficiently large $k$, improving upon the respective, tight $1 - \frac{1}{\sqrt{2πk}}$ guarantee of static-threshold algorithms. We additionally analyze the certainty-equivalent (CE) heuristic, a widely used online allocation algorithm known to yield optimal regret growth in $n$ when evaluated under the fluid scaling assumption. Even in the absence of the fluid scaling, the CE heuristics's performance improves with $k$ to eventually match the leading order terms of the optimal dynamic program's performance ratio. A finer analysis nevertheless reveals that regret can be divergent and large relative to the optimal dynamic program when $n/k \to \infty$. This highlights the sensitivity in viewing the CE heuristic's performance under the commonly adopted, though subjective, fluid scaling assumption. |
| title | Multiunit I.I.D. Prophet Inequalities via Extreme Value Asymptotics |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2602.18756 |