Fair Division of Mixed Divisible and Indivisible Resources

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

Version 1 of 187 papers116 conceptsfrozen 2026-10-04

For decades, the field of fair division was split into two separate worlds. In one world, researchers studied "cake-cutting"—the division of a single, infinitely divisible resource like land or time. In the other, they studied the allocation of "indivisible goods"—discrete items like houses, cars, or art that cannot be split without losing value.

However, real-world scenarios rarely fit into these neat silos. An inheritance might include both a family home (indivisible) and a savings account (divisible). A divorce settlement involves both physical property and liquid assets. Recent research, synthesized in Mixed Fair Division: A Survey by Shengxin Liu, Xinhang Lu, and others, has unified these domains into a single framework that handles "mixed" resources and "mixed" utilities.

The Hybrid Fairness Standard: EFM

The fundamental challenge of mixed fair division is that the fairness criteria for divisible and indivisible resources are mathematically incompatible. For divisible resources, we demand Envy-Freeness (EF): no agent should prefer another's bundle over their own. For indivisible items, perfect envy-freeness is often impossible (you can't split a single diamond between two people), so we settle for Envy-Freeness up to one item (EF1).

To bridge this, Xiaohui Bei, Zihao Li, and their colleagues introduced Envy-Freeness for Mixed goods (EFM) in Fair Division of Mixed Divisible and Indivisible Goods.

The intuition behind EFM is a "sliding scale" of fairness:

  1. If an agent's bundle contains any divisible resource (like a piece of land), they must not envy any other agent at all.
  2. If an agent's bundle consists only of indivisible items, they are allowed to envy another agent, but only by an amount that could be eliminated by removing a single item from the other person's bundle.

This dual standard ensures that the flexibility of divisible resources is used to "smooth out" the inherent unfairness of discrete items. Remarkably, Shengxin Liu and co-authors proved that an EFM allocation always exists for any number of agents with additive preferences.

Mixed Manna: When One Person's Good is Another's Chore

The complexity increases when we move from "goods" (things everyone wants) to "mixed manna." In these scenarios, items can be chores (negative utility) or goods (positive utility). Crucially, these valuations can be subjective: a lawn-mowing task might be a chore to one person but a source of exercise (a good) to another.

Haris Aziz and Simon Rey explored this in Almost Group Envy-free Allocation of Indivisible Goods and Chores. They found that when chores are involved, the logic of fairness must be inverted. Instead of ensuring no one has "too little," we must ensure no one is burdened with "too much."

In mixed manna settings, the standard of EF1 is expanded: envy must be eliminable either by removing a "good" from the envied person's bundle or by removing a "chore" from the envious person's own bundle. Vishwa Prakash HV and Aditi Sethia recently demonstrated in Fair and Efficient Allocation of Indivisible Mixed Manna that we can achieve both fairness and Pareto efficiency simultaneously, even when agents disagree on the sign of an item's value.

Why It Works: The Proximity of Continuous and Discrete

The reason we can find fair allocations in these complex hybrid spaces often comes down to what Hanna Sumita and Yasushi Kawase call "proximity theorems."

In Fair Allocation with Binary Valuations for Mixed Divisible and Indivisible Goods, they show that the solution to a discrete allocation problem often lies "near" the solution to its continuous counterpart. By first solving the problem as if all items were divisible (using techniques like Maximum Nash Welfare) and then carefully rounding that solution to fit discrete items, researchers can maintain strong fairness guarantees.

This approach is further refined by Bo Li in Allocating Mixed Goods with Customized Fairness and Indivisibility Ratio, which introduces a personalized "indivisibility ratio." This allows the system to adjust the fairness requirement based on exactly how "lumpy" or "smooth" a specific agent's assigned resources are.

Computational Landscapes

While the existence of fair allocations is now better understood, computing them remains a challenge. Yu Zhou and Minming Li have mapped the "complexity landscape" for these problems, showing that while general cases are often NP-hard, specific structures—like ternary valuations or graph-based constraints—allow for efficient polynomial-time algorithms (A Complete Landscape of EFX Allocations on Graphs).

By unifying divisible and indivisible resources, and goods with chores, this research direction provides the mathematical tools necessary to handle the messy, heterogeneous resource distributions found in the real world.

Papers in this version

Showing 60 of 87 papers.

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_fair_division_of_mixed_divisible_and_ind_88023d81,
  title = {Fair Division of Mixed Divisible and Indivisible Resources},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fair-division-of-mixed-divisible-and-indivisible-resources/rdr_88023d814ec940ae98f898a889e4f2ad},
  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_fair_division_of_mixed_divisible_and_ind_88023d81_v1,
  title = {Fair Division of Mixed Divisible and Indivisible Resources},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fair-division-of-mixed-divisible-and-indivisible-resources/rdr_88023d814ec940ae98f898a889e4f2ad/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}