Exploring Relations among Fairness Notions in Discrete Fair Division

Jugal Garg, Eklavya SharmaarXiv 2025 · arXiv

TL;DR

This paper establishes a comprehensive, near-complete hierarchy of 22 fairness notions used in the allocation of indivisible items (such as goods, chores, or a mix of both). By combining manual proofs with a custom-built automated inference engine, the authors map out the exact relationships (implications and counterexamples) between these notions across 76 distinct settings, providing a unified foundation for future fair division research.

What Problem Does This Paper Address?

In multi-agent systems and economics, "fair division" focuses on how to distribute a set of items among multiple participants equitably. When items are divisible (like land or cake), classic concepts like envy-freeness (no one prefers someone else's bundle) and proportionality (everyone gets their fair share of the total value) are well-behaved. However, when items are indivisible (like cars, houses, or specific tasks), perfect fairness is often mathematically impossible.

To cope with this, researchers have proposed dozens of relaxations over the years—such as Envy-Freeness up to One Item (EF1), Envy-Freeness up to Any Item (EFX), and Maximin Share (MMS). Because these notions were developed independently across different contexts (goods vs. chores, equal vs. unequal entitlements, additive vs. submodular valuations), the literature became highly fragmented. This paper systematically untangles this web, answering exactly which fairness definitions guarantee others, and under what specific conditions.

Methods

The authors adopt a hybrid approach combining rigorous theory with automated reasoning:

  1. Axiomatic Extensions: They extend existing fairness definitions (originally tailored for simple settings like additive goods) to the most general setting possible: mixed manna (goods and chores combined) with non-additive valuations and unequal agent entitlements.
  2. Manual Proofs: The authors manually prove 113 foundational results (46 known/trivial, 67 entirely new), focusing on creating the simplest possible counterexamples to disprove false implications.
  3. Automated Inference Engine: To avoid a combinatorial explosion of proofs across 76 different settings, they developed a JavaScript-based inference engine. By modeling fair division settings as a partial order, the engine uses transitive closure logic to automatically deduce hundreds of additional conditional implications and non-implications.
  4. Programmatic Verification: They implemented a Python verification suite to programmatically check that their proposed counterexamples correctly satisfy or violate the targeted fairness properties.

Datasets

Not discussed in the paper. As a theoretical computer science and game theory paper, it does not utilize empirical datasets. Instead, it introduces a comprehensive suite of programmatically verifiable counterexamples encoded as Python objects.

Key Insights and Ideas

  • The Goods vs. Chores Asymmetry: One might assume that properties of goods naturally mirror properties of chores (negative goods). The paper highlights sharp asymmetries. For example, under additive valuations with equal entitlements, Proportionality ($\text{PROP}$) implies Maximin Share ($\text{MMS}$) for goods, but $\text{PROP}$ does not imply Epistemic EF1 ($\text{EEF1}$) for chores.
  • Algorithmic Knowledge Mapping: Instead of manually proving all $22 \times 21 = 462$ pairs of relationships for every single setting, treating settings as a structured family allows an inference engine to do the heavy lifting. If a counterexample holds in a simple setting, the engine automatically propagates that non-implication to all more general settings.

Key Results

The paper successfully maps out a near-complete picture of implications for 76 distinct fair division settings, leaving at most 3 unresolved pairs in any single scenario.

The core structural hierarchies are visualized via Directed Acyclic Graphs (DAGs), where a path from notion $F_1$ to $F_2$ indicates that $F_1$ implies $F_2$. Figure 1 illustrates the stark contrast between allocating goods versus chores under additive valuations:

Figure 1: Implications between fairness notions for additive valuations over goods and over chores when agents have equal entitlements. There is a vertex for each fairness notion. Notion F1 implies notion F2 iff there is a path from F1 to F2 in the graph (except that it is not known whether MXS implies EEF1 for goods). Borderless vertices (red) are infeasible notions, vertices with rounded corners (green) are feasible notions, and the feasibility of the remaining vertices (gray) are open problems. Note that goods and chores have some key differences, e.g., for goods, PROP =⇒MMS =⇒EEF1 =⇒PROP1, but for chores, MMS ̸=⇒PROP1, and PROP ̸=⇒EEF1.

Key takeaways from the hierarchy include:

  • For additive goods, $\text{PROP} \implies \text{MMS} \implies \text{EEF1} \implies \text{PROP1}$.
  • For chores, $\text{MMS}$ does not imply $\text{PROP1}$, breaking the clean chain seen in goods.
  • The authors successfully resolved long-standing folklore assumptions by providing explicit, minimal counterexamples for boundaries that were previously only suspected to exist.

Limitations and Future Work

  • Unresolved Gaps: A few open problems remain where the engine could neither prove an implication nor find a counterexample. For instance, it is still unknown whether Minimum EFX Share ($\text{MXS}$) implies Epistemic EF1 ($\text{EEF1}$) for additive goods with equal entitlements.
  • Exclusion of Efficiency and Approximations: The current framework omits fairness concepts that inherently bundle economic efficiency (like Pareto optimality or Competitive Equilibrium with Equal Incomes).
  • Multiplicative Approximations: The inference engine cannot currently reason about parameterized approximations (e.g., $\alpha$-EF1). Scaling the engine to compose and evaluate arbitrary functions of approximation ratios represents a significant future challenge.

Summary updated

Abstract

Fair allocation of indivisible items among agents is a fundamental and extensively studied problem. However, fairness does not have a single universally accepted definition, leading to many competing fairness notions. Some of these notions are considered stronger or more desirable, but they are also more difficult to guarantee. In this work, we examine 22 different fairness notions and organize them into a hierarchy. Formally, we say that a notion $F_1$ implies another notion $F_2$ if every $F_1$-fair allocation is also $F_2$-fair. We give a near-complete picture of implications among fairness notions: for almost every pair of notions, we either prove an implication or give a counterexample demonstrating that the implication does not hold. Although some of these results are already known, many are new. We examine multiple settings, including the allocation of goods, chores, and mixed manna, and different valuation classes like additive, submodular, and subadditive. We believe this work clarifies the relative strengths and applicability of these notions, providing a foundation for future research in fair division. Moreover, we develop an inference engine to automate part of our work. It is available as a user-friendly web application and may have broader applications beyond fair division.
BibTeX
@misc{garg2025exploring,
  author = {Jugal Garg and Eklavya Sharma},
  title = {{Exploring Relations among Fairness Notions in Discrete Fair Division}},
  year = {2025},
  eprint = {2502.02815},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.02815},
}
Figure