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.

On May 27 2014 00:06 Bigbobm wrote: 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.

suppose theres a search for a position. there are 3 things at play
-the more secretaries you search for, the more time and possibly cost goes by
-the longer you search, the longer a position is unfilled
-the days that you are searching you are not paying a new employee

i dont really know what kind of costs it takes to search for a new employee, nor do i know how much value a secretary adds versus her salary (or any position for that matter in a general sense). this seems kinda hard to model even though it likely is the single most important part of the whole real world equation lol

i think keeping it abstract at first is probably the best idea, mainly because the real world applications wont be at all similar. unknown N, ability to go back and call people already interviewed and no way a great candidate wouldnt be snap hired because she was one of the first applicants. its just a little silly to call it a secretary problem. it really should be applied to dating/marriage.

That was pretty cool. I might actually use this in real life. Can you go on further about the significance of e in the initial solution?

Hey I tried to generalize the problem so you do something other than 100 sec's but I'm finding the best match 35% of the time so I screwed up somewhere.
https://gist.github.com/RobertCorey/5fcdc0e6b07ba56fb91a
honestly thinking about ranges makes my brain hurt i'm the worst with off by 1 errors, when i played monopoly as a kid I could never remember if you were supposed to count the square you were on.

Btw in terms if code, you should create a function for all those while loops. Should also try and make those static checkpoints dynamic based on the number being ranked. That will likely take more work than necessary but it's still a good practice to have.

this is cool

Well, it's not an improved solution to secretary problem. Yours is a proposal to a different problem. For your problem:

If n is large you can approximate the distribution of population, say, by sampling first 1 million candidates. Stop at the first candidate who is better than 99.99% of approximated population. With large n, you should able to do this ~100% of the time.

^what you proposed there is a very different problem to op's or the orig secretary problem (which is more similar to op's than yours).. We're considering a situation where n is sufficiently small that there's a tradeoff between sampling enough candidates to get an idea of the distribution and what's considered good, and running the risk of losing the best candidates to the sampling process / not having enough candidates left to select from after. That's a fundamental idea behind the secretary problem, and that's the problem daut is trying to solve but with a modified payoff function (orig payoff function is 1 if best is selected, 0 otherwise). If you lose that tradeoff property from the problem you're looking at, you no longer have so many parallel situations that exist in the real world.

On May 27 2014 03:36 Daut wrote: Show nested quote + On May 27 2014 00:06 Bigbobm wrote: 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. suppose theres a search for a position. there are 3 things at play -the more secretaries you search for, the more time and possibly cost goes by -the longer you search, the longer a position is unfilled -the days that you are searching you are not paying a new employee i dont really know what kind of costs it takes to search for a new employee, nor do i know how much value a secretary adds versus her salary (or any position for that matter in a general sense). this seems kinda hard to model even though it likely is the single most important part of the whole real world equation lol i think keeping it abstract at first is probably the best idea, mainly because the real world applications wont be at all similar. unknown N, ability to go back and call people already interviewed and no way a great candidate wouldnt be snap hired because she was one of the first applicants. its just a little silly to call it a secretary problem. it really should be applied to dating/marriage.

I think we don't need to make such a technical model for search cost.. just linear increasing with number searched will do the job and be close enough to the real world once you get the size of the increment right relative to payoffs.

Once you have search cost I think you don't need to consider a limit to N anymore as you said, since you already have pressure to hurry up and pick someone and not look forever.

Another thing to add to the mix that exists in the real world is a set of a priori beliefs about secretary ability that gets bayesian updated after each search, instead of going in with 0 assumed knowledge of the distribution before your first search

On June 03 2014 06:49 Romm3l wrote: ^what you proposed there is a very different problem to op's or the orig secretary problem (which is more similar to op's than yours).. We're considering a situation where n is sufficiently small that there's a tradeoff between sampling enough candidates to get an idea of the distribution and what's considered good, and running the risk of losing the best candidates to the sampling process / not having enough candidates left to select from after. That's a fundamental idea behind the secretary problem, and that's the problem daut is trying to solve but with a modified payoff function (orig payoff function is 1 if best is selected, 0 otherwise). If you lose that tradeoff property from the problem you're looking at, you no longer have so many parallel situations that exist in the real world.

My understanding of orig secretary problem does not assume sufficiently small n. In orig problem, both cost and benefit of searching are functions of n -that is, when you are concerned with determining the best candidate. Size of n doesn't matter.

Maybe small n was implied in op's problem.

Yeah, its a different problem, we can call it the "Daut's marriage problem", how to maximize the average scoring if they are ranked from 1 to 99. But then you have to prove that your algorithm is the best for that problem (we only know from a numerical method that its better than the original algoritm for the original problem).
I think the most practical result would be to get a set of must have rules like you have to leave your first X girlfriends you expect to date in your life but dont wait more than Y, becouse there are so many variables in the real world and sometimes not enough sample to use exactly the e number.
We can start studying the most basic marriage problem and then adding some complexity and try to solve it analytically.
So I'd do:
1. find the best solution to maximize average
2. add search cost (includes search, time being single, score decreasing becouse you get older)
3. random scores normalized (0 is the bottom of your choosing range, and 1 the top)
4. random scores distributed in a more realistic way (there are more bottom girls than top ones, so maybe you can use a top side of a normal?)
5. think this problem for poker?. If I play 2hr sessions, should I play now against this weak reg or wait for a weaker reg or fish?

Fuck my N number for girlfriend is low. How do I find my distribution ?
More seriously, I really like the problem set this way.

6. what if the girls are also playing the marriage problem and can dump you?

On June 03 2014 14:40 YourHarry wrote: Show nested quote + On June 03 2014 06:49 Romm3l wrote: ^what you proposed there is a very different problem to op's or the orig secretary problem (which is more similar to op's than yours).. We're considering a situation where n is sufficiently small that there's a tradeoff between sampling enough candidates to get an idea of the distribution and what's considered good, and running the risk of losing the best candidates to the sampling process / not having enough candidates left to select from after. That's a fundamental idea behind the secretary problem, and that's the problem daut is trying to solve but with a modified payoff function (orig payoff function is 1 if best is selected, 0 otherwise). If you lose that tradeoff property from the problem you're looking at, you no longer have so many parallel situations that exist in the real world. My understanding of orig secretary problem does not assume sufficiently small n. In orig problem, both cost and benefit of searching are functions of n -that is, when you are concerned with determining the best candidate. Size of n doesn't matter. Maybe small n was implied in op's problem.

heh that's true.. orig problem does give solution in terms of n. if n is so ridic big though that you can leisurely search 1mm candidates and have an excellent idea of the distribution and have plenty of candidates left over afterwards to select from then it doesnt really matter anymore where exactly we draw the line between search/select since it makes no material diff between searching the first 1mm or 1.5mm, so trying to get the answer of the orig problem stops being useful