Notions of anonymity for object assignment: Impossibility theorems

We search for impartiality in the allocation of objects when monetary transfers are not possible. Our main focus is anonymity. The standard definition requires that if agents' names are permuted, their assignments should be permuted in the same way. Since no rule satisfies this definition in this model, we introduce weaker variants, "anonymity on distinct preferences," "pairwise-anonymity on distinct preferences," "pairwise-anonymity on distinct profiles," and "independence of others' permutations." We show that for more than two agents and two objects, no rule is pairwise-anonymous on distinct preferences and Pareto-efficient (Theorem 1), no rule is pairwise-anonymous on distinct preferences and independent of others' permutations (Theorem 2), and no rule is pairwise-anonymous on distinct profiles and strategy-proof (Theorem 3). These results suggest that introducing randomization to object allocation problems is almost inevitable for achieving impartiality.