Polymatroid Prophet Inequalities

DOI10.1007/978-3-662-48350-3_37zbMath1466.68087arXiv1307.5299OpenAlexW1492207119MaRDI QIDQ3452806

Paul Dütting, Robert D. Kleinberg

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Auctions, bargaining, bidding and selling, and other market models (91B26) Economics of information (91B44) Online algorithms; streaming algorithms (68W27) Mechanism design theory (91B03)

Related Items (12)

Prophet Secretary ⋮ 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 ⋮ Hiring Secretaries over Time: The Benefit of Concurrent Employment ⋮ Unnamed Item ⋮ Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Nonstochastic Inputs ⋮ Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents ⋮ Secretary markets with local information ⋮ From pricing to prophets, and back! ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem ⋮ An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial Auctions

Cites Work

• Unnamed Item
• Comparison of threshold stop rules and maximum for independent nonnegative random variables
• Combinatorial Optimization. Polyhedra and efficiency. CD-ROM
• Revenue maximization with a single sample
• Polyhedral Clinching Auctions and the AdWords Polytope
• Multi-parameter mechanism design and sequential posted pricing
• Approximation algorithms for restless bandit problems
• An Ascending Vickrey Auction for Selling Bases of a Matroid
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• Optimal Auction Design
• Semiamarts and finite values
• Multiaccess fading channels. I. Polymatroid structure, optimal resource allocation and throughput capacities
• Multi-armed Bandits with Metric Switching Costs
• Combinatorial Auctions via Posted Prices
• Matroid prophet inequalities
• Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

This page was built for publication: Polymatroid Prophet Inequalities