TY - GEN

T1 - A Combinatorial Proof for the Dowry Problem

AU - Liu, Xujun

AU - Milenkovic, Olgica

AU - Moustakides, George V.

N1 - Funding Information:
Acknowledgment. We thank the anonymous reviewers for their valuable comments. The work was supported in part by the NSF CCF 15-26875 and CIF 1513373 grants.
Publisher Copyright:
© 2023 IEEE.

PY - 2023

Y1 - 2023

N2 - The Secretary problem is a classical sequential decision-making question that can be succinctly described as follows: a set of rank-ordered applicants are interviewed sequentially for a single position. Once an applicant is interviewed, an immediate and irrevocable decision is made if the person is to be offered the job or not and only applicants observed so far can be used in the decision process. The problem of interest is to identify the stopping rule that maximizes the probability of hiring the highest-ranked applicant. A multiple-choice version of the Secretary problem, known as the Dowry problem, assumes that one is given a fixed integer budget for the total number of selections allowed to choose the best applicant. It has been solved using tools from dynamic programming and optimal stopping theory. We provide the first combinatorial proof for a related new query-based model for which we are allowed to solicit the response of an expert to determine if an applicant is optimal. Since the selection criteria differ from those of the Dowry problem, we obtain nonidentical expected stopping times.

AB - The Secretary problem is a classical sequential decision-making question that can be succinctly described as follows: a set of rank-ordered applicants are interviewed sequentially for a single position. Once an applicant is interviewed, an immediate and irrevocable decision is made if the person is to be offered the job or not and only applicants observed so far can be used in the decision process. The problem of interest is to identify the stopping rule that maximizes the probability of hiring the highest-ranked applicant. A multiple-choice version of the Secretary problem, known as the Dowry problem, assumes that one is given a fixed integer budget for the total number of selections allowed to choose the best applicant. It has been solved using tools from dynamic programming and optimal stopping theory. We provide the first combinatorial proof for a related new query-based model for which we are allowed to solicit the response of an expert to determine if an applicant is optimal. Since the selection criteria differ from those of the Dowry problem, we obtain nonidentical expected stopping times.

UR - http://www.scopus.com/inward/record.url?scp=85164994225&partnerID=8YFLogxK

U2 - 10.1109/ITW55543.2023.10161638

DO - 10.1109/ITW55543.2023.10161638

M3 - Conference Proceeding

AN - SCOPUS:85164994225

T3 - 2023 IEEE Information Theory Workshop, ITW 2023

SP - 538

EP - 543

BT - 2023 IEEE Information Theory Workshop, ITW 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2023 IEEE Information Theory Workshop, ITW 2023

Y2 - 23 April 2023 through 28 April 2023

ER -