Research map / Learning theory and algorithms / Fairness
Searching for Unfairness in Algorithms’ Outputs: Novel Tests and Insights
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes quadratic-integer-program tests that audit any partition-producing algorithm's output (outlier detection, clustering, classification, human maps) for count-based and utility-weighted intersectional unfairness, finding fair-by-design methods can increase intersectional unfairness.
Problem
Existing fairness checks are limited to two classes, binary protected statuses, unweighted measures, and a few algorithms, and do not scale to detecting intersectional unfairness across many protected-status combinations.
Approach
A general, algorithm-agnostic search framework formulated as combinatorial optimization (QIP) that finds the simplest conjunction of protected status variables under-represented in one category, with both count-based and utility-weighted (cost-sensitive) variants, so intersectional unfairness is detected without specifying the groups in advance.
Key results
- On CelebA, Fair SVDD yields 48% unfair two-way intersections vs 39% for base SVDD, and 64% vs 49% for three-way intersections.
- Utility-weighted tests on Fair SVDD output find 59% unfair two-way and 78% unfair three-way intersections (vs 37% and 53% for SVDD).
- Fairlet clustering on Adult leaves 2 to 5 unfair intersectional combinations in each remaining PSV set (maximum 8).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the fair-by-design SVDD variant instead of regular SVDD | SVDD on CelebA · CelebA, 2-way intersections (count-based) | unfair intersections: 39% -> 48% | Hurt |
| Apply the fair-by-design SVDD variant instead of regular SVDD | SVDD on CelebA · CelebA, 3-way intersections (count-based) | unfair intersections: 49% -> 64% | Hurt |
| Apply the fair-by-design SVDD variant instead of regular SVDD | SVDD on CelebA · CelebA, 2-way intersections (utility-weighted) | unfair intersections: 37% -> 59% | Hurt |
| Apply the fair-by-design SVDD variant instead of regular SVDD | SVDD on CelebA · CelebA, 3-way intersections (utility-weighted) | unfair intersections: 53% -> 78% | Hurt |
Surprising findings
- Fair-by-design outlier detection increases intersectional unfairness relative to the base SVDD algorithm.
- Fair-by-design clustering satisfies one PSV but leaves intersectional unfairness in the remaining PSVs.
Limitations
- Formulations apply only to algorithms whose decisions induce a set partition of instances.
- Requires expert guidance to choose tolerance values for deciding fairness.
- QIP formulations may be computationally expensive when the number of PSVs is large.
Experimental setup
Datasets: CelebA Adult California congressional district data (ZCTA demographics)
Benchmarks: CelebA Adult
Metrics: percentage of unfair intersections balance utility deviation (20% threshold)
Baselines: Fair SVDD (Zhang and Davidson 2021) SVDD Fairlet clustering (Backurs et al. 2019)
Builds on: Deep SVDD fairlet clustering Chierichetti et al. 2017 balance measure Kearns et al. 2018 subgroup auditing
Closest papers by meaning
- Intersectional Fairness via Mixed-Integer Optimization (NeurIPS 2026 · similarity 0.89)
- Intersectional Unfairness Discovery (ICML 2024 · similarity 0.88)
- LUCID: Exposing Algorithmic Bias through Inverse Design (AAAI 2023 · similarity 0.87)
- Size-adaptive Hypothesis Testing for Fairness (NeurIPS 2025 · similarity 0.85)
- Fairness under Competition (NeurIPS 2025 · similarity 0.85)
- Fairness-aware Anomaly Detection via Fair Projection (NeurIPS 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.