{"id":"arxiv/2602.20398","url":"https://arxiv.org/abs/2602.20398","tags":["cs.GT","math.OC"],"score":0,"title":"Competition Versus Complexity in Multiple-Selection Prophet Inequalities","domain":"cs.GT","source":"arxiv","authors":["Eugenio Cruz-Ossa","Sebastian Perez-Salazar","Victor Verdugo"],"reviews":0,"subject":"cs.GT","summary":"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$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-23","reactions":{}}