Secretary Problem
en.wikipedia.org
Secretary Problem
1–10 of 66 posts
Re: Secretary Problem
#2Is it possible to explain in layman's terms why 1/e is the magic number?
Re: Secretary Problem
#3Very interesting! I assume this is posted because it parallels how YC does their interview admissions. I think the YC method has some differences to this problem. YC has already seen the applications for groups, and probably already developed some kind of best to worse ranking of the applicants. The interview most likely functions as a confirmation that the teams live up to their great application. Additionally, YC expands its class to fit the number of qualified applicants. In this problem there is single spot to fill.
Edit: It is also totally possible many people upvoted this article only because it is interesting. If that is true ignore my post.
Re: Secretary Problem
#4Is it possible to explain in layman's terms why 1/e is the magic number?
The function that approximates the best ideal solution can be approximated with the log function. It's kind of like why the taylor polynomials means that e^pi*i = -1
Re: Secretary Problem
#5On a related note, can someone suggest a good textbook optimal stopping?
Re: Secretary Problem
#6The section on experimental studies touches on it briefly, but it's important to note that costs involved in the selection process are not considered in the standard construction of the problem.
From wikipedia:
> In large part, this work has shown that people tend to stop searching too soon. This may be explained, at least in part, by the cost of evaluating candidates.
and then
> For example, when trying to decide at which gas station to stop for gas, people might not search enough before stopping. If true, then they would tend to pay more for gas than they might had they searched longer.
So you might pay more for gas if you don't use the optimal strategy, but waste more money in fuel costs searching for the cheaper price than you save buy purchasing at that price.
Perhaps most interestingly, there is a formulation of the problem that requires a decision to be made within a certain time period, from an unknown number of candidates who arrive over that time period. If you know (or can estimate) the arrival times of the candidates, you can use a very similar strategy to achieve optimal results.
Essentially, wait until you have seen 1/e of expected candidates in the time frame you have allowed for (based on the arrival density function you know or estimated) then pick the next best option.
This puts a limit on the amount of searching you do, and so provides an optimal strategy with a bounded limit on how long you search for; it provides a bound on the cost involved in the search assuming the cost is related to time taken.
In the searching for gas example, you could use this strategy if you knew roughly how often you pass a gas station, and how long you are willing to search for.
Re: Secretary Problem
#7What about needing to hire M candidates out of N applicants?
Re: Secretary Problem
#8What about needing to hire M candidates out of N applicants?
And what about preferring the second best candidate to the average candidate... say if you interviewed 95% of applicants after rejecting the first 37%, and then you find a candidate who is almost, but not quite, as good as the very best one?
Re: Secretary Problem
#9I'm going to be the dumb guy ranting here and say that I dislike this word problem since external knowledge of the world can change your strategy. I might be stopping too soon because the time cost of evaluating candidates is far too high compared to the work that needs to be done immediately. The sooner I get someone in, the sooner that work gets done, the less behind we all get, the less workload for the new secretary, the better he/she will perform, and the better the first impression.
You might also be able to recognize a rock star secretary immediately or recognize obviously incompetent people. There's a competence threshold that's present here and has to be addressed if you dissect the analogy. Going for 'best' here has diminishing returns beyond a certain level of competence. The immediate need to decline/accept also really doesn't make sense if we're trying to explain this with a hiring analogy.
However, the Game of Googol nails it and I really like this approach much better when explaining this problem. It's a game with arbitrary rules so I can't easily use my worldly experience biases to solve the problem.
Re: Secretary Problem
#10What about needing to hire M candidates out of N applicants?
Without thinking about it too much...
One solution might be to try and find the the best candidate after (N/M)/e candidates, rather than N/e candidates. Then find the best candidate after (N_remaining/(M-1))/e candidates. That is recurse, by finding one candidate at a time, and discarding less then N/e each time to ensure you get enough candidates.