The Online Dating Problem is a variation on the Secretary Problem - a famous problem in optimal stopping theory.
The original form of the problem goes something as follows.
Imagine an administrator willing to hire the best secretary out of n rankable applicants for a position. The applicants are interviewed one-by-one in random order. A decision about each particular applicant is to be taken immediately after the interview. Once rejected, an applicant cannot be recalled. During the interview, the administrator can rank the applicant among all applicants interviewed so far, but is unaware of the quality of yet unseen applicants.
The big question? What is the optimal strategy - stopping rule - maximizing the probability of selecting the best candidate?
The Secretary Problem can be generalized to other decisions. It has been reformulated as the Apartment Problem,the Fussy Suitor Problem and the Streetwalker Problem.
In terms of the Online Dating Problem, we can re-state this problem. If we can expect to meet exactly n eligible partners,what strategy should we use to maximize the chances of choosing the very best one?
- There is a single position to fill.
- There are n candidates for the position, and the value of n is known.
- The candidates, if seen altogether, could be ranked from best to worst unambiguously.
- The candidates are interviewed sequentially (dated) in random order, with each order being equally likely.
- Immediately after an interview (date), the candidate is either accepted or rejected, and the decision is irrevocable.
- The decision to accept or reject a candidate is based only on the relative ranks of the candidates interviewed so far.
- The objective is to select the best candidate with the highest possible probability.
The problem has a surprisingly elegant solution.
The optimal stopping rule is to reject about n / e candidates after the interview where e is the base of the natural logarithm (e= 2.71828) then stop at the first candidate who is better than every applicant interviewed so far (or proceed to the last applicant if this never occurs). Using this simple strategy then, asymptotically, the probability of selecting the best candidate is at least 1/e (about a 37% chance).
If n=100 candidates then we need to date 100/2.71828=37 candidates. Thereafter we stop at the first candidate who is better than the 37 interviewed so far or proceed to the last candidate.
Experimental studies of decision making suggest that people tend to stop searching too soon. This may be explained, at least in part, by the cost of evaluating candidates.
Extrapolating to the real world, these studies suggest that people do not search enough when faced with problems where the decision alternatives are encountered sequentially.
I guess I got lucky.