# Fairness Auditing: Lower Bounds on Company Manipulation

arXiv: https://arxiv.org/abs/2608.00568 · HTML: https://mlsanity.com/paper/2608.00568/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 22 references that are in the map.
- First posted on arXiv 1 Aug 2026.

## Builds on (most cited first, 8 of 8)

- [A Reductions Approach to Fair Classification](https://mlsanity.com/paper/1803.02453/) (2018)
- [Black-Box Access is Insufficient for Rigorous AI Audits](https://mlsanity.com/paper/2401.14446/) (2024)
- [Fairness and Bias in Algorithmic Hiring: a Multidisciplinary Survey](https://mlsanity.com/paper/2309.13933/) (2023)
- [Active Fairness Auditing](https://mlsanity.com/paper/2206.08450/) (2022)
- [Auditing Fairness by Betting](https://mlsanity.com/paper/2305.17570/) (2023)
- [Faking Fairness via Stealthily Biased Sampling](https://mlsanity.com/paper/1901.08291/) (2019)
- [Robust ML Auditing using Prior Knowledge](https://mlsanity.com/paper/2505.04796/) (2025)
- [Under manipulations, are some AI models harder to audit?](https://mlsanity.com/paper/2402.09043/) (2024)

## Abstract (arXiv)

Fairness audits are increasingly mandated in high-stakes applications such as hiring, lending, and automated decision-making. Recent work has established fundamental impossibility results for black-box fairness auditing, showing that sufficiently expressive models can evade any auditing strategy. We complement these results by quantifying the extent of unavoidable post-audit manipulation under finite audit resources. We formulate fairness auditing as a min-max optimization between a computationally unbounded company and a budget-constrained auditor. We study two auditing regimes: (i) a budgeted auditor that certifies fairness using a fixed-size audit set, and (ii) a budgeted α-tolerant auditor that additionally requires the audit set to estimate the fairness of the certified model within an α approximation. For both settings, we derive explicit lower bounds on the worst-case post-audit demographic parity deviation as functions of the audit budget, group imbalance, and fairness tolerance. Finally, we empirically illustrate these theoretical limits using simple audit-set construction heuristics with linear and neural network classifiers. Our results demonstrate that increasing audit resources reduces, but does not eliminate, the scope for post-audit manipulation, highlighting fundamental limitations of finite-budget fairness certification.