When designing algorithms to distribute resources or group data fairly, computer scientists frequently encounter a frustrating trilemma. First, there is the existence threshold: the maximum level of fairness that is mathematically guaranteed to exist in any given scenario. Second, there is the algorithmic bound: the fairness guarantee that our best polynomial-time algorithms can actually secure. Third, there is the hardness bound: the limit beyond which finding a fair solution becomes provably NP-hard.
In a perfect world, our algorithms would achieve the exact fairness guarantees known to exist, or they would hit a clear wall of computational hardness. However, in many core problems within algorithmic fairness, there remains a significant chasm between these boundaries. This chasm is known as the approximation-existence gap (or approximation-hardness gap).
To understand why this gap exists, why it persists, and how researchers are attempting to close it, we must look at how fairness constraints fundamentally alter the landscape of optimization.
The Anatomy of the Gap
To build intuition, consider the classic problem of dividing a set of indivisible items among a group of people. We might want to achieve Maximin Share (MMS) fairness, where every agent receives a bundle worth at least their proportional share if they were to divide the items into $n$ bundles themselves.
Mathematically, we can often prove that a highly fair allocation is guaranteed to exist. Yet, when we try to compute it, we run into a series of gaps:
[ Algorithmic Bound ] -------- ( The Gap ) -------- [ Existence / Hardness Bound ]
What we can compute What is guaranteed to exist
in polynomial time or provably hard to beat
If an algorithm guarantees a $3/4$-approximation of MMS, it means every agent gets at least $75\%$ of their maximin share. If a theoretical proof shows that a $1$-approximation (perfect fairness) always exists, the distance between $3/4$ and $1$ is the approximation-existence gap.
This gap represents our current ignorance: is it missing because our algorithms aren't clever enough, or because there is an undiscovered computational barrier preventing us from reaching perfect fairness in polynomial time?
The Frontier in Fair Division
The tension between existence and constructibility is vividly illustrated in the allocation of indivisible goods and chores.
Breaking Historical Barriers
For years, algorithms dividing indivisible goods could not break past certain approximation thresholds for strong fairness criteria like Envy-Freeness up to any good (EFX) or Groupwise Maximin Share (GMMS). As shown by Georgios Amanatidis et al. in Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination, introducing novel envy-cycle elimination techniques allowed researchers to beat the long-standing $1/2$ barrier, pushing guarantees to roughly $0.618$. However, the authors noted that it remains unknown whether these specific constants represent the absolute theoretical upper bound for polynomial-time solutions.
A similar breakthrough occurred for MMS allocations. For a long time, algorithms were stuck at a $3/4$ approximation factor. Hannaneh Akrami and Jugal Garg bypassed this algorithmic wall in Breaking the 3/4 Barrier for Approximate Maximin Share by introducing highly granular agent categorizations. Yet, as established by Hannaneh Akrami et al. in Simplification and Improvement of MMS Approximation, a persistent gap still remains between these incremental algorithmic improvements and the theoretical limits of fair allocation existence.
Goods vs. Chores
When we shift from dividing pleasant goods to allocating "chores" (items with negative utility, like tasks or liabilities), the approximation gaps often widen significantly. In Weighted Maxmin Fair Share Allocation of Indivisible Chores, Haris Aziz et al. demonstrated a massive distance between their $(4 + \epsilon)$-approximation algorithm and the proven $4/3$ lower bound for asymmetric agents.
To circumvent these stubborn numerical gaps, researchers have altered the problem framing entirely. Hadi Hosseini et al. in Ordinal Maximin Share Approximation for Goods proposed shifting from cardinal values to ordinal rankings. By evaluating fairness based on how agents rank bundles rather than exact numerical utilities, they proved that robust guarantees always exist and can be computed efficiently. Even so, a gap remains between the specific partition bounds we can construct in polynomial time and those known to exist abstractly.
The Gap in Fair Clustering
The approximation-existence gap is not unique to resource allocation; it manifests identically when fairness constraints are injected into traditional machine learning tasks like clustering.
In standard $k$-center clustering, the goal is to choose $k$ center points such that the maximum distance from any data point to its nearest center is minimized. Without fairness constraints, a tight $2$-approximation algorithm is easily achievable, and beating it is provably NP-hard.
But what happens when we demand that each cluster contain a fair, balanced representation of protected demographic groups?
Standard k-Center: [ 2.0 Approximation ] (Tight Hardness Bound)
|
Fairness Constraint Added
v
Fair k-Center: [ 3.0 Approximation ] -------- ( Unresolved Gap ) -------- [ 2.0 Lower Bound ]
As initiated by Flavio Chierichetti et al. in Fair Clustering Through Fairlets, ensuring the "disparate impact" doctrine requires decomposing data into small, balanced groups called fairlets. This decomposition step introduces a performance penalty, leaving a noticeable gap between the theoretical lower bounds of the clustering objective and the approximation ratios achieved.
When extending this to multiple overlapping demographic groups, Xinrui Jia et al. in Fair colorful k-center clustering achieved a $3$-approximation algorithm. This leaves an open foundational question: does the jump from a factor of $2$ to a factor of $3$ represent an intrinsic, unavoidable mathematical cost of fairness, or is it an artifact of our current algorithmic limitations?
Why the Gap Persists
Why can't standard optimization tools easily close these gaps? The answer lies in how fairness constraints interact with combinatorial structures.
In unconstrained optimization, algorithms often exploit smooth, well-behaved mathematical properties like linearity or submodularity (the law of diminishing returns). For example, consider the Submodular Santa Claus problem, where the goal is to allocate items to agents with submodular utility functions such that the least-happy agent is as well-off as possible.
In The Submodular Santa Claus Problem, Etienne Bamas et al. designed a sophisticated $O(n^\epsilon)$-approximation algorithm using recursive linear programming. While this was a massive theoretical breakthrough, a glaring discrepancy remains between this polynomial upper bound and known hardness results.
Fairness constraints introduce discrete, non-linear bottlenecks. In traditional optimization, if an algorithm makes a minor error on a few elements, the overall objective function changes very little. But fairness is defined by the extremes—the most envious agent, the least represented group, or the worst-served cluster. A single poor assignment can completely violate a fairness guarantee.
Because fairness forces us to optimize for the worst-case individual or group outcome simultaneously, standard relaxation techniques (such as rounding a fractional linear programming solution) lose an immense amount of precision. The resulting approximations remain loose, preventing us from reaching the theoretical boundaries of what is mathematically possible. Closing this gap remains one of the central challenges in modern algorithmic social choice.
Key Foundational Work
Optimal Proportional Cake Cutting with Connected Pieces (2012) — contributed 1 concept elements to this direction.
Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation (2016) — contributed 1 concept elements to this direction.
The complexity of fairness through equilibrium (2016) — contributed 1 concept elements to this direction.