


Improved Solution to Secretary Problem? 

4 1 1 4 4 4 1 4 4 1 1 4 4 4 1 4 1 1 1 4

Daut United States. May 26 2014 14:56. Posts 8843   
Posting this here for 2 reasons. First as a brag, thought it was pretty cool that I came across a problem with some real world applications and was able to improve on the solution for the simplest case. And second cause there are some really smart mathematicians here (catyoul for instance and others) who may want to run with my algorithm and apply it to the more general cases or come up with even better algorithms than I have.
Was doing my normal web surfing last week and came across the secretary problem, something I had never heard of before.
http://en.wikipedia.org/wiki/Secretary_problem
" imagine an administrator willing to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed onebyone 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 (nn/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 099, 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 +
+ Show Spoiler +
#Original secretary problem solution based on 100 secretaries and just on the ranking of secretaries from 1100
#want to figure out both average ranking chosen and how often the best candidate is chosen
#function which sorts a list
def sortedRankings(sec):
x=0
while x <99:
import random
from random import randint
a = random.randint(x,99)
temp = sec[x]
sec[x] = sec[a]
sec[a] = temp
x = x+1
return sec
#function which returns a secretary based on original algorithm
def chooseSecretary(sec):
max=sec[0]
x=1
while x<36:
if (sec[x] > max):
max = sec[x]
x=x+1
while x<99:
if (sec[x] > max):
return sec[x]
x=x+1
return sec[99]
sec = list(range(0,100))
b=0
bestCount=0
total=0
winners = []
while b<1000:
secSorted = sortedRankings(sec)
chosen = chooseSecretary(secSorted)
if(chosen == 99):
bestCount=bestCount+1
total=total+chosen
b=b+1
winners.append(chosen)
print bestCount
print total/1000.0
#sort winners
a=0
while a<1000:
b=a
min=100
minLocation=1
while b<1000:
if(min > winners[b]):
min = winners[b]
minLocation=b
b=b+1
temp=winners[a]
winners[a]=winners[minLocation]
winners[minLocation]=temp
a=a+1
print winners
print winners[499]
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 +
+ Show Spoiler +
#edited secretary problem
#function which sorts a list
def sortedRankings(sec):
x=0
while x <99:
import random
from random import randint
a = random.randint(x,99)
temp = sec[x]
sec[x] = sec[a]
sec[a] = temp
x = x+1
return sec
#function which returns a secretary based on original algorithm
def chooseSecretary(sec):
max=sec[0]
max2=0
max3=0
max4=0
max5=0
max6=0
max7=0
max8=0
max9=0
max10=0
x=1
while x<36:
if (sec[x] > max):
max = sec[x]
x=x+1
while x<60:
if (sec[x] > max):
return sec[x]
if (sec[x] > max2):
max2 = sec[x]
x=x+1
while x<74:
if (sec[x] > max2):
return sec[x]
if (sec[x] > max3):
max3 = sec[x]
x=x+1
while x<84:
if (sec[x] > max3):
return sec[x]
if (sec[x] > max4):
max4 = sec[x]
x=x+1
while x<90:
if (sec[x] > max4):
return sec[x]
if (sec[x] > max5):
max5 = sec[x]
x=x+1
while x<93:
if (sec[x] > max5):
return sec[x]
if (sec[x] > max6):
max6 = sec[x]
x=x+1
while x<95:
if (sec[x] > max6):
return sec[x]
if (sec[x] > max7):
max7 = sec[x]
x=x+1
while x<97:
if (sec[x] > max7):
return sec[x]
if (sec[x] > max8):
max8 = sec[x]
x=x+1
while x<98:
if (sec[x] > max8):
return sec[x]
if (sec[x] > max9):
max9 = sec[x]
x=x+1
while x<99:
if (sec[x] > max9):
return sec[x]
if (sec[x] > max10):
max10 = sec[x]
x=x+1
return sec[99]
sec = list(range(0,100))
b=0
bestCount=0
total=0
winners = []
while b<1000:
secSorted = sortedRankings(sec)
chosen = chooseSecretary(secSorted)
if(chosen == 99):
bestCount=bestCount+1
total=total+chosen
b=b+1
winners.append(chosen)
print bestCount
print total/1000.0
#sort winners
a=0
while a<1000:
b=a
min=100
minLocation=1
while b<1000:
if(min > winners[b]):
min = winners[b]
minLocation=b
b=b+1
temp=winners[a]
winners[a]=winners[minLocation]
winners[minLocation]=temp
a=a+1
print winners
print winners[499]
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.


NewbSaibot: 18 TIMES THE SPEED OF LIGHT. Because FUCK YOU, Daut  Last edit: 26/05/2014 17:24 



lhr0909 China. May 26 2014 15:19. Posts 423   
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 




dnagardi Hungary. May 26 2014 15:22. Posts 1580   
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 



Daut United States. May 26 2014 15:26. Posts 8843   
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 

NewbSaibot: 18 TIMES THE SPEED OF LIGHT. Because FUCK YOU, Daut  



Daut United States. May 26 2014 15:34. Posts 8843   
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 

NewbSaibot: 18 TIMES THE SPEED OF LIGHT. Because FUCK YOU, Daut  Last edit: 26/05/2014 15:35 



Daut United States. May 26 2014 15:49. Posts 8843   
running each 5000 times for 099:
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?


NewbSaibot: 18 TIMES THE SPEED OF LIGHT. Because FUCK YOU, Daut  



Romm3l Germany. May 26 2014 15:56. Posts 285   
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. 



Daut United States. May 26 2014 15:57. Posts 8843   
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. 

NewbSaibot: 18 TIMES THE SPEED OF LIGHT. Because FUCK YOU, Daut  



Daut United States. May 26 2014 15:59. Posts 8843   
 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 

NewbSaibot: 18 TIMES THE SPEED OF LIGHT. Because FUCK YOU, Daut  Last edit: 26/05/2014 16:01 



Romm3l Germany. May 26 2014 16:03. Posts 285   
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). 



Romm3l Germany. May 26 2014 16:07. Posts 285   
 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: realworld 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] 

 Last edit: 26/05/2014 16:09 



Daut United States. May 26 2014 16:11. Posts 8843   
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. 

NewbSaibot: 18 TIMES THE SPEED OF LIGHT. Because FUCK YOU, Daut  



Daut United States. May 26 2014 16:17. Posts 8843   
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 

NewbSaibot: 18 TIMES THE SPEED OF LIGHT. Because FUCK YOU, Daut  



Daut United States. May 26 2014 16:36. Posts 8843   
SOMEONE GET FLOOFY TO CONTINUE PROGRAMMING THIS 

NewbSaibot: 18 TIMES THE SPEED OF LIGHT. Because FUCK YOU, Daut  



dnagardi Hungary. May 26 2014 16:39. Posts 1580   
 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 



Daut United States. May 26 2014 16:44. Posts 8843   
 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? 

NewbSaibot: 18 TIMES THE SPEED OF LIGHT. Because FUCK YOU, Daut  



nixxxbg Bulgaria. May 26 2014 22:36. Posts 431   
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. 



nixxxbg Bulgaria. May 26 2014 23:05. Posts 431   



jchysk United States. May 26 2014 23:10. Posts 435   




Bigbobm United States. May 27 2014 01:06. Posts 5490   
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. 

Its time to stop thinking like a bitch and think smart like a poker player  ket  

 


Poker Streams  
