When dividing resources among individuals, two goals naturally conflict: fairness (ensuring no one feels shortchanged) and efficiency (ensuring no resources are wasted). In a world where resources are perfectly divisible—like water or land—we can achieve both simultaneously. By setting up an artificial market where everyone starts with an equal budget, prices naturally adjust until the market clears. The resulting allocation is both envy-free and Pareto optimal.
However, when resources are indivisible—such as houses, cars, or specific shifts—this elegant solution shatters. You cannot give someone half a car to balance a budget. As Bouveret et al. demonstrated, determining whether an allocation exists that is both strictly envy-free and Pareto optimal is computationally intractable ($\Sigma^p_2$-complete).
To circumvent this impossibility, a rich body of research explores how relaxing our definitions of fairness can restore compatibility with economic efficiency. The goal is to design mechanisms that guarantee both properties simultaneously, ensuring that making an allocation fair does not require destroying its overall social value.
The Indivisibility Barrier and Relaxed Fairness
To find a bridge between fairness and efficiency, we must allow for slight, bounded disparities. The most prominent relaxation is Envy-Freeness up to One Item (EF1). Under EF1, Agent $A$ might envy Agent $B$, but if we hypothetically remove just one item from $B$’s bundle, $A$’s envy vanishes. A stricter variant is Envy-Freeness up to Any Item (EFX), where envy vanishes upon the removal of any item from the envied bundle.
Strict Envy-Freeness: [Agent A's Bundle] ≥ [Agent B's Bundle]
EF1 Relaxation: [Agent A's Bundle] ≥ [Agent B's Bundle] - [Best Item]
EFX Relaxation: [Agent A's Bundle] ≥ [Agent B's Bundle] - [Worst Item]
These relaxations provide the "breathing room" needed to pursue Pareto optimality (PO)—the requirement that no other allocation can make someone better off without making someone else worse off. Without this flexibility, an efficiency-seeking algorithm would be forced to withhold an item entirely if giving it to the person who values it most would trigger exact envy in another agent. By allowing a single-item discrepancy, the algorithm can award the item to its most productive user, maximizing efficiency while keeping unfairness strictly bounded.
The Mechanics of Compatibility: Graphs and Markets
How do we systematically find allocations that sit at the intersection of relaxed fairness and Pareto efficiency? Two primary algorithmic frameworks make this possible: Envy Graphs and Market Equilibria.
1. Envy Graphs and Cycle Elimination
Imagine a directed graph where every node is an agent, and a directed edge points from Agent $A$ to Agent $B$ if $A$ envies $B$. If this graph contains a cycle (e.g., $A$ envies $B$, $B$ envies $C$, and $C$ envies $A$), we can perform a cycle elimination trade.
We shift the bundles along the cycle: $A$ gets $B$’s bundle, $B$ gets $C$’s, and $C$ gets $A$’s. Because each agent receives a bundle they strictly preferred over their own, the total welfare increases, and the number of envies decreases. As shown by Aziz et al., managing these envy graphs dynamically allows algorithms to maintain the EF1 property while continuously driving the allocation toward the Pareto frontier.
2. Market-Based Pricing and Bounded Budgets
The most powerful intuition for achieving fractional Pareto optimality (fPO)—where even randomized or fractional shares of the discrete items cannot be mutually improved—comes from competitive market design.
Consider a Fisher Market, where items are given prices, and agents spend an artificial currency to buy their favorite bundles. The First Welfare Theorem guarantees that any market-clearing equilibrium is Pareto optimal. To ensure fairness, we want agents to have equal budgets. However, because items are indivisible, equal budgets might leave the market uncleared (e.g., a fraction of an item remains unbought because no one has the exact change left).
To fix this, algorithms dynamically adjust both prices and agent budgets. By allowing budgets to vary slightly based on the items agents receive, the market can clear perfectly. Murhekar et al. leveraged this pseudo-polynomial market-clearing approach to construct allocations that are simultaneously EF1 and fractionally Pareto optimal. The budget disparities are strictly bounded by the price of a single item, which directly translates to the EF1 guarantee. For chores, the authors in Garg et al. introduced Earning Restricted Equilibria to bound budgets from below, yielding constant-factor approximations of EFX alongside Pareto efficiency.
The Complication of Negative Utility (Chores)
When the items to be distributed are chores (tasks carrying negative utility) or a mixed manna of both goods and chores, the compatibility landscape changes dramatically.
Goods Allocation: Agents pull items toward themselves. Unallocated items are desirable.
Chore Allocation: Agents push items away. Unallocated items are toxic.
With goods, a standard round-robin draft naturally preserves EF1: because you choose your favorite available item when it is your turn, you will never envy another agent by more than your first pick. With chores, this logic flips. If agents take turns picking chores, the agent who picks first is forced to take their least-disliked chore, but as the pool empties, subsequent agents are left with catastrophic tasks.
This asymmetry makes simultaneous fairness and efficiency for chores exceptionally difficult. For instance, Li et al. proved a sobering "zero-efficiency" result: algorithmic transformations that successfully map truthful, fair mechanisms from goods to chores often completely destroy Pareto optimality when scaled to more than two agents.
To overcome this, researchers isolate structured environments. Aziz et al. focused on scenarios where chores fall into just two categories (e.g., cleaning vs. cooking), proving that polynomial-time algorithms can find EF1/EFX and Pareto optimal outcomes by balancing the ratios of these task types across agents. Similarly, Murhekar designed specialized algorithms that exploit specific preference structures to guarantee that chore allocations do not trap agents in highly inefficient, un-tradeable assignments.
The Frontier: Constraints and Mixed Environments
Real-world resource allocation rarely happens in a vacuum; it is frequently bound by physical or operational constraints.
- Mixed Manna: When an allocation contains both goods and chores, an agent's net utility can be positive, negative, or zero. Aziz et al. and Mehta et al. demonstrated that combining proportionality relaxations (like PROP1 or PropMX) with Pareto optimality is achievable, but requires algorithms to carefully transition between "pulling" goods and "pushing" chores depending on an agent's current net utility.
- Assignment Constraints: In many practical settings, items have agent-specific sizes, or agents face strict capacity limits. Under these Generalized Assignment Constraints, Barman et al. noted that while we can guarantee feasible envy-freeness, ensuring Pareto optimality remains an open challenge. The rigid boundaries of the constraints prevent the smooth budget and price adjustments that market-clearing mechanisms rely on.
Ultimately, the research direction demonstrates that fairness and efficiency are not fundamentally incompatible in discrete settings. Instead, their compatibility depends on finding the right mathematical relaxation of fairness—such as EF1 or PROPm—and using market-inspired pricing or graph-theoretic trades to navigate the discrete space toward the Pareto frontier.
Key Foundational Work
Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity (2005) — contributed 1 concept elements to this direction.
An Efficient Protocol for Negotiation over Combinatorial Domains with Incomplete Information (2011) — contributed 1 concept elements to this direction.