Fair assignment of indivisible objects under ordinal preferences
This addresses fairness in resource allocation for agents with ordinal preferences, with incremental contributions to computational complexity and algorithmic design.
The paper tackles the problem of fairly assigning indivisible objects under ordinal preferences by defining and analyzing various fairness notions like proportionality and envy-freeness, presenting polynomial-time algorithms for checking existence in some cases and proving NP-hardness for others, including answering an open question from prior work.
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 for these fairness notions. We also 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. Our algorithmic results also extend to the case of unequal entitlements of agents. Our NP-hardness result, which holds for several variants of envy-freeness, answers an open question posed by Bouveret, Endriss, and Lang (ECAI 2010). We also propose fairness concepts that always suggest a non-empty set of assignments with meaningful fairness properties. Among these concepts, optimal proportionality and optimal weak proportionality appear to be desirable fairness concepts.