Pith. sign in

REVIEW 3 major objections 4 minor 22 references

Fairness Auditing: Lower Bounds on Company Manipulation

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Finite-budget fairness audits cannot prevent a guaranteed post-audit bias increase.

desk verdict The budget-only bound is correct but elementary; the alpha-tolerant bound is not just unproved, it's false on a concrete instance, so the paper's main advertised result doesn't stand. read the letter →

arxiv 2608.00568 v1 pith:YUBVNDTE submitted 2026-08-01 cs.LG cs.AI

Rachit Verma , Padala Manisha , Sujit Gujar This is my paper · ORCID
classification cs.LGcs.AI
keywords fairnessauditingdemographicparitypost-auditmanipulationlowerboundsmin-maxgameauditbudgetalpha-tolerant
open problems P versus NP
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to prove that finite-budget fairness audits have a hard quantitative floor: whatever audit set an auditor chooses, a company with enough representational power can always increase demographic parity violation after certification by an amount that depends only on the budget, the group sizes, and the number of samples it would ideally flip. The authors model auditing as a min-max game between a strategic company and a budget-constrained auditor, and derive closed-form lower bounds for two regimes: a plain budget cap, and a cap plus a tolerance α on how accurately the audit set estimates the certified model's fairness. The results matter because they convert the known qualitative impossibility of black-box fairness auditing into numbers an auditor can inspect: even an optimal finite audit leaves room for manipulation, and the room shrinks but never disappears as resources grow.

What carries the argument

The carrying object is the partition of the dataset by sensitive attribute and current prediction: X00, X01, X10, X11, with N=x00+x11 as the population of samples whose prediction flips would increase DP violation. The company's post-audit gain reduces to (u−nu)/s0 + (p−np)/s1, where u,p are flipped samples in the two groups and nu,np are the monitored ones. In the α-tolerant regime, the tolerance constraint is rewritten as n0 = f0u(1−t−n1/(f1p)) with t=Δ(h*)+α, and the solution of the resulting linear allocation problem yields the closed-form bound.

What would settle it

Take any concrete dataset and enumerable hypothesis class; fix x00,x01,x10,x11,B, and α, then brute-force all audit sets S with |S|≤B and |Δ(S,h*)−Δ(h*)|≤α and all classifiers consistent with S, and compute the exact minimax value. If any instance with imbalanced groups yields a value strictly below the Theorem 2 expression—or below the Theorem 1 expression in the budget-only case—the claimed lower bound is false.

Watch

Extended reading notes

Core claim

Formally, the paper claims that for any audit set of size at most B, the company can raise the empirical demographic parity violation by at least max{(N−B)/smax, 0}, where N=x00+x11 is the number of samples the company would ideally flip and smax is the larger sensitive group. When the auditor also requires |Δ(S,h*)−Δ(h*)|≤α, the lower bound increases by x10(s1−s0t)/(s0s1(1−t)) with t=Δ(h*)+α, because the tolerance constraint forces the auditor to spend part of its budget on non-manipulated samples. The paper proves tightness when the two sensitive groups are balanced, and provides a simpler bound for balanced audit sets. Empirically, linear and neural classifiers deviating under a replaceme

Load-bearing premise

The α-tolerant lower bound stands on the claim that the auditor's best audit set has a specific shape—it monitors only manipulable samples from the two privileged/underprivileged directions plus unchanged samples from exactly two of the four prediction cells—and that this shape makes sensitive group 1 the privileged group; if that shape is not optimal, the closed-form bound collapses.

Editorial extensions

