An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions

DOI10.1137/20M1382799OpenAlexW3018978060MaRDI QIDQ5864664

Thomas Kesselheim, Paul Dütting, Brendan Lucier

Publication date: 8 June 2022

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

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

zbMATH Keywords

mechanism designcombinatorial auctionprophet inequalityposted prices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stopping times; optimal stopping problems; gambling theory (60G40) Online algorithms; streaming algorithms (68W27)

Related Items (1)

Optimal item pricing in online combinatorial auctions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comparison of threshold stop rules and maximum for independent nonnegative random variables
• Approximate revenue maximization with multiple items
• The power of randomness in Bayesian optimal mechanism design
• Multi-parameter mechanism design and sequential posted pricing
• Intrinsic Robustness of the Price of Anarchy
• Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs
• Polymatroid Prophet Inequalities
• Two Randomized Mechanisms for Combinatorial Auctions
• Semiamarts and finite values
• Online Contention Resolution Schemes
• Best-Response Dynamics in Combinatorial Auctions with Item Bidding
• Combinatorial Prophet Inequalities
• Simple mechanisms for subadditive buyers via duality
• Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders
• A Simple and Approximately Optimal Mechanism for an Additive Buyer
• On revenue maximization for selling multiple independently distributed items
• On Maximizing Welfare When Utility Functions Are Subadditive
• Pricing for Online Resource Allocation: Intervals and Paths
• Beyond matroids: secretary problem and prophet inequality with general constraints
• A duality based unified approach to Bayesian mechanism design
• An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications
• Combinatorial Auctions via Posted Prices
• Matroid prophet inequalities
• Simultaneous auctions are (almost) efficient
• Composable and efficient mechanisms
• Bayesian Combinatorial Auctions

This page was built for publication: An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions