A Generalized Problem of Optimal Selection and Assignment

We consider the infinite version of the secretary problem. From an infinite stream of applicants, we are to select m choices and assign them, in order, to m positions to be filled. We receive a reward c_k(m) for 1 ≤ k ≤ m(0 ≤ c₁(m) ≤ ⋯ ≤ c_m(m) = 1) if the best k applicants are selected and correctly ranked (i.e., the ith best applicant is assigned to the ith position for 1 ≤ i ≤ k). We consider two versions of the problem: (i) once an applicant is selected and assigned to some position, he cannot be promoted to a better position at a later time, and (ii) previously selected applicants can be promoted. In this paper, we concentrate on the double selection problem, m = 2, and derive, for both the promotion and nonpromotion versions of the problem, the optimal strategy that maximizes the expected reward.