Order Symmetry: A new fairness criterion for assignment mechanisms


Friday, October 8, 2021, 1:00pm to 2:30pm

Presenter:  Mark Wilson
Topic:  Order symmetry: a new fairness criterion for assignment mechanisms

Fall 2021

The EconCS Group holds an Economics and Computer Science research seminar each semester.

Fall 2021 meetings are held at 1 - 2:30 PM on Fridays. Seminar Coordinators for Fall '21 are Srivatsa R Sai and Daniel Halpern.

Abstract: We introduce a new fairness criterion, order symmetry, for assignment mechanisms that match N objects to N agents with ordinal preferences over the objects (the housing allocation problem). An assignment mechanism is order symmetric with respect to some probability measure over preference profiles if every agent is equally likely to receive their favorite object, every agent is equally likely to receive their second favorite, and so on. When associated with a sufficiently symmetric probability measure, order symmetry is a relaxation of anonymity that, crucially, can be satisfied by discrete assignment mechanisms. 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 ex post efficiency via the top trading cycles mechanism (but not serial dictatorship). We additionally design a novel mechanism that is both order symmetric and ordinally efficient. The practical utility of order symmetry is substantiated by simulations on Impartial Culture and Mallows-distributed preferences for four common assignment mechanisms. We feel that this new average-case fairness concept has more applications to come.