If this is right

  • Larger budgets shrink but never eliminate the guaranteed manipulation: the term (N−B)/smax is positive whenever B<N, so full certification requires auditing essentially every manipulable sample.
  • When the sensitive groups have equal size, the lower bound is tight, so for balanced datasets the budget-only formula exactly predicts the worst-case post-audit deviation.
  • Requiring fairness certificates to be within tolerance α costs the auditor a fixed extra amount of unavoidable deviation; a more tolerant auditor sacrifices less to representativeness.
  • Balanced audit sets, a common practical choice, make the bound (N−B(1+t)/2)/s0, showing that even a balanced protocol cannot certify away manipulation.
  • Since empirical deviations from linear and neural classifiers track the bounds' shape but sit below them, real-world audits of restricted model classes can expect smaller but still nonzero post-audit bias.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct extension the paper does not pursue: the formulas depend only on the group-wise counts xij, so an auditor could compute a 'minimum unavoidable manipulation' estimate before auditing, using the same counts, to decide whether a certification effort is worth running at all.
  • The paper only proves tightness for balanced groups; for imbalanced groups the true minimax value may be lower than the closed form, so an exact enumeration on small instances would be the natural check for slack in Theorem 2 outside s0=s1.
  • If the structural lemma about optimal α-tolerant audit sets is correct, it implies an operational ranking: among two certified classifiers with the same initial DP violation, the one with smaller x10 carries a lower guaranteed manipulation penalty, so auditors could prefer it.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies one-shot fairness certification under finite audit budgets. It models a strategic company that may deploy a classifier consistent with the audited samples while maximizing the increase in demographic parity (DP) violation, and it contrasts a budget-only auditor with an alpha-tolerant auditor that also requires the audit set's DP estimate to be within alpha of the certified classifier. The main theoretical claims are Theorem 1 (lower bound (N-B)/s_max for budget-only audits), Theorem 2 (a closed-form lower bound for alpha-tolerant audits), and Proposition 1 (a variant for balanced audit sets). The paper also contributes a heuristic audit-set construction (RASC) and empirical illustrations on three datasets. The central advertised result is the alpha-tolerant bound; the paper argues that finite budgets and tolerance both create unavoidable post-audit manipulation.

Significance. If Theorems 1 and 2 were correct, the paper would provide a useful quantitative complement to black-box auditing impossibility results: explicit, parameter-free lower bounds on post-audit manipulation as a function of budget, group imbalance, and tolerance. The derivations are self-contained counting arguments over the paper's own definitions, with no fitted parameters and no dependence on prior work, which is a strength. Theorem 1 appears plausible and is a reasonable contribution. However, the main alpha-tolerant result, Theorem 2, is false as stated, and Proposition 1 is also false. A concrete admissible instance yields a claimed lower bound larger than the unconditional maximum possible deviation, and an explicit feasible audit set gives a worst-case deviation far below the bound. This is not a disagreement with a consensus or a stylistic issue; it is an internal mathematical contradiction. The central contribution of the paper is therefore not established, and the empirical plots that compare against the invalid theoretical bounds are misleading in their current form.

