Welcome back. In our previous lesson, we analyzed how to find stable partner pairings using the Gale-Shapley algorithm, a powerful tool for situations where all potential partners and their preferences are known from the outset. However, life and relationships rarely present such complete information. More often, we encounter potential partners sequentially, without a full picture of who else might be out there.
This brings us to a different kind of strategic challenge: when should you commit to a good option, knowing a better one might appear later, but also that a rejected option may be lost forever? This lesson addresses that very question by introducing you to the framework of optimal stopping. We will formulate the process of selecting a secondary partner as a classic "Secretary Problem," allowing you to determine the best strategy under time or search constraints.
The Sequential Search Dilemma
Imagine a hotwife, let's call her Hannah, who has decided to find one secondary partner for the upcoming year. She estimates she will meet roughly a dozen potential partners ("bulls") during this time. She meets them one by one. After each date, she must decide: is this the one, or should she hold out for someone better? If she rejects a potential partner, he moves on and is no longer available. If she commits, her search ends.
This scenario is a classic example of an optimal stopping problem. The core dilemma is the trade-off between exploration and exploitation:
- Explore: If she decides too early, she might miss out on a much better partner who would have appeared later. She has insufficient data to know what a "good" partner even looks like in this pool.
- Exploit: If she waits too long, the best partner may have been in the group she already rejected, and she might be forced to settle for a less-than-ideal partner at the end of her search.
To formalize this, we turn to the Secretary Problem. The problem has several key conditions, which you will recognize in Hannah's dilemma. The following short video provides an excellent introduction.
Where e Hides - Secretary Problem
This video from the channel Dubious Insights introduces the Secretary Problem using a relatable apartment-hunting analogy. It clearly lays out the foundational assumptions of the model.
Please watch the first minute, from the beginning to the introduction of the problem. Pay close attention to the three conditions it outlines: immediate decision, no prior information on quality (only relative comparison), and the goal of selecting the absolute best.
As the video explains, the goal is to devise a strategy that maximizes the probability of selecting the single best candidate from the entire pool.
The Optimal Strategy: Look, Then Leap
The solution to the Secretary Problem is both elegant and surprisingly simple. It's a strategy often called "look, then leap." It consists of two distinct phases:
- The "Look" Phase (Exploration): You first interview a predetermined number of candidates, let's say
rout of a total ofn. You commit to rejecting all of them, no matter how good they seem. The sole purpose of this phase is to gather data and establish a quality baseline—a "best-so-far" benchmark. - The "Leap" Phase (Selection): After the
r-th candidate, you switch to a new mode. You will immediately commit to the very first candidate you meet who is better than everyone you saw in the "look" phase. If you reach the end of the line (n-th candidate) without finding such a person, you are obligated to choose that last candidate.
The image below illustrates this strategy and its possible outcomes.
The crucial question, of course, is how large should the "look" phase be? How do you determine the optimal number r? The remarkable answer is that for a large number of candidates, you should set your rejection phase r to be approximately n / e, where e is Euler's number (≈2.718). This means you should explore for roughly 37% of your total search window.
This "37% Rule" is the optimal strategy. No other choice of r gives you a higher probability of selecting the single best candidate. And what is that maximum probability? It is also 1/e, or about 37%.
Let's return to Hannah's case.
- Total candidates (n): 12
- Optimal look phase (r):
12 / e ≈ 4.4. We'll round down to 4. - Strategy: Hannah should go on dates with the first 4 potential bulls with the firm intention of rejecting them. Her goal is simply to establish a benchmark for charisma, compatibility, etc. Then, starting with the 5th bull, she should commit to the first man who is better than all of the first four.
- Outcome: This strategy gives her a ~37% chance of finding the single best partner out of the 12.
Given your background, you will likely find the mathematical underpinnings of this result interesting. It's not just a random number. The following video provides an intuitive walkthrough of the proof.
Where e Hides - Secretary Problem
Let's return to the "Where e Hides" video. The second half explains the mathematics behind the 1/e result.
Watch the segment from the mathematical explanation. It shows how the problem is framed as maximizing a probability function, which, through calculus, yields the 1/e solution. The appearance of the natural logarithm from the integral of 1/t is the key connection.
For a more formal, step-by-step derivation, the paper "Revisiting the Secretary Problem" is an excellent resource.
[PDF] Revisiting the Secretary Problem - New York University
This paper by Steven Brams and D. Marc Kilgour provides a clear analysis of the standard method and compares it to several interesting variations. We will focus on their derivation of the optimal strategy.
Please read Section 2, The Standard Method. Focus on the derivation of the probability Q(r). The formula Q(r) represents the probability of success for a given r. The authors then use this formula to find the optimal r* = 3 for their example of n=9. The footnote explains how calculus and a logarithmic approximation for the harmonic series lead to the general r* ≈ n/e result, which should be familiar from your own studies.
Generalizing the Goal: "Good Enough" is a Success
The classic Secretary Problem is rigid: success is defined as picking the #1 candidate, and anything else is a failure. In relationship dynamics, this is often unrealistic. A partner might be perfectly happy finding someone in the top 20% of the dating pool, not just the single best person.
This is a generalized version of the problem: maximizing the probability of selecting a candidate from the top k ranks. How does this change the strategy? A recent paper provides a thorough analysis.
[PDF] Secretary problem revisited: Optimal selection strategy for top ...
This paper by Lubomír Štěpánek extends the classic problem to selecting one of the top k candidates. This is highly relevant for scenarios where "good enough" is the goal.
Please read the Abstract and Introduction (Section I) to understand the paper's goal. Then, review the Problem setup (Section II), which formally defines the strategy and the probability P(d, n, k). Finally, jump to the results in Section III.C and Table I. Focus on Table I. This table numerically shows how the optimal rejection phase (d*) and the probability of success change as k (the number of acceptable top candidates) increases for n=20.
The key insight from this paper is intuitive: as your definition of success becomes less restrictive (i.e., k gets larger), your optimal exploration phase should get shorter. If any of the top 5 candidates is an acceptable outcome, you don't need to sample as many to set a benchmark; you can afford to "leap" earlier.
The graph below, from an article on the topic, illustrates this principle perfectly. The "tolerance" (tol) is analogous to k.
Let's apply this to Hannah's scenario.
- Original Goal: Find the #1 best bull (
k=1) out ofn=12. Strategy: Reject the first 4 (r/n ≈ 33%). Success chance: ~37%. - New Goal: Hannah decides she'd be happy with a bull from the top 25% of the pool. For
n=12, this meansk=3. - New Strategy: Looking at Table I in the paper for
k=3(n=20), the optimal ratiod*/nis 0.25. Applying this to Hannah's search, her new rejection phase should be12 * 0.25 = 3. She should explore the first 3 bulls, then leap for the first one who is better than all of them. - New Outcome: By modifying her goal and strategy, her probability of success skyrockets. The table shows a success rate of 62.7% for finding a top-3 candidate out of 20. This is a significant improvement over the 37% chance of finding the single best.
Conclusion
Today, we've moved from the world of complete information to the more realistic realm of sequential search and decision-making under uncertainty. The Secretary Problem provides a powerful framework for navigating the "explore-exploit" trade-off inherent in processes like partner selection.
Key Takeaways:
- The partner selection process, when candidates are encountered sequentially, can be modeled as an optimal stopping problem.
- The classic solution, known as the "37% Rule," dictates an initial exploration phase (rejecting the first
n/ecandidates) followed by a selection phase (choosing the first candidate better than any in the exploration phase). - This strategy maximizes the probability of finding the single best candidate, with a maximum success rate of
1/e(or 37%). - By generalizing the goal to accept any of the top
kcandidates, the optimal strategy shifts. A more flexible goal allows for a shorter exploration phase and results in a significantly higher probability of a successful outcome.
Preview of the Next Lesson:
This lesson concludes our module on partner selection models. We have covered matching markets with complete information (Gale-Shapley) and sequential searches with incomplete information (Secretary Problem). Our final module is a capstone project where we will integrate the concepts from this entire course. In our next lesson, we will begin this synthesis by building a multi-stage game model of a complete relationship scenario, from the initial signaling of interest to the dynamics of ongoing negotiation.