Equitable Allocations of Indivisible Goods

Rupert Freeman, Sujoy Sikdar, Rohit Vaish, Lirong Xia

TL;DR

This paper explores how to fairly divide indivisible goods among people, focusing on "equitability" (everyone getting the same utility) alongside efficiency (Pareto optimality). They show that achieving both equitability and efficiency is possible, even with relaxations, but combining it with envy-freeness can be impossible. They also provide algorithms for finding these fair and efficient allocations.

What Problem Does This Paper Address?

Fair division is about dividing resources (goods) among individuals. Traditionally, fairness has been viewed in two ways: either agents should prefer their own bundle to others' (envy-freeness), or everyone should derive the same level of happiness or "utility" from their share (equitability). While envy-freeness has been extensively studied, this paper highlights that equitability is often perceived as more important by people, especially when dealing with indivisible items (like a house or a car, which can't be easily split).

The challenge is that achieving perfect equitability with indivisible goods is often impossible, even with just two people and one item. This leads to the need for approximate fairness notions. Furthermore, any fair allocation should ideally also be "Pareto optimal," meaning no other allocation can make at least one person better off without making someone else worse off. This paper investigates the complex interplay between different fairness criteria (equitability and its relaxations, envy-freeness and its relaxations) and Pareto optimality when allocating indivisible goods.

Methods

The paper uses a combination of theoretical analysis and algorithmic design.

  • Theoretical Analysis: They prove existence results for various combinations of fairness and efficiency properties. This involves constructing specific instances of fair division problems to demonstrate when certain allocations are possible or impossible.
  • Algorithmic Design: They develop algorithms to compute allocations that satisfy specific fairness and efficiency criteria. For instance, they propose a pseudopolynomial-time algorithm for finding an allocation that is "equitable up to one good" (EQ1) and Pareto optimal (PO) for strictly positive valuations. They also leverage existing algorithms and concepts like Leximin optimality and Nash social welfare.
  • Complexity Analysis: They analyze the computational complexity of finding these allocations, showing that some problems are NP-hard, while others are solvable in polynomial or pseudopolynomial time under certain conditions (e.g., binary valuations).

Datasets

The paper uses two types of datasets for their experiments:

  • Spliddit Data: Real-world preference data from the fair division website Spliddit. They specifically used instances with strictly positive valuations, more agents than goods, and a limited number of agents and goods.
  • Synthetic Data: Artificially generated instances with a fixed number of agents and goods, and strictly positive valuations drawn from a Dirichlet distribution to mimic real-world preferences.

Key Insights and Ideas

  • Equitability is Key for Perceived Fairness: Experimental studies suggest that people often prioritize equitability over envy-freeness when judging fairness, making this a crucial aspect of fair division research.
  • EQx is Always Possible (with PO): For strictly positive valuations, an allocation that is "equitable up to any good" (EQx) and Pareto optimal (PO) is guaranteed to exist. This is a strong result, showing that a high degree of approximate equitability is achievable.
  • EQ1+PO is Computable: They provide an algorithm that can find an allocation satisfying "equitable up to one good" (EQ1) and Pareto optimal (PO) in pseudopolynomial time for strictly positive valuations. This is a significant algorithmic contribution.
  • The Impossibility of Combining All Three: A surprising finding is that it's impossible to guarantee an allocation that is simultaneously equitable up to one good (EQ1), envy-free up to one good (EF1), and Pareto optimal (PO) for all instances, even with strictly positive valuations. This highlights a fundamental trade-off.
  • Binary Valuations Simplify Things: When agents' valuations for goods are only 0 or 1 (binary valuations), several complex problems become more tractable. For example, an equitable and Pareto optimal allocation is also envy-free, and algorithms can find EQ1+EF1+PO allocations efficiently.

Key Results

  • Existence:
    • An EQx + PO allocation always exists for strictly positive valuations.
  • An EQ1 + PO allocation might fail to exist if valuations can be zero.
  • An EQ1 + EF1 + PO allocation does not always exist, even with strictly positive valuations.
  • Computation:
    • An EQx allocation can be computed in polynomial time.
  • An EQ1 + PO allocation can be computed in pseudopolynomial time for strictly positive valuations.
  • For binary valuations, EQ + PO allocations can be found in polynomial time, and EQ1 + EF1 + PO allocations can also be found efficiently.
  • Complexity:
    • Determining the existence of an EQ1 + PO allocation is strongly NP-hard in general.
  • Determining the existence of an EF + PO allocation is NP-complete for binary valuations.

Limitations and Future Work

  • Hardness for General Valuations: While they provide algorithms for specific cases (like strictly positive or binary valuations), determining the existence of EQ1+PO or EQx+PO allocations remains strongly NP-hard in the general case.
  • Future Directions: The authors suggest extending their work to other models, such as public decisions, settings with additional feasibility constraints, or scenarios involving both goods and chores. They also pose an open question about whether EQx+PO allocations can be computed in polynomial time for strictly positive valuations.

Summary updated

Abstract

In fair division, equitability dictates that each participant receives the same level of utility. In this work, we study equitable allocations of indivisible goods among agents with additive valuations. While prior work has studied (approximate) equitability in isolation, we consider equitability in conjunction with other well-studied notions of fairness and economic efficiency. We show that the Leximin algorithm produces an allocation that satisfies equitability up to any good and Pareto optimality. We also give a novel algorithm that guarantees Pareto optimality and equitability up to one good in pseudopolynomial time. Our experiments on real-world preference data reveal that approximate envy-freeness, approximate equitability, and Pareto optimality can often be achieved simultaneously.
BibTeX
@inproceedings{freeman2019equitable,
  author = {Rupert Freeman and Sujoy Sikdar and Rohit Vaish and Lirong Xia},
  title = {{Equitable Allocations of Indivisible Goods}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/40},
}
Figure