arXiv preprint ·
Single-Sample Prophet Inequalities: A Combinatorial to Single-Item Reduction
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We study single-sample prophet inequalities for online combinatorial allocation. Our main contribution is a general reduction from combinatorial to single-item prophet inequalities for valuation classes admitting suitable supporting prices. The reduction uses a free-disposal value to separate buyer-side combinatorial constraints from item-side supply constraints, yielding a modular framework that applies in the stronger Game of Googol model. This framework yields a $\frac{1}{6\sqrt{3}}\approx\frac{1}{10.4}$-competitive single-sample prophet inequality and a $(β_{k-1}/4)$-competitive $k$-sample prophet inequality for XOS valuations, where $β_k$ is the competitive ratio of a $k$-sample single-item prophet inequality, improving upon the work of [DKL+24]. Both results extend directly to divisible resources with capped-XOS valuations. Along the way, we obtain new results for online free disposal and an optimal single-sample prophet inequality for fractional knapsack in the Game of Googol model.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Normal-Form Correlation in Markov Games
Maximizing $p$-Mean Social Welfare in the High-Multiplicity Setting: Few Agent Types and Few Item Types
On prediction from expert advice with more than five experts
Priority Gas Auction Cadence and Searcher Competition: Evidence from Flashblocks on Base
Settling the Computational Complexity of Max-Min Allocation with Ternary Valuations
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.