Monday, January 18, 2010

Onur Kesten on discrete allocation

Onur Kesten of CMU has two recent papers that offer new views of old problems.

Kesten, Onur , Why do popular mechanisms lack efficiency in random environments?
Journal of Economic Theory, Volume: 144 Issue: 5 Pages: 2209-2226 SEP 2009

"We consider the problem of randomly assigning n indivisible objects to n agents. Recent research introduced a promising mechanism, the probabilistic serial that has superior efficiency properties than the most common real-life mechanism random priority. On the other hand, mechanisms based on Gale's celebrated top trading cycles method have long dominated the indivisible goods literature (with the exception of the present context) thanks to their outstanding efficiency features. We present an equivalence result between the three kinds of mechanisms, that may help better understand why efficiency differences among popular mechanisms might arise in random environments. This result also suggests that the probabilistic serial and the random priority mechanisms can be viewed as two top trading cycles based mechanisms that essentially differ in the initial conditions of the market before trading starts."

Kesten, Onur, "SCHOOL CHOICE WITH CONSENT, Quarterly Journal of Economics, forthcoming.

"An increasingly popular practice for student assignment to public schools in the U.S. is the use of school choice systems. The celebrated Gale-Shapley student-optimal stable mechanism (SOSM) has recently replaced two de.cient student assignment mechanisms that were in use in New York City and Boston. We provide theoretical evidence that the SOSM outcome may produce large welfare losses. Then we propose an e¢ ciency adjusted deferred acceptance mechanism (EADAM) that allows a student to consent to waive a certain priority that has no e¤ect on his assignment. Under EADAM a consenting student causes himself no harm, but may help many others bene.t as a consequence. We show that EADAM can recover any welfare losses due to SOSM while also preserving immunity against strategic behavior in a particular way. It is also possible to use EADAM to eliminate welfare losses due to randomly breaking ties in student priorities."

No comments: