Random Serial Dictatorship versus Probabilistic Serial Rule: A Tale of Two Random Mechanisms
This work addresses the practical challenge of choosing between two randomized mechanisms for resource allocation, with implications for domains like school choice or housing assignments, though it is incremental in analyzing specific preference domains.
The paper compares Random Serial Dictatorship (RSD) and Probabilistic Serial Rule (PS) for assignment problems with ordinal preferences, showing that RSD satisfies envy-freeness under lexicographic preferences, while PS is strategyproof only when objects are fewer than agents and manipulable otherwise, and provides empirical insights on their comparability and applicability.
For assignment problems where agents, specifying ordinal preferences, are allocated indivisible objects, two widely studied randomized mechanisms are the Random Serial Dictatorship (RSD) and Probabilistic Serial Rule (PS). These two mechanisms both have desirable economic and computational properties, but the outcomes they induce can be incomparable in many instances, thus creating challenges in deciding which mechanism to adopt in practice. In this paper we first look at the space of lexicographic preferences and show that, as opposed to the general preference domain, RSD satisfies envyfreeness. Moreover, we show that although under lexicographic preferences PS is strategyproof when the number of objects is less than or equal agents, it is strictly manipulable when there are more objects than agents. In the space of general preferences, we provide empirical results on the (in)comparability of RSD and PS, analyze economic properties, and provide further insights on the applicability of each mechanism in different application domains.