14

As you know, we use the "Secretary Problem" to choose the single best candidate. Now I would like to know can we use this rule to find the worst candidate, too? If yes, how to accomplish this?

Vahid Damanafshan
  • 243
  • 15
    Just turn the evaluation upside down, i.e., "better" ~~-> "worse" – vonbrand Mar 03 '14 at 16:17
  • 1
    There is a useful lesson here: When you have an algorithm or a theorem involving an ordering, it usually works for the opposite ordering too (though not always). – Jørgen Fogh Mar 04 '14 at 12:57
  • Reminds me of a joke my boss told me about the executive who had to decide which two of his three secretaries he had to let go... – Michael Mar 04 '14 at 15:52
  • 3
    @JørgenFogh Interesting thought. Can you give examples which use ordinal (not interval/ratio) data which won't work? Or are interval/ratio algorithms the exceptions you were referring to? ACtually, I think maybe I should ask this in its own question. – rumtscho Mar 04 '14 at 16:14
  • 1
    @JørgenFogh I doubt there's any decision algorithm which won't work for the opposite ordering. An example would be really nice. – flonk Mar 06 '14 at 16:13
  • 1
    I think I expressed myself incorrectly. What I was trying to convey was that you cannot assume something always works, just because you can't think of a counterexample. – Jørgen Fogh Mar 06 '14 at 16:45

3 Answers3

45

Yes.

The algorithm simply finds the participant who is optimal according to some property, but does not care what that property means (as long as it defines an ordering relation on the candidates). Changing that property from being good to being bad (or whatever else) is just a definition without algorithmic relevance.

flonk
  • 2,434
19

I think he wants to know if you can use the procedure to choose the worst (instead of the best) candidate. The answer is yes.

The situation is: you know how many candidates $N$ there are, but you don't know the distribution of the quality of the candidates. Also, you can only look at one candidate at a time, and not go back to a previous candidates ("no recall").

You use the $1/e$ algorithm: first look at $1/e$ of the $N$ candidates, and remember the quality of the worst of those, which is, say, $\underline{q}$. After the $N/e$ sampled candidates, you choose the first candidate that is worse than what you have previously seen, i.e., you choose candidate $i$ if $q_i\le \underline{q}$, and candidate $N$ if no candidate's quality was worse. This procedure maximizes the probability to choose the worst candidate.

This is just the inversion of the solution to maximize the probability to choose the best candidate.

Nameless
  • 4,045
  • 2
  • 20
  • 36
17

Sure, the algorithm will just choose a highly ranked candidate (probably). It's up to you how you rank them - by how good they are, or by how bad they are, the algorithm doesn't know what the ranking system means.

Neil W
  • 2,495
  • 1
  • 13
  • 16