Optimal Sequential Selection of Secretaries

The problem is to select as rapidly as possible a pre-specified number of secretaries (sequentially and without recall) from a proffered queue of applicants. Each candidate makes demands in each of several currencies, and we know the joint probability distribution of these demands. We also have a given total budget in each currency. We consider procedures that minimize the expected number of interviews and derive an asymptotically optimal procedure. Derivation of this procedure depends on the following result. Given a probability measure F on the positive orthant Q and a point ρ₀ ∈ Q, consider a region A ⊂ Q whose center of gravity lies below ρ₀ coordinatewise. Then F(A) is maximal when A is a simplicial section A = {ρ : ρ · θ ≤ r}, where r ≥ 0 and θ is a unit vector in Q.

The original motivation for this problem arose in connection with a scheme for selecting optical fibers.