Talk:Secretary problem

Untitled

I disagree with the comment in the section 'Deriving the optimal policy' where it says (second best overall). This is not necessarily the case, the second best overall may occur AFTER i (the best), but we may still choose i as long as the best in the (i-1) options falls in the first (r-1) as stated. Hsenrab (talk) 09:53, 26 August 2014 (UTC)

Sounds like Amazon's gold box. --Mr. Vernon 05:21, 23 May 2006 (UTC)

This issue gets attention in mainstream-ish press every now and then, due to its application to finding a life partner (hence the names "marriage problem" and "fussy suitor problem"). I wonder if the romantic implications should be fleshed out a bit, or at least mentioned after the first sentence. --AlexChurchill 14:51, 3 October 2007 (UTC)

This is covered in the references I added. I think an additional sentence is still a good idea. Spot (talk) 22:33, 25 February 2009 (UTC)

Actually I think it's worth a whole section, especially in light of what Ketelaar and Todd have to say, ie that using the 37% Rule you end up waiting on average 75% before finding a match, and the chances of being squeezed out at the end are high. Making a faster decision substantially reduces the worst case, and in fact biological systems seem to do this. Spot (talk) 00:45, 31 March 2009 (UTC)

I had some trouble determining what it meant to 'skip' an applicant, whether to skip their interview, or ignore their ranking. It seems it has to mean simply to not select them. Couldn't we just say that? Also, wouldn't that mean you have a 1/e probability of ending up without a secretary? I don't think that's acceptable. –Sarregouset (talk) 18:44, 30 October 2008 (UTC)

I've always know it as the marriage problem -- is maybe more politically correct nowadays, I believe the original secretary problem was not about hiring for typing speed. Should we change the title? — Preceding unsigned comment added by 143.167.9.250 (talk) 09:09, 5 March 2014 (UTC) What you personally might have known it as seems like an overly subjective criterion, and "secretary problem" is the classic name (See Cormen, Leiserson and many other core references in computer science and discrete mathematics et al.). and how is that not politically correct, assuming that was even a valid criterion? — Preceding unsigned comment added by 2602:306:CC28:1850:6233:4BFF:FE25:3DC7 (talk) 13:39, 19 February 2016 (UTC)

Concerning Making precise+Unknown number+1/e-law

Making precise: The optimality of a strategy to wait until a number r of applicants and then to select a candidate is n o t proven here. This is why I have added " it can be shown ...."

Unknown number of options: This question is probably the most often asked about the secretary problems (at least acccording to my experience) and should therefore figure in this article. The same holds for the 1/e-law.

Perhaps it would be a good idea to make these two paragraphs a separate Wikipedia article under the title 1/e-law. 81.243.238.145 (talk) 21:04, 2 March 2009 (UTC)

91.177.137.217 (talk) 01:25, 2 March 2009 (UTC)

Remark (date 7 March 2009) to modification done 6th March 2009: Note that the term "37%-rule" should not be inserted under the subsection for an unknown number of applicants. In real time this stays compatible only if the arrival time density f is uniform on [0,T]. (Of course you are right in the sense that it is still an expected 37% of applications, but the clarity would suffer) 91.176.39.254 (talk) 11:35, 7 March 2009 (UTC)

Why is 37% Rule is less clear than 1/e strategy? Both refer to the same thing. Spot (talk) 18:44, 9 March 2009 (UTC)

Deriving the Expression

Could someone provide an explanation of the terms in the sum for the probability of finding the optimal candidate? The (1/n) term I can guess comes from each candidate having a 1/n probability of being the best, but the second term befuddles me. Thanks! Matt.matolcsi (talk) 00:23, 26 January 2010 (UTC)

I've updated the formula to explain this more clearly. ZfKswHexTW (talk) 21:31, 31 March 2011 (UTC)

Why did you tag your edit as “minor”? DES (talk) 21:44, 1 April 2011 (UTC)

It would be nice to explicitly state that the assumptions of the (1/n) term. If, for example, you have some reason to expect the candidates will get better as you get nearer to N, a different distribution should be used, perhaps something like 2i/(N(N+1)). — Preceding unsigned comment added by 24.86.238.180 (talk) 05:44, 28 January 2012 (UTC)

