Fair Division of Indivisible Items with Minimal Subsidies

36 concepts14 papers1 proposal

Imagine trying to fairly divide an estate consisting of a house and a car between two siblings. If both value the house significantly more than the car, no clean split of these items can prevent envy. In the classical theory of fair division, achieving perfect fairness—such as envy-freeness, where no agent prefers another's bundle—is often mathematically impossible when items cannot be broken into pieces.

To bridge this gap, economists and computer scientists introduce a small amount of a divisible resource, like money, to act as a subsidy. By giving a little extra cash to the person who received the less valuable item, we can perfectly balance the scales. However, a major practical challenge arises: if a mechanism requires an astronomical amount of money to guarantee fairness, it becomes economically unfeasible for the organizer.

A rapidly growing body of research focuses on subsidy minimization: finding the absolute minimum financial compensation required to guarantee various notions of fairness, and designing efficient algorithms to achieve them.

The Core Framework: Envy-Freeable Allocations

How do we formalize the idea of balancing items with cash? As surveyed by Liu et al. (2024), we can model this as a mixed fair division problem. An allocation of indivisible items is said to be envy-freeable if there exists a set of non-negative monetary transfers given to the agents such that no agent envies the combined package (items plus cash) of any other agent.

To find these optimal allocations, Caragiannis et al. (2021) introduced the Subsidized Minimum Envy-Freeness (SMEF) framework. The core intuition relies on a two-step optimization process:

  1. Partitioning: Group the indivisible items into discrete bundles.
  2. Linear Programming: For a given partition, set up a linear program where the constraints represent the envy-free conditions. Agent $i$'s valuation of their own bundle plus their subsidy must be at least their valuation of Agent $j$'s bundle plus $j$'s subsidy. The objective function directly minimizes the total subsidy payout.

While solving this globally is computationally hard for an arbitrary number of agents, it provides a clean mathematical foundation for bounding the worst-case costs of fairness.

Tightening the Bounds on Envy-Freeness

Early theoretical models often relied on loose upper bounds for the total subsidy required to eliminate envy, which risked overestimating the necessary financial intervention. Recent breakthroughs have significantly tightened these bounds by exploiting the structural properties of "near-fair" allocations.

For instance, consider an allocation that is already Envy-Free up to One Good (EF1)—meaning any envy an agent feels can be eliminated by removing a single item from the envied agent's bundle. Sumita et al. (2023) demonstrated that this bounded item-level envy translates directly to a bounded monetary requirement. Specifically, the authors proved that for $n$ agents, a total subsidy capped at $n(n-1)/2$ times the maximum item value is always sufficient to achieve perfect envy-freeness. This significantly tightened previous quadratic estimates, proving that the financial cost of absolute fairness is far more manageable than previously thought.

Leveraging Structured Preferences for Cost Reductions

The financial burden of fairness drops even more dramatically when agents have structured or simplified preferences. When agents value items in a binary or highly symmetric manner, the overlap in worst-case scenarios is severely constrained.

Dichotomous and Matroidal Valuations

If agents have binary marginal utilities—meaning the marginal value of any additional item is either 0 or 1—the individual subsidy required drops to a maximum of 1 unit of currency per agent. Krishna et al. (2022) showed that under dichotomous valuations, a total subsidy of just $n-1$ is sufficient to achieve envy-freeness, shifting the scaling from quadratic to linear.

Similarly, Goko et al. (2021) and Goko et al. (2024) proved that for agents with matroidal valuations, a "Subsidized Egalitarian" mechanism can simultaneously guarantee envy-freeness, utilitarian optimality, and truthfulness using at most 1 unit per agent. This demonstrates that minimal financial compensations can align individual incentives with social fairness goals without inviting strategic manipulation.

Identical Preferences

When all participants value items identically, the preference alignment eliminates complex cross-envy loops. Aziz et al. (2024) demonstrated that in this setting, a constant total subsidy is sufficient to eliminate envy, completely independent of the total number of items or disparities in agent entitlements.

Alternative Fairness Criteria: Proportionality and Maximin Share

If guaranteeing perfect envy-freeness remains too expensive or complex in general settings, can we achieve alternative, slightly relaxed benchmarks with even lower subsidies? Research by Wu et al. (2023) and Wu et al. (2025) answers this by looking at proportionality (where every agent receives at least $1/n$ of the total value of all items).

The authors proved that while envy-freeness scales with $O(n^2)$ or $O(n)$ subsidies, a total subsidy of at most $n/4$ (for even $n$) or $(n^2 - 1)/(4n)$ (for odd $n$) is sufficient to guarantee proportionality. To achieve this optimally without complex fractional rounding, Wu et al. (2025) designed a clean two-stage algorithmic framework:

[ Indivisible Items ] 
         │
         ▼
┌────────────────────────────────┐
│   1. Initial Partitioning      │ ──► Divide items into n bundles
└────────────────────────────────┘
         │
         ▼
┌────────────────────────────────┐
│     2. Greedy Matching         │ ──► Match agents to bundles requiring the
└────────────────────────────────┘     smallest subsidy to reach the fair share
         │
         ▼
[ Proportional Allocation + Minimal Subsidy ]

For other criteria like the Maximin Share (MMS)—the value an agent could guarantee if they divided the items into $n$ bundles and chose last—the required subsidies drop even further. For three agents, Wu et al. (2025) proved that a tiny total subsidy of just $1/6$ of the maximum item value is enough to guarantee an MMS allocation for both goods and chores. This highlights a clear hierarchy in the economic costs of different fairness standards, allowing system designers to choose the right balance between the strength of the fairness guarantee and the available budget.

Key Foundational Work

Computing Envy-Freeable Allocations with Limited Subsidies (2021) — contributed 3 concept elements to this direction.
Fair and Truthful Mechanism with Limited Subsidy (2021) — contributed 2 concept elements to this direction.
Almost Envy-Freeness with General Valuations (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_subsidy_minimization_for_envy_freeness_82a25ef0,
  title = {subsidy minimization for envy-freeness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subsidy-minimization-for-envy-freeness/rdr_82a25ef0a9374860901168b520a23274},
  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_subsidy_minimization_for_envy_freeness_82a25ef0_v1,
  title = {subsidy minimization for envy-freeness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/subsidy-minimization-for-envy-freeness/rdr_82a25ef0a9374860901168b520a23274/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake