The Combinatorial Barriers to Verifying Fairness

28 concepts18 papers1 proposal

When we design algorithms to distribute resources, select committees, or make automated decisions, we want to ensure the outcomes are fair. Intuitively, fairness means that no group of people is systematically ignored or underrepresented.

However, a profound computational challenge lurks beneath this goal. Across voting theory, machine learning, and network analysis, researchers have uncovered a striking asymmetry: it is often much easier to find a fair solution than it is to prove that a given solution is fair.

This difficulty stems from a combinatorial explosion. To verify that an outcome is fair, an auditor must typically prove a negative—that no cohesive subgroup of individuals has been left unsatisfied. Because the number of potential subgroups grows exponentially with the size of the population, checking every possibility quickly becomes computationally intractable.

The Asymmetry of Proportional Representation

The tension between finding and verifying fairness is most clearly visible in multi-winner committee elections. Suppose a group of voters uses approval ballots (checking boxes for candidates they like) to elect a fixed-size committee. We want the committee to satisfy Proportional Justified Representation (PJR) or Extended Justified Representation (EJR)—axioms ensuring that if a large enough cohesive group of voters agrees on a set of candidates, they are guaranteed a proportional number of representatives.

In On the Complexity of Extended and Proportional Justified Representation, Haris Aziz et al. demonstrated that verifying whether an arbitrary committee satisfies PJR or EJR is coNP-complete. To understand why, imagine trying to audit an election result. To prove the committee is unfair, you only need to find one large group of voters who agree on candidates but received no representation. Finding this single "aggrieved" group is an NP-complete search problem. Consequently, proving that no such group exists—the very definition of verification—is coNP-complete.

Remarkably, Haris Aziz et al. also showed that we can construct a committee satisfying EJR in polynomial time using algorithmic rules like Phragmén's or the Method of Equal Shares. Barton E. Lee echoed this asymmetry in The expanding approvals rule: improving proportional representation and monotonicity, noting that while the Expanding Approvals Rule efficiently generates proportional outcomes, formal validation of an arbitrary outcome remains computationally intractable.

This creates a paradox for digital governance and auditing: we can run a trusted algorithm to get a fair result, but we cannot independently audit an untrusted election result without facing an exponential wall.

Constructing a Fair Committee:
[Voter Preferences] ---> (Polynomial-Time Algorithm) ---> [Fair Committee] (Easy)

Auditing an Arbitrary Committee:
[Committee] ---> Check all 2^N possible voter coalitions ---> Is anyone underrepresented? (coNP-complete)

This intractability persists even when we try to quantify how fair a committee is. Łukasz Janeczko et al. evaluated the "Proportionality Degree" (PD) in The Complexity of Proportionality Degree in Committee Elections. They found that moving from a qualitative check to a quantitative metric does not alleviate the burden; ensuring that no cohesive group's satisfaction falls below a specific numerical threshold remains coNP-complete.

The Combinatorial Explosion Beyond Voting

This verification bottleneck is not unique to voting; it reappears wherever fairness is defined relative to subsets of agents.

Matching Markets

In matching markets—such as assigning students to schools or workers to shifts—we might want to select a portfolio of multiple fair matchings. As Markus Brill et al. showed in Proportional representation in matching markets: selecting multiple matchings under dichotomous preferences, verifying PJR in this context is also coNP-complete. The auditor must search through an exponential space of alternative matchings to ensure no group of agents could have been better represented.

Clustering

In unsupervised learning, "proportional fairness" dictates that no group of data points should be forced into a distant cluster if they are large enough to justify their own cluster center. In Proportional Fairness in Non-Centroid Clustering, Ioannis Caragiannis et al. proved that evaluating whether a clustering configuration satisfies these representation rights is computationally prohibitive. The exponential search space over all possible subsets of agents makes auditing existing clustering partitions incredibly difficult.

Graph Theory

When discovering communities or cliques in social networks, we may want to ensure that the discovered groups represent diverse node attributes (e.g., balanced gender or demographic representation). Minjia Pan et al. explored this in Fairness-aware Maximal Clique Enumeration, demonstrating that verifying the maximality of a subgraph under relative attribute proportions introduces severe computational overhead, requiring sophisticated pruning heuristics to remain scalable.

Subgroup and Individual Fairness in Machine Learning

When we move from discrete algorithms to statistical machine learning, the combinatorial explosion shifts from "coalitions of voters" to "subgroups of features" or "pairs of inputs."

Subgroup Auditing

To ensure a predictive model is fair, we often want to verify subgroup fairness—meaning the model performs equally well across overlapping demographic intersections (e.g., Black women, elderly veterans). In Polynomial time auditing of statistical subgroup fairness for Gaussian data, Daniel Hsu et al. demonstrated that auditing general halfspace subgroups is computationally intractable even under perfectly well-behaved Gaussian data distributions. They proved that merely deciding whether a biased subgroup exists is just as hard as constructively identifying it, showing that the hardness of fairness auditing is a fundamental geometric property rather than a consequence of messy data.

Individual Fairness

Instead of looking at groups, individual fairness requires that a model treats similar individuals similarly. To verify this in a deep neural network, you must check that for every possible pair of similar inputs, the network's outputs remain close. As Arya Fayyazi et al. noted in Efficient Counterexample-Guided Fairness Verification and Repair of Neural Networks Using Satisfiability Modulo Convex Programming, this creates a massive search space of potential input pairs, leading to a combinatorial explosion that breaks standard verification tools.

However, this hardness depends heavily on the scope of the audit. In On Testing for Discrimination Using Causal Models, Hana Chockler et al. observed that while proving a system is fair across all possible inputs is globally intractable, verifying fairness for a specific individual case is highly feasible. Because the number of sensitive attributes (like race or gender) for a single person is small, an auditor can efficiently permute those attributes to test for local discrimination.

Designing Around Intractability

Because verifying traditional fairness axioms is so difficult, researchers have developed three primary strategies to make auditing practical: market-based certificates, robust polynomial axioms, and structural restrictions.

1. Market-Based Certificates

Instead of forcing an auditor to search for aggrieved coalitions, what if the algorithm provided a "certificate" proving its own fairness? Dominik Peters et al. proposed this in Market-Based Explanations of Collective Decisions by introducing Stable Priceability.

The outcome is modeled as a virtual market where voters spend a fixed budget to "buy" candidates. If a price equilibrium exists, the market prices themselves serve as an explanation. An auditor does not need to check every voter subset; they only need to verify the linear programming constraints of the market prices, turning an NP-hard verification problem into a polynomial-time check.

2. Verifiable Axioms

Another approach is to redesign the fairness axioms themselves so they are inherently easier to check. In Robust and Verifiable Proportionality Axioms for Multiwinner Voting, Jannik Peters et al. introduced new, "robust" proportionality standards. Unlike EJR or PJR, which require checking arbitrary, loosely aligned voter coalitions, these robust axioms focus on structured, easily identifiable groups. As a result, compliance can be verified in polynomial time, and outcomes can be generated using a simple greedy algorithm.

3. Structural Restrictions

Sometimes, the complexity can be tamed by restricting the domain of the problem. In Approval-Based Apportionment (and its extended analysis in Approval-based apportionment (2024)), Markus Brill et al. studied a middle ground between party-list systems and open candidate elections. By forcing voter preferences into this structured framework, they proved that strong fairness guarantees like core stability—which are normally mathematically elusive or intractable—become achievable and verifiable.

When structural workarounds are unavailable, practitioners must rely on heavy computational machinery. Piotr Faliszewski et al. demonstrated in An Experimental View on Committees Providing Justified Representation that while JR verification is coNP-complete, Integer Linear Programming (ILP) solvers can bridge the gap in practice, allowing real-world election results to be audited efficiently despite the theoretical worst-case complexity.

Key Foundational Work

Justified representation in approval-based committee voting (2017) — contributed 2 concept elements to this direction.
On the Complexity of Extended and Proportional Justified Representation (2018) — contributed 2 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_fairness_verification_complexity_2b237049,
  title = {fairness verification complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fairness-verification-complexity/rdr_2b237049638148f49bf8383b26dc66b3},
  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_fairness_verification_complexity_2b237049_v1,
  title = {fairness verification complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fairness-verification-complexity/rdr_2b237049638148f49bf8383b26dc66b3/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