Missing Assumption

I believe that the development of the solution is making an assumption not listed in the premises: That there is no upper bound to the quality of candidates. Suppose that you have a job to fill and that you have some quantifiable requirements. It is possible that one or many candidates fulfill those requirements completely. Then, you should accept such a candidate whenever he/she appears, for you can never do better, and there is a substantial chance that you may not find another 100% suited candidate later. Actually, even if you accept that there can always be a better candidate (ie, no upper bound on suitability), the proposed solution may be wrong depending on the assumed distribution of candidate's suitability. For instance, suppose you are to interview a total of 100 candidates. The given solution calls for unconditionally rejecting the first 37 or so. But suppose you also estimate that the percentage of very good candidates (for some definition of 'very good') is just 0.01% of the general population. Then, if the, say, second candidate that you interview is very good, does it make any sense to send him away? The expected chance of having some other very good candidate among those still waiting for an interview is very small, less than 1%. —Preceding unsigned comment added by 93.102.239.14 (talk) 17:12, 17 September 2010 (UTC)

Good point there. I would also add that another unstated assumption seems to be that the selector has 100% accuracy in discerning candidate quality. 74.12.5.218 (talk) 20:52, 28 March 2015 (UTC)

Right, the stated solution to the Secretary Problem is the best possible only when there is no a priori knowledge of the distribution of values (eg, candidate's scores). Martin Gardner's formulation of the problem (as the Googol problem) makes this much clearer, since in the real world, in general, a prospective employer will have at least some notion of the job market he's hiring from. When this (even approximate) a priori knowledge is available, one can in fact do better (systematically) than the stated solution. — Preceding unsigned comment added by 79.168.138.50 (talk) 01:08, 20 September 2016 (UTC)

Heuristics

This is not my area, but CSP is used without being defined, I have no idea what it is.--Billymac00 (talk) 06:31, 6 March 2011 (UTC)

It's been added in this edit, possibly it means Constraint satisfaction problem...? --CiaPan (talk) 11:53, 9 March 2011 (UTC)

Evidently it means "classical secretary problem", i.e., the problem as described at the top of the page, since (a) it refers to the n/e solution already noted as optimal, and (b) the phrase "classical secretary problem" does appear elsewhere in the article. I've replaced CSP with this expansion. Joule36e5 (talk) 01:45, 27 January 2012 (UTC)

Generalizations / Variants

The article now has three *non-consecutive* sections about generalizations / variants: "cardinal payoff variant", "other modifications", and (4 sections later!) "combinatorial generalization". it would be great to somehow compile these together into a coherent section about generalizations. also, it should probably include more central variants: i know that in computer science the "matroid secretary problem" has been very popular - maybe someone with operation research background can make better suggestions. — Preceding unsigned comment added by 2602:306:CE74:C530:0:0:0:3E8 (talk) 16:45, 26 November 2015 (UTC)

a paradox of T. Cover.

... which is closely related to a paradox of T. Cover.

— [1]

What is "a paradox of T. Cover"? Is T. Cover a name of somebody? --Quest for Truth (talk) 02:11, 10 July 2016 (UTC)

@Quest for Truth: Possibly it's Thomas M. Cover, probably the author referenced by Alexander V. Gnedin (Secretary problem#CITEREFGnedin1994) – see the linked page for a PDF file, open it and scroll down to the page 8.
In References you'll find

Cover, T.M. (1987). Pick the largest number. In Open Problems in Communication and Computation (T.M. Cover and B. Gopinath, eds.) Springer, New York

And a little of googling returns (a.o.) this link:

http://www-isl.stanford.edu/~cover/papers/paper73.pdf

HTH. --CiaPan (talk) 08:06, 11 July 2016 (UTC)

@CiaPan: Thanks! I've added a link to Thomas M. Cover. It's a shame that Wikipedia does not have an article about "the paradox", not even a mention in Thomas M. Cover's article. --Quest for Truth (talk) 17:45, 11 July 2016 (UTC)

@Quest for Truth: There exists an article Two envelopes problem about a specific version of the paradox (with arbitrary numbers A and B replaced with x and 2x, for some unknown x). The article has been created in 2005, and a reference wikilink to T.M.Cover was added by Gill110951 in May 2011 (Special:Diff/428222564). --CiaPan (talk) 14:04, 12 December 2019 (UTC)

I have been writing a long paper on the various versions of this paradox, take a look at [2]. Maybe I will finish it one day. Note: "the two envelopes problem" is actually also the name for a whole family of related problems, of which Cover's is just one variant. That's why it is cited in the Wikipedia article on TEP. Richard Gill (talk) 16:16, 2 January 2020 (UTC)

Abstraction boundary

I just added the following text to the bottom of the lead:

It's assumed in this algorithm that the applicants have no knowledge of the decision algorithm employed, because the algorithm depends on the early applicants (who have no chance at all) bothering to actually show up, and then behaving as if the job is winnable. It also assumes that candidates always put forward the same performance, regardless of their own assessment of the depth of the competition, whereas in real life, people faced with long odds (or what they perceive or construe as long odds) tend to take greater risks in order to stand out.

It some ways, that's probably not suitable text. But perhaps it's better than nothing in pointing out some of the paradoxical assumptions involved in achieving this clean, simple abstract solution.

The first moment I really thought about the algorithm, the part about assigning zero chance at all to the first n/e applicants, from the point of view of the applicants I LOLed because of my economics training.

Way to wins friends and motivate people: involve them in an interaction where you have a high margin on the quality of their behaviour, but they have no upside at all on the quality of the performance they put forward.

Clearly this can't work under any kind of accurate disclosure at all.

"I've invited you here to prime the pump—with no chance of winning this job for yourself whatsoever—but do please put forward your most earnest supplication betters it matters to my own algorithm a great deal."

It's almost an economic paradox to think this could ever work.

One could even question whether this algorithm is ethical in all cases.

Probably something should be said about this, somewhere in the article. — MaxEnt 13:35, 5 November 2018 (UTC)

Probability of success of the "postdoc" variant (in the section "other modifications")

Why isn't the formula ${\frac {0.25n^{2}}{n(n-1)}}$ simplified to ${\frac {0.25n}{n-1}}$? MaigoAkisame (talk) 00:00, 15 July 2019 (UTC)

Whatever Happened to Common Sense ?

This "secretary problem" just needs the application of common sense. The algorithm totally fails if all the best applicants are in the first third to be interviewed !

As the interviews are random, the best applicant is equally likely to be the first, the last, or the middle one.

The best solution is so simple: interview all the applicants, then select the most suitable.

This whole "problem" (and many like it) demonstrate the way that many academics have their heads in the clouds and have lost touch with reality and plain simple common sense. — Preceding unsigned comment added by Darkman101 (talk • contribs) 21:53, 3 April 2022 (UTC)

It’s a fun math problem. Learning how to solve it teaches you how to approach real world problems, too. Of course it is totally unrealistic. Nobody takes it seriously. Part of the point is that if you are only satisfied with the best you’re often going to end up disappointed. Richard Gill (talk) 02:17, 4 April 2022 (UTC)

Harvard refs

In-line Harvard citations were deprecated two years ago. See Template:Harvard citation no brackets and WP:PARREF. I have changed a few of these, but it would be good to convert the rest of them. GA-RT-22 (talk) 17:54, 19 August 2022 (UTC)

Doubts about ranking in Strategic analysis and Heuristic performance sections

In Strategic analysis section the best option has the highest ranking: "... For example,  0.2, 0.3, 0.3, 0.1 is changed to 2, 3, 4, 1 or 2, 4, 3, 1 with equal probability ...". The largest value 0.3 has the highest rank (3 or 4)

In Heuristic performance section: "... first encountered candidate (i.e., an applicant with relative rank 1) ...non-candidates (i.e., applicants with relative rank > 1)". This implies that the best candidate has rating 1.

Unless I miss something, it seems inconsistent and misleading Merlin.anthwares (talk) 10:35, 14 October 2024 (UTC)