Secretary Problem

http://en.wikipedia.org/wiki/Secretary_problem#body

by nate_martin • 12 years ago

90 64 12 years ago

en.wikipedia.org

_xhok• 12 years ago

Is it possible to explain in layman's terms why 1/e is the magic number?

gargarplex6• 12 years ago

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

mchusma• 12 years ago

I don't think that was exactly a lay explanation. Was interested myself.

zindlerb• 12 years ago

Very 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.

forgotprevpass• 12 years ago

On a related note, can someone suggest a good textbook optimal stopping?

judk• 12 years ago

If you get a stream kf recommendations, how will you choose which one to read?

tunesmith2• 12 years ago

Since the first candidate always gets ignored, I'll recommend "Green Eggs And Ham".

Cogito2• 12 years ago

The 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.

sesqu3• 12 years ago

The formulation you're talking about is mentioned in the article, under "unknown number of applicants".

However, it's worth pointing out that the strategy is unacceptable for the gas station scenario, because of the high probability of total failure.

vehementi• 12 years ago

What about needing to hire M candidates out of N applicants?

D_Alex• 12 years ago

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?

Cogito2• 12 years ago

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.

hoonose• 12 years ago

There's a large body of work on variations of the secretary problem. The one I know of which is most relevant to your question is section 4 of the following: http://www.cs.cornell.edu/~rdk/papers/secArt4.pdf

Section 6 is particularly interesting, where you're further restricted - you want to choose multiple secretaries, but there's certain constraints on the sets you can choose. For example, the secretaries might be edges in a graph, and you can't pick a subset of edges which would result in a cycle (this is a "graphic matroid," which is an example of a mathematical object known as a matroid). The reason why this formulation of the problem is interesting is because the best known algorithm is O(sqrt(log k))-competitive (where k is the rank of the matroid), whereas it is conjectured that an O(1)-competitive algorithm exists.

yogeshgirdhar• 12 years ago

I worked on a version on this problem where the goal is to maximize the probability of hiring all top M candidates while using a similar single threshold strategy.

Here is a link to my paper: http://www.cim.mcgill.ca/~yogesh/publications/crv2009.pdf

imdsm2• 12 years ago

I modified the one I worked on:

http://jsbin.com/woyehiyu/1/edit

(JavaScript, Console tabs. Click Run)

FLUX-YOU2• 12 years ago

I'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.

chaz• 12 years ago

I think the difference is that you're reading it as practical word problem, when the intent is to present a math problem.

I first heard about this problem in a politically incorrect variation: a tribe chief is given the opportunity to choose a wife from a pool of n women, presented in a random order, one at a time. He can choose any woman, but can't choose a woman who he has already passed up. What's the strategy for the chief to choose the most beautiful wife?

aaronsnoswell• 12 years ago

How is that variation politically incorrect? Genuine question here. If anything, to me it seems culturally correct.

aleksi• 12 years ago

Interesting. In Russia this problem is known as choosy bride problem, where bride is looking for the best groom.

Sammi• 12 years ago

Isn't that basically how dating works? It's hard to go back to an ex...

roel_v3• 12 years ago

I think that when presenting a problem like this, it's not unreasonable to assume that the audience is capable of the abstract thinking that is needed to distill the underlying problem from the application in which it is presented.

Come to think of it, maybe I'd argue even stronger: when I was younger, I had a hard time understanding programming problems that were explained in terms of 'foo / bar' classes or function names. 'Applied' examples with cars and wheels made more sense, even if I could easily have come up with 'not every car has 4 wheels' counterarguments. Nowadays, I like foo / bar better, because they expose the problem directly, without an additional layer of real-world application, but only because I've gotten better at abstract reasoning.

jakobe• 12 years ago

As I became more experienced, I started understanding abstract concepts better because I have already seen more real world things. I can now quicky think of my own examples in my head.

(Aside: This is why I think you should work first, study later. University deals with abstract concepts, but without experience these abstract concepts often mean nothing to you)

gyom• 12 years ago

If you play that game with any kind of prior belief about the values that you're about to see, then the theoretical solution is not longer valid.

What you're describing with the rock star vs incompetent people scenario is about bringing prior knowledge in there. You see a rock star as first candidate. You figure that, in your lineup of 10 people, odds are that no one will be better than that rock star. So you pick him/her.

This makes the theoretical solution at best a kind of intuitive justification in practical settings, but you shouldn't apply it mechanically without using your judgment.

sk5t• 12 years ago

Quite interesting that discarding the first n/e candidates produces a 1/e probability of choosing the optimal one...

As for real-world applications, the only one that comes readily to mind is rolling up a D&D character, supposing one has only the patience for some predetermined n rolls. Somewhat ironically it is not a realistic fit for hiring, as there is seldom a need to accept or eliminate candidates immediately, interviewing more than 5-6 people for a role is torturous, and an interviewer uses his experience interviewing and interacting with people generally to have no mathematical prejudice against hiring the very first pretty-good option.

thaumasiotes• 12 years ago

Quite interesting that discarding the first n/e candidates produces a 1/e probability of choosing the optimal one...

Freeform thoughts from here:

1/e is the probability of failing (every time) if you try a 1/n chance n times, where n is large.

To get the optimal choice, there are two (generously defined) requirements:

- #1 does not occur in the discarded group

- #1 occurs before everyone else who was not discarded, but exceeds the maximum of the discarded group

The second one seems hairy to me, so I'll wrap things up here. ;p

As for real-world applications, the only one that comes readily to mind is rolling up a D&D character

This was introduced to me as a marriage problem, and wikipedia also notes it by that name. The analogy never seemed inaccurate to me; it's frowned upon to evaluate candidates simultaneously and rare to accept someone other than the latest candidate.

