Multiunit I.I.D. Prophet Inequalities via Extreme Value Asymptotics
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.18756
curl -X POST /api/v1/records/arxiv/2602.18756/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.18756/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'