Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Single-Sample Prophet Inequalities Revisited
arXiv (Cornell University)
23 Nov 2021
Abstract
The study of the prophet inequality problem in the limited information regime
was initiated by Azar et al. [SODA'14] in the pursuit of prior-independent
posted-price mechanisms. As they show, $O(1)$-competitive policies are
achievable using only a single sample from the distribution of each agent. A
notable portion of their results relies on reducing the design of single-sample
prophet inequalities (SSPIs) to that of order-oblivious secretary (OOS)
policies. The above reduction comes at the cost of not fully utilizing the
available samples. However, to date, this is essentially the only method for
proving SSPIs for many combinatorial sets. Very recently, Rubinstein et al.
[ITCS'20] give a surprisingly simple algorithm which achieves the optimal
competitive ratio for the single-choice SSPI problem $-$ a result which is
unobtainable going through the reduction to secretary problems. Motivated by
this discrepancy, we study the competitiveness of simple SSPI policies
directly, without appealing to results from OOS literature. In this direction,
we first develop a framework for analyzing policies against a greedy-like
prophet solution. Using this framework, we obtain the first SSPI for general
(non-bipartite) matching environments, as well as improved competitive ratios
for transversal and truncated partition matroids. Second, motivated by the
observation that many OOS policies for matroids decompose the problem into
independent rank-$1$ instances, we provide a meta-theorem which applies to any
matroid satisfying this partition property. Leveraging the recent results by
Rubinstein et al., we obtain improved competitive guarantees (most by a factor
of $2$) for a number of matroids captured by the reduction of Azar et al.
Finally, we discuss applications of our SSPIs to the design of mechanisms for
multi-dimensional limited information settings with improved revenue and
welfare guarantees.
Metrics
10 Record Views
Details
- Title
- Single-Sample Prophet Inequalities Revisited
- Creators
- Constantine CaramanisMatthew FawOrestis PapadigenopoulosEmmanouil Pountourakis
- Publication Details
- arXiv (Cornell University)
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Computer Science (Computing)
- Other Identifier
- 991021869007904721