major comments (3)
  1. [Theorem 2, Section 4.2] Theorem 2 is false. Take x00=2, x01=8, x10=6, x11=14, so s0=10, s1=20, N=16, smax=20, and Δ(h*)=8/10-14/20=0.1. Let B=10 and α=0.3, so t=0.4. The claimed bound is (16-10)/20 + 6(20-10·0.4)/(10·20·0.6) = 0.3+0.8 = 1.1. But no classifier can increase the violation by more than x00/s0 + x11/s1 = 0.2+0.7 = 0.9, since only X00 samples can be moved from 0 to 1 and only X11 samples from 1 to 0 to increase the DP gap. Moreover, the audit set S={2 X00, 2 X01, 1 X10, 5 X11} has size 10, satisfies |Δ(S,h*)-Δ(h*)|=|1/3-0.1|=0.2333≤0.3, and leaves 9 X11 samples unmonitored, so the company can achieve increase 9/20=0.45. Hence WCD_{B,α}(h*)≤0.45<1.1, contradicting the theorem. This is a decisive numerical counterexample, not a gap in a proof detail.
  2. [Appendix A.2, Lemmas 1-3] The structural derivation behind Theorem 2 is invalid on the domain of feasible audit sets. Lemma 3 gives f1 = x10/((1-t)p) and f0 = (1/u)(B - x10/(1-t)). In the counterexample above, this gives f1p = 10 and f0u = 0; after the proof's replacement of n1=x10=6 samples by X10, the audit set would consist of 4 X11 and 6 X10 and no group-0 samples, so Δ(S,h*) is undefined and the tolerance constraint cannot be satisfied. Thus the claimed closed-form allocation is not feasible. The proof also asserts, without proof, that an optimal audit set makes group 1 privileged and contains only manipulated samples from U and P plus samples from X01 and X10. The counterexample satisfies that asserted structure, yet the formula still fails, showing that Lemma 1 is insufficient and the 'feasibility conditions' referred to in Theorem 2 are never stated and cannot rescue the bound.
  3. [Proposition 1, Section 4.3] Proposition 1 is also false. Using the same counts as above, with B=10 and t=0.4, the bound is (N - B(1+t)/2)/s0 = (16 - 5·1.4)/10 = 0.9. But the balanced audit set S={2 X00, 3 X01, 5 X11} has exactly 5 samples from each group, size 10, and Δ(S,h*)=|3/5 - 5/5|=0.4, within α=0.3 of Δ(h*)=0.1. The company can flip the 9 unmonitored X11 samples, giving post-audit violation Δ(h')=|8/10 - 5/20|=0.55, an increase of 0.45, less than the claimed 0.9. Since 0.45 is also the maximum increase given that all X00 are monitored, the proposition's bound is contradicted. The proof in Appendix A.3 does not address this possibility and relies on the same unsupported monotonicity and feasibility assumptions.
minor comments (4)
  1. [Throughout] The phrase 'subject to feasibility conditions on B, t, x10' in Theorems 2 and Proposition 1 is never made explicit. Since the theorem statements depend on these conditions for their validity, they should be stated precisely in the main text; the current formulation makes the results effectively unfalsifiable as written.
  2. [Appendix A.2, Lemma 1] The tolerance constraint is written as 'f1p−n1 / f1p − n0 / f0u = t', which is ambiguous due to missing parentheses. It should be written as (f1p−n1)/(f1p) − n0/(f0u) = t or with an explicit definition of the terms.
  3. [References] Reference [5] contains a malformed author string ('Bourré, J. G.e, Augustin Godinot, ...'), and the reference list inconsistently renders the same group's name. Please correct the bibliography entries.
  4. [Figures 2-4] The legends mix 'Budgeted Auditor', '0.1-Tolerant Budgeted Auditor', etc., but the caption does not identify which line uses which tolerance. The comparison with theory is hard to read and, given the counterexamples, the plotted theoretical bounds for alpha-tolerant audits should not be presented as valid lower bounds.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower bounds are self-contained counting arguments over the paper's own definitions, with no fitted parameters or load-bearing self-citations.

full rationale

The paper's derivations are self-contained. The DP violation and audit-set constraints are defined in Section 2-3, and Theorems 1 and 2 are proved in Appendix A by counting manipulated samples (u, p) and monitored samples (nu, np). No parameter is fitted to data, and no prior result by the same authors is used as a premise; the few external citations are for background or unrelated technical tools. The lower bounds are intended to follow algebraically from the paper's own definitions of the company objective and auditor constraints. The main risk in the paper is correctness, not circularity: the skeptic's counterexample and the unproven structural assumptions in Lemma 1 and Lemma 2 concern whether Theorem 2's closed form is valid for all feasible audit sets, which is a soundness issue rather than a reduction of the claim to its inputs. A false or under-proved theorem does not make the derivation circular. Therefore no circular step can be exhibited, and the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters are fitted and no new entities are introduced. The analysis rests entirely on group-wise counts and the worst-case assumptions described above. The main burden is the unproved structural assumption about the optimal alpha-tolerant audit set and the unstated feasibility conditions, both of which are ad hoc to this paper's derivation.

assumptions (5)
  • domain assumption The company has unrestricted representational capacity and may choose any classifier consistent with the audit set.
    Section 2.2 states this explicitly, motivated by over-parameterized models. It is the standard worst-case assumption and is needed for the lower bounds.
  • domain assumption Without loss of generality, group 0 is the privileged group with x01/s0 > x11/s1.
    Used throughout Section 4 and Appendix A to set the direction of manipulation. It is valid by symmetry of demographic parity, but it must hold for the stated formulas to apply as written.
  • ad hoc to paper An optimal alpha-tolerant audit set contains only manipulated samples from U and P plus samples from X01 and X10, and makes group 1 the privileged group.
    Lemma 1 in Appendix A.2 asserts this structure without a complete proof. It is load-bearing for Theorem 2; if the optimal audit set has a different structure, the closed-form bound is not established.
  • ad hoc to paper The alpha-tolerance constraint can be represented by the linearized equation n0 = f0u(1 - t - n1/(f1p)).
    Lemma 2 in Appendix A.2 derives this by dropping the non-manipulated samples from the denominators of the demographic parity estimate. The exact DP equation would be f1p/(f1p+n1) - n0/(f0u+n0) = t, so the linearization is an additional unstated approximation.
  • ad hoc to paper The feasibility conditions on B, t, and x10 in Theorems 2 and Proposition 1 are satisfied whenever the stated inequalities are used.
    The main text never specifies these conditions. Until they are stated, the theorems are not self-contained and cannot be applied or checked.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fairness Auditing: Lower Bounds on Company Manipulation." pith.science (2026). https://pith.science/paper/YUBVNDTE

@misc{pith2026260800568,
  author       = {Pith},
  title        = {Pith review of: Fairness Auditing: Lower Bounds on Company Manipulation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YUBVNDTE}},
  note         = {Machine review of arXiv:2608.00568}
}
read the original 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.

