NDLI: Prophet Secretary

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Liaghat, Vahid Esfandiari, Hossein Hajiaghayi, MohammadTaghi Monemizadeh, Morteza
Copyright Year	2017
Abstract	Optimal stopping theory is a powerful tool for analyzing scenarios such as online auctions in which we generally require optimizing an objective function over the space of stopping rules for an allocation process under uncertainty. Perhaps the most classic problems of stopping theory are the prophet inequality problem and the secretary problem. The classical prophet inequality states that by choosing the same threshold OPT/2 for every step, one can achieve the tight competitive ratio of $0.5$. On the other hand, for the basic secretary problem, the optimal strategy achieves the tight competitive ratio of $1/e\approx 0.36$ In this paper, we introduce prophet secretary, a natural combination of the prophet inequality and the secretary problems. In the prophet secretary problem we are given a set $\{D_1,\ldots,D_n\}$ of (not necessarily identical) distributions. A number $X_i$ is drawn from each distribution $D_i$ and then, after applying a random permutation $\pi_1,\ldots, \pi_n$, the numbers are given to us in an online fashion, i.e., at step $k$, $X_{\pi_k}$ is revealed. We are allowed to choose only one number, which can be done only upon receiving that number. The goal is to maximize the expectation of the chosen value, compared to the expectation of the optimum offline solution that knows the drawn values in advance. In particular, we show that by using a single uniform threshold one cannot break the 0.5 barrier of the prophet inequality for the prophet secretary problem. However, we show that $\bullet$ using $n$ distinct nonadaptive thresholds one can obtain a competitive ratio that goes to $(1-1/e \approx 0.63)$ as $n$ grows, and $\bullet$ no online algorithm can achieve a competitive ratio better than 0.75. Our results improve the (asymptotic) approximation guarantee of single-item sequential posted pricing mechanisms from 0.5 to $(1-1/e)$ when the order of agents (customers) is chosen randomly. We also consider the minimization variants of stopping theory problems and, in particular, the prophet secretary problem. Interestingly, we show that, even for the simple case in which the input elements are drawn from identical and independent distributions, there is no constant competitive online algorithm for the minimization variant of the prophet secretary problems. We extend this hardness result to the minimization variants of both the prophet inequality and the secretary problem as well.
Sponsorship	Google. Deutsche Forschungsgemeinschaft. Grantovâ Agentura Ceské Republiky. Goethe-Universität Frankfurt am Main. Air Force Office of Scientific Research. Office of Naval Research. National Science Foundation
Starting Page	1685
Ending Page	1701
Page Count	17
File Format	PDF
ISSN	08954801
DOI	10.1137/15M1029394
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	31
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2017-08-03
Access Restriction	Subscribed
Subject Keyword	secretary problem online algorithms prophet inequality
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Beyond matroids: secretary problem and prophet inequality with general constraints

Online prophet-inequality matching with applications to ad allocation

A Prophet Inequality Related to the Secretary Problem

A Prophet Inequality Related to the Secretary Problem

Automated online mechanism design and prophet inequalities (2007)

Beating 1-1/e for ordered prophets

Matroid Secretary Problem in the Random-Assignment Model

Automated online mechanism design and prophet inequalities (2007)

Submodular secretary problem and extensions

Prophet Secretary

Similar Documents

Beyond matroids: secretary problem and prophet inequality with general constraints

Online prophet-inequality matching with applications to ad allocation

A Prophet Inequality Related to the Secretary Problem

A Prophet Inequality Related to the Secretary Problem

Automated online mechanism design and prophet inequalities (2007)

Beating 1-1/e for ordered prophets

Matroid Secretary Problem in the Random-Assignment Model

Automated online mechanism design and prophet inequalities (2007)

Submodular secretary problem and extensions

Prophet Secretary