Secretary problem
In statistics, game theory and decision theory, the secretaries problem called (also known as marriage problem, but not to be confused with the problem, which is the marriage rate was based ), the task of selecting the best of a number successively considered one of the candidates of different quality. This rejection is irrevocable. Because of the contained elements of chance, the problem is usually formulated so that the highest probability is determined for the selection of the best offer. A solution algorithm for this problem is given by the odds - strategy.
The optimal solution of the problem as 37 % rule (or rule) designated and described by Geoffrey Miller in his book "The mating mind". It says that one the first 37 % (or more precisely ) candidates considered and then accepts the first candidate (ie, the previously found optimum) is better than all previous. It may happen that the rule fails: The best candidate was perhaps already in the top 37 percent, so the last candidate is taken. The rule is not very successful when the first 37 percent of the applicants were the worst, then the next best thing is merely accepted.
- 3.1 Unknown number N of options
Problem
In an often cited as an example of variant an organization wants to hire a secretary. The candidates speak in succession before; in the review can be set up a ranking, and the qualities of each candidate can be held. However, a rejected candidate is ruled out and is finally in the course no longer available, a premise that contradicts the actual staffing reality.
Another formulation of the problem is based on the choice of a spouse of a number of candidates. This Problemeinkleidung is realistic, if it is considered not to love marriage. The problem with includes that the probability of selecting the best candidates each, to be maximized. If instead of the expected value, based on all the possible candidates, can be maximized, a different strategy was required.
Strategy
This problem has a very simple strategy that also creates less optimal:
Consider the first of the candidates ( with ) - and totally reject.
Choose from the remaining candidates the first, which is better than each of the first.
It can be shown that for large, the optimal value for apparent from, the base of the natural logarithm ( Euler's number). With this strategy, the probability to select the best candidates, at, or about 37%.
Evidence
For the proof are only two candidates of interest, the best candidate - we assume it is the - te - as well as the second best of the first applicants.
If, then the best candidate is also among the fixed price rejected, so that the strategy has failed.
If the second best is not part of the first to the flat-rate first rejected, he goes th the above, is also better than each of the first and it is taken (or possibly even another candidate before him). Again, the strategy fails.
It remains the case that the among the first applicants is already second best among the first applicants, this is the probability; then (and only then ) the -th candidate is actually taken.
The best candidate is equally likely at any point in the sequence 1, 2, .... Taking this into account, the probability of success of the strategy given by:
For the sum of one makes with growing increasingly better integral approximation:
Takes the maximum of this approximate expression at the point where its derivative is equal to 0, namely, at the position; it is. The maximum is not very pronounced, for the vast area that is consistently never fallen below.
Applicability in practice
The practical applicability of the problem is likely to be very limited in this model ( classical secretary problem). (See comparison below, the alternative model, in which the " 1/e-Gesetz the best choice " is based. ) The problem is, first, that in order to determine the optimal " stop number", you also need to know from the outset how large is. This may be possible if a fixed number of interviews agreed; However, in the guise of "marriage problemes " this prediction is difficult.
Furthermore, sets the " secretaries problem " requires that the quality of candidates is random and independent of the place number. Also, this requirement may be given in the application case under certain circumstances. However, a counter-example is the " marriage problem ", as one can best be shown on the basis of traditional role models: With increasing age of the woman, the quality of potentially interested partners will tend to decline, on the other hand is with increasing prosperity of the man or improve his social position, the quality of its potentially interested partners may rise. In this setting, the woman should be advised to a weighted reduction in the " stop number", the man rather to an increase in " stop number". Another problem is the fact that a long time must be overcome without problem solution due to the effect of lagged decision phase, which can lead to welfare losses.
Another difficulty is that the solution of the secretaries problem is then optimized to choose the best solution, for which a relatively high probability is taken into account that eventually the space- digit moderately last, possibly a clearly inferior option is selected. In practice, in such an optimization towards the best solution is often unnecessary, should often be cheaper risikomeidende a strategy (eg minimax rule). Thus, if a solution to be a good compromise, or even as objectively appears well before reaching the stop number, then this solution should - be dialed immediately ( satisficing ) - deviating from the strategy.
Unknown number N of options
The main drawback of the classic secretaries problem of possible applications is the fact that the number of options ( candidate ) as is known in advance is required. One way around this is to assume that the distribution of this number is known ( Presman and Sonin, 1972). In this model, however, it is generally difficult to determine the optimal solution. In addition, in particular, that the optimal win probability is often significantly smaller. It is intuitively clear that ignorance of the N number of options should come at a price, but this price is often very high. Indeed in some cases the optimal win probability is substantially zero. A clever reformulation of this model solves this problem.
1/e-Gesetz the best choice
The essence of the reformulated model ( the so-called generalized approach in continuous time ) is based on the idea that it is easier to estimate when candidates are likely to come more or less than the distribution of the number estimate itself ( under the hypothesis that they are coming).
The generalized model: A candidate is to be selected from an unknown number of candidates in the time interval. The objective is to maximize the probability of selecting the best candidate for equiprobable arrival sequences of various ranks. It is believed that all the ranks have independently the same arrival time density. Be the corresponding arrival time distribution, ie
The 1/e-Gesetz then states: Since the solution of the equation Furthermore, let S be the strategy to wait until all the candidates at the time, and if possible to select the first candidate who is better than all of its predecessors ahead of time. This so-called 1/e-Strategie S has the following characteristics: If there is at least one candidate, then applies
The 1/e-Gesetz, discovered in 1984, was received with surprise (see Math Reviews 85: m), for a winning percentage of 1 / e seemed for an unknown number of candidates is not feasible, whereas this value is now considered a lower bound and this even in a model with recognized as weaker hypotheses. The 1/e-Gesetz is often confused with the solution of the secretaries problem because 1 / e there also plays an important role. Note, however, that the 1/e-Gesetz goes much further, as it is on the one hand for an unknown number of candidates and on the other hand arises from a much friendlier application model.
Other variants of the classical model
The problem has been studied in many different variants, including:
- The number of applicants is unknown.
- Equivalent candidates are important.
- Rejected applicants are not final excreted.