Computer Science - Computer Science and Game Theory Computer Science - Data Structures and Algorithms
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 Caramanis
Matthew Faw
Orestis Papadigenopoulos
Emmanouil Pountourakis
Publication Details
arXiv (Cornell University)
Resource Type
Preprint
Language
English
Academic Unit
Computer Science (Computing)
Other Identifier
991021869007904721
Research Home Page
Browse by research and academic units
Learn about the ETD submission process at Drexel
Learn about the Libraries’ research data management services