kokey• 12 years ago

Interesting. It describes roughly the strategy that I've settled on when looking for accommodation to rent. I think it also has the added advantage of making you feel you've made a good decision.

jmtame• 12 years ago

I worked on several iterations in the dating space for about a year, and this type of stuff was pretty interesting to me. Wrote a bit more about it here: https://medium.com/unfinished-thoughts/2cac1e6cc7b4

Johnie• 12 years ago

The same strategy can be used in dating too.

When you live in a major city and the dating options are boundless, there is always someone around the corner that is "perfect" or more perfect than the current person that you are dating. Next thing you know, you're in your late 30s and still single.

gargarplex6• 12 years ago

I always feel bad when I see these posts. I'm 26 and in a major city, but finding dates is a serious problem for me. My looks are only slightly below average (4/10) but my personality is probably the deal breaker.

aegiso2• 12 years ago

Having been where you've been, may I suggest that the dealbreaker is that you're treating dating like a World of Warcraft inventory checklist? I wish someone had told me that when I was saying the same things.

roel_v3• 12 years ago

Cheer up, there must be below-average looking people with shitty personalities just like yourself out there who are just right for you!

(just kidding and don't take it personal - this one was too easy to pass up...)

brc• 12 years ago

Everybody gets what they want out of dating.

If you want excitement, you'll get excitement. If you want stability, you'll get stability. If you want to confirm an opinion of yourself as undateable - guess what, that's what you'll get.

Most people say they want one thing but actually don't work towards that thing. They just pay it lip service.

philbarr3• 12 years ago

Try out my guaranteed chat up line: "Polar bear! It's just something to break the ice..."

Then laugh drunkenly at your own joke - that bit's important.

Worked for me - married over 10 years now.

aegiso2• 12 years ago

This only works if you stick with every partner long enough to get a perfectly accurate assessment of them as a long term mate, that your assements are perfectly objective, independent, and stable, and that you know n.

The amount of ifs, ands, and buts in this caveat means it's time to defer to one of my favorite xkcd's of all time. [0]

[0] http://xkcd.com/55/

eonwe• 12 years ago

And then commit to the choice you've made: http://xkcd.com/310/

cheald• 12 years ago

How do you arrive at n, your total pool of potential candidates?

azernik• 12 years ago

http://en.wikipedia.org/wiki/Secretary_problem#Unknown_numbe...

blinry• 12 years ago

Note that if you want to optimize the quality of the candidate, not the probability of picking the best one, it's better to stop after sqrt(n) candidates: https://en.wikipedia.org/wiki/Secretary_problem#Cardinal_pay...

philjohn• 12 years ago

There's a TV show in the UK that uses a spin on this - it's called 4 rooms.

The premise is that people come on the show with, what they consider to be, a valuable artifact. They then have the chance to take it to 4 collectors who will offer them a sum of money for said artifact.

The aim is to come away with the best offer you can get - but you only get one shot with each collector, you can't go back to a previous one because all other offers have been lower.

oggy• 12 years ago

Are the collectors aware of the order in which they talk to the seller? That is, is the 4th collector aware that he's the "last chance" for the seller?

ronaldx• 12 years ago

No, it's claimed they are not aware.

Although it's not clear how they avoid timing attacks.

AUmrysh• 12 years ago

Sometimes they ask and the seller will tell them. Sometimes the seller will try to use it as a bargaining tactic (which inevitably fails).

jonlucc• 12 years ago

According to the article, with such a small n, the contestant should visit ~1.47 of collectors before picking the best one. That's hard to do in practice.

sesqu3• 12 years ago

According to the article, with such a small n, the contestant should reject the first collector and pick the best offer from the other three.

cshimmin• 12 years ago

See also Feynman's Restaurant Problem: http://www.feynmanlectures.info/exercises/Feynmans_restauran...

philbarr3• 12 years ago

Hmm, I wonder if this could be used to find a decent pub whilst in a strange city?

It's always a problem when you're on holiday and you know there are n pubs around, but you don't want to spend all your time going around and checking each and every pub 'cos that gets tedious. The question is - how many pubs should I visit before I give up?

As a general rule is this saying you should visit n/e pubs and then just pick the next best one?

prof_hobart• 12 years ago

It would. But you'd need to know, or at least guess, how many pubs there were in the city (to know when you'd reached n/e), and it would also depend on whether the pubs were randomly distributed or not. If there's nice end and a trashy end of town, you could easily have exhausted all of the good pubs before you hit the n/e.

philbarr3• 12 years ago

Yes, I guess you'd have to use real world factors to try and trim down your n before you start with the n/e thing. Although if you're in a strange place you probably won't know that much about which areas are good or not.

vijucat• 12 years ago

I, like many others, used to have the attitude that "puzzles are for interviews". But recently, I have started seeing that there can be practical applications for seemingly academic ideas.

For example, I know a proprietary trader who uses a concept similar to this from the field of Optimal Stopping for his trading system exclusively, i.e., his entire trading strategy, managing tens of millions of dollars for a big bank, is basically an application of Optimal Stopping to the markets!

imdsm2• 12 years ago

Well, that was fun. (use console output)

Single candidate: http://jsbin.com/cupiloye/1/edit

M candidates: http://jsbin.com/woyehiyu/1/edit

cschmidt• 12 years ago

This gets posted on HN occasionally, and when it does I post this fun blog post by Michael Trick, a CMU Operations Research professor, who used the Secretary problem to pick his wife:

http://mat.tepper.cmu.edu/blog/?p=1392

Secretary Problem

Related Stories