Improved Solution to Secretary Problem?

" imagine an administrator willing to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed one-by-one in random order. A decision about each particular applicant is to be made immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator can rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants. The question is about the optimal strategy (stopping rule) to maximize the probability of selecting the best applicant. If the decision can be deferred to the end, this can be solved by the simple maximum selection algorithm of tracking the running maximum (and who achieved it), and selecting the overall maximum at the end. The difficulty is that the decision must be made immediately."

When I read the solution I was at first impressed by it's mathematical beauty: Reject the first n/e applicants, choose the next best applicant after that or choose the last one. this gives a probability of 1/e of delivering the best applicant.

But on second thought it seemed rather risky. When the best applicant occurs in the first n/e spots, the last applicant is always the one chosen. Which means ~36.8% of the time you get a random choice between the worst and 2nd best applicant. It's likely that the applicants are normally distributed about an average number, and while the best applicant may be a standard deviation above the 2nd best or next group of best applicants, the worst applicant might be just as far on the other side of the spectrum or worse. This could be really disastrous.

For example, the most likely real world application of this problem is in dating. Sure you dont know exactly what N will be, but you date a certain number of girls and then eventually you choose one to settle down with. If you wait a while and refuse to settle for someone worse than your first set of applicants, you may end up getting stuck with a real shitty girl at an older age.

I thought I could immediately improve the solution to this problem. My solution was fairly simple: iterate this same process. Go through first n/e applicants, write down max, reject those. now there are n - n/e applicants. look through next (n-n/e)/e applicants, if you find a better one in there you choose it, if not you write down the max from that group, etc. iterated on to the end where you just go 1 at a time.

I programmed a simple version of both in python. I ranked secretaries 0-99, randomized their order and used each method to test the % choosing best applicant, the median applicant chosen and the average applicant chosen.

original algorithm code in python, very long:
+ Show Spoiler +

results: Ran the simulation 1000 times. The best secretary was chosen 375 times. The median secretary chosen was the 2nd best. The average choice was the 18th best. And roughly 3.5% of the time a bottom 10 secretary was chosen.



my algorithm

code:
+ Show Spoiler +

Results: ran 1000 times. best chosen 263. 3rd best was median choice. average: 4th best. worst chosen: 50th best.

this seems much much better. of course i didnt program it for random values in a normal distribution, nor did i program it for the more likely real world scenario of an unknown N. but this clearly seems like a much better solution despite the fact that the original solution chooses the best secretary ~10% more often.



So, if you guys would like, run with this in the more general forms or try and come up with an even better solution.

0 votes

Hmm, seems to me that original algo is "better" in terms of # of best chosen and the median.

And I am sure that the original algo made the decision a tad bit faster.

Really depends on what kind of criteria you would like to measure when it comes to "better".

A very fun problem indeed! I regularly get on http://www.spoj.com/ or https://code.google.com/codejam/ to do some coding

i remember our math prof showed this problem to us in university, but with a prince wanting to find the most beautiful princess

btw i dont get it, the original finds the best 375 out of 1000 while yours 263 of 1000. The original one is clearly the better in case of finding the best one. Isnt that the main thing? not the average. Or am i missing something

yes, clearly they choose the best more often. but my top choice and median are close enough and the average/floor are not at all close. sure its not an improvement over the actual problem, but as an application nobody in their right mind would risk getting the bottom of the barrel choices that the original algorithm gets you by just trying to get as high a choice as possible or bust

the point isnt to improve the likelihood of choosing the best candidate: this is not possible. clearly stopping once yields the highest likelihood of choosing the best candidate, and it is proven that N/e is the best stopping point.

the point is what is the best method to implement in practice. if i were a CEO forced to hire a secretary in this method, i would clearly choose my method over the other.


that said, im going to implement 1/2, 3/4, 7/8, 15/16, etc to see the comparison

running each 5000 times for 0-99:

halving method: best 1501 (30%), average 92.346, median 97, worst 7. was less than 25 about 30 times.
original method: best 1886 (36.5%), average 80.28, median 98, worst 0. was less than 25 ~10%
iterative n/e method: best 1334 (26.65%), average 95.102, median 97, worst 8. but was less than 25 twice in 5000 trials. and was 48 or higher 4991 out of 5000 tries.

which method would you choose of the 3?

Interesting stuff. Bit dubious about calling it a "brag" that your algo can beat another algo according to your yardstick X (maximise probability of achieving a good outcome according to your subjective value system), when that algo is made for / proven best at accomplishing a specific objective Y.

some others:
stop at 25/50/75/99, or return 100th
best: 1305, average 94.6788, median 97, worst 0, bottom happens quite a bit


stop at 10/20/30/40/50/60/70/80/90/99:
best: 613, average 92.325, median 94, worst: 36, rarely worse than 53.

On May 26 2014 14:56 Romm3l wrote: Interesting stuff. Bit dubious about calling it a "brag" that your algo can beat another algo according to your yardstick X (maximise probability of achieving a good outcome according to your subjective value system), when that algo is made for / proven best at accomplishing a specific objective Y.

yes, but i tried googling for it and i didnt see anyone using multiple stops. its not so much that my algorithm beat theirs, but i seem to be the first who thought of it and i cant come up with another that seems to be better than mine. its rather hard to believe nobody else thought of this as well when studying the problem, but it doesnt seem like its a popular solution when in the real world it should be. im more bragging that it seems to be somewhat innovative and that i was able to program it out in a few hours and test it. just felt good to do something not mindless for once lol

What would be interesting is if you formally define your value system X and then try to (+invite others to try to) find the best possible algo at maximising according to X.

Looks like from your code that you ordinally rank secretaries (best, second best, etc). Instead how about random generate a list of 100 numbers where the random freq distribution is normal and each number in the list corresponds to the ability of that secretary. Then try to maximise for the 'payoff' (ability of secretary picked).

On May 26 2014 15:03 Romm3l wrote: What would be interesting is if you formally define your value system X and then try to (+invite others to try to) find the best possible algo at maximising according to X. Looks like from your code that you ordinally rank secretaries (best, second best, etc). Instead how about random generate a list of 100 numbers where the random freq distribution is normal and each number in the list corresponds to the ability of that secretary. Then try to maximise for the 'payoff' (ability of secretary picked).

And if you want to make it look more like the real world, another 2 things:

- Introduce a "search cost" where the payoff you get from the secretary you picked is that secretary's ability minus some function of the number of secretaries you interviewed before accepting her

- payoff function has nonlinear correspondence to ability of secretary


edit: real-world proof of search costs (cp from ricky gervais wiki):

"Gervais later worked as an assistant events manager for the University of London Union (ULU),[19] where he continued working until he took a similar job as "head of speech" at XFM London.[20]

Needing an assistant, Gervais interviewed the first person whose curriculum vitae he saw. The CV belonged to Stephen Merchant. " [and he hired him]

your first point would be the next thing i programmed for sure. i.e. normally distribute about 0 with standard deviation 10, try to maximize the average and invite others to do the same?

never even thought about your 2nd post, but pretty cool idea. i think that would come after implementing something for unknown N.

and i just got real lazy. will likely come back to it at some point, but i have no work ethic to finish something i start because i havent done anything productive in 8 years

SOMEONE GET FLOOFY TO CONTINUE PROGRAMMING THIS

On May 26 2014 15:17 Daut wrote: and i just got real lazy. will likely come back to it at some point, but i have no work ethic to finish something i start because i havent done anything productive in 8 years

lold

you seem like a creative guy with good ideas, how can u not be productive. I mean how do you want to spend your next 50 years

On May 26 2014 15:39 dnagardi wrote: Show nested quote + On May 26 2014 15:17 Daut wrote: and i just got real lazy. will likely come back to it at some point, but i have no work ethic to finish something i start because i havent done anything productive in 8 years lold you seem like a creative guy with good ideas, how can u not be productive. I mean how do you want to spend your next 50 years

with a belly full of wine and a girls mouth around my cock?

The original algorithm maximizes P(r =1), where r is the rank of the chosen candidate. You are interested in maximizing E(r), the expected rank of the chosen candidate. Try to prove that your algorithm achieves a better value than the other one for the criterion E(r). Im sure someone has worked on such a variation before.

This link studies the generalized secretary problem. It seems that the optimal solution is similar to what you propose. I didn't read in detail.

http://vlab.ethz.ch/ROM/DBGT/Curves_files/BeardenMurphyDraft.pdf

This might be of interest too: http://www.spotlightmind.com/optimal-search

It was difficult to try your code because there's no spacing in the quotes. I put slightly cleaned up versions in gists:

Original:
https://gist.github.com/jchysk/2ea832c30f4a2d475079

Daut version:
https://gist.github.com/jchysk/7582c7618f9a35b9b5bd

I'm with Romm3l on implementing a search cost. Real world applications open up pretty dramatically when you incorporate a cost function to the mix. Then you can add in variable/static secretary salaries that scale with their overall ranks. I'm not very good with Python, but I could probably model this up in excel pretty easily. Either way, pretty interesting problem.