Fair assignment of indivisible objects under ordinal preferences
From MaRDI portal
Publication:899158
DOI10.1016/J.ARTINT.2015.06.002zbMATH Open1346.68106arXiv1312.6546OpenAlexW2107944092WikidataQ28111603 ScholiaQ28111603MaRDI QIDQ899158FDOQ899158
Authors: Haris Aziz, Serge Gaspers, Simon MacKenzie, Toby Walsh 
Publication date: 21 December 2015
Published in: Artificial Intelligence (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1312.6546
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
Analysis of algorithms and problem complexity (68Q25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Reducibility among Combinatorial Problems
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- A new solution to the random assignment problem.
- A solution to the random assignment problem on the full preference domain
- Title not available (Why is that?)
- Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
- Fair division of indivisible items
- A survey of approximability and inapproximability results for social welfare optimization in multiagent resource allocation
- Maximizing Nash product social welfare in allocating indivisible goods
- Title not available (Why is that?)
- Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity
- On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences
- ``Almost stable matchings in the roommates problem with bounded preference lists
- Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
- Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equity
- The undercut procedure: an algorithm for the envy-free division of indivisible items
- An approximation algorithm for max-min fair allocation of indivisible goods
- Assignment Problem Based on Ordinal Preferences
- Equitable distribution of indivisible objects
- Algorithms and Computation
- Assigning papers to referees
- On popular random assignments
- Assignment Using Choice Lists
Cited In (30)
- Proportional Borda allocations
- Serial rules in a multi-unit Shapley-Scarf market
- Ordinal Maximin Share Approximation for Goods
- A general equivalence theorem for allocation of indivisible objects
- Competitive Equilibrium with Indivisible Goods and Generic Budgets
- Almost Envy-Freeness with General Valuations
- Envy-free matchings in bipartite graphs and their applications to fair division
- Envy-free allocations respecting social networks
- Size versus truthfulness in the house allocation problem
- The fair OWA one-to-one assignment problem: NP-hardness and polynomial time special cases
- Fair in the Eyes of Others
- Multi resource allocation with partial preferences
- Collective decision making
- A new fairness notion in the assignment of indivisible resources
- Social orderings for the assignment of indivisible objects
- Borda-induced hedonic games with friends, enemies, and neutral players
- Fair division under ordinal preferences: computing envy-free allocations of indivisible goods
- Obtaining a proportional allocation by deleting items
- A note on the undercut procedure
- On fair division with binary valuations respecting social networks
- Random assignments on preference domains with a tier structure
- Fairness in temporal slot assignment
- Allocating indivisible items with minimum dissatisfaction on preference graphs
- Ex ante and ex post envy-freeness on polytope resources
- Allocation of indivisible items with individual preference graphs
- Approximate and strategyproof maximin share allocation of chores with ordinal preferences
- Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity
- Envy-free relaxations for goods, chores, and mixed items
- Computing a small agreeable set of indivisible items
- Computational complexity of necessary envy-freeness
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)
