Competition Versus Complexity in Multiple-Selection Prophet Inequalities
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$…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2602.20398
curl -X POST /api/v1/records/arxiv/2602.20398/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.20398/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'