When we divide indivisible resources—such as houses, shifts, or specialized equipment—among multiple participants, we run into a fundamental combinatorial wall. Classical economic fairness concepts, like perfect envy-freeness, often do not exist in discrete settings. Even when fair allocations do exist, finding them typically requires searching through an exponential combination of items, making the problem NP-hard.
To bypass this computational bottleneck, a major research direction focuses on designing polynomial-time algorithms for fair division. Instead of forcing exact solutions on intractable problems, this field uncovers "islands of tractability" by relaxing fairness criteria, mapping discrete items into continuous spaces, and exploiting hidden network and matroid structures.
Relaxing the Boundaries: Bounded Envy and Approximations
The most direct way to achieve polynomial-time performance is to replace strict, binary fairness targets with relaxed criteria that accommodate the discrete "jumps" of indivisible items.
Consider Envy-Freeness up to One Item (EF1). An allocation is EF1 if agent $A$ envies agent $B$, but removing just a single item from $B$'s bundle eliminates the envy. This slight relaxation completely changes the computational landscape. Krishnamurthy et al. demonstrate in Finding Fair and Efficient Allocations that allocations satisfying both EF1 and Pareto efficiency can be computed in pseudopolynomial time for additive valuations by leveraging the structural properties of economic market equilibria.
When even EF1 or its stronger counterpart EFX (Envy-Freeness up to Any Item) prove elusive or hard to compute, researchers introduce alternative epistemic or proportional baselines:
- Epistemic and Minimum Shares: Caragiannis et al. show in New Fairness Concepts for Allocating Indivisible Items that by shifting to concepts like Epistemic EFX (EEFX) and Minimum EFX Share (MXS), existence is always guaranteed, and allocations can be found efficiently in polynomial time.
- Maximin Item Proportionality: In PROPm Allocations of Indivisible Goods to Multiple Agents, Baklanov et al. prove that proportionality up to the maximin item (PROPm) can be constructed in polynomial time, transforming a theoretical existence proof into a practical multi-agent tool.
- Polynomial-Time Approximation Schemes (PTAS): Instead of changing the definition of fairness, we can approximate the target numerical value. Akrami et al. demonstrate this in Breaking the 3/4 Barrier for Approximate Maximin Share, operationalizing complex existence proofs into a PTAS that finds near-optimal Maximin Share (MMS) allocations efficiently.
Continuous Machinery for Discrete Lotteries
Another powerful mechanism for achieving polynomial-time tractability is to temporarily pretend the items are divisible. Continuous optimization problems—like maximizing Nash Social Welfare or finding competitive market equilibria—can often be solved efficiently using convex programming or linear programming. Once a continuous, fractional solution is found, it is mapped back into a discrete allocation.
A clear example of this is found in Simultaneously Achieving Ex-ante and Ex-post Fairness. Here, Aziz et al. map continuous consumption rates into a square matrix of items and agent-time slots. By decomposing this fractional matrix into a weighted average of discrete assignments (akin to a Birkhoff-von Neumann decomposition), the authors compute fair lotteries in polynomial time that satisfy fairness constraints both before and after the random draw.
[Continuous Preferences] ──> [Convex/Linear Program] ──> [Fractional Matrix]
│
▼
[Discrete Fair Allocation] <── [Matrix Decomposition] <─────────┘
Similarly, market models provide a smooth geometric landscape that guarantees rational solutions. In Convex Program Duality, Fisher Markets, and Nash Social Welfare, Cole et al. utilize convex programming duality to show that market models with spending restrictions admit rational equilibria. This structural rationality ensures that standard, polynomial-time optimization methods can be used to resolve the underlying fair division problem.
Embedding Fairness into Network Flows and Matroids
When allocations must satisfy physical or structural constraints—such as network topologies, category limits, or scheduling dependencies—the problem threatens to become doubly intractable. To maintain polynomial runtime, algorithms must exploit the mathematical properties of the underlying constraints, such as matroids or network flow conservation.
Matroid Constraints and Multiplicative Convergence
When items fall into categories with strict capacity limits (modeled as matroids), a simple greedy approach can get stuck in infinite loops. In Matroid Constrained Fair Allocation Problem, Arpita Biswas introduces the SWAP algorithm. The intuition behind its polynomial-time convergence is elegant: the algorithm ensures that each local redistribution step strictly reduces the valuation of the most advantaged agent's bundle by a specific multiplicative factor. This geometric reduction prevents cycling and forces rapid convergence to an EF1 allocation.
Network Flow Reductions
Network flow formulations allow algorithms to offload combinatorial complexity onto highly optimized, polynomial-time graph algorithms (like Max-Flow Min-Cut).
- Task Allocation: Ye et al. demonstrate in Fair task allocation in transportation that fair logistics distribution can be modeled as a series of max-flow problems over a specialized network structure containing "dummy jobs," ensuring polynomial runtime.
- Bargaining and Capacities: In Network bargaining with general capacities, Farczadi et al. reduce complex, multi-contract bargaining networks into simpler, unit-capacity auxiliary graphs. This reduction proves that allowing agents to hold multiple contracts does not exponentially increase the computational complexity of finding a fair, balanced split.
Controlling Complexity via State Tracking
When a fair allocation problem remains NP-hard in the general case, polynomial or pseudopolynomial tractability can still be achieved by isolating the source of the complexity—often the number of agents ($n$)—and tracking agent interactions through dynamic programming.
In Computing welfare-Maximizing fair allocations of indivisible goods, Aziz et al. show that if the number of agents is fixed, welfare-maximizing fair allocations can be found in pseudopolynomial time. The algorithm works by using dynamic programming to track the utility differences between agents as state variables. Instead of exploring every possible combination of items, the algorithm only needs to explore the reachable vectors of utility differences, drastically bounding the search space.
Similarly, when agents have externalities (caring about who else receives an item), Deligkas et al. show in The Complexity of Fair Division of Indivisible Items with Externalities that the problem can be modeled as an Integer Linear Program (ILP). By fixing the number of agents and distinct item types, they apply Lenstra’s theorem—which states that ILPs with a bounded number of variables can be solved in polynomial time—to achieve fixed-parameter tractability.
Summary
Polynomial-time fair allocation works because it avoids the brute-force search of discrete combinations. By relaxing the boundaries of what is considered "fair" (such as EF1), mapping discrete choices into continuous convex spaces, or routing allocations through structured network flows, these algorithms transform intractable combinatorial nightmares into smooth, mathematically predictable, and scalable systems.
Key Foundational Work
Fair Bandwidth Allocation for Multicasting in Networks with Discrete Feasible Set (2004) — contributed 1 concept elements to this direction.
Fair allocation of utilities in multirate multicast networks: a framework for unifying diverse fairness objectives (2002) — contributed 1 concept elements to this direction.