Efficient random allocation of discrete goods, Mihai Manea

In this season of Ph.D. dissertation defenses, Mihai Manea just completed the last defense that I'm intimately involved in. His work includes papers on the ex-ante efficiency of allocations involving lotteries in large markets.
This is a topic that comes up in school choice systems, for example, with the random element coming from the fact that a given school may not have the capacity to serve all the students who would like to enroll, so that some random tie breaking procedure has to be employed.

An important paper by Bogolmanaia and Moulin (2001) noted that random serial dictatorship, although ex post efficient, may be ex ante inefficient. They proposed an "ordinally efficient" random mechanism called the probabilistic serial mechanism. An ordinally efficient mechanism chooses a probability matrix (assigning each player some probability of obtaining each object) that cannot be Pareto improved upon by another random assignment that first order stochastically dominates the first.

Random serial dictatorship is the procedure for allocating indivisible goods by putting the claimants in a random order, and then allowing the first to choose the object he prefers, the second to choose the object he prefers from those that remain, etc. This results in a lottery over ex post efficient allocations, which B&M noted may be an inefficient lottery: it induces a stochastic allocation matrix with the property that some claimants would be willing to trade some of their probability of getting one object with one another, to yield a mutually preferable stochastic matrix. One of Mihai's early papers shows that efficient probability-exchange contracts of this sort can be written by agents agreeing to exchange their orders in some realizations: i.e. the agents can write an ordinally efficient ordering-exchange contract that they all prefer to the random serial dictatorship allocation in the sense of first-order stochastic dominance. (Random Serial Dictatorship and Ordinally Efficient Contracts, International Journal of Game Theory 2008.)

One drawback of the probabilistic serial mechanism is that, while it is ordinally efficient (unlike random serial dictatorship) it does not make it a dominant strategy for agents to state their true preferences (again, unlike random serial dictatorship). Mihai and Fuhito Kojima show that this drawback goes away when the number of identical copies of each object is sufficiently large: Strategy-Proofness of the Probabilistic Serial Mechanism in Large Random Assignment Problems . Their result isn't just a limit theorem, rather, they show that there is a finite number such that, when the number of identical copies of each object is larger than that, the psm is strategy proof.

Separately, Mihai and Fuhito study the efficiency of random serial dictatorship in different ways as markets grow large. Mihai shows that , as the market becomes large (in particular, as the number of types of objects grows along with the number of participants), the proportion of preference profiles at which rsd is ordinally inefficient goes to one in the limit. (Asymptotic Ordinal Inefficiency of Random Serial Dictatorship, forthcoming Theoretical Economics.)

Fuhito, together with Yeon-Koo Che, shows, in a market that grows large in a different way (the number of copies of each object type grows along with the number of participants) that random serial dictatorship converges to the probabilistic serial mechanism. (Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms , 2008.)

In general, looking at efficiency ex-ante as well as ex post opens up new avenues for investigation, and how these interact in large markets has been a fruitful way to start thinking about them.

Welcome to the club, Mihai.