For One and All: Individual and Group Fairness in the Allocation of Indivisible Goods

Jonathan Scarlett, Nicholas Teh, Yair Zick

Introduction

The fair division of resources is a fundamental challenge in economics and computer science, particularly when the resources are "indivisible"—items like course slots, medical supplies, or housing that cannot be split into smaller pieces. Traditionally, fairness research has branched into two distinct paths: individual fairness, which ensures no single person feels mistreated relative to another, and group fairness, which ensures that demographic or professional groups receive equitable treatment.

In practice, these two goals often conflict. An allocation that satisfies every individual might result in systemic imbalances between groups, while an allocation designed for group parity might leave individuals within those groups feeling cheated. This paper bridges this gap by proposing algorithms that concurrently guarantee individual and group fairness across various preference structures.

The Fairness Framework

The authors focus on two primary fairness notions:

  1. Individual Envy-Freeness up to one/any good (i-EF1/EFX): An agent does not envy another's bundle after removing at most one item (EF1) or any item (EFX) from the other's bundle.
  2. Group Weighted Envy-Freeness up to one good (g-WEF1): This accounts for groups of different sizes. A group should not envy another group's "weighted" bundle, acknowledging that larger groups require more resources to achieve parity.

A significant theoretical contribution of the paper is the proof that the strongest version of group fairness (g-WEFX) is mathematically incompatible with even basic individual fairness (i-EF1), even when all agents share identical valuations. This finding justifies the authors' focus on the g-WEF1 relaxation as a robust and achievable standard.

Algorithmic Solutions

The paper introduces two polynomial-time algorithms designed to handle different levels of agent preference complexity.

SM-IWRR: Sequential Maximin-Iterative Weighted Round Robin

Designed for All-Common Valuations (where everyone values items identically), SM-IWRR employs a two-stage process. First, it creates an individually fair allocation using a Maximin approach. It then treats these individual bundles as "representative goods." By reducing complex bundles into single abstract items, the algorithm can apply group-level fairness logic—using a weighted round-robin strategy—without disrupting the individual-level fairness already established. This approach successfully achieves i-EFX and g-WEF1 simultaneously.

IWRR: Iterative Weighted Round Robin

For Group-Common Valuations (where agents within a group share preferences, but groups differ), the authors propose a greedy approach. In each step, the group with the lowest current "weighted bundle size" is selected to pick an item. Within that group, the agent with the fewest items picks their favorite remaining good. This ensures i-EF1 and g-WEF1 are met concurrently.

Handling General Valuations

When agents have entirely unique preferences (General Valuations), achieving exact group fairness alongside individual fairness becomes significantly more difficult. The authors pivot to ex-ante g-WEF1, which considers the expected utility a group member would receive. For this complex case, they demonstrate that while maintaining i-EF1, their algorithms can achieve a 1/3-approximation to ex-ante group fairness.

Key Results and Efficiency

The paper’s findings are summarized by several key properties:

  • Simultaneous Guarantees: The algorithms are the first to provide formal guarantees for both individual and group fairness in these settings.
  • Computational Feasibility: All proposed algorithms run in polynomial time, making them suitable for real-world, large-scale applications.
  • Robustness: The allocations also satisfy Proportionally Envy-Free (PEF) standards and Group Stability, meaning agents have no incentive to misreport their group membership to gain a better allocation.

Limitations and Future Directions

While the paper provides a strong theoretical foundation, several avenues for future research remain:

  • Closing the Approximation Gap: The 1/3-approximation for general valuations is a starting point; future work may find tighter bounds or non-sequential algorithms that improve this ratio.
  • Defining Group Value: The current model assumes a group's value is the sum of its members' values. Alternative "allocation-based" definitions, where value depends on internal distribution, could be explored.
  • Chores and Efficiency: The study focuses on "goods." Extending these fairness guarantees to "chores" (undesirable tasks) and exploring the trade-offs with economic efficiency (Pareto optimality) are logical next steps for the field.

By providing a unified framework for individual and group concerns, this research offers a more holistic approach to resource allocation that respects both the person and the collective.

Summary updated

Abstract

Fair allocation of indivisible goods is a well-explored problem. Traditionally, research focused on individual fairness - are individual agents satisfied with their allotted share? - and group fairness - are groups of agents treated fairly? In this paper, we explore the coexistence of individual envy-freeness (i-EF) and its group counterpart, group weighted envy-freeness (g-WEF), in the allocation of indivisible goods. We propose several polynomial-time algorithms that provably achieve i-EF and g-WEF simultaneously in various degrees of approximation under three different conditions: (i) when agents have identical additive valuation functions, i-EFX and g-WEF1 can be achieved simultaneously; (ii) when agents within a group share a common valuation function, an allocation satisfying both i-EF1 and g-WEF1 exists; and (iii) when agents' valuations for goods within a group differ, we show that while maintaining i-EF1, we can achieve a 1/3-approximation to a notion termed ex-ante g-WEF1. Our results thus provide a first step towards connecting individual and group fairness in the allocation of indivisible goods, in the hopes of its useful application to domains requiring the reconciliation of diversity with individual demands.
BibTeX
@inproceedings{scarlett2023one,
  author = {Jonathan Scarlett and Nicholas Teh and Yair Zick},
  title = {{For One and All: Individual and Group Fairness in the Allocation of Indivisible Goods}},
  booktitle = {AAMAS},
  year = {2023},
  url = {https://openreview.net/forum?id=AsV9OW6xhi},
}
Figure