Secretary Problem - Cardinal Payoff Variant

Cardinal Payoff Variant

Finding the single best applicant might seem like a rather strict objective. One can imagine that the interviewer would rather hire a higher-valued applicant than a lower-valued one, and not only be concerned with getting the best. That is, he will derive some value from selecting an applicant that is not necessarily the best, and the value he derives is increasing in the value of the one he selects.

To model this problem, suppose that the applicants have "true" values that are random variables X drawn i.i.d. from a uniform distribution on . Similar to the classical problem described above, the interviewer only observes whether each applicant is the best so far (a candidate), must accept or reject each on the spot, and must accept the last one if he is reached. (To be clear, the interviewer does not learn the actual relative rank of each applicant. He learns only whether the applicant has relative rank 1.) However, in this version his payoff is given by the true value of the selected applicant. For example, if he selects an applicant whose true value is 0.8, then he will earn 0.8. The interviewer's objective is to maximize the expected value of the selected applicant.

Since the applicant's values are i.i.d. draws from a uniform distribution on, the expected value of the tth applicant given that is given by

As in the classical problem, the optimal policy is given by a threshold, which for this problem we will denote by, at which the interviewer should begin accepting candidates. Bearden 2006 showed that c is either or . (In fact, whichever is closest to .) This follows from the fact that given a problem with applicants, the expected payoff for some arbitrary threshold 1 = c = n is

Differentiating with respect to c, one gets

Since for all permissible values of, we find that is maximized at . Since V is convex in, the optimal integer-valued threshold must be either or . Thus, for most values of the interviewer will begin accepting applicants sooner in the cardinal payoff version than in the classical version where the objective is to select the single best applicant. Note that this is not an asymptotic result: It holds for all .