Secretary Problem
The secretary problem is a classic concept in decision theory that illustrates an optimal strategy for selecting the best choice from a sequence of options when decisions must be made immediately and irrevocably. It belongs to the broader category of optimal stopping theory, which explores when to take a particular action to maximize an expected reward. The problem assumes a known number of candidates, who are presented sequentially in random order, and the decision-maker can only assess their relative rank among those already observed. Once a candidate is rejected, they cannot be recalled. The objective is to maximize the probability of selecting the single best candidate.49
History and Origin
The secretary problem, also known by various other names such as the "marriage problem" or the "sultan's dowry problem," has a rich history within mathematics and related fields.48 It was reportedly introduced in 1949 by Merrill M. Flood, who referred to it as the "fiancée problem" in lectures and correspondence throughout the 1950s. 47Although no formal publication existed at the time, its principles spread through academic folklore. The problem gained significant public attention and was first formally published in Martin Gardner's "Mathematical Games" column in Scientific American in February 1960. 44, 45, 46This popularization sparked extensive study and development by prominent probabilists and statisticians, solidifying its place as a foundational problem in applied probability and decision science. 43For a detailed historical account, the paper by Thomas S. Ferguson, "Who Solved the Secretary Problem?", provides further insight into its origins and early developments.
42
Key Takeaways
- The secretary problem addresses how to make an irreversible decision from a sequence of choices to maximize the chance of selecting the absolute best option.
- It operates under specific constraints: a known total number of options, sequential evaluation, immediate and final decisions, and the ability to only rank relative quality.
- The optimal strategy, often called the "37% rule" or "1/e rule," involves an initial observation phase followed by a selection phase.
39, 40, 41* The probability of success using this optimal strategy approaches approximately 37% (or 1/e) for a large number of options, significantly outperforming random selection.
37, 38* While a mathematical abstraction, the secretary problem offers valuable insights into balancing exploration and exploitation in various real-world scenarios.
Formula and Calculation
The optimal strategy for the classic secretary problem involves a "look-then-leap" approach. The decision-maker should observe a certain proportion of the candidates without making a selection, establishing a benchmark. After this observation phase, the decision-maker selects the first subsequent candidate who is better than all previously observed candidates.
35, 36
Let (n) be the total number of candidates.
Let (r) be the number of candidates in the observation phase (rejected unconditionally).
The optimal value for (r) is approximately (n/e), where (e) is the base of the natural logarithm (approximately 2.71828).
34
The probability of selecting the best candidate, (P(n, r)), is given by:
To find the optimal (r), one typically maximizes this probability. As (n) becomes large, the optimal (r) approaches (n/e), and the maximum probability of selecting the best candidate approaches (1/e). 33This calculation demonstrates how dynamic programming and calculus can be used to derive an optimal stopping point for a sequence of random variable outcomes.
32
Interpreting the Secretary Problem
The secretary problem provides a framework for understanding sequential decision-making under uncertainty. The core insight is the existence of an optimal strategy that balances the need to gather information (exploration) with the risk of missing the best option (exploitation). 31The "37% rule" suggests that a significant initial period of observation is crucial to establish a reliable standard. After this exploratory phase, the focus shifts to immediately acting on the next superior option.
29, 30
This rule isn't about achieving a guaranteed outcome but rather maximizing the probability of achieving the desired outcome. For instance, if there are 100 potential choices, the strategy advises observing the first 37 without selecting any. The decision-maker then commits to the very next option that surpasses all 37 previously observed. This approach optimizes the chances of picking the best candidate to around 37%. 28Understanding this balance is key in fields ranging from investment to strategic planning, where limited information and irreversible choices are common.
Hypothetical Example
Imagine an investor deciding when to purchase a particular financial asset over a fixed period of 10 days. The investor wants to buy at the lowest price possible within this period, but can only make one purchase and must decide daily whether to buy or wait, knowing they cannot go back to a previously observed lower price.
Following the secretary problem's 1/e rule (approximately 37%), the investor would observe the asset's price for the first 3.7 days, which, rounded, means the first 4 days (or (10/e \approx 3.67)). During these initial 4 days, the investor records the lowest price seen but does not make a purchase. This serves as their benchmark.
Starting on day 5, the investor will purchase the asset on the first day its price is lower than any of the prices observed during the first 4 days. If, by chance, no such price appears lower than the benchmark before the end of day 10, the investor would then purchase the asset on day 10, accepting whatever price is available. This systematic approach, based on probability, aims to maximize the chance of securing the lowest price in the sequence.
Practical Applications
Beyond its theoretical underpinnings, the secretary problem finds practical applications in various domains where sequential decision-making under uncertainty is prevalent:
- Hiring and Recruitment: As the name suggests, the problem directly applies to hiring processes where candidates are interviewed sequentially, and a decision must be made on the spot. 27Companies aim to hire the best person from a pool of applicants.
- Real Estate: When searching for a home, buyers often view properties one by one and must make quick decisions. The principles of the secretary problem can inform how long to explore the market before committing to a property that surpasses previously seen options.
24, 25, 26* Dating and Relationships: The problem has been humorously, yet insightfully, applied to the search for a life partner, suggesting an optimal period of "exploration" before committing. 19, 20, 21, 22, 23While a simplified model for complex human relationships, it highlights the trade-off between waiting for a better option and risking the loss of a good one.
18* Online Auctions and Resource Allocation: In scenarios like online auctions, where bids are revealed sequentially, or in resource allocation within computer networks, the problem's insights help design algorithms for optimal selection. 16, 17The publication "The Secretary Problem with Independent Sampling" by Management Science explores its applications in economics and management, noting its relevance in scenarios with uncertain sequences of values.
15* Financial Trading and Portfolio Optimization: While more complex in finance due to continuous data and recallability, the core principles of optimal stopping, as demonstrated by the secretary problem, are relevant. For example, deciding when to sell an financial asset to maximize profit or minimize loss, or when to exit an investment position, draws upon similar considerations.
13, 14
Limitations and Criticisms
While the secretary problem offers a fascinating mathematical solution to sequential decision-making, its practical applicability is often debated due to its restrictive assumptions:
- Known Number of Candidates ((n)): In most real-world scenarios, the total number of available options is rarely known beforehand. This fundamental assumption of the secretary problem is often unrealistic.
11, 12* Irreversible Decisions: The model assumes that once an option is rejected, it cannot be recalled. This is true in some cases (e.g., a job offer that expires), but in many situations, previously rejected options might become available again. - Relative Ranking Only: The problem assumes the decision-maker can only determine the relative rank of the current candidate compared to those already seen, not their absolute "value." In reality, people often assess intrinsic quality.
10* Objective Function: The classic secretary problem aims to maximize the probability of selecting the absolute best candidate, treating all other outcomes (even selecting the second best) as failures. This "all or nothing" utility function is often not how decisions are made in complex situations, where a "good enough" option might be perfectly acceptable.
8, 9* Random Order of Presentation: The assumption that candidates appear in a completely random order might not hold true, as some processes could introduce bias.
7
Critics argue that these simplifications make the secretary problem a poor match for providing direct practical guidance in many real-life decisions, despite its theoretical elegance. Robert Wiblin, for instance, argues that the model's assumptions make it too simplistic for complex human decisions like hiring or dating. 6However, it remains valuable for illustrating the broader principle of balancing information gathering with timely action, a concept widely applicable in behavioral finance and other fields.
Secretary Problem vs. Optimal Stopping Problem
The secretary problem is a specific and highly constrained instance of the broader Optimal Stopping Problem. While both involve deciding when to stop a sequential process to maximize a reward, they differ in scope and complexity.
The Optimal Stopping Problem is a general class of problems in mathematics and game theory where the objective is to choose a specific time to take a particular action in order to maximize an expected value or payoff. It can involve various information structures, different types of rewards, and dynamic changes in the underlying process. Examples include deciding when to sell a stock, when to exercise a financial option, or when to end a search for a partner. These problems often deal with continuous time, stochastic processes, and more complex payoff structures.
The secretary problem, by contrast, imposes very strict conditions:
- A finite and known number of items ((n)).
- Items are presented sequentially.
- Decisions are irreversible.
- Only relative ranks of observed items are known.
- The goal is to select the single best item.
The secretary problem's simplified framework allows for a surprisingly elegant and precise mathematical solution (the 1/e rule), making it an excellent pedagogical tool for introducing concepts within optimal stopping theory. However, the general Optimal Stopping Problem encompasses a much wider range of scenarios and often requires more sophisticated mathematical tools to solve, particularly in the realm of risk management and complex financial models.
FAQs
What is the "37% rule" in the secretary problem?
The "37% rule," also known as the 1/e rule, is the optimal strategy for the classic secretary problem. It suggests that to maximize the probability of selecting the best candidate, you should first observe approximately 37% (or 1/e) of the total candidates without making any selection. After this observation phase, you should select the very next candidate who is better than all previous candidates you have observed.
4, 5
Can the secretary problem predict the future?
No, the secretary problem cannot predict the future. It is a mathematical model that provides an optimal strategy to maximize the probability of success under specific, idealized conditions. It helps in making decisions when faced with a sequence of choices and limited information, but it does not guarantee a perfect outcome or foresee unforeseen events.
Is the secretary problem only for hiring secretaries?
Despite its name, the secretary problem is not limited to hiring secretaries. It is a theoretical framework applicable to any sequential decision-making scenario where options appear one by one, choices are irreversible, and the goal is to select the best among a known total number of options. Its principles can be applied to diverse fields such as real estate, dating, or even certain aspects of market analysis and supply and demand.
3
What happens if the best candidate appears in the initial observation phase?
If the absolute best candidate appears within the initial observation phase (the first approximately 37% of candidates), the optimal strategy dictates that you must reject them. This is a key trade-off: you sacrifice the certainty of a good option to gather enough information to identify the best option later. The model inherently accepts this risk to maximize the overall probability of selecting the ultimate top choice.
2
How does the secretary problem relate to financial decisions?
While financial markets are more complex, the secretary problem's core principle of optimal stopping is relevant. For example, it can inform decisions about when to sell an investment (when to stop holding it) or when to acquire an asset from a series of potential opportunities. It highlights the importance of balancing the desire for better future opportunities with the risk of missing out on current good ones, a concept relevant to managing financial risks and returns.1