When dividing a pool of resources among multiple participants, we traditionally expect to face a series of harsh trade-offs. If we prioritize strict individual fairness—such as ensuring no participant envies another—we assume we must sacrifice global economic efficiency (Pareto optimality). Similarly, if we try to satisfy multiple distinct definitions of fairness at once, we expect them to conflict.
However, a powerful insight has emerged from recent research in computational social choice: fairness criteria and economic efficiency are not inherently opposed, but are frequently compatible. By leveraging structural alignments between different metrics and designing clever algorithmic mechanisms, it is possible to provide simultaneous fairness and efficiency guarantees.
Why Multiple Fairness Criteria Align
Fairness is not a monolithic concept. Envy-based metrics (like Envy-Freeness up to one good, EF1, or up to any good, EFX) focus on interpersonal comparisons, ensuring no agent prefers another's bundle. Share-based metrics (like Maximin Share, MMS) focus on an absolute baseline, ensuring every agent receives a minimum guaranteed value based on their own valuation.
At first glance, satisfying both types of guarantees simultaneously seems like a double mathematical burden. Yet, they often align because strong envy-based metrics act as natural proxies for share-based metrics. If an allocation ensures that Agent A does not envy Agent B's bundle after removing a single item, it inherently bounds how poorly Agent A can be treated overall.
This proxy effect allows a single algorithmic strategy to hit multiple targets at once:
- Envy-Cycle Elimination as a Multi-Tool: Amanatidis et al. (2020) demonstrated that a single allocation of indivisible goods can simultaneously satisfy EF1 and strong approximations of both EFX and Groupwise Maximin Share (GMMS). By resolving cycles of envy dynamically, the algorithm naturally balances the distribution across both comparative and absolute benchmarks.
- The Power of EFX: Chaudhury et al. (2021) showed that pursuing EFX allocations with minimal unallocated items (charity) automatically yields a high approximation for GMMS. This proves that EFX is a robust proxy metric; solving for it implicitly solves for other strong fairness standards.
- Coexisting Relaxations: Akrami and Rathi (2025) proved that a 2/3 approximation of MMS can be achieved simultaneously with EFX or EF1 guarantees. Similarly, Ashuri (2024) showed that proportionality-based and envy-based relaxations can be satisfied at the same time, removing the need for practitioners to trade off between the two.
To navigate these relationships, researchers like Baklanov et al. (2021) have introduced intermediate hierarchical metrics like "Proportionality up to the maximin item" (PROPm), which bridge the gap between strict envy-free conditions and proportional guarantees, making it easier to prove when and why these simultaneous guarantees exist.
The Geometry of Efficiency and Fairness
Why can individual fairness coexist with global Pareto optimality? The intuition lies in the mathematical landscape of optimization.
When we maximize an objective function like Nash Social Welfare (the geometric mean or product of all agents' utilities), the optimization process naturally pushes the solution away from extreme inequality. Because a product drops to zero if even a single agent receives nothing, maximizing Nash Social Welfare inherently balances the distribution.
Garg et al. (2019) leveraged this geometric property to show that algorithms designed to maximize weighted geometric means of valuations simultaneously satisfy strong individual fairness benchmarks like EF1. The efficiency objective itself acts as a fairness engine.
In continuous settings, such as dividing a cake, Brams et al. (2012) showed that maximizing social welfare within the constraints of fairness (like envy-freeness or equitability) guarantees Pareto optimality. For discrete matching problems, Bonchi and García-Soriano (2020) demonstrated a "zero price of fairness," proving that individual maxmin fairness can be achieved without reducing the total number of matches simply by selecting an equitable solution from the set of all maximum-size configurations.
Smoothing Out Indivisibility
The primary obstacle to simultaneous guarantees is the discrete nature of indivisible goods (e.g., houses, cars). You cannot cut a car in half to eliminate envy, which creates mathematical friction. However, this friction can be smoothed out by introducing slight structural regularities, minor relaxations, or hybrid resource pools.
Structural Regularity
When items share uniform characteristics, the potential for perceived inequality drops sharply. Khan et al. (2023) showed that when items have uniform size, value, or density, a simple greedy allocation algorithm naturally improves its fairness guarantee from EF2 to EF1. Similarly, Ghosal et al. (2025) proved that if a majority of agents share identical preferences, complete EFX allocations are guaranteed to exist, showing that fairness is highly resilient to limited agent heterogeneity.
Hybrid Resource Pools
When divisible resources (like money or land) are mixed with indivisible items, they act as a buffer to absorb envy. Bei et al. (2020) introduced Envy-Freeness for Mixed goods (EFM), proving that a unified fairness criterion combining strict envy-freeness for divisible resources and relaxed envy-freeness for indivisible items is always guaranteed to exist. In a similar vein, Lu et al. (2024) extended multiwinner voting and cake sharing into a unified "mixed goods" framework, proving that proportional representation is mathematically guaranteed when discrete and continuous resources are managed together.
The Challenge of Chores
The compatibility of fairness and efficiency becomes significantly harder when distributing chores—items or tasks that carry negative utility. In a world of goods, agents want more; in a world of chores, agents want less. This inversion complicates traditional market clearing and envy-elimination strategies.
To restore compatibility in negative-utility settings, researchers introduce minor structural flexibility into the allocation mechanism:
- Allowing Surplus: Akrami et al. (2023) showed that by allowing a small surplus of duplicated tasks (up to $n-1$), an algorithm can achieve both EF1 and fractional Pareto optimality simultaneously in polynomial time.
- Information Asymmetry: Hosseini et al. (2023) introduced the concept of "dubious chores"—tasks that appear costly to an observer but cost nothing to the person performing them. By leveraging this asymmetry, they proved that perceived envy-freeness can coexist perfectly with fractional Pareto optimality.
- Market Equilibria: By framing chore division through economic frameworks like Earning Restricted (ER) equilibria, Garg et al. (2024) proved that Pareto optimality can coexist with a constant-factor relaxation of EFX (specifically, 4-EFX) for chore division.
Whether dealing with subjective mixed utilities where an item is a good to one person and a chore to another (Aziz et al. (2019)), or mapping the formal hierarchy between envy-freeness levels in multi-copy environments (Gafni et al. (2023)), the underlying conclusion remains the same. By understanding the structural relationships between fairness metrics and economic objectives, system designers do not have to choose between an efficient system and a fair one—they can design for both simultaneously.
Key Foundational Work
Fair Allocation of Indivisible Goods and Chores (2019) — contributed 1 concept elements to this direction.
Approximating Nash Social Welfare under Submodular Valuations through (Un)Matchings (2019) — contributed 1 concept elements to this direction.
Improving Nash Social Welfare Approximations (2019) — contributed 1 concept elements to this direction.