Talks & Seminars
Title: The Bayesian matroid secretary with applications to mechanism design
Shuchi Chawla, University of Wisconsin at Madison.
Date & Time: August 26, 2010 14:15
Venue: Seminar Hall, old CSE building
Consider the following variant of the classic secretary problem: we interview a number of candidates with the goal of hiring one; hiring decisions are irrevocable; each candidate's "quality" is drawn from a known distribution; our goal is to maximize the expected quality of the candidate we hire. The optimal algorithm for this problem can be found using dynamic programming, but suffers from sensitivity to the knowledge of the distributions, ordering of the candidates, etc. Optimal stopping theory provides a much simpler and robust stopping rule that obtains a 2-approximation. We extend this "prophet-inequality" result to settings involving hiring multiple candidates, and show how this theory leads to simple, robust, and approximately optimal mechanisms for maximizing revenue in Bayesian settings, providing the first non-trivial approximations in the elusive "multi-parameter" setting. This talk is based on joint work with Jason Hartline, David Malec, and Balu Sivan (STOC'10).
Speaker Profile:
Shuchi Chawla is an Assistant Professor at the University of Wisconsin at Madison.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback