Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Secretary Problem

en.wikipedia.org

Post reply on HN
Print view View original

61–66 of 66 posts

Re: Secretary Problem

#61

Post by AUmrysh »

oggy wrote: post #40
philjohn wrote: post #31

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…

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?

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

Re: Secretary Problem

#62

Post by sesqu »

Cogito wrote: post #6

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…

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.

Re: Secretary Problem

#63

Post by sesqu »

jonlucc wrote: post #52
philjohn wrote: post #31

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…

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.

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.

Re: Secretary Problem

#64

Post by sesqu »

philbarr wrote: post #53
prof_hobart wrote: post #51

Earlier quoted context omitted.

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.

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.

However, to find merely a good pub, √n is enough, given the assumptions mentioned later in the article.

Re: Secretary Problem

#65

Post by gyom »

FLUX-YOU wrote: post #9

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 secret…

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.

Re: Secretary Problem

#66

Post by jamesiain »

sesqu wrote: post #63
jonlucc wrote: post #52

Earlier quoted context omitted.

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.

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.

More precisely; reject the first offer but note the price, accept any offer that beats the first one, or accept the final offer if none beat the first.
Post reply on HN