Prophet Secretary

DOI10.1137/15M1029394zbMath1378.91094arXiv1507.01155OpenAlexW4251714048MaRDI QIDQ5348218

Vahid Liaghat, Morteza Monemizadeh, Hossein Esfandiari, Mohammad Taghi Hajiaghayi

Publication date: 14 August 2017

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

online algorithmssecretary problemprophet inequality

Mathematics Subject Classification ID

Stopping times; optimal stopping problems; gambling theory (60G40) Auctions, bargaining, bidding and selling, and other market models (91B26) Optimal stopping in statistics (62L15) Probabilistic games; gambling (91A60) Online algorithms; streaming algorithms (68W27)

Related Items (11)

The secretary problem with distributions ⋮ Finding the second-best candidate under the Mallows model ⋮ Prophet inequalities vs. approximating optimum online ⋮ Optimal and Efficient Auctions for the Gradual Procurement of Strategic Service Provider Agents ⋮ Unnamed Item ⋮ Tight Revenue Gaps Among Simple Mechanisms ⋮ The importance of knowing the arrival order in combinatorial Bayesian settings ⋮ Prophet inequalities via the expected competitive ratio ⋮ On submodular prophet inequalities and correlation gap ⋮ Prophet secretary for combinatorial auctions and matroids ⋮ Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Prophet-type inequalities for multi-choice optimal stopping
• Optimal choice and assignment of the best \(m\) of \(n\) randomly arriving items
• Ratio prophet inequalities when the mortal has several choices
• Improved Algorithms and Analysis for Secretary Problems and Generalizations
• The Online Stochastic Generalized Assignment Problem
• Multi-parameter mechanism design and sequential posted pricing
• Submodular secretary problem and extensions
• Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)
• Polymatroid Prophet Inequalities
• A Knapsack Secretary Problem with Applications
• The Secretary Problem and Its Extensions: A Review
• The d choice secretary problem
• The Optimal Choice of a Subset of a Population
• Optimal Auction Design
• Semiamarts and finite values
• The Submodular Secretary Problem Goes Linear
• 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

This page was built for publication: Prophet Secretary