Fair Resource Allocation under Combinatorial Constraints

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 235 papers43 conceptsfrozen 2026-10-04

In classical fair division theory, we often imagine a group of people splitting a pile of treasures where everyone can take as much as they want, provided the division is "fair." However, real-world resources come with strings attached. A student cannot take ten university courses even if they love them all; a charity cannot ship more food than their trucks can carry; and a project manager cannot assign a task to someone who lacks the specific skill to perform it.

These restrictions—budgets, capacities, and structural dependencies—are known as combinatorial constraints. Recent research has shifted from idealized "unconstrained" fairness to a more practical framework: how do we ensure equity when the rules of the world prevent us from reaching a perfect split?

The Feasibility Gap

The fundamental challenge is that standard fairness guarantees, such as Envy-Freeness up to One Item (EF1), often become mathematically impossible when constraints are introduced. In a standard setting, EF1 means that if Alice envies Bob’s bundle, she would stop envying him if just one item were removed from his pile.

As Xiaowei Wu, Bo Li, and their colleagues demonstrate in Budget-feasible Maximum Nash Social Welfare is Almost Envy-free, adding a simple budget limit breaks this. If Alice has a small budget and Bob has a large one, Alice might envy Bob’s expensive items, but she couldn't legally hold them even if they were offered to her. This creates a "feasibility gap" where traditional algorithms try to solve for a version of fairness that the system's physical or financial rules won't allow.

Redefining Envy: Feasible Envy-Freeness

To bridge this gap, researchers have introduced the concept of Feasible Envy-Freeness. The intuition is simple: you should only be jealous of what you could actually have.

In On Fair Division under Heterogeneous Matroid Constraints, Amitay Dror, Michal Feldman, and Erel Segal-Halevi argue that fairness should be measured by assessing envy only after "trimming" a peer’s bundle. If Alice envies Bob, we check if she would still envy him if his bundle were reduced to a subset that Alice is legally permitted to hold. This F-EF1 metric acknowledges that heterogeneous capacities (where different agents have different limits) are a feature of the problem, not a bug.

Algorithmic Solutions: Greedy and Round Robin

How do we actually find these allocations? The problem essentially turns fair division into a variation of the knapsack problem, which is notoriously difficult to solve optimally.

One approach is the DensestGreedy algorithm, proposed by Arindam Khan and Sudarshan Shyam in Finding Fair Allocations under Budget Constraints. Instead of just picking the most valuable item, the algorithm prioritizes items that offer the best "value-to-cost" ratio while staying within individual budgets. This greedy approach is proven to maintain an EF2 guarantee (envy-free up to two items) even under strict knapsack constraints.

Another strategy is the Constrained Round Robin (CRR), developed by Haris Aziz and Nicholas Mattei in The Constrained Round Robin Algorithm for Fair and Efficient Allocation. CRR uses a standard picking sequence but embeds a "welfare oracle." Before an agent picks an item, the system checks if that pick would violate global feasibility or efficiency targets. This allows designers to "dial in" a specific level of social welfare while the round-robin mechanism naturally steers the outcome toward fairness.

Reconciling Market Values and Social Welfare

The complexity increases when external constraints, like Fair Market Value (FMV), are introduced. In many legal disputes, an allocation isn't just about what people want; it's about the dollar value of the piles. Soroush Ebadian and Nisarg Shah explore this in Fair Division with Market Values, showing that fixed market prices significantly restrict the set of "fair" outcomes, often forcing a trade-off between subjective happiness and objective financial equality.

Despite these hurdles, the research suggests that fairness is surprisingly resilient. In The Price of Opportunity Fairness in Matroid Allocation Problems, Rémi Castera and Vianney Perchet demonstrate that in many randomized or large-scale settings, we can achieve "opportunity fairness"—ensuring groups receive resources proportional to their potential—with zero loss to total social welfare.

Why It Works: The Power of Downward-Closure

The reason many of these algorithms succeed is a structural property called downward-closure. If a set of items is "feasible" (e.g., fits in a budget), then any smaller subset of those items is also feasible. By exploiting this, researchers like Mashbat Suzuki in Compatibility of Fairness and Nash Welfare under Subadditive Valuations have shown that we can "fair-ify" efficient allocations. We start with a high-welfare distribution and incrementally swap or remove items until fairness constraints are met, knowing that the downward-closed nature of the constraints won't suddenly break the feasibility of the remaining bundles.

Papers in this version

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 1, frozen text):

@misc{lacuna_fair_resource_allocation_under_combinato_d9e02c6e_v1,
  title = {Fair Resource Allocation under Combinatorial Constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fair-resource-allocation-under-combinatorial-constraints/rdr_d9e02c6edcd748928546a19ff9973a7e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-18},
}