Fair Assignment Of Indivisible Objects Under Ordinal Preferences

摘要

We consider the discrete assignment problem in which agents express ordinal preferences over objects and these objects are allocated to the agents in a fair manner. We use the stochastic dominance relation between fractional or randomized allocations to systematically define varying notions of proportionality and envy-freeness for discrete assignments. The computational complexity of checking whether a fair assignment exists is studied systematically for the fairness notions. We characterize the conditions under which a fair assignment is guaranteed to exist. For a number of fairness concepts, polynomial-time algorithms are presented to check whether a fair assignment exists or not. Our algorithmic results also extend to the case of variable entitlements of agents. Our NP-hardness result, which holds for several variants of envy-freeness, answers an open problem posed by Bouveret, Endriss, and Lang (ECAI 2010).