קולוקוויום בביה"ס למדעי המחשב - Incentive Compatible Mechanisms for the Secretary Problem

In the classical secretary problem, an employer sequentially interviews n randomly ordered rankable candidates; following each interview, the employer must immediately decide whether to hire the candidate. The celebrated elegant solution that maximizes the probability of hiring the best candidate calls for ignoring about one third of the first interviewed candidates and then selecting the best candidate so far. Recognizing that the early candidates have no chance to be selected, and thus have no incentive to be interviewed, Buchbinder, Jain and Singh introduced an LP based selection mechanism that guarantees that all candidates have an equal probability of being selected. In this talk we introduce a tighter LP formulation whose dual is the direct formulation of the incentive problem as a Markov Decision Problem. This approach provides a clear insight into the LP formulation, simplifies the proofs of their validity, and provides a general framework for other incentive mechanisms. In particular, we present and analyze an incentive mechanism that maximizes the expected rank of the selected candidate. In addition, we introduce a couple of novel mechanisms that allow the candidates to set deadlines for accepting hiring offers. We show that these mechanisms guarantee equal probability of being selected for all the candidates that are interviewed, while the probability of selecting the best candidate is higher than that of the classical problem (though both converge - as n tends to ∞ - to the same value).‏