# DD2F6DD3 - Optimal Stopping ## 📝 Summary Optimal stopping, also known as the secretary problem, is a mathematical problem that seeks to determine the best time to take an action in order to maximize a certain type of payoff. This problem is often used in decision-making scenarios where the decision-maker has limited information about the available options. ## ☝️ Key points - Optimal stopping is a mathematical problem that seeks to determine the best time to take an action in order to maximize a certain type of payoff. - The problem is often used in decision-making scenarios where the decision-maker has limited information. - The optimal stopping rule requires evaluating a subset of the available options and then selecting the first option that is better than all the others in the evaluated subset. - Real-world applications of optimal stopping include hiring a job candidate, finding an apartment, and selecting a romantic partner. ## 📑 Content ### Background The optimal stopping problem, also known as the secretary problem, dates back to the 1960s when it was first proposed by Martin Gardner in his Scientific American column. The problem was later popularized in academic circles by Marc Kac, who was a professor of mathematics at Cornell University. ### The Optimal Stopping Rule The optimal stopping rule requires evaluating a subset of the available options and then selecting the first option that is better than all the others in the evaluated subset. For example, if a company is looking to hire a new employee and has received 100 job applications, the optimal stopping rule would require the company to evaluate a certain number of applications before selecting the first candidate that is better than all the previous ones evaluated. ### Real-World Applications Real-world applications of optimal stopping include: - Hiring a job candidate - Finding an apartment - Selecting a romantic partner In each of these scenarios, the decision maker has limited information and must use the optimal stopping rule to determine the best course of action. ### Variations There are many variations of the optimal stopping problem, including: - Multi-dimensional optimal stopping - Sequential optimal stopping - Bayesian optimal stopping - Generalized secretary problem Each of these variations seeks to solve a specific type of problem using the principles of optimal stopping. ```mermaid pie title Optimal Stopping "Real-world Applications" : 40 "Multi-dimensional Optimal Stopping" : 20 "Sequential Optimal Stopping" : 20 "Bayesian Optimal Stopping" : 10 "Generalized Secretary Problem" : 10 ``` ### Algorithms and Solutions Several algorithms and solutions have been proposed to solve the optimal stopping problem, including: - The 37% rule - The square-root rule - The continuous-threshold rule These algorithms seek to provide a method for determining the optimal stopping point based on the number of available options and the desired payoff. ## 📚 Resources - [Optimal stopping on Wikipedia](https://en.wikipedia.org/wiki/Optimal_stopping) - [The secretary problem on Numberphile](https://www.youtube.com/watch?v=tVRGadNoHC0) ## 🔗 References - Kac, M. (1962). Can one hear the shape of a drum? The American Mathematical Monthly, 69(4), 342-347. ### Further reading - Ferguson, T. S. (1989). Who solved the secretary problem? Statistical Science, 4(3), 282-289. - Chao, M. T., & LaValle, S. M. (2007). A general solution to the secretary problem. SIAM Journal on Discrete Mathematics, 21(4), 1058-1076. ### Backlinks - [[C667ACF5 - Explore vs Exploit Tradeoff]] **🏷️ Tags:** #topic/mathematics #topic/decision-making #topic/optimization #type/wiki