Fairness and Efficiency in Indivisible Resource Allocation

This direction is merged into another direction: indivisible resource allocation. Its last version stays readable and citable here.

Version 1 of 152 papers54 conceptsfrozen 2026-10-04

In classical economics, there is often an assumed "Price of Fairness"—the idea that ensuring an equitable distribution of resources must come at the cost of total system efficiency. However, a growing body of research suggests that this trade-off is frequently avoidable. In many complex allocation scenarios, from assigning conference papers to distributing delivery orders, we can achieve high levels of fairness and Pareto optimality simultaneously.

The Vanishing Price of Fairness

The central intuition behind recent breakthroughs is that the set of "efficient" outcomes is often large enough to contain at least one "fair" outcome. In bipartite matching problems, such as matching students to schools, Rémi Castera, Felipe Garrido-Lucero, and their colleagues have shown in The Price of Fairness in Bipartite Matching that the price of fairness is often zero. Because there are typically many different ways to achieve a maximum-size matching, a system can simply select the one that is most equitable without reducing the total number of matches.

This principle extends to more complex constraints. Francesco Bonchi and David García-Soriano demonstrate in Fair-by-design matching that "egalitarian" matching—where we prioritize the least-satisfied participants—can be scaled to massive graphs without sacrificing global efficiency.

Structural Compatibility of Fairness Notions

A major hurdle in fair division is that different definitions of "fair" can seem to contradict each other. For example, Envy-Freeness (EF) (no one wants anyone else's bundle) and Maximin Share (MMS) (everyone gets at least a specific "fair share" value) are conceptually distinct.

Recent work has proven these notions are more compatible than previously thought. Hannaneh Akrami and Nidhi Rathi showed in Achieving Maximin Share and EFX/EF1 Guarantees Simultaneously that it is possible to guarantee agents 2/3 of their maximin share while maintaining envy-freeness up to any good (EFX). Similarly, Arash Ashuri demonstrated that proportionality-based and envy-based fairness can be satisfied at the same time in Simultaneously Satisfying MXS and EFL.

The "why" behind this compatibility often lies in the discrete nature of the items. By allowing for small relaxations—like being envy-free "up to one item" (EF1)—algorithms gain the flexibility to optimize for social welfare or Pareto optimality without violating the core spirit of fairness.

Reconciling Goods and Chores

The problem becomes harder when the "manna" being divided includes both goods (things people want) and chores (tasks people dislike). Traditionally, these were studied separately, but real-world problems—like a gig worker receiving a mix of high-tip and long-distance delivery orders—require a unified approach.

Haris Aziz and Ayumi Igarashi have shown that for small groups, EF1 and Pareto optimality can coexist even with mixed utilities in Fair Allocation of Indivisible Goods and Chores. More recently, Siddharth Barman and Paritosh Verma proved in Proximately Envy-Free and Efficient Allocation of Mixed Manna that efficiency and fairness can coexist even when agents have conflicting valuations for the same items.

The mechanism that often bridges this gap is the leximin solution. As Zijie Liu argues in The Fairness of Leximin in Allocation of Indivisible Chores, by lexicographically maximizing the utility of the worst-off agent, the system naturally finds an allocation that is both Pareto optimal and highly fair.

When Preferences Align

The trade-off between fairness and efficiency further collapses when agent preferences follow certain structural patterns:

  1. Matroid Valuations: When agents value items based on their "rank" in a matroid (a common structure in task assignment), Siddharth Barman and Paritosh Verma proved that a maximin share allocation exists that also maximizes total social welfare (Existence and Computation of Maximin Fair Allocations Under Matroid-Rank Valuations).
  2. Lexicographic Preferences: If agents rank items in a strict order of importance, Hadi Hosseini and Lirong Xia found that EFX is always compatible with Pareto optimality (Fair and Efficient Allocations under Lexicographic Preferences).
  3. Monotone Likelihood Ratios: In continuous division (like cake-cutting), Nidhi Rathi showed that if preferences follow certain probability distributions, every envy-free allocation is automatically Pareto optimal (Fair Cake Division Under Monotone Likelihood Ratios).

These findings suggest that the "conflict" between equity and efficiency is not a fundamental law of economics, but rather a hurdle that can be cleared by choosing the right fairness relaxations and leveraging the underlying structure of agent preferences.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fairness_and_efficiency_in_indivisible_r_9f847bac,
  title = {Fairness and Efficiency in Indivisible Resource Allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fairness-and-efficiency-in-indivisible-resource-allocation/rdr_9f847bac239c4994b3c5ec0df406a3bf},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_fairness_and_efficiency_in_indivisible_r_9f847bac_v1,
  title = {Fairness and Efficiency in Indivisible Resource Allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fairness-and-efficiency-in-indivisible-resource-allocation/rdr_9f847bac239c4994b3c5ec0df406a3bf/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}