Duration problem with multiple exchanges

DOI10.3934/NACO.2012.2.333zbMATH Open1274.60134arXiv0812.3765OpenAlexW2962792092MaRDI QIDQ450751FDOQ450751

Mitsushi Tamaki, Krzysztof J. Szajowski, Charles E. M. Pearce

Publication date: 14 September 2012

Published in: Numerical Algebra, Control and Optimization (Search for Journal in Brave)

Abstract: We treat a version of the multiple-choice secretary problem called the multiple-choice duration problem, in which the objective is to maximize the time of possession of relatively best objects. It is shown that, for the $m$--choice duration problem, there exists a sequence (s1,s2,...,sm) of critical numbers such that, whenever there remain k choices yet to be made, then the optimal strategy immediately selects a relatively best object if it appears at or after time $s_k$ ($1leqkleqm$). We also exhibit an equivalence between the duration problem and the classical best-choice secretary problem. A simple recursive formula is given for calculating the critical numbers when the number of objects tends to infinity. Extensions are made to models involving an acquisition or replacement cost.

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

zbMATH Keywords

dynamic programmingoptimal stoppingrelative ranksbest-choice problemone-step look ahead rule

Mathematics Subject Classification ID

Special processes (60K99) Stopping times; optimal stopping problems; gambling theory (60G40) Optimal stopping in statistics (62L15) Markov and semi-Markov decision processes (90C40)

Cited In (3)

• On the optimal stopping problems with monotone thresholds
• Optimal Stopping Rule for the No-Information Duration Problem with Random Horizon
• Shelf life of candidates in the generalized secretary problem

   Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Duration problem: basic concept and some extensions 👍 👎
• Infinite exchange problems 👍 👎
• Title not available (Why is that?) 👍 👎
• On the complexity of exchanging 👍 👎
• Interdependent Durations 👍 👎
• Duration problem on trajectories 👍 👎
• Optimal Multiple Trading Times Under the Exponential OU Model with Transaction Costs 👍 👎
• Exchanges procedures for timetabling problems 👍 👎

This page was built for publication: Duration problem with multiple exchanges

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q450751)