Fair Division of Indivisible Resources

1,219 concepts598 papers6 proposals

When dividing a continuous resource like a cake, we can achieve perfect fairness: if someone envies another person's slice, we can simply trim a sliver off the larger piece until the envy vanishes. But when resources are discrete and indivisible—such as houses, cars, or specific task assignments—this continuous adjustment is impossible. If two agents both highly value a single unique item, one will receive it and the other will not, creating an unavoidable baseline of envy.

Because perfect envy-freeness is often mathematically impossible in discrete settings, the core challenge of modern fair division is to design relaxations that bound envy by the granularity of the items themselves, and to build algorithms that can guarantee these relaxed states efficiently.

Bounding Envy by a Single Item

To handle the lopsidedness of discrete allocations, researchers shift the goal from absolute envy-freeness to envy-freeness up to a single item. The two primary standards are Envy-Freeness up to One Item (EF1) and Envy-Freeness up to Any Item (EFX).

The intuition behind EF1 is simple: Agent $A$ might envy Agent $B$'s bundle, but this envy should disappear if we hypothetically remove at least one item from $B$'s bundle. As noted by Aziz et al., EF1 provides a robust, mathematically achievable standard for discrete resource allocation.

EFX is a stricter, more elusive standard: Agent $A$'s envy must disappear if we remove any item from $B$'s bundle (specifically, the item least valuable to $A$ that still eliminates the envy). While EF1 allows for a large item to mask a significant disparity, EFX demands that even the smallest item cannot be the sole cause of envy.

The Mechanics of Envy Cycle Elimination

Why is EF1 always guaranteed to exist, and how do we find it? The answer lies in a powerful algorithmic mechanism known as Envy Cycle Elimination, highlighted by Amanatidis et al..

Imagine an allocation process where we distribute items one by one. At any intermediate step, we can construct a directed graph called an envy graph, where each node represents an agent, and a directed edge points from Agent $A$ to Agent $B$ if $A$ envies $B$'s current bundle.

If the graph contains no cycles, we can find a "source" node—an agent whom nobody envies—and hand the next unallocated item to them. Because nobody envied this agent before, giving them an item might make others envy them, but that envy is caused by exactly one item (the one just handed out), preserving the EF1 property.

What happens if a cycle forms? For example, Agent $A$ envies Agent $B$, Agent $B$ envies Agent $C$, and Agent $C$ envies Agent $A$. This cycle represents a Pareto inefficiency in the distribution of envy. We can resolve the cycle by rotating the bundles along the cycle: $A$ gets $B$'s bundle, $B$ gets $C$'s bundle, and $C$ gets $A$'s bundle. Because every agent in the cycle receives a bundle they strictly prefer over their previous one, the total satisfaction increases, and the cycle is broken. By repeatedly allocating to unenvied agents and clearing cycles when they appear, we can completely distribute all items while maintaining an EF1 state.

Bypassing Combinatorial Deadlocks with Charity and Subsidies

While envy cycle elimination guarantees EF1, achieving the stricter EFX standard is notoriously difficult because certain item combinations create combinatorial deadlocks where cycles cannot be cleanly resolved. To bypass these deadlocks, algorithms often must relax the requirement that every item is distributed.

One prominent strategy is charity or buffering. Instead of forcing a complete allocation, algorithms set aside a small pool of highly contested items. For instance, Caragiannis et al. demonstrated that by donating a small subset of items to charity, one can always find an EFX allocation for the remaining items. Building on this concept, Akrami et al. introduced further relaxations like EF2X to significantly reduce the number of items that must be discarded, moving closer to full item distribution.

When leaving items unallocated is unacceptable, another way to smooth out the discrete bumps of indivisible goods is through monetary transfers or subsidies. By introducing a small amount of liquid currency, an algorithm can compensate agents who receive less valuable bundles. As shown by Caragiannis et al. and Aziz et al., calculating minimal financial subsidies allows systems to achieve true envy-freeness without sacrificing items or violating physical bundle constraints.

The Price of Fairness

Enforcing these fairness guarantees does not come for free. In an unconstrained system, maximizing total economic efficiency (social welfare) is straightforward: give each item to the agent who values it the most. However, this utilitarian approach frequently concentrates resources in the hands of a few highly enthusiastic agents, creating massive envy.

When we impose fairness constraints like EF1, EFX, or maximin share guarantees, we force the algorithm to divert items away from their highest-utility users to balance the distribution. This tension creates a measurable efficiency loss known as the price of fairness. As explored by Ge et al., minimizing inequality can sometimes lead to substantial sacrifices in aggregate social welfare. Similarly, Caragiannis et al. demonstrated that even when using randomized mechanisms or lotteries to smooth out ex-ante expectations, a quantifiable efficiency cost persists, scaling with the number of participants in the system.

Ultimately, the study of indivisible resource allocation is a balancing act. By shifting from binary definitions of perfect equity to granular, item-based relaxations, and leveraging structural tools like envy graphs, researchers can navigate the fundamental trade-offs between fairness, efficiency, and computational tractability.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 667 papers
  2. Version 1 · 2026-10-04 · 621 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_indivisible_resource_allocation_ca5f1842,
  title = {indivisible resource allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/indivisible-resource-allocation/rdr_ca5f1842e2684dda99dae6bfe9c4612b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_indivisible_resource_allocation_ca5f1842_v2,
  title = {indivisible resource allocation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/indivisible-resource-allocation/rdr_ca5f1842e2684dda99dae6bfe9c4612b/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake