Prophet secretary for combinatorial auctions and matroids

DOI10.1137/19m1264047MaRDI QIDQ6640585

Thomas Kesselheim, Mohammad Taghi Hajiaghayi, Sahil Singla, Soheil Ehsani

Publication date: 20 November 2024

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

zbMATH Keywords

optimal stopping timesecretary problemcombinatorial auctionsprophet inequalityfixed pricing mechanismsposted price mechanism

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40) Auctions, bargaining, bidding and selling, and other market models (91B26) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal stopping of independent random variables and maximizing prophets
• Prophet-type inequalities for multi-choice optimal stopping
• Online matroid intersection: beating half for random arrival
• An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
• Multi-parameter mechanism design and sequential posted pricing
• Online Submodular Welfare Maximization
• Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders
• Thirteen Reasons Why the Vickrey-Clarke-Groves Process Is Not Practical
• Polymatroid Prophet Inequalities
• Submodular Secretary Problem and Extensions
• Comparison of optimal value and constrained maxima expectations for independent random variables
• Semiamarts and finite values
• Combinatorial Prophet Inequalities
• Beating 1-1/e for ordered prophets
• A Framework for the Secretary Problem on the Intersection of Matroids
• Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
• On Maximizing Welfare When Utility Functions Are Subadditive
• Prophet Secretary Through Blind Strategies
• Beating Greedy for Stochastic Bipartite Matching
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• Prophet Secretary
• Beyond matroids: secretary problem and prophet inequality with general constraints
• Combinatorial Auctions via Posted Prices
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
• Matroid prophet inequalities
• Online bipartite matching with unknown distributions
• Online bipartite matching with random arrivals
• Prophet Inequalities for I.I.D. Random Variables with Random Arrival Times
• Algorithmic Game Theory
• Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers

This page was built for publication: Prophet secretary for combinatorial auctions and matroids