2021/07/28 by Kurokawa, Sachika, Matsui, Tomomi
#Applications (stat.AP) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Primary 60G40 #Secondary 60L15
paper · doi:10.48550/arxiv.2107.13146
This paper discusses the odds problem, proposed by Bruss in 2000, and its variants. A recurrence relation called a dynamic programming (DP) equation is used to find an optimal stopping policy of the odds problem and its variants. In 2013, Buchbinder, Jain, and Singh proposed a linear programming (LP) formulation for finding an optimal stopping policy of the classical secretary problem, which is a special case of the odds problem. The proposed linear programming problem, which maximizes the probability of a win, differs from the DP equations known for long time periods. This paper shows that an ordinary DP equation is a modification of the dual problem of linear programming including the LP formulation proposed by Buchbinder, Jain, and Singh.