Random serial dictatorship and ordinally efficient contracts (Q2482677)

This paper deals with the assignment problem, where \(n\) indivisible objects that are collectively owned need to be allocated to \(n\) agents, with each agent entitled to receive one object. Random serial dictatorship allocates the objects by choosing each possible ordering of the agents with probability \(1/n!\) and, for each ordering realization, assigning the first agent his most preferred object, the next agent his most preferred object among the ones remaining, and so on. A random allocation is called ordinally efficient if it is not first-order stochastically dominated for all agents by any other random allocation. An ordering exchange contract \(\mathcal C\) is an agreement by which agents engage to replace any ordering draw \(f\) from the serial dictatorship lottery by the corresponding ordering \({\mathcal C}(f)\). It is shown, that when the preferences of the agents are commonly known, and the random serial dictatorship allocation is not ordinally efficient, 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.