Majority graphs of assignment problems and properties of popular random assignments

Randomized mechanisms for assigning objects to individual agents have received increasing attention by computer scientists as well as economists. In this paper, we study a property of random assignments, called popularity, which corresponds to the well-known notion of Condorcet-consistency in social choice theory. Our contribution is threefold. First, we define a simple condition that characterizes whether two assignment problems induce the same majority graph and which can be checked in polynomial time. Secondly, we analytically and experimentally investigate the uniqueness of popular random assignments. Finally, we prove that popularity is incompatible with very weak notions of both strat- egyproofness and cnvy-freeness. This settles two open problems by Aziz et al. [3] and reveals an interesting tradeoff between social and individual goals in random assignment.