Matroid prophet inequalities

DOI10.1145/2213977.2213991zbMath1286.60037arXiv1201.4764OpenAlexW2012672170MaRDI QIDQ5415470

S. Matthew Weinberg, Robert D. Kleinberg

Publication date: 13 May 2014

Published in: Proceedings of the forty-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

optimal stoppingmatroidsonline optimizationprophet inequalitiesBayesian mechanism design

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Stopping times; optimal stopping problems; gambling theory (60G40) Optimal stopping in statistics (62L15)

Related Items (39)

Deals or No Deals: Contract Design for Online Advertising ⋮ Prophet Secretary ⋮ Approximation algorithms for stochastic combinatorial optimization problems ⋮ Revenue Maximization for Selling Multiple Correlated Items ⋮ Polymatroid Prophet Inequalities ⋮ Prophet Secretary ⋮ Online Appointment Scheduling in the Random Order Model ⋮ Sequential Posted Price Mechanisms with Correlated Valuations ⋮ Formal barriers to simple algorithms for the matroid secretary problem ⋮ Submodular Stochastic Probing on Matroids ⋮ Optimal item pricing in online combinatorial auctions ⋮ Prophet Inequalities for Independent and Identically Distributed Random Variables from an Unknown Distribution ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ Bayesian auctions with efficient queries ⋮ Optimal revenue guarantees for pricing in large markets ⋮ Optimal pricing for MHR distributions ⋮ Prophet inequalities vs. approximating optimum online ⋮ Technical Note—Bifurcating Constraints to Improve Approximation Ratios for Network Revenue Management with Reusable Resources ⋮ Hiring Secretaries over Time: The Benefit of Concurrent Employment ⋮ Unnamed Item ⋮ Optimal prophet inequality with less than one sample ⋮ Unnamed Item ⋮ Tight Revenue Gaps Among Simple Mechanisms ⋮ Brief Announcement: Bayesian Auctions with Efficient Queries. ⋮ Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs ⋮ Prophet secretary through blind strategies ⋮ Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents ⋮ On the product dimension of clique factors ⋮ Secretary markets with local information ⋮ Prior independent mechanisms via prophet inequalities with limited information ⋮ From pricing to prophets, and back! ⋮ Budget feasible mechanisms on matroids ⋮ On Policies for Single-Leg Revenue Management with Limited Demand Information ⋮ A Duality-Based Unified Approach to Bayesian Mechanism Design ⋮ Pricing Social Goods ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem ⋮ Online Allocation and Pricing: Constant Regret via Bellman Inequalities ⋮ Online Contention Resolution Schemes with Applications to Bayesian Selection Problems ⋮ An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions

This page was built for publication: Matroid prophet inequalities