%run ../initscript.py
HTML("""
<div id="popup" style="padding-bottom:5px; display:none;">
    <div>Enter Password:</div>
    <input id="password" type="password"/>
    <button onclick="done()" style="border-radius: 12px;">Submit</button>
</div>
<button onclick="unlock()" style="border-radius: 12px;">Unclock</button>
<a href="#" onclick="code_toggle(this); return false;">show code</a>
""")

Enter Password:

Submit

Unclock show code

%run loadoptfuncs.py
toggle()

show code

Secretary Problem

Imagine you’re interviewing a set of applicants for a position as a secretary, and your goal is to maximize the chance of hiring the single best applicant in the pool. While you have no idea how to assign scores to individual applicants, you can easily judge which one you prefer. You interview the applicants one at a time. You can decide to offer the job to an applicant at any point and they are guaranteed to accept, terminating the search. But if you pass over an applicant, deciding not to hire them, they are gone forever.

In your search for a secretary, there are two ways you can fail: stopping early and stopping late. When you stop too early, you leave the best applicant undiscovered. When you stop too late, you hold out for a better applicant who doesn’t exist.

The optimal solution takes the form of the Look-Then-Leap Rule:

• You set a predetermined amount of time for “looking”, that is, exploring your options, gathering data — in which you categorically don’t choose anyone, no matter how impressive.

• After that point, you enter the “leap” phase, prepared to instantly commit to anyone who outshines the best applicant you saw in the look phase.

We can see how the Look-Then-Leap Rule emerges by considering how the secretary problem plays out in a small applicant pool.

hide_answer()

show answer

• One applicant the problem is easy to solve — hire her!

• With two applicants, you have a 50% chance of success no matter what you do. You can hire the first applicant (who’ll turn out to be the best half the time), or dismiss the first and by default hire the second (who is also best half the time).

• Add a third applicant, and all of a sudden things get interesting. Can we do better than chance which is 33%?

  • When we see the first applicant, we have no information — she’ll always appear to be the best yet.

  • When we see the third applicant, we have no agency — we have to make an offer to the final applicant.

  • For the second applicant, we have a little bit of both: we know whether she is better or worse than the first, and we have the freedom to either hire or dismiss her.

• What happens when we just hire her if she’s better than the first applicant, and dismiss her if she’s not? This turns out to be the best possible strategy with 50% of chance getting the best candidate.

• Suppose there are three candidates: Best, Good, Bad. There are 6 possible orders:

  1. Best, Good, Bad: hire Bad (the last one)

  2. Best, Bad, Good: hire Good (the last one)

  3. Good, Best, Bad: hire Best

  4. Good, Bad, Best: hire Best

  5. Bad, Best, Good: hire Best

  6. Bad, Good, Best: hire Good

successful_rate(5, [2], printtable=True)

The best candidate is hired 2171 times in 5000 trials with 2 rejection

	person1	person2	person3	person4	person5	best_score	best	best_at_stop	hired_score	hired
0	40	35	81	61	98	98	person5	40	81	person3
1	14	51	45	13	52	52	person5	51	52	person5
2	75	65	72	19	44	75	person1	75	44	person5
3	96	20	29	83	86	96	person1	96	86	person5
4	61	79	59	52	18	79	person2	79	18	person5
5	73	63	85	83	4	85	person3	73	85	person3
6	86	70	61	94	15	94	person4	86	94	person4
7	97	23	86	76	44	97	person1	97	44	person5
8	14	86	61	65	40	86	person2	86	40	person5
9	20	2	66	28	10	66	person3	20	66	person3

{2: 43.419999999999995}

style = {'description_width': '150px'}
widgets.interact_manual.opts['manual_name'] = 'Run Simulation'
interact_manual(secretary,
                n=widgets.BoundedIntText(value=20, min=5, max=100,
                                         description='number of candidates:', disabled=False, style=style));

The optimal rule is the 37% Rule: look at the first 37% of the applicants, choosing none, then be ready to leap for anyone better than all those you’ve seen so far. To be precise, the mathematically optimal proportion of applicants to look at is \(1/e\). So, anything between 35% and 40% provides a success rate extremely close to the maximum.

In the secretary problem we know nothing about the applicants other than how they compare to one another. Some variations of the problem are studied:

• If every secretary, for instance, had a GRE scored, which is the only thing that matters about our applicants. Then, we should use the Threshold Rule, where we immediately accept an applicant if she is above a certain percentile.

• If waiting has a cost measured in dollars, a good candidate today beats a slightly better one several months from now.

• If we have ability to recall a past candidate.