Figures

Figures reproduced from arXiv: 2608.00568 by the authors.

Figure 1
Figure 1. Analysis of classifier deviations under auditing sets. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. (Left) Post-audit manipulation by the Logistic Regression class with varying budget (Right) Post-audit [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. (Left) Post-audit manipulation by the Logistic Regression class with varying values of [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: (Left) Post-audit manipulation values for the Logistic Regression class with varying values of [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]
Figure 5
Figure 5. Figure 5: Post-audit deviation with varying budget for [PITH_FULL_IMAGE:figures/full_fig_p014_5.png]
Figure 6
Figure 6. Figure 6: Post-audit deviation with varying α for ∆(h ⋆ ) = 0.26 (Left) and ∆(h ⋆ ) = 0.69 (Right). 0.2 0.4 0 0.5 1 ∆(h ⋆ ) ∆( h ′ ) RASC Random Selection Budgeted Auditor α-Tolerant Budgeted Auditor [PITH_FULL_IMAGE:figures/full_fig_p014_6.png]
Figure 7
Figure 7. Figure 7: Post-audit DP violation with varying values of [PITH_FULL_IMAGE:figures/full_fig_p014_7.png]
Figure 8
Figure 8. Figure 8: Post-audit deviation with varying budget for [PITH_FULL_IMAGE:figures/full_fig_p015_8.png]
Figure 9
Figure 9. Figure 9: Post-audit deviation with varying α for ∆(h ⋆ ) = 0.28 (Left) and ∆(h ⋆ ) = 0.83 (Right). 0.2 0.4 0.6 0 0.2 0.4 0.6 0.8 1 ∆(h ⋆ ) ∆( h ′ ) RASC Random Selection Budgeted Auditor α-Tolerant Budgeted Auditor [PITH_FULL_IMAGE:figures/full_fig_p015_9.png]
Figure 10
Figure 10. Figure 10: Post-audit DP violation with varying values of [PITH_FULL_IMAGE:figures/full_fig_p015_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 21 canonical work pages

  1. [1]

    Agarwal, A

    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

    work page 2018

  2. [2]

    Angwin, J

    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

    work page 2016

  3. [3]

    Angwin, J

    J. Angwin, J. Larson, S. Mattu, and L. Kirchner. Propublica compas recidivism data. https://github.com/ propublica/compas-analysis, 2016

    work page 2016

  4. [4]

    Barocas and A

    S. Barocas and A. D. Selbst. Big data’s disparate impact.Cal. L. Rev., 104:671, 2016

    work page 2016

  5. [5]

    G.e, Augustin Godinot, Martijn De V os, Milos Vujasinovic, Sayan Biswas, Gilles Tredan, Erwan Le Merrer, and Anne-Marie Kermarrec

    Bourré, J. G.e, Augustin Godinot, Martijn De V os, Milos Vujasinovic, Sayan Biswas, Gilles Tredan, Erwan Le Merrer, and Anne-Marie Kermarrec. Robust ML auditing using prior knowledge. InICML Workshop on Technical AI Governance (TAIG), 2025

    work page 2025

  6. [6]

    J. G. Bourrée, E. L. Merrer, G. Tredan, and B. Rottembourg. Mitigating fairwashing using two-source audits, 2025

    work page 2025

  7. [7]

    Casper, C

    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. V on 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. InThe 2024 FAccT, FAccT ’24, page 2254–2272, 2024

    work page 2024

  8. [8]

    Chugg, S

    B. Chugg, S. Cortes-Gomez, B. Wilder, and A. Ramdas. Auditing fairness by betting. InProceedings of the 37th International Conference on Neural Information Processing Systems, 2023

    work page 2023

Show all 22 references
  1. [9]

    P. Cortez. Student Performance. UCI Machine Learning Repository, 2008

    2008

  2. [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

    2021

  3. [11]

    Dwork, M

    C. Dwork, M. Hardt, T. Pitassi, O. Reingold, and R. Zemel. Fairness through awareness. InProceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 214–226, 2012

    2012

  4. [12]

    Fabris, N

    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

    2025

  5. [13]

    Fukuchi, S

    K. Fukuchi, S. Hara, and T. Maehara. Faking fairness via stealthily biased sampling. InAAAI, volume 34, pages 412–419, 2020

    2020

  6. [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. InProceedings of the 2025 FAccT, page 29–44, 2025

    2025

  7. [15]

    Godinot, E

    A. Godinot, E. L. Merrer, G. Trédan, C. Penzo, and F. Taïani. Under manipulations, are some ai models harder to audit? In2024 SaTML (SaTML), page 644–664, 2024

    2024

  8. [16]

    H. Hofmann. Statlog (German Credit Data). UCI Machine Learning Repository, 1994

    1994

  9. [17]

    Maneriker, C

    P. Maneriker, C. Burley, and S. Parthasarathy. Online fairness auditing through iterative refinement. InProceedings of the 29th KDD, page 1665–1676, 2023

    2023

  10. [18]

    European and Union, C. o. t. E. Parliament. Regulation (eu) 2024/1689: Artificial intelligence act. Official Journal of the European Union, 2024

    2024

  11. [19]

    Shahin Shamsabadi, M

    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

    2022

  12. [20]

    J. J. Smith, M. Madaio, R. Burke, and C. Fiesler. Pragmatic fairness: Evaluating ml fairness within the constraints of industry. InProceedings of the 2025 FAccT, page 628–638, 2025

    2025

  13. [21]

    Yan and C

    T. Yan and C. Zhang. Active fairness auditing. InICML, pages 24929–24962, 2022

    2022

  14. [22]

    Zhang, S

    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 APREPRINT- AUGUST4, 2026 A Omitted Proofs We present the proofs of Theorem 1, Theorem 2, and Propos...

    2021

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.