Fair assignment of indivisible objects under ordinal preferences
From MaRDI portal
Abstract: 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.
Recommendations
- Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
- A solution to the random assignment problem on the full preference domain
- Fair solutions to the random assignment problem
- A new fairness notion in the assignment of indivisible resources
- Size versus fairness in the assignment problem
Cites work
- scientific article; zbMATH DE number 5017566 (Why is no real title available?)
- scientific article; zbMATH DE number 1015852 (Why is no real title available?)
- A new solution to the random assignment problem.
- A solution to the random assignment problem on the full preference domain
- A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
- Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
- Algorithms and Computation
- An approximation algorithm for max-min fair allocation of indivisible goods
- Assigning papers to referees
- Assignment Problem Based on Ordinal Preferences
- Assignment Using Choice Lists
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity
- Equitable distribution of indivisible objects
- Fair division of indivisible items
- Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equity
- Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
- Maximizing Nash product social welfare in allocating indivisible goods
- On popular random assignments
- On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences
- Reducibility among combinatorial problems
- The undercut procedure: an algorithm for the envy-free division of indivisible items
- ``Almost stable matchings in the roommates problem with bounded preference lists
Cited in
(44)- Ex ante and ex post envy-freeness on polytope resources
- Almost envy-freeness with general valuations
- Competitive equilibrium with indivisible goods and generic budgets
- Fair division of indivisible goods under risk
- Envy-free allocations respecting social networks
- Picking sequences and monotonicity in weighted fair division
- Favoring Eagerness for Remaining Items: Designing Efficient, Fair, and Strategyproof Mechanisms
- Democratic fair allocation of indivisible goods
- Your college dorm and dormmates: fair resource sharing with externalities
- Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity
- Allocation of indivisible items with individual preference graphs
- Envy-freeness in house allocation problems
- Fair solutions to the random assignment problem
- Fair in the Eyes of Others
- Fair allocation with diminishing differences
- Envy-free relaxations for goods, chores, and mixed items
- Minimal envy and popular matchings
- Collective decision making
- Computing a small agreeable set of indivisible items
- A note on the undercut procedure
- On fair division with binary valuations respecting social networks
- Proportional Borda allocations
- Serial rules in a multi-unit Shapley-Scarf market
- Size versus truthfulness in the house allocation problem
- Fairness and rank-weighted utilitarianism in resource allocation
- Social orderings for the assignment of indivisible objects
- Fair in the eyes of others
- Fairness in temporal slot assignment
- A new fairness notion in the assignment of indivisible resources
- Borda-induced hedonic games with friends, enemies, and neutral players
- A general equivalence theorem for allocation of indivisible objects
- Computational complexity of necessary envy-freeness
- Envy-free matchings in bipartite graphs and their applications to fair division
- Multi resource allocation with partial preferences
- Fair division with two-sided preferences
- The fair OWA one-to-one assignment problem: NP-hardness and polynomial time special cases
- Allocating indivisible items with minimum dissatisfaction on preference graphs
- On reachable assignments in cycles
- Approximate and strategyproof maximin share allocation of chores with ordinal preferences
- Size versus fairness in the assignment problem
- Obtaining a proportional allocation by deleting items
- Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
- Ordinal Maximin Share Approximation for Goods
- Random assignments on preference domains with a tier structure
This page was built for publication: Fair assignment of indivisible objects under ordinal preferences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q899158)
