A New Solution to the Random Assignment Problem
by
Anna Bogomolnaia
Southern Methodist University
Coauthors: Herve Moulin (Rice University)

We introduce the new concept of ordinal efficiency in the random assignment problem: it relies on the stochastic dominance relation induced by individual preferences over sure objects; it is more demanding than ex post efficiency and less demanding than ex ante (i.e., with respect to Von Neumann-Morgenstern utility functions) efficiency.

We characterize the set of ordinally efficient assignments by means of a simple algorithm; our new solution, the Probabilistic Serial (PS) assignment, is a central point within this set.

The familiar Random Priority (RP) assignment obtains by choosing randomly and without bias an ordering of the agents and letting them successively choose an object in this order. The RP assignment is ex post efficient but may not be ordinally efficient. Moreover, the PS assignment is nonenvious ex ante, whereas the RP one is nonenvious in the ordinal sense only. On the other hand the RP mechanism is ex ante strategyproof whereas the PS one is only ordinally strategyproof.

There is no mechanism combining the properties of ordinal efficiency, ex ante strategyproofness and equal treatment of equals.

Date received: June 7, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafi-04.