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 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.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessOpen-Ended Question AnsweringSimilar Papers 제목 키워드 기반
The Probabilistic Serial and Random Priority Mechanisms with Minimum Quotas
Consider the problem of assigning indivisible objects to agents with strict ordinal preferences over objects, where each agent is interested in consuming at most one object, and objects have integer minimum and maximum q…
First-Choice Maximality Meets Ex-ante and Ex-post Fairness
For the assignment problem where multiple indivisible items are allocated to a group of agents given their ordinal preferences, we design randomized mechanisms that satisfy first-choice maximality (FCM), i.e., maximizing…
FairnessEfficiency and Sequenceability in Fair Division of Indivisible Goods with Additive Preferences
In fair division of indivisible goods, using sequences of sincere choices (or picking sequences) is a natural way to allocate the objects. The idea is the following: at each stage, a designated agent picks one object amo…
FairnessFavoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms
In the assignment problem, the goal is to assign indivisible items to agents who have ordinal preferences, efficiently and fairly, in a strategyproof manner. In practice, first-choice maximality, i.e., assigning a maxima…
FairnessAn Axiomatization of the Random Priority Rule
We study the problem of assigning indivisible objects to agents where each is to receive at most one. To ensure fairness in the absence of monetary compensation, we consider random assignments. Random Priority, also know…
Fairness