An equilibrium analysis of the probabilistic serial mechanism

Abstract

The prominent mechanism of the recent literature in the assignment problem is the probabilistic serial (PS). Under PS, the truthful (preference) proÖle always constitutes an ordinal Nash Equilibrium, inducing a random assignment that satisÖes the appealing ordinal e¢ ciency and envy-freeness properties. We show that both properties may fail to be satisÖed by a random assignment induced in an ordinal Nash Equilibrium where one or more agents are non-truthful. Worse still, the truthful proÖle may not constitute a Nash Equilibrium, and every non-truthful proÖle that constitutes a Nash Equilibrium may lead to a random assignment which is not ordinally e¢ cient, not even weakly envy-free, and which admits an ex-post ine¢ cient decomposition. A strong ordinal Nash Equilibrium may not exist, but when it exists, any proÖle that constitutes a strong ordinal Nash Equilibrium induces the random assignment induced under the truthful proÖle. The results of our equilibrium analysis of PS call for caution when implementing it in small assignment problems.