Fairness Auditing: Lower Bounds on Company Manipulation

• URL: http://arxiv.org/abs/2608.00568v1
• Date: Sat, 01 Aug 2026 10:11:20 GMT
• Title: Fairness Auditing: Lower Bounds on Company Manipulation
• Abstract summary: Fairness audits are increasingly mandated in high-stakes applications such as hiring, lending, and automated decision-making.<n>Recent work has established fundamental impossibility results for black-box fairness auditing.<n>We quantify the extent of unavoidable post-audit manipulation under finite audit resources.
• Score: 4.867679624126028
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 α-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.

Related papers

• Manipulation-Proof Oblivious Audits against Deceptive Model Providers [4.614773550999029]
  In regulatory contexts, audits are typically declared or easily detected, enabling model providers to manipulate the process.<n>This vulnerability is particularly acute in the context of fairness evaluations.<n>We introduce a novel audit protocol designed to significantly increase the post-audit detectability of such manipulations.
  arXiv  Detail & Related papers  (2026-08-05T02:12:54Z)
• BRA-Audit: Budgeted Runtime Auditing for LLM Multi-Agent Systems via Cumulative-Exposure Audit-Point Placement [5.4775608854724345]
  Multi-agent systems (LLM-MAS) solve complex tasks through specialized collaboration, but inter-agent dependencies can propagate hallucinated or malicious outputs into system-level failures.<n>We propose BRA-Audit, a budget-aware runtime auditing framework that models MAS execution as a dynamic dependency graph and formulates audit scheduling as audit-point placement under a fixed audit-call budget to minimize cumulative unchecked exposure.<n>Across structured coordination, complex reasoning, and open-ended tasks, BRA-Audit restores performance close to the clean setting, remains competitive with heavy guard methods and reduces end-to-end token consumption by (
  arXiv  Detail & Related papers  (2026-08-02T14:35:43Z)
• Sequential Fairness Auditing with Limited Output Access [6.933020649563105]
  External evaluations are becoming increasingly central to the governance of AI systems.<n>In practice, independent auditors often have limited access to deployed models and must rely on query-based interactions.<n>Most existing fairness evaluation methods assume static datasets and fixed-sample statistical tests.<n>We formulate fairness auditing as a tolerance-aware sequential hypothesis-testing problem under limited model output access.
  arXiv  Detail & Related papers  (2026-06-29T14:17:33Z)
• Bayesian control for coding agents [63.64172141184361]
  We propose a cost-sensitive sequential hypothesis testing framework for coding agents.<n>A Bayesian controller maintains a belief over correctness and decides whether to gather more evidence, refine the candidate, verify it, or stop.<n>We show that the belief state yields an interpretable correctness score that outperforms token-probability and raw tool-success baselines for uncertainty quantification.
  arXiv  Detail & Related papers  (2026-06-23T11:41:32Z)
• Time to REFLECT: Can We Trust LLM Judges for Evidence-based Research Agents? [61.49434544687523]
  We introduce REFLECT, a meta-evaluation benchmark targeting fine-grained failure detection in agentic environments.<n> REFLECT defines a detailed taxonomy of process- and outcome-level failure modes, instantiated by performing controlled and localized interventions.<n>Our experiments show that even the best-performing models achieve overall accuracies below 55% across reasoning, tool-use, and report-quality failures.
  arXiv  Detail & Related papers  (2026-05-18T23:55:08Z)
• IMMACULATE: A Practical LLM Auditing Framework via Verifiable Computation [49.796717294455796]
  We present IMMACULATE, a practical auditing framework that detects economically motivated deviations.<n>IMMACULATE selectively audits a small fraction of requests using verifiable computation, achieving strong detection guarantees while amortizing cryptographic overhead.
  arXiv  Detail & Related papers  (2026-02-26T07:21:02Z)
• Governing AI Forgetting: Auditing for Machine Unlearning Compliance [30.173215964349044]
  We introduce the first economic framework for auditing machine unlearning compliance, by integrating certified unlearning theory with regulatory enforcement.<n>We first characterize MU's inherent verification uncertainty using a hypothesis-testing interpretation of certified unlearning.<n>We then propose a game-theoretic model to capture the strategic interactions between the auditor and the operator.
  arXiv  Detail & Related papers  (2026-02-16T08:32:09Z)
• Preventing the Collapse of Peer Review Requires Verification-First AI [49.995126139461085]
  We propose truth-coupling, i.e. how tightly venue scores track latent scientific truth.<n>We formalize two forces that drive a phase transition toward proxy-sovereign evaluation.
  arXiv  Detail & Related papers  (2026-01-23T17:17:32Z)
• UniAud: A Unified Auditing Framework for High Auditing Power and Utility with One Training Run [9.400936999321415]
  We propose a unified framework, UniAud, for data-independent auditing.<n>We then extend this framework as UniAud++ for data-dependent auditing.<n>We show that our framework matches the state-of-the-art auditing results of O(T) auditing with thousands of runs.
  arXiv  Detail & Related papers  (2025-07-06T16:35:48Z)
• Auditing for Bias in Ad Delivery Using Inferred Demographic Attributes [50.37313459134418]
  We study the effects of inference error on auditing for bias in one prominent application: black-box audit of ad delivery using paired ads.<n>We propose a way to mitigate the inference error when evaluating skew in ad delivery algorithms.
  arXiv  Detail & Related papers  (2024-10-30T18:57:03Z)
• The Decisive Power of Indecision: Low-Variance Risk-Limiting Audits and Election Contestation via Marginal Mark Recording [51.82772358241505]
  Risk-limiting audits (RLAs) are techniques for verifying the outcomes of large elections. We define new families of audits that improve efficiency and offer advances in statistical power. New audits are enabled by revisiting the standard notion of a cast-vote record so that it can declare multiple possible mark interpretations.
  arXiv  Detail & Related papers  (2024-02-09T16:23:54Z)
• RESHAPE: Explaining Accounting Anomalies in Financial Statement Audits by enhancing SHapley Additive exPlanations [1.3333957453318743]
  We propose (RESHAPE) which explains the model output on an aggregated attribute-level. Our results show empirical evidence that RESHAPE results in versatile explanations compared to state-of-the-art baselines. We envision such attribute-level explanations as a necessary next step in the adoption of unsupervised DL techniques in financial auditing.
  arXiv  Detail & Related papers  (2022-09-19T16:23:43Z)
• Learning Sampling in Financial Statement Audits using Vector Quantised Autoencoder Neural Networks [1.2205797997133396]
  We propose the application of Vector Quantised-Variational Autoencoder (VQ-VAE) neural networks. We demonstrate, based on two real-world city payment datasets, that such artificial neural networks are capable of learning a quantised representation of accounting data.
  arXiv  Detail & Related papers  (2020-08-06T09:02:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.