|
|
Discrete Mathematics and Optimization Seminar
|
Mar. 22nd, 2010
|
Incentives in Secretary Problems and Online Auctions via Linear Programming
Mohit Singh
McGill University
|
In the secretary problem, an employer would like to choose the best candidate in an online manner among n competing candidates. The candidates are assumed to arrive in a random order. The optimal mechanism is to interview the first n/e candidates for the purpose of evaluation, and then hire the first candidate that is better than all previous candidates. This simple mechanism suffers from a crucial drawback. Candidates arriving early in the process have an incentive to delay their interview. Using this mechanism, when candidates can influence their position, can lead to sub-optimal result and challenges the basic assumption that the candidates arrive in a random order.
In this talk, I will describe a linear programming framework which characterizes all mechanisms for
the secretary problem and its extensions. This characterization helps us obtain optimal incentive compatible mechanisms for the secretary problem. We will also show an application of this result to an auction scenario where a single item has to be sold to n competing bidders arriving in an online manner.
This is joint work with Niv Buchbinder and Kamal Jain
|
|
|
|