COWLES FOUNDATION FOR RESEARCH IN
ECONOMICS Box 208281
COWLES FOUNDATION DISCUSSION PAPER NO. 1677 Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms Yeon-Koo Che and Fuhito Kojima October 2008 The random priority (random serial dictatorship) mechanism is a common method for
assigning objects to individuals. The mechanism is easy to implement and strategy-proof.
However this mechanism is inefficient, as the agents may be made all better off by another
mechanism that increases their chances of obtaining more preferred objects. Such an
inefficiency is eliminated by the recent mechanism called probabilistic serial, but this
mechanism is not strategy-proof. Thus, which mechanism to employ in practical applications
has been an open question. This paper shows that these mechanisms become equivalent when
the market becomes large. More specifically, given a set of object types, the random
assignments in these mechanisms converge to each other as the number of copies of each
object type approaches infinity. Thus, the inefficiency of the random priority mechanism
becomes small in large markets. Our result gives some rationale for the common use of the
random priority mechanism in practical problems such as student placement in public
schools. |
