Source-linked AI summary
Fair assignment of indivisible objects under ordinal preferences
Haris Aziz, Serge Gaspers, Simon Mackenzie, Toby Walsh
TL;DR
Fair assignment of indivisible objects is challenging when agents express only ordinal preferences. The paper defines and relates fairness concepts using stochastic dominance, then studies their existence and computation, finding both polynomial-time cases and NP-complete envy-freeness variants.
Problem
The paper studies how to define and check fairness for assignments of indivisible objects when agents report ordinal preferences.
Source: §1 · p. 2Method
The paper systematically formulates ordinal proportionality and envy-freeness concepts using stochastic dominance and studies their existence, computation, and relationships.
Source: §1 · p. 2Results
Polynomial-time existence checks cover SD proportionality, SD envy-freeness for two agents, and weak SD proportionality for a constant number of agents, while possible, SD, and weak SD envy-freeness existence are NP-complete.
Source: §1 · pp. 2–3Takeaways & Limitations
Optimal proportionality is polynomial-time computable, and optimal weak proportionality is polynomial-time computable for a constant number of agents; both appear promising and are compatible with Pareto optimality.
Source: §9 · p. 34The complexity of finding weak SD proportional discrete assignments remains open for an unbounded number of agents with non-strict preferences.
Source: §9 · p. 34
Abstract
from arXiv · showhide
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.
1. Introduction
The paper develops ordinal fairness concepts for assigning indivisible objects and studies their relationships, existence, and computation. It gives tractability and hardness results and proposes optimal proportionality variants when fairness may not be attainable.
1. Introduction
- Stochastic dominance (SD) supplies a systematic basis for defining envy-freeness and proportionality when agents report ordinal preferences rather than cardinal utilities.The paper studies SD envy-freeness, weak SD envy-freeness, possible envy-freeness, SD proportionality, and weak SD proportionality.Source: §1 · p. 2
- The paper proves logical relationships among fairness properties and introduces weak SD proportionality, motivating a progression to weaker notions when stronger ones are unavailable.The authors suggest checking the strongest fairness notion first, then trying a weaker one if necessary.Source: §1 · p. 2
- Polynomial-time existence checks cover SD proportionality even with indifferences, SD envy-freeness for two agents, and weak SD proportionality for a constant number of agents.For two agents, weak SD envy-freeness and possible envy-freeness are also polynomial-time checkable.Source: §1 · pp. 2–3
- Existence checking is NP-complete for possible, SD, and weak SD envy-freeness; the possible envy-freeness result answers an open question posed in.For strict preferences and an unbounded number of agents, the paper characterizes when weak SD proportionality exists.Source: §1 · p. 3
- The two main algorithms extend to unequal agent entitlements and to settings that additionally require Pareto optimality.The study also compares fractional versus discrete assignments, strict versus non-strict preferences, and single versus multiple objects per agent.Source: §1 · p. 3
- Because the proposed fairness notions may not exist, the paper defines optimal proportionality and optimal weak proportionality; the former is polynomial-time computable, and the latter is polynomial-time computable for a constant number of agents.The paper contrasts these gradual proportionality relaxations with maximizing the number of agents whose fairness constraints are met, which may leave some agents completely dissatisfied.Source: §1 · p. 3
2. Related work
Prior fair-division work studies proportionality and envy-freeness in divisible, cardinal, or more expressive settings. This paper instead focuses on discrete assignments with ordinal preferences and examines fairness concepts systematically.
2. Related work
- The paper situates its work among established proportionality and envy-freeness concepts, including their histories in cake-cutting and microeconomics.Proportionality is also called a fair-share guarantee, and Foley is cited for an early formal study of envy-freeness in microeconomics.Source: §2 · pp. 3–4
- Earlier work on discrete assignments often assumes cardinal utilities; this paper studies ordinal preferences, which require less information and may be more suitable when cardinal preferences are unavailable.The authors also note that eliciting cardinal preferences without money transfers may create greater opportunities for manipulation.Source: §2 · p. 4
- Some ordinal models extend preferences to sets of objects, while others impose cardinal scores; the paper restricts agents to ordinal preferences over individual objects.The cited set-preference models can have higher computational complexity or require exponential space, while scoring approaches do not handle indifferences canonically.Source: §2 · pp. 4–5
- Prior work examined SD envy-freeness in randomized assignments and related discrete concepts, but not systematically for discrete assignments; several equivalent concepts were limited to strict preferences.The paper identifies SD proportionality with a concept studied by Pruhs and Woeginger, and notes that weak SD or possible proportionality had not been studied in these settings to the authors’ knowledge.Source: §2 · p. 5
3. Preliminaries
The preliminaries formalize agents’ ordinal preferences, fractional and discrete assignments, and the stochastic-dominance comparison used to define fairness. They also connect SD comparison to utility and set-preference formulations.
3. Preliminaries
- An assignment problem consists of agents, objects, and a complete, transitive preference ordering for each agent; agents may be indifferent among objects.Preferences are represented by ordered equivalence classes, with strict preferences when every class is a singleton.Source: §3 · p. 5
- A fractional assignment gives each object across agents in total, with each entry representing an allocation probability; it is discrete when every entry is zero or one.The uniform assignment gives each agent a 1/n share of each object and is useful for defining fairness, although algorithms target discrete assignments.Source: §3 · pp. 5–6
- Under stochastic dominance, one allocation is at least as good for an agent when it gives at least as much probability to objects at or above every preference level.The text relates this comparison to all cardinal utilities consistent with the agent’s ordinal preferences.Source: §3 · p. 6
- The responsive set extension compares bundles by allowing objects to be replaced by more-preferred ones; the SD relation for discrete assignments is characterized using an injection matching objects in one bundle to at-least-as-preferred objects in the other.The proof uses Hall’s theorem to relate failure of such a matching to a preference-level count inequality.Source: §3 · p. 7
- Table 2 groups fairness concepts that are equivalent, including weak SD proportionality and possible proportionality.The paper’s theorem connects SD comparisons with utility-based characterizations.Source: §3 · p. 7, Table 2 · p. 8
4. Fairness concepts under ordinal preferences
The paper defines ordinal envy-freeness and proportionality concepts by comparing discrete allocations with other agents’ allocations or with the uniform assignment. These concepts distinguish guaranteed, possible, and weak forms of fairness.
4. Fairness concepts under ordinal preferences
- SD proportionality requires each agent to SD-prefer their allocation to the uniform assignment, while weak SD proportionality requires that no agent strictly SD-prefer the uniform assignment.Possible proportionality instead requires, for each agent, some consistent utility function under which their allocation is worth at least 1/n of all objects.Source: §4 · p. 8
- Necessary proportionality requires proportionality for every cardinal utility consistent with preferences; weak SD envy-freeness rules out any strict SD preference for another agent’s allocation.Possible envy-freeness requires for each agent some consistent utility under which their own allocation is at least as valuable as every other agent’s.Source: §4 · pp. 8–9
- SD envy-freeness requires each agent to SD-prefer their own allocation to every other agent’s, while necessary envy-freeness imposes envy-freeness for all consistent cardinal utilities.Necessary and possible completion envy-freeness quantify over set-preference relations consistent with the responsive set extension.Source: §4 · p. 9
- In the two-agent example, the allocation giving agent 1 objects o1 and o4 and agent 2 objects o2 and o3 is neither SD proportional nor SD envy-free, but satisfies three weaker concepts.It is weak SD proportional, possible envy-free, and weak SD envy-free.Source: §4 · p. 9
5. Relations between fairness concepts
The section establishes implication and equivalence relationships among fairness notions, including special equivalences for two agents. It also gives examples showing that several implications do not hold in reverse.
General equivalences
- Weak SD proportionality is equivalent to possible proportionality, and weak SD envy-freeness is equivalent to possible completion envy-freeness.SD envy-freeness is equivalent to necessary envy-freeness and necessary completion envy-freeness.Source: §5 · p. 10
Theorem 3
- SD envy-freeness implies SD proportionality, while SD proportionality and possible envy-freeness each imply weak SD proportionality.Possible envy-freeness also implies weak SD envy-freeness.Source: §5 · p. 11
Two-agent equivalences
- For two agents, proportionality is equivalent to envy-freeness, and SD proportionality is equivalent to SD envy-freeness.Weak SD proportionality is equivalent to both possible envy-freeness and weak SD envy-freeness.Source: §5 · pp. 11–12
Counterexamples
- SD proportionality does not imply weak SD envy-freeness, possible envy-freeness, or SD envy-freeness.A three-agent example is SD proportional but leaves one agent envious of another's allocation.Source: §5 · p. 13
- Weak SD envy-freeness does not imply possible envy-freeness or weak SD proportionality; possible envy-freeness also need not imply SD proportionality.The latter failure is illustrated with two agents, where one receives the top-ranked object and the other receives the remaining objects.Source: §5 · pp. 13–14
Existence
- Randomized assignments satisfy all considered proportionality and envy-freeness notions by giving each agent 1/n of every object, but discrete weak SD proportional assignments may not exist.Nonexistence examples include identical strict preferences even when the number of objects is a multiple of agents.Source: §5 · pp. 14–15
6. Computational Complexity
This section studies the complexity of checking whether fair assignments exist, presenting polynomial-time checks for several proportionality and envy-freeness notions and NP-completeness results for multiple envy-freeness existence questions, including through an Exact Cover by 3-sets reduction.
6. Computational Complexity
- Fairness of a given assignment is easy to verify for all considered notions, and existence can be checked in polynomial time when the number of objects is constant.Source: §6 · p. 15
6.1. SD proportionality
- Discrete SD proportionality requires m to be divisible by n, with each agent receiving m/n objects, and its existence is polynomial-time decidable even with indifferences.The existence check reduces to finding a feasible b-matching.Source: §6 · p. 15, §6.1 · p. 16
6.2. Weak SD proportionality
- With strict preferences, weak SD proportionality exists exactly when m > n, or when m = n and every agent can receive an object that is not least preferred; existence is polynomial-time decidable.Source: §6.2 · p. 17
- With indifferences, weak SD proportionality existence is polynomial-time decidable when the number of agents is constant.The algorithm enumerates combinations of agent satisfaction conditions and checks feasible b-matchings.Source: §6.2 · pp. 18–19
6.3. Envy-freeness
- For two agents, SD, weak SD, and possible envy-freeness are polynomial-time decidable; with strict preferences, possible envy-freeness is linear-time decidable.For strict preferences, complete weak SD envy-freeness is also linear-time decidable; with identical preferences, SD envy-freeness exists exactly when each equivalence class size is a multiple of n.Source: §6.3 · p. 20
- Checking existence is NP-complete for weak SD envy-free, possible envy-free, and SD envy-free discrete assignments.Weak SD envy-freeness is equivalent to possible completion envy-freeness; Bouveret et al. had identified the possible-completion case with indifferences as open.Source: §6.3 · p. 21
- The hardness construction considers weak SD envy-freeness, possible envy-freeness, and SD envy-freeness as assignment criteria.The proof’s observations about the constructed assignments are stated for all three notions.Source: §6.3 · p. 22
- The X3C reduction makes an SD envy-free assignment possible when an exact cover exists, while the absence of a cover rules out weak SD envy-freeness.The construction associates each 3-set with an agent and nine additional agents, encoding set elements and buffer objects in the assignment problem.Source: §6.3 · pp. 21, 23
- Checking whether an envy-free allocation exists is NP-complete when agents have responsive preferences, for either weak or strong envy-freeness; with cardinal object utilities of 1 or 0, checking existence is also NP-complete.Source: §6.3 · p. 24
7. Extensions
The extensions address assignments that must also be Pareto optimal and settings with unequal agent entitlements. For Pareto optimality, the paper gives polynomial-time results for proportional assignments; for entitlements, it extends fairness definitions and algorithms.
7.1. Additionally requiring Pareto optimality
- Cloning each agent into one-object agents preserves Pareto optimality, enabling multi-object assignments to be analyzed through a one-object assignment problem.A cloned assignment can be transformed back to the original by giving each agent the objects assigned to their clones.Source: §7.1 · p. 24
- A Pareto improvement of a weak SD proportional or SD proportional assignment retains that fairness property, so a Pareto-optimal fair assignment exists whenever such an assignment exists.The paper also states that a Pareto improvement that is Pareto optimal can be computed in polynomial time.Source: §7.1 · p. 25
- Pareto-optimal SD proportional assignments can be computed in polynomial time; the same holds for weak SD proportional assignments when the number of agents is constant.Source: §7.1 · p. 25
7.2. Unequal entitlements
- With unequal entitlements, proportionality and envy-freeness are redefined to account for entitlement differences, and the possible and necessary notions extend to this setting.The proportionality algorithms can be adapted by replacing 1/n with each agent’s share of total entitlements when specifying a matching lower bound.Source: §7.2 · p. 26
- For unequal entitlements, possible proportionality is polynomial-time checkable with a constant number of agents, while necessary proportionality is polynomial-time checkable.Source: §7.2 · p. 26
8. Fairness Concepts that Guarantee the Existence of Fair Outcomes
This section introduces fairness concepts designed to guarantee a nonempty set of outcomes, including approaches that maximize the number of agents meeting a fairness condition or optimize proportionality uniformly. For equal numbers of agents and objects with strict preferences, it relates optimal weak proportionality to maximin, which maximizes the minimum rank of objects received.
8.1. Maximal and Maximum Fairness
- Computing a maximum SD envy-free assignment is NP-hard, while maximal SD-proportional assignments are polynomial-time computable (weak SD-proportional ones if n is constant).Maximum fairness maximizes the number of agents whose condition is satisfied; maximal fairness means no more agents can be satisfied without losing fairness for those already satisfied.Source: §8.1 · pp. 26–27
8.2. Optimal proportionality
- An optimal proportional assignment can be computed in polynomial time even with indifferences, and its proportionality parameter is finite exactly when every agent can receive a most-preferred object.The algorithm checks at most nm² rational candidate values; when the parameter is infinite, any assignment is optimal, while SD proportionality always implies optimal proportionality.Source: §8.2 · pp. 29–30
8.3. Optimal weak proportionality
- For a constant number of agents, optimal weakly proportional assignments can be computed in polynomial time even with indifferences; extending this result beyond constant n remains open.The optimal weak proportionality parameter is finite exactly when m ≥ n; moreover, a weak SD-proportional assignment need not be optimal weakly proportional.Source: §8.3 · pp. 31–33
- With n = m and strict preferences, maximin—defined by Brams and King as maximizing the minimum rank of objects received—is equivalent to optimal weak proportionality.Source: §8.3 · p. 34
9. Conclusions
The paper maps relationships among ordinal fairness concepts and considers alternatives for cases where fair outcomes may not exist. It identifies optimal proportionality and optimal weak proportionality as promising concepts, while leaving some existence-checking complexity questions open.
9. Conclusions
- The taxonomy identifies relationships among fairness concepts; using cardinal utilities with stochastic dominance offers flexibility for entitlements and can aid algorithm design.Source: §9 · p. 34
- Because fair outcomes are not guaranteed to exist, the paper discusses maximal and maximum fairness and less stringent reference vectors as alternatives.The paper relates the computational problems for maximal and maximum fairness.Source: §9 · p. 34
- Optimal proportionality is computable in polynomial time, while optimal weak proportionality is computable in polynomial time when the number of agents is bounded.Both notions are compatible with Pareto optimality.Source: §9 · p. 34
- Two existence-checking complexity questions remain open: weak SD proportionality with unbounded agents and non-strict preferences, and SD envy-freeness with bounded agents.Source: §9 · pp. 34–35