Fair Division Under Capacity and Budget Constraints

28 concepts21 papers1 proposal

In classical fair division theory, we typically assume that any agent can receive any combination of items. If Alice envies Bob's bundle of goods, the theoretical remedy is straightforward: evaluate whether swapping or modifying their allocations can eliminate that envy.

However, real-world resource allocation rarely happens in an unconstrained vacuum. Agents face hard physical, financial, or legal boundaries. Alice might have a strict budget limit, a maximum carrying capacity, or eligibility restrictions that prevent her from legally or physically holding Bob's bundle.

When these constraints are introduced, traditional fairness guarantees like Envy-Freeness up to One Item (EF1) or Envy-Freeness up to Any Item (EFX) break down. As noted by Xiaowei Wu et al. in Budget-feasible Maximum Nash Social Welfare is Almost Envy-free, an agent might be structurally incapable of receiving a specific item even if it would optimize global welfare or reduce envy. This creates a fundamental tension: a globally efficient or theoretically fair allocation may be completely unaffordable or illegal for the individual participants (Ariel D. Procaccia et al. in Fair Rent Division on a Budget; Benjamin Cookson et al. in Constrained Fair and Efficient Allocations).

Redefining Envy Through Feasibility

To bridge this gap, recent research shifts the definition of fairness itself. If Alice cannot legally or financially hold Bob's entire bundle due to her own capacity constraints, does it make sense to say she envies it?

The core insight of this research direction is Feasible Envy-Freeness. Instead of comparing full bundles, an agent's envy is evaluated only against subsets of another agent's bundle that the envying agent could actually accommodate within their own constraints.

This concept manifests in two primary ways:

  1. Capacity-Constrained Envy-Freeness: As formulated by Siddharth Barman et al. in Guaranteeing Envy-Freeness under Generalized Assignment Constraints, an agent only perceives unfairness if they prefer a subset of another's bundle that fits within their own knapsack or budget limit.
  2. Feasible Envy-Freeness up to One Item (F-EF1): Introduced by Amitay Dror et al. in On Fair Division under Heterogeneous Matroid Constraints, this metric evaluates fairness by checking if envy persists after trimming a peer's bundle down to a subset that the envying agent is legally permitted to hold, and then removing a single item.

By grounding envy in what is individually achievable, these frameworks prevent the mathematical impossibility of unconstrained envy-freeness while respecting the operational realities of the system.

Algorithmic Paradigms and Guarantees

Computing these allocations requires navigating the combinatorial complexity of matching preferences with knapsack-like constraints.

Budget and Knapsack Limits

When budget constraints are strict, maximizing standard metrics like Nash Social Welfare (the geometric mean of utilities) no longer guarantees perfect EF1 allocations. However, the authors of Budget-feasible Maximum Nash Social Welfare is Almost Envy-free prove that a budget-feasible Max-NSW allocation still preserves a robust fairness floor of $1/4$-EF1, which improves toward $1/2$-EF1 as budgets grow relative to item costs. For stronger fairness notions, Marius Garbea et al. in EFx Budget-Feasible Allocations with High Nash Welfare provide algorithms that guarantee EFX allocations alongside constant-factor Nash welfare approximations for small numbers of agents. For strict item limits, Arindam Khan et al. in Finding Fair Allocations under Budget Constraints design a polynomial-time greedy algorithm that guarantees an Envy-Free up to 2 goods (EF2) allocation under general capacities.

Structural and Matroid Constraints

Often, constraints are structural rather than purely financial. Items might be partitioned into distinct categories (e.g., course schedules, housing types, or work shifts) where agents have specific category limits or eligibility criteria (Hanna Sumita et al. in Random Assignment of Indivisible Goods under Constraints; Argyrios Deligkas et al. in EF1 and EFX Orientations). When these constraints form a matroid structure, Amitay Dror et al. demonstrate that polynomial-time algorithms can successfully find F-EF1 allocations even when agents have highly heterogeneous restrictions. Furthermore, Nicholas Teh et al. in Weighted Fair Division with Matroid-Rank Valuations: Monotonicity and Strategyproofness show that weighted additive welfarist rules preserve critical properties like strategyproofness and monotonicity under binary submodular preferences.

Two-Sided and Global Constraints

In platforms like social commerce or multi-type exchange markets, constraints apply to both sides of the market simultaneously. For instance, a platform must respect a reseller's capacity while fulfilling a product's minimum exposure or contractual visibility requirements (Anjali Gupta et al. in Towards Fair Allocation in Social Commerce Platforms). Similarly, Sujoy Sikdar et al. in Mechanism Design for Multi-Type Housing Markets with Acceptable Bundles incorporate bundle acceptability constraints into multi-category exchange mechanisms to ensure that final allocations remain practically usable for participants.

The Cost of Constraints

Enforcing these limits naturally impacts the overall social welfare of the system. This trade-off is formalized as the "Price of Cardinality" or the cost of external constraints. Alexander Lam et al. in The (Exact) Price of Cardinality for Indivisible Goods: A Parametric Perspective provide exact parametric bounds on this loss, showing that system efficiency is dictated by the relative tightness of constraints across distinct item categories.

Whether dealing with fixed market values in legal disputes (Soroush Ebadian et al. in Fair Division with Market Values) or logistical shipping costs in online donation distribution (Martin Aleksandrov in Online Fair Division Redux), integrating feasibility constraints transforms fair division from an abstract mathematical exercise into a robust framework for real-world resource engineering.

Key Foundational Work

Incompleteness and Incomparability in Preference Aggregation (2007) — contributed 1 concept elements to this direction.
Hotelling-Downs Model with Limited Attraction (2016) — contributed 1 concept elements to this direction.
Online Fair Division Redux (2016) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_budget_constrained_fair_division_d9e02c6e,
  title = {budget-constrained fair division},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/budget-constrained-fair-division/rdr_d9e02c6edcd748928546a19ff9973a7e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-18},
}

This exact version (version 2, frozen text):

@misc{lacuna_budget_constrained_fair_division_d9e02c6e_v2,
  title = {budget-constrained fair division},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/budget-constrained-fair-division/rdr_d9e02c6edcd748928546a19ff9973a7e/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-18},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake