The Combinatorial Complexity of Intersectional Fairness Constraints

44 concepts28 papers2 proposals

When algorithmic systems make decisions—whether selecting a committee, ranking job applicants, or distributing ads—ensuring fair representation is a primary goal. If we define fairness along a single axis, such as ensuring a minimum number of female candidates in a selection, the problem is computationally straightforward. You can simply sort candidates within each group and select the top performers until the quota is met.

However, real-world populations are defined by intersecting identities. A person is not merely a single demographic label; they possess a combination of attributes like gender, ethnicity, age, and geographic location. When we attempt to enforce fairness across multiple overlapping categories simultaneously, a seemingly simple optimization problem undergoes a severe phase transition, running into what researchers call a combinatorial explosion and a feasibility wall.

The Core Intuition: Discrete Packages of Traits

To understand why intersectional fairness is difficult, consider how optimization algorithms view individuals. As noted by Jérôme Lang et al. in their work on multi-attribute representation, candidates cannot be broken down into independent variables; instead, they must be treated as discrete packages of traits.

If an algorithm selects a candidate to satisfy an ethnicity quota, that candidate also possesses a specific gender, age, and expertise level. This single choice automatically alters the remaining quotas for all other categories. Because these attributes are inseparable, satisfying a target for one category can inadvertently violate a target for another. The choices become deeply coupled.

Single Attribute (Independent)         Multi-Attribute (Coupled)
[ Candidate A: Female ]                [ Candidate A: Female, Tech, Senior ]
[ Candidate B: Male   ]                [ Candidate B: Male,   Sales, Junior ]
      │                                      │
      ▼                                      ▼
Easy to balance:                       Extremely hard to balance:
Just count and swap.                   Swapping A for B changes 
                                       three counters simultaneously.

This coupling means that as the number of protected attributes increases, the number of distinct subgroups grows exponentially. As Harikrishna Narasimhan et al. explain, defining fairness across overlapping categories leads to an explosion of subgroups, making standard penalty-based or constraint-satisfaction methods struggle to manage the sheer volume of distinct rules.

The Feasibility Wall

The difficulty of intersectional fairness is not just that finding the best or most optimal solution is hard. In many cases, simply determining whether any valid solution exists at all is computationally intractable.

In groundbreaking work on multiwinner voting, L. Elisa Celis et al. identified what is known as the feasibility wall. They proved that when candidates belong to one or two overlapping demographic groups, efficient polynomial-time algorithms can find valid solutions. However, the moment candidates belong to three or more overlapping categories, determining if there is any committee that satisfies all upper and lower representation bounds becomes NP-hard.

This computational barrier changes how we must design fair systems. If an algorithm assumes a feasible solution exists, it will fail entirely when confronted with highly intersectional data. As L. Elisa Celis et al. later demonstrated, optimization algorithms in these multi-dimensional environments must either permit minor deviations from strict fairness bounds or rely on heuristic relaxations to function.

How the Complexity Manifests Across Domains

This combinatorial barrier is not unique to voting; it reappears across almost every major algorithmic domain:

  • Matching Markets: In school choice or job matching, individuals often satisfy multiple diversity criteria simultaneously. Jiehua Chen et al. showed that finding stable matchings under these conditions is $\Sigma^P_2$-complete—placing it on the second level of the polynomial hierarchy—because a single assignment impacts multiple capacity constraints at once. Similarly, Haris Aziz et al. noted that this intersectionality makes it exceptionally difficult to maintain core properties like strategyproofness and stability.
  • Ranking and Retrieval: In search engines and recommendation systems, Ferdinando Fioretto et al. observed that traditional penalty methods fail to scale as intersecting identities increase, leading to severe drops in ranking accuracy. When diversifying outputs for Large Language Models across multiple attributes like genre and language, Thinh On et al. found that finding a feasible distributional fit quickly becomes an NP-hard optimization problem.
  • Influence Maximization: When selecting a seed set of users to spread information through a social network, accounting for intersectionality forces a steep trade-off. Alan Tsang et al. showed that overlapping group memberships lead to more severe utility losses than disjoint structures, while Yuting Feng et al. highlighted the computational impracticality of optimizing models across high-dimensional intersections of traits like age, gender, and geography.

Surmounting the Wall: Why the Solutions Work

To bypass the feasibility wall, computer scientists cannot rely on exact, brute-force optimization. Instead, they exploit specific mathematical structures to design algorithms that balance equity and efficiency.

1. Fixed-Parameter Tractability (FPT)

If the total dataset size ($N$) is massive, but the number of intersecting demographic groups ($k$) is relatively small, we can design algorithms whose exponential complexity is isolated entirely to $k$.

In their work on fair clustering for data summarization, Ameet Gadekar et al. demonstrated that while intersectional clustering is inapproximable in standard polynomial time, fixed-parameter tractable algorithms can find high-quality solutions. By scaling exponentially with the number of groups rather than the dataset size, these algorithms remain highly efficient in practice.

2. Matroid Theory and Structural Relaxations

Many optimization problems can be framed using matroids—mathematical structures that generalize the concept of independence in vector spaces. Flavio Chierichetti et al. showed that while adding upper and lower bounds for multiple groups typically turns polynomial-time problems into NP-hard ones, high-quality fair solutions are often achievable if the underlying constraints conform to specific matroid structures. When the attribute system is organized hierarchically rather than completely independently, the overlap structure simplifies, allowing for polynomial-time solutions (Piotr Faliszewski et al.).

3. Continuous Relaxations and Randomized Rounding

Because discrete choices are what cause the combinatorial lock, a powerful workaround is to temporarily treat choices as continuous fractions. For instance, an algorithm might decide to select "0.4 of Candidate A" and "0.6 of Candidate B" to perfectly satisfy all intersectional proportions in expectation.

Once a fractional solution is found, researchers use techniques like randomized rounding to convert these fractions back into discrete individuals. Sharmila Duppala et al. leveraged this approach to manage fairness across multiple overlapping categories in automated matching systems, providing a provable way to satisfy complex representation bounds without triggering exponential runtime.

By shifting the goal from perfect, rigid constraint satisfaction to bounded approximation and structural relaxation, these frameworks allow modern algorithmic systems to scale, ensuring that fairness protections remain viable even as our definitions of identity become more nuanced and intersectional.

Key Foundational Work

Group Fairness in Multiwinner Voting (2017) — contributed 4 concept elements to this direction.
Ranking with Fairness Constraints (2017) — contributed 2 concept elements to this direction.
Multi-Attribute Proportional Representation (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_intersectional_fairness_scalability_10f74703,
  title = {intersectional fairness scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/intersectional-fairness-scalability/rdr_10f7470323fc4eba8f72eb1ad68a9bb1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_intersectional_fairness_scalability_10f74703_v1,
  title = {intersectional fairness scalability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/intersectional-fairness-scalability/rdr_10f7470323fc4eba8f72eb1ad68a9bb1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake