Introduction

You have to fill one job. The applicants arrive one at a time, in random order, and you can rank any two you have seen. The catch: right after each interview you must say hire or pass, on the spot. Pass, and that person is gone forever. Hire, and the search ends. You want the single best applicant of them all.

How do you even start? Hire the first person and you are almost certainly settling. Wait too long and the best one may have already walked out the door. Every step is a bet with no take-backs.

This is the secretary problem, and it has a clean, surprising answer. There is a single rule that maximizes your odds — and it wins far more often than instinct says it should.

Try the 37% Rule

Here is the rule. Look, don't leap for the first r applicants — interview them, hire none, just remember the best score you saw. After that, hire the first applicant who beats everyone in that look phase. Below, set how many candidates and what fraction to skip, then run many random trials and see how often each strategy lands the true best.

<p class="hint">The <b>look-then-leap</b> rule: interview the first <i>r</i> candidates and hire none — just remember the best you saw. Then hire the <b>first</b> later candidate who beats that best. Run many random orderings and see how often each strategy lands the true #1.</p>
<label class="row">Candidates (n): <b id="nVal">30</b>
  <input id="n" type="range" min="3" max="100" value="30"></label>
<label class="row">Skip fraction (r/n): <b id="fVal">37%</b>
  <input id="f" type="range" min="0" max="90" value="37"></label>
<div class="btns">
  <button id="run" type="button">Run 5000 trials</button>
  <button id="reset" type="button" class="ghost">Clear</button>
</div>
<div class="bars" id="bars"></div>
<div class="status" id="status">Press "Run 5000 trials".</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.row { display: flex; align-items: center; gap: .6rem; font-size: .9rem; margin: .4rem 0; }
.row input[type=range] { flex: 1; }
.row b { min-width: 3.2em; text-align: right; color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin: .6rem 0; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.bars { display: grid; gap: .5rem; margin: .7rem 0; }
.bar { display: grid; grid-template-columns: 9em 1fr; align-items: center; gap: .6rem; font-size: .85rem; }
.bar .name { color: #1d3557; font-weight: 600; }
.track { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 6px; height: 26px; position: relative; overflow: hidden; }
.fill { height: 100%; background: #c9ccd1; transition: width .35s; }
.fill.win { background: #0a7d33; }
.pct { position: absolute; right: 8px; top: 0; line-height: 26px; font-weight: 700; color: #173; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Secretary problem, verified by Monte Carlo. A "trial" is a random permutation of
// distinct scores 1..n. A strategy wins iff it ends up hiring the single best (rank n).
//
// 37% rule (look-then-leap): skip the first r candidates, remembering the best score
// among them; then hire the first later candidate that exceeds it. If none exceeds it,
// we are forced to take the last candidate. As n grows, the optimal r is n/e and the win probability tends to 1/e ≈ 0.368.
const TRIALS = 5000;
const $ = id => document.getElementById(id);

function shuffledScores(n){
  const a = []; for (let i=1;i<=n;i++) a.push(i);
  for (let i=n-1;i>0;i--){ const j=(Math.random()*(i+1))|0; const t=a[i]; a[i]=a[j]; a[j]=t; }
  return a; // a[k] is the score of the k-th interviewed candidate; best score is n
}
// Returns the score the strategy hires for one ordering.
function ruleSkip(a, r){
  const n = a.length;
  let best = -Infinity;
  for (let k=0;k<r;k++) if (a[k] > best) best = a[k]; // look phase, hire none
  for (let k=r;k<n;k++) if (a[k] > best) return a[k]; // leap: first one beating it
  return a[n-1]; // forced last hire
}
function simulate(n, r){
  let winSkip=0, winFirst=0, winLast=0;
  for (let t=0;t<TRIALS;t++){
    const a = shuffledScores(n);
    if (ruleSkip(a, r) === n) winSkip++;
    if (a[0] === n) winFirst++;          // "always hire the first"
    if (a[n-1] === n) winLast++;         // "always hire the last"
  }
  return {
    skip: winSkip/TRIALS, first: winFirst/TRIALS, last: winLast/TRIALS
  };
}

function bar(name, p, win){
  return '<div class="bar"><span class="name">'+name+'</span>'+
    '<div class="track"><div class="fill'+(win?' win':'')+'" style="width:'+(p*100).toFixed(1)+'%"></div>'+
    '<span class="pct">'+(p*100).toFixed(1)+'%</span></div></div>';
}

function syncLabels(){
  const n = +$('n').value, f = +$('f').value;
  $('nVal').textContent = n;
  $('fVal').textContent = f + '%';
}
function run(){
  const n = +$('n').value, f = +$('f').value;
  const r = Math.round(n * f / 100);
  const res = simulate(n, r);
  $('bars').innerHTML =
    bar(fmt('37% rule (skip (%r%)', { r: r }), res.skip, true) +
    bar('Always first', res.first, false) +
    bar('Always last', res.last, false);
  const ideal = (1/Math.E*100).toFixed(1);
  $('status').textContent = fmt('Look-then-leap won %v%% of %TRIALS% trials. Optimal limit ≈ %ideal%% (1/e).', { v: (res.skip*100).toFixed(1), TRIALS: TRIALS, ideal: ideal });
}
$('n').addEventListener('input', syncLabels);
$('f').addEventListener('input', syncLabels);
$('run').addEventListener('click', run);
$('reset').addEventListener('click', ()=>{ $('bars').innerHTML=''; $('status').textContent='Press "Run 5000 trials".'; });
syncLabels();
Result
Console

Drag the skip fraction toward 37% and watch the win rate climb to its peak. Compare it with "always hire the first" and "always hire the last" — both crawl along near 1/n. The magic number is no accident: as the pool grows, the best cutoff converges to 1/e ≈ 0.368, and the win rate converges to the very same 1/e ≈ 37%.

The Real Complexity

So how good is the 37% rule, really? Not "pretty good" — it is provably the best possible.

  • It is solved exactly. The strategy is: reject the first n/e applicants (about 37%), then hire the first one who is better than all of those. As n grows, this rule wins the very best candidate with probability approaching 1/e ≈ 0.368.
  • No strategy beats it. Among all rules that must decide on the spot with no look-back, none can win more often than ≈ 1/e. The bound is tight — this is the famous 1/e law of optimal stopping.
  • It is cheap to compute. Each step is one comparison; the whole policy is just a threshold. The hard part was never speed — it was proving that this simple threshold cannot be improved.
  • Author and year. The clean solution was published by D. V. Lindley (1961) and E. B. Dynkin (1963), building on the puzzle that circulated in the late 1950s.

That is the punchline: most "decide as you go" problems are messy and only approximately solvable, but this one is closed. Unlike the open frontier of P vs NP, here we know the optimal algorithm and a matching proof that nothing can do better.

Where It Matters

"Commit now or keep looking, with no rewind" is the shape of countless real decisions, and the secretary problem is its cleanest model:

  • Hiring and admissions: interviewing in rounds where strong candidates accept other offers if you hesitate.
  • Apartment and house hunting: in hot markets a listing is gone if you sleep on it — look-then-leap gives a principled cutoff.
  • Selling under deadlines: take this offer or wait for a better one that may never come.
  • Online algorithms and auctions: ad systems and matching markets must accept or reject each arriving item before the rest are revealed; secretary-style guarantees underpin many of them.

Understand the 37% rule and you have met optimal stopping — the same engine behind sequential decisions in optimal testing and many online, commit-as-you-go problems.

Conclusion

The secretary problem hides a rare gift: a real-world, decide-as-you-go choice that mathematics has completely solved. Spend the first 37% of your search just learning, then grab the first candidate who beats everything you have seen. You will land the very best about 37% of the time — and no strategy, however clever, can do better.

So the next time you must choose without a rewind — an apartment, an offer, a hire — remember that "looking before you leap" is not just folk wisdom. It is a theorem, with the number 1/e stamped right on it.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/secretary-problem/Content licensed under CC BY-NC 4.0.