Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs

DOI10.1137/20M1323850zbMath1454.91090arXiv1612.03161OpenAlexW3033498332MaRDI QIDQ3304731

Thomas Kesselheim, Michal Feldman, Paul Dütting, Brendan Lucier

Publication date: 3 August 2020

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

optimal stoppingcompetitive analysisonline algorithmsprice of anarchyprophet inequalitiesposted-price mechanisms

Mathematics Subject Classification ID

Microeconomic theory (price theory and economic markets) (91B24) Optimal stochastic control (93E20) Stopping times; optimal stopping problems; gambling theory (60G40) Online algorithms; streaming algorithms (68W27)

Related Items (18)

Strategyproof facility location in perturbation stable instances ⋮ Learning in auctions: regret is hard, envy is easy ⋮ Optimal item pricing in online combinatorial auctions ⋮ Prophet Matching with General Arrivals ⋮ Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution ⋮ A Dual Approach for Dynamic Pricing in Multidemand Markets ⋮ Max-min greedy matching problem: hardness for the adversary and fractional variant ⋮ Tight Revenue Gaps Among Simple Mechanisms ⋮ Unnamed Item ⋮ Prophet secretary through blind strategies ⋮ Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents ⋮ Secretary markets with local information ⋮ Mechanism design for perturbation stable combinatorial auctions ⋮ On Policies for Single-Leg Revenue Management with Limited Demand Information ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems ⋮ Market Pricing for Matroid Rank Valuations ⋮ An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions ⋮ Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property

Uses Software

• Sociodynamica

Cites Work

• Unnamed Item
• Unnamed Item
• Comparison of threshold stop rules and maximum for independent nonnegative random variables
• Optimal auctions vs. anonymous pricing
• Combinatorial auctions with decreasing marginal utilities
• The Online Stochastic Generalized Assignment Problem
• Multi-parameter mechanism design and sequential posted pricing
• Intrinsic Robustness of the Price of Anarchy
• Polymatroid Prophet Inequalities
• Two Randomized Mechanisms for Combinatorial Auctions
• Semiamarts and finite values
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Learning and Efficiency in Games with Dynamic Population
• Online Contention Resolution Schemes
• Combinatorial Prophet Inequalities
• Beating 1-1/e for ordered prophets
• Simple mechanisms for subadditive buyers via duality
• Dynamic and Non-uniform Pricing Strategies for Revenue Maximization
• Non-approximability results for optimization problems on bounded degree instances
• Beyond matroids: secretary problem and prophet inequality with general constraints
• The price of anarchy in large games
• Pricing Online Decisions: Beyond Auctions
• Combinatorial Auctions via Posted Prices
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
• Prophet Inequalities with Limited Information
• Matroid prophet inequalities
• Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers
• Simultaneous auctions are (almost) efficient
• Composable and efficient mechanisms
• Truthful randomized mechanisms for combinatorial auctions
• Submodular Maximization over Multiple Matroids via Generalized Exchange Properties
• Bayesian Combinatorial Auctions

This page was built for publication: Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs