A Combinatorial Proof for the Dowry Problem

Xujun Liu, Olgica Milenkovic, George V. Moustakides

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication2023 IEEE Information Theory Workshop, ITW 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9798350301496
StatePublished - 2023
Event2023 IEEE Information Theory Workshop, ITW 2023 - Saint-Malo, France
Duration: Apr 23 2023Apr 28 2023

Publication series

Name2023 IEEE Information Theory Workshop, ITW 2023


Conference2023 IEEE Information Theory Workshop, ITW 2023

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Signal Processing
  • Control and Optimization


Dive into the research topics of 'A Combinatorial Proof for the Dowry Problem'. Together they form a unique fingerprint.

Cite this