It is time to write something longer than a tweet on this research topic, which in my opinion, trying to be as objective as possible, is very promising and conceptually important. I have worked on this with collaborators Jacky Lo, Geoff Pritchard and especially Rupert Freeman.

Let’s start with the model where we first noticed this new concept, namely one-to-one matching under ordinal preferences (“housing allocation”). Each of N agents has strict preferences over a set of N objects and we aim to find an assignment, namely a bijection between agents and objects. The famous mechanism called Serial Dictatorship fixes an order on the agents, and lets them choose in turn their most preferred object from those remaining. On the other hand, Top Trading Cycles starts with a fixed allocation, and gets each agent to point to the most preferred object. There must be at least one cycle, and we redistribute objects along the cycle so everyone in the cycle is satisfied. After removing these agents and objects, we continue with 2nd preferences, etc, until we reach a final assignment. A famous result of Abdulkadiroglu and Sonmez says that if the choosing order for SD is taken uniformly at random (this is called RSD), as is the initial allocation for TTC (which we call TTC-RE), then the probability distribution over assignments for these different-looking mechanisms is the same.

However, imagine yourself as an agent when RSD is used. No matter how you feel before the choosing order is determined, if you turn out to be at the beginning, you know you will always get your first choice object. If you turn out to be at the end, you know that you will have to take whatever is left. There is clear bias toward the front of the choosing order. On the other hand, it seems clear that no agent in TTC-RE will be as systematically advantaged just by virtue of their position in the mechanism.

A standard social choice concept is anonymity, meaning that a mechanism treats agents symmetrically, and the outcomes depend only on the profile of agent preferences, not the identities of the agents. However full anonymity is not possible in this model. RSD is anonymous, but once the choosing order is determined, the resulting SD is not anonymous. Similarly TTC-RE is anonymous but TTC is not. Yet TTC seems more symmetric than SD.  It seems there is an elusive criterion involving agent symmetry. The randomization discussed above turns out to be a red herring – we can define it in the deterministic case directly.

Our idea is to define such a criterion using average-case analysis. For a fixed probability distribution P on profiles (e.g. the uniform distribution), we consider the expected rank distribution for each agent, and if this is the same for all agents we call the mechanism order symmetric with respect to P. Some restriction on P is needed, because a point mass concentrated on a unanimous profile will prevent all mechanisms from being order symmetric. We show that provided P has sufficient symmetry between agents and between objects, TTC is order symmetric but SD is very far from being so. In other words, no agent is disadvantaged once the randomness in the mechanism is realized, and before preferences are elicited.

Not only does this definition clarify the difference between SD and TTC, it suggests tweaks to existing mechanisms. Full order symmetry may not be achieved in some situations, but we can try to equalize the bias between agents. The Boston mechanism clearly treats those early  in the tiebreaking order much better than those later in the order. A simple idea is to reverse the tiebreaking order after the first round. Simulations show this reduces bias substantially.

I feel that this idea has a bright future, with possible extensions to other social choice models and to practical mechanism design. Now we need a journal or conference to see that – we have had surprising difficulty in getting published. The two types of randomness can be confusing, and many researchers seem to think about fairness in terms of outcomes rather  than a procedural criterion of this sort. Some may just not think it is important, but we should first ensure there is no misunderstanding.