When dividing resources among multiple participants—whether allocating cloud computing infrastructure, splitting an estate, or distributing research grants—the ideal outcome is perfect fairness. In algorithmic game theory, this is often formalized as envy-freeness (EF), where every participant values their own allocated share at least as much as anyone else's.
However, when resources are indivisible (like a house or a specific computer server), perfect envy-freeness is mathematically impossible to guarantee. Even when resources are divisible (like a continuous "cake"), computing a perfectly fair allocation under complex, realistic preferences is often computationally intractable.
To bypass these fundamental barriers, a powerful research direction has emerged: polynomial-time approximate fair allocation. Instead of searching for an elusive, computationally impossible perfect allocation, this paradigm designs efficient algorithms that guarantee near-perfect fairness. By relaxing fairness criteria or leveraging market-clearing economic principles, these algorithms find highly equitable solutions in polynomial time.
Relaxing Envy-Freeness: EF1 and EFX
The most intuitive way to handle indivisible items is to relax what "envy-free" means. If we cannot eliminate envy entirely, can we bound it by a single item?
As surveyed by Aziz et al. in Algorithmic Fair Allocation of Indivisible Items: A Survey and New Questions, a foundational relaxation is Envy-Free up to One Good (EF1). An allocation is EF1 if Agent A might envy Agent B, but that envy would vanish if we removed just one item from Agent B’s bundle. The authors highlight that EF1 allocations are always mathematically guaranteed to exist and can be computed efficiently.
A stricter and more desirable relaxation is Envy-Free up to Any Good (EFX), where envy must vanish upon removing any single item from the envied bundle. Finding exact EFX allocations is notoriously difficult and has long resisted polynomial-time solutions.
To make this tractable, researchers look for approximations. Chan et al. in Maximin-Aware Allocations of Indivisible Goods broke through previous exponential-time barriers by introducing a polynomial-time algorithm that guarantees a 1/2-approximate EFX allocation for agents with subadditive valuations.
Perfect Envy-Freeness (Often Impossible)
│
▼
Envy-Free up to Any Good (EFX) (Computationally Hard)
│
▼
1/2-Approximate EFX / EF1 (Polynomial-Time Tractable)
Another way to achieve near-EFX guarantees is to leave a small number of items unallocated. Chaudhury et al. in Improving EFX Guarantees through Rainbow Cycle Number achieved a $(1-\epsilon)$-EFX allocation by mapping the problem to extremal graph theory. By identifying and eliminating "envy cycles" (where Agent A envies B, B envies C, and C envies A) using a graph-theoretic structure called the rainbow cycle number, the authors efficiently reallocate bundles to drive down envy while leaving only a sublinear number of goods unallocated.
Approximating Nash Social Welfare via Market Clearing
Instead of evaluating fairness purely through pairwise envy, we can optimize a global objective function that inherently balances fairness and efficiency: Nash Social Welfare (NSW). The NSW of an allocation is the geometric mean of all agents' utilities ($\prod_{i=1}^n U_i^{1/n}$). Maximizing NSW acts as a natural mediator; because it is a product, the metric penalizes allocations that leave any single agent with zero utility, forcing a fair distribution of goods.
Unfortunately, maximizing NSW over indivisible items is NP-hard. To solve this, algorithms borrow a concept from mathematical economics: Fisher Markets. In a virtual Fisher market, agents are given a budget of artificial currency to spend on fractional shares of goods, and prices adjust until the market clears.
The core intuition of this approach is a two-step pipeline:
- Compute a fractional equilibrium: Solve a continuous convex program to find a perfectly fair, fractional market clearance.
- Round to an integral allocation: Convert the fractional shares into whole items without destroying the fairness guarantees.
Cole et al. in Convex Program Duality, Fisher Markets, and Nash Social Welfare utilized convex program duality to bridge the gap between continuous market models and discrete allocations, proving that a factor-2 approximation of the maximum NSW can be computed in polynomial time.
When agents have utility caps (satiation) or budget constraints, rounding becomes significantly harder because an agent might easily be pushed past their utility limit or starved of items. Garg et al. in Satiation in Fisher Markets and Approximation of Nash Social Welfare designed a specialized rounding algorithm that carefully transitions fractional market equilibria into discrete allocations, yielding the first constant-factor approximation for budget-additive valuations.
This rounding paradigm has been progressively extended to more complex preference structures. For instance, Feng et al. in Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations introduced a "large vs. small item" sorting strategy to achieve a constant-factor approximation even when agents have submodular preferences (exhibiting diminishing returns) and asymmetric weights.
Tractable Fragments and Greedy Heuristics
When agent preferences are highly structured, we can achieve even tighter approximations. Vaish et al. in Greedy Algorithms for Maximizing Nash Social Welfare demonstrated that if all agents share identical valuations for the items, a simple, combinatorial greedy allocation strategy achieves a near-optimal 1.061-approximation.
Expanding on these structured settings, Murhekar et al. in Tractable Fragments of the Maximum Nash Welfare Problem showed that for identical valuations, the maximum NSW can actually be approximated to any arbitrary degree of accuracy ($\epsilon$) in polynomial time. Their algorithm rounds item values into a fixed number of configurations and finds the optimal allocation path through a layered graph representation.
Where simple query models fail against highly expressive preferences, Krishna et al. in Sublinear Approximation Algorithm for Nash Social Welfare with XOS Valuations showed that by utilizing demand and XOS oracles, algorithms can break long-standing linear approximation barriers to achieve sublinear approximations for fractionally subadditive preferences.
Approximate Cake Cutting and Maximin Share
The approximation paradigm is equally vital for divisible resources, traditionally modeled as "cake cutting." While a cake can theoretically be cut into contiguous pieces such that no agent envies another, computing these exact boundaries is impossible for a finite algorithm.
To resolve this, Goldberg et al. in Contiguous Cake Cutting: Hardness Results and Approximation Algorithms proved that while adding simple real-world constraints (like a fixed ordering of agents) makes exact division NP-hard, a polynomial-time algorithm can guarantee a 1/3-approximate envy-free allocation. In this setting, no agent perceives another's share as more than one-third more valuable than their own.
Kulkarni et al. in Approximation Algorithms for Envy-Free Cake Division with Connected Pieces pushed this boundary further, developing an algorithm that guarantees a tighter $(\frac{1}{4} + o(1))$-additive envy bound in polynomial time.
[─── Agent 1's Piece ───][─── Agent 2's Piece ───][─── Agent 3's Piece ───]
▲ ▲
Algorithmically calculated cuts guarantee that
perceived envy between any two pieces is ≤ 1/4.
Maximin Share (MMS) Guarantees
Another cornerstone fairness standard is the Maximin Share (MMS)—the worst-case value an agent can secure if they are allowed to divide the resources into $n$ bundles but must choose their bundle last.
When exact MMS cannot be guaranteed, algorithms seek a constant fraction of this share. Biswas et al. in Groupwise Maximin Fair Allocation of Indivisible Goods proved a powerful structural link: any allocation satisfying EF1 automatically guarantees every agent at least a 1/2-approximation of their Groupwise Maximin Share (GMMS).
For divisible goods where agents have complex, non-linear preferences, Aziz et al. in Fair Allocation of Divisible Goods under Non-Linear Valuations designed a novel algorithm providing a $\frac{2}{2n-1}$-MMS allocation for $n$ agents, proving that this bound is asymptotically tight for general non-decreasing valuations.
Balancing Fairness and Efficiency
In many practical applications, fairness cannot be pursued in a vacuum; it must be balanced against global efficiency or strategic behavior.
When agents are strategic and might lie about their preferences, Barman et al. in Fair Division of Indivisible Goods Among Strategic Agents introduced bi-criteria approximation mechanisms. These mechanisms manage computational hardness and strategic manipulation simultaneously by relaxing both the fairness threshold and the social welfare target by a constant fraction, ensuring truthful participation while remaining competitive with the optimal fair allocation.
Similarly, when optimizing for external objectives like seller revenue under hard budget constraints, Daskalakis et al. in Revenue Maximization and Ex-Post Budget Constraints demonstrated that an efficient 3-approximation algorithm can maximize a mixed-sign virtual welfare objective while strictly respecting individual budget limits.
Finally, fairness constraints often seem to force a massive drop in total societal benefit. Flammini et al. in Fair Division with Social Impact addressed this by modeling items that carry both private value to an agent and a "social impact" value to society. The authors proved that by designing algorithmic frameworks that factor societal contribution into the allocation rule, we can recover a significant portion of potential social value, guaranteeing a bounded approximation of optimal social welfare while strictly satisfying individual EF1 fairness criteria.
Even when perfect welfare and fairness are fundamentally incompatible, Aziz et al. in Achieving Envy-freeness and Equitability with Monetary Transfers showed that introducing minor monetary transfers allows polynomial-time algorithms to smoothly navigate these trade-offs, driving the system into stable, approximately envy-free outcomes.
By shifting the goalposts from exact mathematical perfection to bounded polynomial-time approximations, this field provides the algorithmic tools necessary to deploy provably fair resource allocation policies in real-world computational and economic systems.
Key Foundational Work
Computing good nash equilibria in graphical games (2007) — contributed 1 concept elements to this direction.
A Truthful-in-Expectation Mechanism for the Generalized Assignment Problem (2014) — contributed 1 concept elements to this direction.