Order Symmetry: A New Fairness Criterion for Assignment Mechanisms

We introduce a new criterion, order symmetry , for assignment mechanisms that bijectively match n objects to n agents having ordinal preferences over the objects. An assignment mechanism is order-symmetric with respect to a given probability measure over preference profiles if every agent has equal probability of receiving their favorite object, every agent has equal probability of receiving their second favorite, and so on. Crucially, and unlike other fairness notions such as anonymity or envy-freeness, order symmetry can be satisfied by discrete assignment mechanisms when associated with a sufficiently symmetric probability measure. It can also be interpreted as a criterion of procedural fairness or fairness under uncertainty. Furthermore, it can be achieved without sacrificing other desirable axiomatic properties satisfied by existing mechanisms. In particular, we show that it can be achieved in conjunction with strategyproofness and Pareto efficiency by the Top Trading Cycles mechanism, but not by Serial Dictatorship. We also use the lens of order symmetry to improve the fairness of existing mechanisms with no loss in social welfare, focusing on the widely used family of Boston mechanisms. In addition to the theoretical results on the superiority of the order-symmetric mechanisms, we present simulations using data from the Mallows distribution over its full range of parameters. These show an improvement in fairness even when complete order symmetry is impossible because of the nature of the probability measure on profiles. We expect the idea of order symmetry to extend fruitfully to other allocation models including school choice.