Prophet Inequalities with Limited Information

DOI10.1137/1.9781611973402.100MaRDI QIDQ5384062zbMATH OpenOpenAlexFDO

Authors Pablo Azar, S. Matthew Weinberg, Robert D. Kleinberg

Publication date 20 June 2019

Published in Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1307.3736

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Probabilistic games; gambling (91A60) Auctions, bargaining, bidding and selling, and other market models (91B26)

Abstract: In the classical prophet inequality, a gambler observes a sequence of stochastic rewards $V_1,\mathrm{...},V_n$ and must decide, for each reward $V_i$, whether to keep it and stop the game or to forfeit the reward forever and reveal the next value $V_i$. The gambler's goal is to obtain a constant fraction of the expected reward that the optimal offline algorithm would get. Recently, prophet inequalities have been generalized to settings where the gambler can choose $k$ items, and, more generally, where he can choose any independent set in a matroid. However, all the existing algorithms require the gambler to know the distribution from which the rewards $V_1,\mathrm{...},V_n$ are drawn. The assumption that the gambler knows the distribution from which $V_1,\mathrm{...},V_n$ are drawn is very strong. Instead, we work with the much simpler assumption that the gambler only knows a few samples from this distribution. We construct the first single-sample prophet inequalities for many settings of interest, whose guarantees all match the best possible asymptotically, emph{even with full knowledge of the distribution}. Specifically, we provide a novel single-sample algorithm when the gambler can choose any $k$ elements whose analysis is based on random walks with limited correlation. In addition, we provide a black-box method for converting specific types of solutions to the related emph{secretary problem} to single-sample prophet inequalities, and apply it to several existing algorithms. Finally, we provide a constant-sample prophet inequality for constant-degree bipartite matchings. We apply these results to design the first posted-price and multi-dimensional auction mechanisms with limited information in settings with asymmetric bidders.

Recommendations

• Expectation inequalities associated with prophet problems¹
• A statistical version of prophet inequalities
• scientific article; zbMATH DE number 3860099
• Optimal prophet inequality with less than one sample
• Polymatroid Prophet Inequalities
• Prophet inequalities for dependent random variables
• scientific article; zbMATH DE number 67296
• Combinatorial prophet inequalities

Cited in

(39)

• Matroid prophet inequalities and applications to multi-dimensional mechanism design
• Relaxing the independence assumption in sequential posted pricing, prophet inequality, and random bipartite matching
• Formal barriers to simple algorithms for the matroid secretary problem
• Prophet inequalities vs. approximating optimum online
• Prophet secretary through blind strategies
• Prior independent mechanisms via prophet inequalities with limited information
• From pricing to prophets, and back!
• Performance bounds for optimal sales mechanisms beyond the monotone hazard rate condition
• Bayesian auctions with efficient queries
• Prophet inequality with competing agents
• Prophet inequalities made easy: stochastic optimization by pricing nonstochastic inputs
• Online network design with outliers
• Robust auctions for revenue via enhanced competition
• The submodular secretary problem goes linear
• On policies for single-leg revenue management with limited demand information
• Strong algorithms for the ordinal matroid secretary problem
• Posted price mechanisms and optimal threshold strategies for random arrivals
• Prophet matching with general arrivals
• Prophet inequalities for independent and identically distributed random variables from an unknown distribution
• A Framework for the Secretary Problem on the Intersection of Matroids
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Prophet secretary
• Matroid prophet inequalities
• Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
• Secretary and online matching problems with machine learned advice
• Optimal prophet inequality with less than one sample
• A constant factor prophet inequality for online combinatorial auctions
• The importance of knowing the arrival order in combinatorial Bayesian settings
• Competition and recall in selection problems
• Order-competitive ratio
• The outer limits of contention resolution on matroids and connections to the secretary problem
• Efficient two-sided markets with limited information
• Competitive analysis with a sample and the secretary problem
• Simple and optimal online contention resolution schemes for k-uniform matroids
• Single sample prophet inequality for uniform matroids of rank 2
• Pairwise-independent contention resolution
• Matroid Bayesian online selection
• Pairwise-independent contention resolution
• The last success problem with samples

This page was built for publication: Prophet Inequalities with Limited Information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384062)