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 random-ized 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 fair-ness concepts, polynomial-time algorithms are presented to check whether a fair assignment exists or not. Our algorith-mic 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 b