Paper deep dive
Fairness Auditing: Lower Bounds on Company Manipulation
Rachit Verma, Padala Manisha, Sujit Gujar
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/4/2026, 4:40:48 AM
Summary
This paper investigates the fundamental limits of fairness auditing by modeling the interaction between a budget-constrained auditor and a strategic company as a min-max optimization problem. The authors derive explicit lower bounds on the worst-case post-audit demographic parity deviation, demonstrating that finite audit resources inevitably allow for some degree of strategic manipulation. Two auditing regimes are analyzed: a budgeted auditor using a fixed-size audit set, and an alpha-tolerant auditor that requires the audit set to estimate fairness within a specified tolerance. Theoretical bounds are validated empirically using linear and neural network classifiers on benchmark datasets, showing that while increased audit resources reduce manipulation, they do not eliminate it.
Entities (10)
Relation Signals (7)
Fairness Auditing → modelsas → Min-Max Optimization
confidence 95% · We formulate fairness auditing as a min-max optimization between a computationally unbounded company and a budget-constrained auditor.
Budgeted Auditor → constrainedby → Audit Budget
confidence 93% · The auditor is restricted only by the audit budget, S B ={S ⊆ D : |S|≤ B}.
Alpha-Tolerant Auditor → constrainedby → Fairness Tolerance
confidence 93% · the audit set must estimate the fairness of the certified classifier within an additive tolerance α
Demographic Parity → measuredby → Fairness Auditing
confidence 92% · We measure fairness using the empirical Demographic Parity (DP) violation.
Audit Budget → influences → Post-Audit Manipulation
confidence 90% · increasing audit resources reduces, but does not eliminate, the scope for post-audit manipulation
Group Imbalance → influences → Post-Audit Manipulation
confidence 88% · derive explicit lower bounds on the worst-case post-audit demographic parity deviation as functions of the audit budget, group imbalance, and fairness tolerance
RASC → usedfor → Audit Set Construction
confidence 85% · We instantiate the audit constraints using a simple audit-set construction heuristic (RASC).
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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 {\alpha}-tolerant auditor that additionally requires the audit set to estimate the fairness of the certified model within an {\alpha} 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.
Tags
Links
- Source: https://arxiv.org/abs/2608.00568v1
- Canonical: https://arxiv.org/abs/2608.00568v1
Trouble viewing inline? Open PDF directly →
Full Text
43,428 characters extracted from source content.
Expand or collapse full text
FAIRNESS AUDITING: LOWER BOUNDS ON COMPANY MANIPULATION Rachit Verma Indian Institute of Technology Gandhinagar Padala Manisha Indian Institute of Technology Gandhinagar Sujit Gujar International Institute of Information Technology Hyderabad August 4, 2026 ABSTRACT 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 (i) 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. 1 Introduction Machine learning (ML) models are increasingly deployed in high-stakes applications such as hiring, lending, and criminal justice, where concerns about algorithmic fairness have motivated regulations requiring bias assessments before deployment [2,12,4,10,18]. Consequently, fairness auditing has emerged as an important mechanism for certifying that deployed models satisfy prescribed fairness criteria. A fundamental challenge, however, is that fairness audits are inherently resource constrained. Auditors typically certify a model using only a limited number of queries or samples, while the deployed model itself remains inaccessible. This creates opportunities for a strategic company to present a model that passes the audit while deploying a different model that agrees with the audited model only on the inspected samples (Figure 1). Recent work has formalized this setting in the black-box auditing framework [21,15,5]. In particular, [15] proves that for sufficiently expressive hypothesis classes, no black-box auditing strategy can outperform uniform random sampling. These results establish that strategic manipulation is fundamentally unavoidable. However, they leave open a complementary quantitative question: Given a finite audit budget, how much post-audit unfairness can a strategic company always guaran- tee? In this paper, we study this question by modeling fairness auditing as a min-max optimization between a computationally unbounded company and a budget-constrained auditor. Rather than proposing a new auditing algorithm, we characterize arXiv:2608.00568v1 [cs.LG] 1 Aug 2026 A PREPRINT - AUGUST 4, 2026 Feature 1 Feature 2 h h ′ h ′ △ △ △ △ ▲ ▲ Consider the set of pointsE. The red circles belong to the sensitive group0and the blue triangles belong to the sensitive group1. In this case, the company starts with the classifierh, and the auditor chooses the points highlighted in yellow as the auditing set. Points that are visually filled with color denote instances assigned a positive label, whereas points represented by outlines indicate instances assigned a negative label. Clearly,∆(E,h) =| 4 6 − 2 6 | = 1 3 . The company then changes its classifier toh ′ , with ∆(E,h ′ ) =| 5 6 − 1 6 | = 2 3 while being consistent with the audit set, achieving its goal of deviation. The company cannot deviate toh ′ since it will violate consistency with the auditing set. Figure 1: Analysis of classifier deviations under auditing sets. the limits of fairness certification under finite audit resources. We consider two natural auditing regimes. In the first, the auditor is restricted only by the size of the audit set. In the second, the auditor must additionally ensure that the certified fairness estimate approximates the fairness of the audited model within an additive tolerance α. Our main contribution is an explicit characterization of the unavoidable post-audit demographic parity deviation under these audit constraints. For a budget-constrained auditor, Theorem 1 derives a lower bound on the post-audit demographic parity deviation as a function of the audit budget and group imbalance. We further extend this analysis to anα-tolerant auditor in Theorem 2, where the auditor must additionally certify the fairness of the audited model within an additive tolerance. Together, these results complement existing impossibility results by making the dependence on finite audit resources explicit and providing quantitative guarantees on what fairness audits can certify. Finally, we empirically illustrate these theoretical limits using linear and neural network classifiers. We instantiate the audit constraints using a simple audit-set construction heuristic (Algorithm 1) and compare against random auditing. The experiments are intended to illustrate the theoretical trends rather than introduce a new auditing algorithm. Consistent with our analysis, increasing the audit budget and tightening the fairness tolerance reduce, but do not eliminate, the scope for post-audit manipulation. Related Work. Strategic manipulation in fairness auditing was introduced by [21], who formalized manipulation-proof auditing and showed that a company can present a compliant model during an audit while deploying a different model afterward. Subsequent work showed that private auditor priors can mitigate such manipulation under certain conditions, whereas public priors remain vulnerable [5]. Most closely related to our work, [15] established fundamental impossibility results for black-box fairness auditing, proving that for sufficiently expressive hypothesis classes no auditing strategy can outperform uniform random sampling. More broadly, limited access has also been identified as a fundamental obstacle in AI safety evaluations [7]. Our work complements these results by quantifying the extent of unavoidable post-audit manipulation under finite audit budgets, providing explicit lower bounds that depend on the audit budget, group imbalance, and fairness tolerance. Several other works study complementary forms of audit manipulation, including biased sampling [13], statistical fairwashing [19], auditing with external datasets [8], and practical challenges in real-world bias audits [14,20]. In contrast, we focus on the strategic manipulation of the deployed model itself and characterize the limits of fairness certification under finite audit resources. 2 Preliminaries In this section, we define the major notations and definitions formally. 2.1 Classification Setup LetD =(x i ,a i ,y i ) n i=1 be a dataset, wherex i ∈X ⊂R d denotes the feature vector,a i ∈0, 1the binary sensitive attribute, and y i ∈0, 1 the label. A binary classifier h :X →0, 1 predicts ˆy i = h(x i ). Demographic Parity. We measure fairness using the empirical Demographic Parity (DP) violation [11]. For any subset of samples S ⊆ D, the DP violation of a classifier h is defined as 2 A PREPRINT - AUGUST 4, 2026 ∆(S,h) = P (x i ,a i )∈S h(x i )a i P a i ∈S a i − P (x i ,a i )∈S h(x i )(1− a i ) P a i ∈S (1− a i ) .(1) A classifier satisfies demographic parity on S if ∆(S,h) = 0. When the subset is the entire dataset, we simply write ∆(h) := ∆(D,h). 2.2 Auditing Setup A company owns a proprietary classifierh ⋆ that must be certified before deployment by an external auditor. The auditor selects an audit setS ⊆ Dof size at mostB, observes the predictions ofh ⋆ onS, and estimates its demographic parity violation ∆(S,h ⋆ ). After certification, the company may deploy a classifierh ′ . To remain consistent with the audit, the deployed classifier must satisfy h ′ (x) = h ⋆ (x), ∀x∈ S, while it may differ arbitrarily outside the audit set (Figure 1). Following the worst-case analysis of prior work [15], we assume the company has unrestricted representational capacity and may choose any classifier satisfying the above consistency constraint. This assumption is motivated by the ability of over-parameterized models to memorize arbitrary labelings [22]. Group-wise notation. For the audited classifier h ⋆ , let X ij =(x,a,y)∈ D : a = i, h ⋆ (x) = j, where i,j ∈0, 1, and denote x ij =|X ij |. The corresponding group sizes are s 0 = x 00 + x 01 , s 1 = x 10 + x 11 , and, without loss of generality, we assume group0is privileged. Throughout the paper,N = x 00 +x 11 denotes the total number of samples whose labels can increase the demographic parity violation if manipulated. Under this convention, ∆(h ⋆ ) = x 01 s 0 − x 11 s 1 , and we write s max = max(s 0 ,s 1 ). 3 Formulation for Worst-case Analysis We formulate fairness auditing as a two-player min-max optimization between a budget-constrained auditor and a strategic company. The auditor first selects an audit set subject to its certification constraints, after which the company deploys a classifier consistent with the audit while maximizing demographic parity (DP) violation. The auditor operates under one of the following audit models. • Budgeted Audit. The auditor is restricted only by the audit budget, S B =S ⊆ D : |S|≤ B.(2) • Budgetedα-Tolerant Audit. In addition to the budget constraint, the audit set must estimate the fairness of the certified classifier within an additive tolerance α, S B,α =S ⊆ D :|S|≤ B, |∆(S,h ⋆ )− ∆(h ⋆ )|≤ α.(3) Feasible Classifiers. For a certified classifier h ⋆ and audit set S, define H S,h ⋆ =h∈H : h(x) = h ⋆ (x), ∀x∈ S, the set of classifiers that are indistinguishable from h ⋆ on the audited samples. 3 A PREPRINT - AUGUST 4, 2026 Company Objective. The company seeks to maximize post-audit demographic parity violation. Its utility from deploying h∈H S,h ⋆ is U (h,h ⋆ ) = ∆(h)− ∆(h ⋆ ).(4) This objective models a worst-case strategic or adversarial company and is used to derive lower bounds on unavoidable post-audit manipulation. The auditor minimizes this utility by selecting an audit set, while the company maximizes it by choosing a feasible classifier. For a budgeted audit, the worst-case deviation is WCD B (h ⋆ ) = inf S∈S B sup h∈H S,h ⋆ (∆(h)− ∆(h ⋆ )),(5) whereas for a budgeted α-tolerant audit, WCD B,α (h ⋆ ) = inf S∈S B,α sup h∈H S,h ⋆ (∆(h)− ∆(h ⋆ )).(6) In the next section, we derive explicit lower bounds for both formulations, quantifying how post-audit manipulation depends on the audit budget, group imbalance, and fairness tolerance. 4 Quantifying the Limits of Budget-Constrained Fairness Audits In the previous section, we formulated fairness auditing as two min–max optimization problems. In this section, we derive explicit lower bounds on the values of these optimization problems. These bounds characterize the minimum post-audit demographic parity deviation that every auditor must tolerate under the respective audit constraints. For clarity, complete proofs are deferred to Appendix A. Here we emphasize the intuition underlying each result. 4.1 Budgeted Audits We first consider the simplest auditing model in which the auditor is constrained only by its sampling budget. Since every audited sample is protected from post-audit manipulation, increasing the budget directly limits the company’s ability to alter the deployed classifier. The following theorem quantifies this dependence. Manipulation Strategy. The lower bounds are derived by analyzing the company’s most advantageous post-audit manipulation. Observe that increasing the demographic parity violation requires changing predictions in opposite directions across the two sensitive groups. Consequently, the company only needs to consider two sets of samples: U : samples from X 00 whose predictions are changed from 0 to 1, P : samples from X 11 whose predictions are changed from 1 to 0. Letu =|U|andp =|P|denote the number of manipulated samples in each set. If the auditor includesn u samples fromUandn p samples fromPin the audit set, those manipulations become infeasible. Consequently, the company’s remaining post-audit deviation depends only on the unaudited manipulated samples, namely ∆(h ′ )− ∆(h ⋆ ) = u− n u s 0 + p− n p s 1 . The proofs of Theorems 1 and 2 characterize how the auditor should allocate its limited budget between these two manipulation sets. The following theorem lower bounds the value of WCD B (h ⋆ ) (Equation 5). Theorem 1 (Lower Bound under Budgeted Audit). Leth ⋆ be the initial classifier, and the auditor selects an audit setS ⊆ Ds.t.|S|≤ B. Then, the maximum increase in demographic parity violation that the company can achieve through strategic deviation is lower bounded as: ∆(h ′ )− ∆(h ⋆ )≥ max N − B s max , 0 , where h ′ is the classifier that the company ends with. Moreover, this bound is tight when s 0 = s 1 . 4 A PREPRINT - AUGUST 4, 2026 Interpretation. The lower bound admits a simple interpretation. The quantityN = x 00 + x 11 represents the total number of samples whose labels the company would ideally manipulate in the absence of auditing. Since the auditor can monitor at mostBsamples, at leastN − Bcandidate manipulations remain available. Their contribution to demographic parity is normalized by the larger sensitive group, giving the factor s max . Consequently, it captures the minimum manipulation that any budget-constrained auditor must tolerate. The bound is tight when the two sensitive groups are balanced. Proof sketch. The company first proposes a manipulation set by changing labels inX 00 andX 11 to maximize demographic parity violation. The auditor responds by selecting B samples from these candidate manipulations. Whens 0 < s 1 , each monitored sample from group0blocks a larger increase in demographic parity than monitoring a sample from group1, and vice versa. Accordingly, the auditor allocates its budget to the group with the larger marginal influence until either the budget or the manipulation set is exhausted. Analyzing these cases yields the auditor’s optimal strategy. Substituting the company’s optimal manipulation u = x 00 , p = x 11 , into the resulting expression gives the stated lower bound. 4.2 Budgeted α-Tolerant Audits The previous result allows the auditor to construct arbitrary audit sets. In practice, however, audit certificates are expected to accurately reflect the fairness of the certified model. We therefore consider auditors whose audit sets must estimate the demographic parity of the certified classifier within an additive toleranceα. The following theorem lower bounds WCD B,α (h ⋆ ) (Equation 6). Theorem 2 (Lower Bound under Budgetedα-Tolerant Audit). Leth ⋆ be the initial classifier with DP violation ∆(h ⋆ ). The auditor has budgetBand tolerates up toαdeviation from the fairness ofh ⋆ . Definet = ∆(h ⋆ ) + α. Then, the maximum increase in fairness violation achievable by the company is lower bounded by: ∆(h ′ )− ∆(h ⋆ )≥ N − B s max + x 10 (s 1 − s 0 t) s 0 s 1 (1− t) , subject to feasibility conditions onB,t,x 10 . The bound is tight whens 0 = s 1 .h ′ is the classifier that the company ends with. Interpretation. Unlike Theorem 1, the lower bound now consists of two components, N − B s max |z Budget + x 10 (s 1 − s 0 t) s 0 s 1 (1− t) |z Tolerance . The first term is identical to the budget-only setting and captures the unavoidable manipulation arising from unaudited samples. The second term is a consequence of the tolerance constraint. Since the auditor must preserve the demographic parity of the certified model, it loses the freedom to concentrate its entire budget on the company’s manipulation set. This additional restriction creates further opportunities for strategic deviation. Proof sketch.Theα-tolerance constraint introduces an additional coupling between the composition of the audit set and its estimated demographic parity. We first show that an optimal auditor prioritizes monitoring manipulated samples, using non-manipulated samples only when necessary to satisfy the tolerance constraint. This reduces the auditor’s optimization to determining how its budget should be allocated between the two sensitive groups. Solving the resulting constrained optimization yields closed-form expressions for the monitored samples(n u ,n p ). Substituting these into the company’s objective together with its optimal manipulation strategy gives the stated lower bound. 5 A PREPRINT - AUGUST 4, 2026 Algorithm 1: Replacement-based Auditing Set Construction (RASC) Input: Dataset D, classifier h ⋆ , audit budget B, tolerance α Output: Audit set S Partition D intoX 00 ,X 01 ,X 10 ,X 11 according to the predictions of h ⋆ Rank samples in each partition according to their proximity to the decision boundary Initialize an audit set S of size at most B using the highest-priority samples while|∆(S,h ⋆ )− ∆(h ⋆ )| > α do Replace samples in S with the next highest-priority candidates to reduce the fairness estimation error return S 4.3 Practical Variant: Balanced Audit Sets Although Theorem 2 applies to general audit sets, many practical auditing protocols construct balanced audit sets. Under this common assumption we obtain a simpler closed-form bound. Assumption 1. The auditor ensures that the chosen setS B,α contains an equal number of elements from both the sensitive attribute groups. Proposition 1 (Lower Bound under Assumption 1 and Budgetedα-Tolerant Audit). Leth ⋆ be the initial classifier and the auditor have a budgetBunderα-tolerance. Definet := ∆(h ⋆ ) + α. Then, under Assumption 1, the maximum increase in fairness violation achievable by the company is lower bounded by: ∆(h ′ )− ∆(h ⋆ )≥ N − B 2 (1 + t) s 0 , subject to appropriate feasibility constraints onB. The bound is tight whens 0 = s 1 .h ′ is the classifier that the company ends with. Interpretation.Balanced audit sets reduce the flexibility available to the auditor, but they do not eliminate strategic manipulation. The resulting lower bound continues to scale with the number of unaudited samples, showing that balanced representation alone cannot guarantee robust fairness certification under finite audit budgets. The bound remains tight when the two sensitive groups are balanced. 5 Illustrating the Theoretical Limits To illustrate the theoretical limits derived in the previous section, we instantiate the audit constraints using a simple audit-set construction heuristic (RASC). The heuristic ranks samples according to their susceptibility to post-audit manipulation and constructs an audit set by prioritizing those that are most likely to influence the classifier’s decision boundary. The audit set is then iteratively refined until the requiredα-tolerance constraint is satisfied. Algorithm 1 summarizes the procedure. For the experiments in this section, the ranking criterion is instantiated using the geometry of the underlying classifier. For linear models, samples are ranked by their distance to the decision boundary, whereas for neural networks, they are ranked using the classifier’s prediction confidence. The heuristic serves only to instantiate the audit constraints used in our theoretical analysis and is not intended as a novel auditing algorithm. 5.1 Datasets and Baselines Datasets. We evaluate the proposed audit-set construction heuristic on three benchmark datasets: Student Perfor- mance [9], German Credit Risk [16], and COMPAS Recidivism [3]. We use gender as the sensitive attribute for Student Performance and German Credit Risk, and race for COMPAS. Experimental Setup. We compare the proposed heuristic against random audit-set selection under varying audit budgetsB, tolerance levelsα, and initial demographic parity violations∆(h ⋆ ). For each audit set, we compute the most biased classifierh ′ that remains consistent with the audit set using the reduction-based approach of [1], following [21]. Random auditing is repeated 10 times and the average post-audit deviation is reported. For reference, we also plot the theoretical lower bounds from Theorem 1 and Proposition 1, which correspond to a computationally unbounded company operating on the same group-wise countsx ij . Unless otherwise stated, results 6 A PREPRINT - AUGUST 4, 2026 050100 0 0.2 0.4 0.6 0.8 Budget ∆( h ′ ) − ∆( h ⋆ ) 050100 0 0.2 0.4 0.6 0.8 Budget ∆( h ′ ) − ∆( h ⋆ ) RASC with α = 0.05RASC with α = 0.1 RASC with α = 0.2 Random Selection Budgeted Auditor0.1-Tolerant Budgeted Auditor 0.4-Tolerant Budgeted Auditor0.7-Tolerant Budgeted Auditor Figure 2: (Left) Post-audit manipulation by the Logistic Regression class with varying budget (Right) Post-audit manipulation by the Neural Network class with varying budget 00.20.40.6 0 0.2 0.4 α ∆( h ′ ) − ∆( h ⋆ ) 00.20.40.6 0 0.2 0.4 0.6 0.8 α ∆( h ′ ) − ∆( h ⋆ ) RASC Random SelectionBudgeted Auditor α-Tolerant Budgeted Auditor Figure 3: (Left) Post-audit manipulation by the Logistic Regression class with varying values ofα(Right) Post-audit manipulation by the Neural Network class with varying values of α are shown for the Student Performance dataset; analogous trends for the remaining datasets are provided in the supplementary. 5.2 Results Effect of Audit Budget. Figure 2 shows the post-audit demographic parity (DP) violation as the audit budgetB increases. Across both logistic regression and neural network classifiers, larger audit budgets reduce the company’s ability to manipulate the deployed model, consistent with the theoretical lower bounds. The proposed audit-set construction heuristic consistently achieves lower post-audit deviation than random auditing, with the improvement being more pronounced for the more expressive neural network models. Comparison with Theory. The empirical deviations are consistently below the theoretical bounds derived in Theorem 1 and Proposition 1. This is expected since the theoretical analysis assumes a computationally unbounded company, whereas the experiments restrict manipulation to finite hypothesis classes. Nevertheless, the empirical trends closely mirror the theoretical prediction that increasing the audit budget reduces, but does not eliminate, post-audit manipulation. Effect of Fairness Tolerance. Figure 3 examines the influence of the tolerance parameterαwith a fixed audit budget. Asαincreases, the auditor has greater flexibility in constructing representative audit sets, leading to lower post-audit manipulation for logistic regression models. For neural networks, the same qualitative trend is less pronounced, reflecting the increased expressivity of the underlying hypothesis class. 7 A PREPRINT - AUGUST 4, 2026 0.10.20.30.4 0.2 0.4 0.6 0.8 ∆(h ⋆ ) ∆( h ′ ) 0.10.20.30.4 0 0.5 ∆(h ⋆ ) ∆( h ′ ) RASC Random SelectionBudgeted Auditor 0.05-Tolerant Budgeted Auditor Figure 4: (Left) Post-audit manipulation values for the Logistic Regression class with varying values of∆(h ⋆ )(Right) Post-audit manipulation values for the Neural Network class in the learned space with varying values of ∆(h ⋆ ) Comparison with Theory. The theoretical analysis predicts that larger tolerance allows theα-tolerant auditor to approach the behavior of the budget-only auditor while producing audit sets that remain representative of the certified classifier. The empirical results broadly support this behavior. Effect of Initial Fairness. Figure 4 studies the effect of the initial demographic parity violation∆(h ⋆ ). Under finite hypothesis classes, the post-audit DP generally increases with the initial unfairness of the certified classifier, indicating that starting from a more biased model can benefit a strategic company. This effect is substantially reduced under tighter α-tolerant auditing. Comparison with Theory. In contrast, the theoretical bounds are largely insensitive to the initial fairness ofh ⋆ , since an unrestricted company can already realize near-optimal manipulation even from relatively fair starting points. The discrepancy highlights the gap between worst-case guarantees and practical manipulation under finite hypothesis classes. 6 Discussion and Conclusion The lower bounds derived in this paper provide a quantitative characterization of the limitations of finite-budget fairness auditing. A key insight from Theorem 1 is that the difficulty of auditing is fundamentally determined by the number of samples that remain outside the audit set. Every unaudited sample provides an opportunity for strategic post-audit manipulation. This interpretation also explains why increasing the audit budget produces diminishing returns; unless the auditor is able to certify nearly all manipulable samples, some degree of manipulation is unavoidable. Theorem 2 further shows that requiring audit sets to accurately estimate the fairness of the certified classifier introduces an inherent trade-off. In the budget-only setting, the auditor is free to concentrate its budget entirely on the samples most valuable to the company. Theα-tolerance constraint restricts this flexibility by requiring the audit set to remain representative of the certified model. Consequently, the auditor sacrifices some ability to directly block manipulation in exchange for producing a more faithful fairness certificate. At the same time, representative certificates expose the fairness of the initially certified classifier, discouraging companies from beginning with highly biased models. Thus, α-tolerant auditing balances two competing objectives: limiting post-audit manipulation and providing an informative fairness certificate. Our empirical study suggests that these theoretical insights persist even under practical hypothesis classes. Although the observed post-audit deviations are substantially smaller than the worst-case lower bounds, they exhibit the same qualitative dependence on the audit budget, fairness tolerance, and initial classifier fairness. This gap is expected, since the theoretical analysis assumes a computationally unbounded company, whereas practical models are constrained by finite hypothesis classes. Finally, our analysis focuses on static, one-shot fairness certification. An important direction for future work is to understand how richer auditing protocols, such as repeated audits, deployment-time monitoring, or multiple independent information sources [6,17], can reduce the gap between practical auditing procedures and the worst-case limits characterized in this work. 8 A PREPRINT - AUGUST 4, 2026 References [1] A. Agarwal, A. Beygelzimer, M. Dudik, J. Langford, and H. Wallach. A reductions approach to fair classification. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th ICML, volume 80, pages 60–69, 2018. [2] J. Angwin, J. Larson, S. Mattu, and L. Kirchner. Machine bias: There’s software used across the country to predict future criminals. and it’s biased against blacks. ProPublica, 2016. [3]J. Angwin, J. Larson, S. Mattu, and L. Kirchner. Propublica compas recidivism data.https://github.com/ propublica/compas-analysis, 2016. [4] S. Barocas and A. D. Selbst. Big data’s disparate impact. Cal. L. Rev., 104:671, 2016. [5]Bourré, J. G.e, Augustin Godinot, Martijn De Vos, Milos Vujasinovic, Sayan Biswas, Gilles Tredan, Erwan Le Merrer, and Anne-Marie Kermarrec. Robust ML auditing using prior knowledge. In ICML Workshop on Technical AI Governance (TAIG), 2025. [6]J. G. Bourrée, E. L. Merrer, G. Tredan, and B. Rottembourg. Mitigating fairwashing using two-source audits, 2025. [7]S. Casper, C. Ezell, C. Siegmann, N. Kolt, T. L. Curtis, B. Bucknall, A. Haupt, K. Wei, J. Scheurer, M. Hobbhahn, L. Sharkey, S. Krishna, M. Von Hagen, S. Alberti, A. Chan, Q. Sun, M. Gerovitch, D. Bau, M. Tegmark, D. Krueger, and D. Hadfield-Menell. Black-box access is insufficient for rigorous ai audits. In The 2024 FAccT, FAccT ’24, page 2254–2272, 2024. [8]B. Chugg, S. Cortes-Gomez, B. Wilder, and A. Ramdas. Auditing fairness by betting. In Proceedings of the 37th International Conference on Neural Information Processing Systems, 2023. [9] P. Cortez. Student Performance. UCI Machine Learning Repository, 2008. [10]New Y. C. Council. New york city local law 144 of 2021: Automated employment decision tools. Local Law No. 144 of 2021, effective January 1, 2023, 2021. [11] C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. Fairness through awareness. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 214–226, 2012. [12]A. Fabris, N. Baranowska, M. J. Dennis, D. Graus, P. Hacker, J. Saldivar, F. Zuiderveen Borgesius, and A. J. Biega. Fairness and bias in algorithmic hiring: A multidisciplinary survey. ACM Transactions on Intelligent Systems and Technology, 16(1):1–54, 2025. [13]K. Fukuchi, S. Hara, and T. Maehara. Faking fairness via stealthily biased sampling. In AAAI, volume 34, pages 412–419, 2020. [14]M. K. Gerchick, Ro Encarnación, Cole Tanigawa-Lau, Lena Armstrong, Ana Gutiérrez, and Danaé Metaxa. Auditing the audits: Lessons for algorithmic accountability from local law 144’s bias audits. In Proceedings of the 2025 FAccT, page 29–44, 2025. [15]A. Godinot, E. L. Merrer, G. Trédan, C. Penzo, and F. Taïani. Under manipulations, are some ai models harder to audit? In 2024 SaTML (SaTML), page 644–664, 2024. [16] H. Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994. [17]P. Maneriker, C. Burley, and S. Parthasarathy. Online fairness auditing through iterative refinement. In Proceedings of the 29th KDD, page 1665–1676, 2023. [18]European and Union, C. o. t. E. Parliament. Regulation (eu) 2024/1689: Artificial intelligence act. Official Journal of the European Union, 2024. [19]A. Shahin Shamsabadi, M. Yaghini, N. Dullerud, S. Wyllie, Ulrich Aïvodji, Aisha Alaagib, Sébastien Gambs, and Nicolas Papernot. Washing the unwashable: On the (im) possibility of fairwashing detection. NeurIPS, 35:14170–14182, 2022. [20]J. J. Smith, M. Madaio, R. Burke, and C. Fiesler. Pragmatic fairness: Evaluating ml fairness within the constraints of industry. In Proceedings of the 2025 FAccT, page 628–638, 2025. [21] T. Yan and C. Zhang. Active fairness auditing. In ICML, pages 24929–24962, 2022. [22]C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107–115, 2021. 9 A PREPRINT - AUGUST 4, 2026 A Omitted Proofs We present the proofs of Theorem 1, Theorem 2, and Proposition 1. Throughout the appendix, letUdenote the set of manipulated samples from sensitive group0, andPdenote the manipulated samples from sensitive group1. Let u =|U|andp =|P|denote the corresponding numbers of manipulated samples, whilen u andn p denote the numbers of monitored samples selected by the auditor from U and P , respectively. A.1 Proof of Theorem 1 Proof. Assume, without loss of generality, that x 01 s 0 > x 11 s 1 , so increasing predictions in group 0 and decreasing predictions in group 1 increases the demographic parity violation. After the company manipulatesusamples fromUandpsamples fromP, and the auditor monitorsn u andn p of these samples, respectively, the post-audit increase in demographic parity becomes ∆(h ′ )− ∆(h ⋆ ) = u− n u s 0 + p− n p s 1 , wheren u + n p ≤ B. The auditor therefore allocates its budget to maximize n u s 0 + n p s 1 ,giving priority to the sensitive group with the smaller denominator. Case 1: s 0 < s 1 . The auditor first monitors samples from U . This yields ∆(h ′ )− ∆(h ⋆ )≥ u− B s 0 + p s 1 , B ≤ u, u + p− B s 1 , u < B ≤ u + p, 0,B > u + p. Case 2: s 1 < s 0 . By symmetry, the auditor first monitors samples from P , giving ∆(h ′ )− ∆(h ⋆ )≥ p− B s 1 + u s 0 , B ≤ p, u + p− B s 0 , p < B ≤ u + p, 0,B > u + p. Case 3: s 0 = s 1 . Both groups contribute equally, and therefore ∆(h ′ )− ∆(h ⋆ )≥ u + p− B s 0 , B ≤ u + p, 0,B > u + p. Finally, the company’s optimal manipulation is obtained by choosing u = x 00 , p = x 11 , so that u + p = x 00 + x 11 = N. Combining the above cases and using 1 s max ≤ 1 s 0 , 1 s max ≤ 1 s 1 , gives ∆(h ′ )− ∆(h ⋆ )≥ max N − B s max , 0 . When s 0 = s 1 , the inequality becomes an equality, establishing tightness. 10 A PREPRINT - AUGUST 4, 2026 A.2 Proof of Theorem 2 The proof proceeds in three steps. We first characterize the structure of an optimal audit set under theα-tolerance constraint. We then solve the auditor’s optimization problem for a fixed manipulation proposed by the company, and finally substitute the company’s optimal manipulation strategy to obtain the stated lower bound. Lemma 1 (Structure of an Optimal Audit Set). For an optimalα-tolerant auditor, every sample outside the manipulation setsUandPis selected fromX 01 orX 10 . Furthermore, the resulting audit set makes sensitive group1the privileged group. Proof.The auditor maximizes the number of monitored manipulated samples while satisfying theα-tolerance constraint. Replacing samples fromX 00 orX 11 by manipulated samples fromUorPcan only increase the number of monitored deviations without affecting feasibility. Hence an optimal audit set never contains samples fromX 00 orX 11 outside the manipulation sets. Starting from an audit set consisting entirely of manipulated samples (with a fractionf 1 samples fromPand a fraction f 0 samples fromU), the auditor introduces samples fromX 01 andX 10 only as needed to satisfy the tolerance constraint. Since this requires the smallest number of replacements, it is optimal. The resulting audit set necessarily satisfies f 1 p− n 1 f 1 p − n 0 f 0 u = t, where f 1 p + f 0 u = B. Lemma 2 (Optimal Replacement Strategy). For initial fixed fractionsf 1 andf 0 for samples fromPandUrespectively , the optimal replacement satisfies n 1 = x 10 , n 0 = f 0 u 1− t− x 10 f 1 p . Proof. Using the tolerance constraint, n 0 = f 0 u 1− n 1 f 1 p − t , the auditor’s objective becomes a linear function of n 1 . The feasible interval forn 1 is determined by0≤ n 0 ≤ x 01 and0≤ n 1 ≤ x 10 . Under the feasibility assumptions of the theorem, the objective is monotone over this interval and therefore attains its optimum at the boundary,n 1 = x 10 . Substituting this value yields the stated expression for n 0 . Lemma 3 (Optimal Budget Allocation). The optimal allocation of the audit budget satisfies f 1 = x 10 (1− t)p , f 0 = 1 u B− x 10 1− t , provided the feasibility conditions of the theorem hold. Proof. Substituting the optimal values of n 0 and n 1 reduces the auditor’s objective to g(f 1 ) = f 1 p 1 s 1 − t s 0 + Bx 10 s 0 f 1 p . The feasible interval forf 1 is determined by the budget constraint and the non-negativity ofn 0 . Sinceg(f 1 )has no interior maximum over this interval, its optimum is attained at an endpoint. Under the theorem’s feasibility conditions, the lower endpoint is optimal, yieldingf 1 = x 10 (1−t)p ,and the expression forf 0 follows immediately from f 0 u + f 1 p = B. 11 A PREPRINT - AUGUST 4, 2026 Proof. The company’s objective is u− n u s 0 + p− n p s 1 . Clearly,u = x 00 andp = x 11 maximize this quantity. Substituting the optimal values ofn u andn p obtained from Lemma A.3 yields ∆(h ′ )− ∆(h ⋆ )≥ N − B s max + x 10 s 1 − s 0 t s 0 s 1 (1− t) . Since the bound decreases monotonically witht, the auditor chooses the largest feasible value,t = ∆(h ⋆ ) + α,which completes the proof. A.3 Proof of Proposition 1 Proof. Under Assumption 1, the auditor allocates exactly half of its budget to each sensitive group. Consequently, n u + n 0 = B 2 , n p + n 1 = B 2 , wheren u ,n p denote monitored manipulated samples andn 0 ,n 1 denote monitored non-manipulated samples. The α-tolerance constraint requires n p n p +n 1 − n 0 n u +n 0 = t, where∆(h ⋆ )− α ≤ t ≤ ∆(h ⋆ ) + α. Combining the above equalities immediately gives n p − n 0 = Bt 2 , and therefore n u + n p = B(1+t) 2 . Hence, for a fixed manipulation proposed by the company, the auditor’s optimization reduces to maximizing n u s 0 + n p s 1 , subject to the above constraints. Whens 0 < s 1 , every monitored sample from group0blocks a larger increase in demographic parity than one from group1. The auditor therefore allocates as many manipulated samples as possible to n u . By symmetry, whens 1 < s 0 , the auditor instead prioritizesn p . Finally, whens 0 = s 1 , every feasible allocation yields the same objective value. In all three cases, the resulting post-audit deviation satisfies ∆(h ′ )− ∆(h ⋆ )≥ max ( u + p− B(1+t) 2 s max , 0 ) , subject to the feasibility conditions stated in the proposition. Finally, the company maximizes the deviation by choosingu = x 00 ,p = x 11 ,so thatu + p = x 00 + x 11 = N. Substituting these values gives ∆(h ′ )− ∆(h ⋆ )≥ max ( N − B 2 (1 + t) s max , 0 ) . Since 1 s max ≤ 1 s 0 , we obtain the stated lower bound ∆(h ′ )− ∆(h ⋆ )≥ N − B 2 (1 + t) s 0 . Finally, the bound is decreasing in t, and therefore the auditor chooses the largest admissible value, t = ∆(h ⋆ ) + α. When s 0 = s 1 , the inequality becomes an equality, establishing the tightness of the bound. 12 A PREPRINT - AUGUST 4, 2026 B Architecture of the Neural Network used in the Experiments The neural network consists of three fully connected layers with tanh activations. It is defined as f (x) =W ⊤ 3 tanh W ⊤ 2 tanh(W ⊤ 1 x +b 1 ) +b 2 +b 3 , where W 1 ∈R i×50 ,W 2 ∈R 50×30 ,W 3 ∈R 30×2 , andb 1 ,b 2 ,b 3 are the corresponding bias vectors. Here, i denotes the input dimension of the dataset. C Additional Experiments We present results for the COMPAS Recidivism Racial Bias and the German Credit Risk datasets in this section. We experiment with only the Logistic Regression class for these datasets to better illustrate the trends in deviation achieved by the company with varying DP violation of the initial classifier∆(h ⋆ ). We explain observations for only the COMPAS Recidivism Racial Bias dataset, since the trends are very similar for the German Credit Risk dataset. C.1 COMPAS Recidivism Racial Bias Dataset Effect of BudgetB. We evaluate the deviation by varying the audit budgetBwhile keeping the tolerance levelαfixed. As shown in Figure 5 (Left), the deviation is very low for budgets greater than about 50. There is a slight benefit for the auditor to using RASC vs random selection, due to the heuristic working more naturally for linear classifiers. Also, there is little change in the deviation with varying value ofα, as all the approaches (including random selection) restrict the company’s deviation strongly. As a result, the gains for the auditor obtained by increasing the value ofαare less pronounced. Comparison with Theoretical Bounds. Again, the empirical deviations observed are substantially more conservative than the theoretical bounds derived in Theorem 1 and Proposition 1. This is expected due to the limited expressivity of the empirical hypothesis class. Moreover, the Budgeted andα-Tolerant auditors give very similar bounds, due to the significantly lower values of the budget B with respect to the overall dataset. Effect of Initial Classifier Fairness. A similar trend is observed when the initial classifier is more biased, though the gap between RASC and random selection is higher due to the ease of auditing a more biased linear classifier. Assuming a distribution with non-trivial variance along all dimensions (like most datasets), a company with limited expressivity in its hypothesis class will have progressively more difficulty in deviating as ∆(h ⋆ ) increases. Effect of Toleranceα. We examine the impact of varying toleranceαon RASC with fixed budget (25samples). As shown in Figure 6 (Left), the company’s ability to deviate worsens as α increases, plateauing beyond a threshold. Effect of Initial Classifier Bias. As visible in Figure 6 (Right),α’s influence is more pronounced for a highly biased classifier. This is because empirically, for the Logistic Regression class, the auditor is better able to constrain the company’s deviation with fairer audit sets. For higher∆(h ⋆ ), there is an increased scope of getting fairer audit sets with increasing α. Effect of Initial Classifier Fairness (∆(h ⋆ )) on post-audit DP. In this experiment, we fix the tolerance parameter αat0.05and the audit budget at25samples. We evaluate the effect of increasing∆(h ⋆ )on the DP violation of the post-audit model. Specifically, we compare the DP violation of the most biased classifier consistent with the audit sets produced by RASC and random selection. We also report the theoretical bounds corresponding to the optimal post-audit deviation achievable under the Budgeted and 0.05-Tolerant Budgeted audits. As also observed for the Student Performance Dataset, Figure 7 (Left) shows that the empirical DP violation of the company’s post-audit model increases with higher initial values of ∆(h ⋆ ). Comparison with Theoretical Behavior. Similar to the Student Performance dataset, under the theoretical setting, the DP violation of the company’s post-audit model remains nearly constant across varying∆(h ⋆ ), suggesting a powerful company would be indifferent to initial fairness, while also achieving its objective of deviation almost perfectly due to the significantly lower size of the budget in comparison to the size of the whole dataset. 13 A PREPRINT - AUGUST 4, 2026 050100 0 0.2 0.4 0.6 0.8 Budget ∆( h ′ ) − ∆( h ⋆ ) ∆(h ⋆ ) = 0.16 050100 0 0.2 0.4 Budget ∆( h ′ ) − ∆( h ⋆ ) ∆(h ⋆ ) = 0.50 RASC with α = 0.05RASC with α = 0.1 RASC with α = 0.2 Random Selection Budgeted Auditor0.1-Tolerant Budgeted Auditor 0.2-Tolerant Budgeted Auditor0.3-Tolerant Budgeted Auditor Figure 5: Post-audit deviation with varying budget for ∆(h ⋆ ) = 0.16 (Left) and ∆(h ⋆ ) = 0.50 (Right). 00.20.40.6 0.2 0.4 0.6 0.8 α ∆( h ′ ) − ∆( h ⋆ ) ∆(h ⋆ ) = 0.26 00.20.40.6 0 0.2 0.4 α ∆( h ′ ) − ∆( h ⋆ ) ∆(h ⋆ ) = 0.69 RASC Random SelectionBudgeted Auditor α-Tolerant Budgeted Auditor Figure 6: Post-audit deviation with varying α for ∆(h ⋆ ) = 0.26 (Left) and ∆(h ⋆ ) = 0.69 (Right). 0.20.4 0 0.5 1 ∆(h ⋆ ) ∆( h ′ ) RASC Random SelectionBudgeted Auditor α-Tolerant Budgeted Auditor Figure 7: Post-audit DP violation with varying values of ∆(h ⋆ ) 14 A PREPRINT - AUGUST 4, 2026 C.2 German Credit Risk Dataset 050100 0 0.2 0.4 0.6 0.8 Budget ∆( h ′ ) − ∆( h ⋆ ) ∆(h ⋆ ) = 0.20 050100 0 0.2 0.4 Budget ∆( h ′ ) − ∆( h ⋆ ) ∆(h ⋆ ) = 0.50 RASC with α = 0.05RASC with α = 0.1 RASC with α = 0.2 Random Selection Budgeted Auditor0.1-Tolerant Budgeted Auditor 0.2-Tolerant Budgeted Auditor0.3-Tolerant Budgeted Auditor Figure 8: Post-audit deviation with varying budget for ∆(h ⋆ ) = 0.20 (Left) and ∆(h ⋆ ) = 0.50 (Right). 00.20.40.6 0 0.2 0.4 0.6 α ∆( h ′ ) − ∆( h ⋆ ) ∆(h ⋆ ) = 0.28 00.20.40.6 0 5· 10 −2 0.1 α ∆( h ′ ) − ∆( h ⋆ ) ∆(h ⋆ ) = 0.83 RASC Random SelectionBudgeted Auditor α-Tolerant Budgeted Auditor Figure 9: Post-audit deviation with varying α for ∆(h ⋆ ) = 0.28 (Left) and ∆(h ⋆ ) = 0.83 (Right). 0.20.40.6 0 0.2 0.4 0.6 0.8 1 ∆(h ⋆ ) ∆( h ′ ) RASC Random SelectionBudgeted Auditor α-Tolerant Budgeted Auditor Figure 10: Post-audit DP violation with varying values of ∆(h ⋆ ) 15