Reconciling Fairness and Efficiency in Indivisible Resource Allocation

This direction is split into other directions: Pareto optimal fair division. Its last version stays readable and citable here.

Version 1 of 181 papers86 conceptsfrozen 2026-10-04

In a world of divisible goods—like a cake or a plot of land—fairness is mathematically elegant. You can always cut the cake such that everyone feels they received a fair share. However, most real-world resources are indivisible: you cannot split a car, a specific house, or a single work shift without destroying its value.

When items cannot be divided, "perfect" fairness (envy-freeness) is often impossible. If there is only one diamond and two people want it, someone will inevitably envy the other. The research direction emerging from these 68 papers focuses on finding the best possible relaxations of fairness—such as Envy-Freeness up to One Item (EF1)—while ensuring the allocation remains Pareto Optimal (PO), meaning no resources are wasted.

The Fundamental Tension

The core challenge in this field is that fairness and efficiency often pull in opposite directions. An allocation might be perfectly fair (e.g., giving no one anything) but horribly inefficient. Conversely, giving everything to the person who values it most is perfectly efficient but profoundly unfair.

Sylvain Bouveret and Jérôme Lang demonstrated in Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity that simply determining if a division exists that is both envy-free and Pareto efficient is $\Sigma^p_2$-complete—a level of computational hardness that suggests these two goals are fundamentally at odds in discrete settings.

Relaxing Fairness: EF1 and EFX

To make progress, researchers use "relaxations." The most prominent is EF1: Agent A does not envy Agent B, provided we can ignore one item in Agent B’s bundle. A stricter version is EFX: Agent A does not envy Agent B even if we remove any single item from B's bundle.

For goods (items with positive utility), the "Maximum Nash Welfare" (MNW) solution—which maximizes the product of agents' utilities—is the gold standard. As noted by Sanath Kumar Krishnamurthy in Finding Fair and Efficient Allocations, MNW naturally satisfies both EF1 and PO. However, computing this is NP-hard, leading to a search for approximation algorithms that can achieve these properties in reasonable time.

The Difficulty of Chores

Dividing "chores" (items with negative utility, like cleaning or difficult tasks) is significantly harder than dividing goods. In chore division, the goal is to minimize the "cost" assigned to each agent.

Haris Aziz and colleagues have shown that while EF1 is relatively easy to achieve for goods, its compatibility with Pareto optimality for chores remains a major hurdle. In New Algorithms for the Fair and Efficient Allocation of Indivisible Chores, Aniket Murhekar and Jugal Garg proved that for chores, even simple two-agent cases can make it mathematically impossible to satisfy both EFX and fractional Pareto optimality.

To bypass this, researchers look for "islands of tractability"—specific scenarios where the math works out:

New Benchmarks: PROPm and Mixed Manna

Beyond envy-freeness, researchers are developing new benchmarks to capture the nuance of fairness. Artem Baklanov and Vasilis Gkatzelis introduced PROPm (Proportionality up to the maximin item) in Achieving Proportionality up to the Maximin Item with Indivisible Goods. This provides a stronger guarantee than standard proportionality relaxations and is proven to exist for any number of agents.

The current frontier of the field is Mixed Manna—scenarios where a single item might be a "good" to one person but a "chore" to another (e.g., a research task that one student loves and another hates). Siddharth Barman and Paritosh Verma have recently explored "introspective" versions of envy-freeness to handle these mixed utilities, though proving the existence of standard EF1+PO allocations in these settings remains one of the field's most significant open questions.

Why This Matters

This research moves us away from simple "split the difference" heuristics toward algorithms that are provably fair and economically sound. By understanding the boundaries of what is mathematically possible, researchers like Ariel D. Procaccia and Jugal Garg are building the foundations for automated systems that can fairly distribute everything from kidney donations and school seats to cloud computing resources and household chores.

Papers in this version

Showing 60 of 81 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

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

This exact version (version 1, frozen text):

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