Order Symmetry: A New Fairness Criterion for Assignment Mechanisms

Order Symmetry: A New Fairness Criterion for Assignment Mechanisms

---

연구 분야: Verification

---

---

학회: AAMAS '25: Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems

---

초록

We introduce a new criterion, order symmetry, for assignment mechanisms that 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, 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 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 theoretical results, we present simulations using data from the Mallows distribution over its full range of parameters, which show an improvement in fairness even on probability measures for which full order symmetry is impossible.

---