{"id":"eedbe4b1-c4f2-45c0-8d6c-0baaa8f17fc8","arxiv_id":"2608.00568","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A company can always raise demographic parity violation by at least (N-B)/s_max by flipping un-audited samples, but the paper's alpha-tolerant auditi ng extension is not supported by its proofs.","lead":"This paper derives lower bounds on how much a company can distort a model's demographic parity after passing a budget-limited fairness audit. The simple budget-only bound is sound, but the more complex tolerance-aware bound and the balanced-audit variant fail under their own equations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2 is numerically false: an admissible instance has worst-case deviation 0.45 while the claimed lower bound is 1.1.","rationale":"The reader rejected the paper on proof gaps; my pass found a sharper, load-bearing problem: Theorem 2's closed-form bound is contradicted by an admissible numerical instance. I verified that the counts satisfy the group-0-privileged convention and the α-tolerance interval. The explicit audit set shows the minimax value is at most 0.45, while the claimed lower bound is 1.1, which also exceeds the absolute upper bound 0.9. This is not a question of tightness or of an unproven structural lemma; a lower bound that exceeds an unconditional upper bound cannot be repaired by filling in the proof. The same family of issues affects Proposition 1, whose final replacement of smax by s0 uses the wrong inequality direction when s0<s1. Because the paper's main quantitative claims are false as stated, rejection is appropriate. I agree with the reader that Theorem 1 is the only clean result; the α-tolerant contribution fails.","tokens_in":11969,"tokens_out":29123,"duration_ms":273859,"concrete_test":"Recompute WCD_{B,α}(h*) for the instance x00=2, x01=8, x10=6, x11=14, B=10, α=0.3. The theorem predicts the lower bound 1.1. An explicit feasible α-tolerant audit set S with 2 X00, 2 X01, 1 X10, and 5 X11 achieves sup_{h consistent with S} (Δ(h)−Δ(h*)) = 0.45, and the unconditional upper bound is 0.9. If these computations are confirmed, Theorem 2 is false as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central advertised result, Theorem 2, is not merely under-proved; it is contradicted by a concrete instance. Take x00=2, x01=8 (so s0=10) and x10=6, x11=14 (so s1=20). Then Δ(h*)=8/10−14/20=0.1, so group 0 is privileged; N=16, smax=20. Set B=10, α=0.3, so t=0.4. Theorem 2's bound is (16−10)/20 + 6(20−10·0.4)/(10·20·0.6) = 0.3 + 0.8 = 1.1. But the company's increase can never exceed x00/s0 + x11/s1 = 0.2+0.7=0.9, since only X00 and X11 samples are flippable. Thus the claimed lower bound exceeds the unconditional maximum possible deviation by 0.2. Concretely, the α-tolerant audit set with 2 X00, 2 X01, 1 X10, and 5 X11 has size 10 and Δ(S,h*)=|2/4−5/6|=1/3, which is within 0.3 of Δ(h*)=0.1. This S monitors all X00 and leaves 9 of 14 X11 unmonitored, so the company's best deviation is 9/20=0.45. Hence WCD_{B,α}(h*) ≤ 0.45 < 1.1, contradicting Theorem 2. The example even satisfies the proof's own feasibility requirements: x10/(1−t)=10≤B and ≤x11. This is a decisive numerical falsification of the main α-tolerant lower bound, not just a gap in the structural lemma.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12498,"tokens_out":8935,"duration_ms":102243,"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":[{"comment":"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.","section":"Theorem 2, Section 4.2"},{"comment":"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.","section":"Appendix A.2, Lemmas 1-3"},{"comment":"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.","section":"Proposition 1, Section 4.3"}],"minor_comments":[{"comment":"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.","section":"Throughout"},{"comment":"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.","section":"Appendix A.2, Lemma 1"},{"comment":"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.","section":"References"},{"comment":"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.","section":"Figures 2-4"}],"recommendation":"reject","confidential_remarks":"The reader's stress-test counterexample is correct and decisive. Both Theorem 2 and Proposition 1 are contradicted by simple admissible instances, so the paper's central claims are false. The failure is not an omitted proof or a stylistic issue; the closed-form bounds exceed the unconditional maximum possible manipulation. Even a major revision would require replacing the central theorems with different results, so rejection is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nQuick take: this paper has one correct result, a simple counting bound, and two advertised results that don't hold up. Theorem 2 is numerically contradicted by an admissible example; Proposition 1 has a sign error. Not publishable in current form, and I don't think a referee cycle fixes it without redoing the core derivation.\n\nWhat's new: the min-max formulation is clean, and the question—how much post-audit DP deviation is unavoidable given a finite budget and a tolerance constraint—is worth asking. Theorem 1, saying the company can always get at least (N-B)/s_max, is true and tight when group sizes are equal. It's not deep; it's essentially “you can only monitor B of the N flippable points,” but it's correctly proven.\n\nThe trouble is in the alpha-tolerant part. Lemma 3's allocation doesn't account for the non-manipulated samples the proof itself puts into the audit set, so the claimed closed form doesn't follow. Worse, Theorem 2 is false as stated. The stress-test example works: with x00=2, x01=8, x10=6, x11=14, B=10, alpha=0.3, the claimed bound is 1.1, but the max possible deviation is x00/s0 + x11/s1 = 0.9, and there's an actual audit set of size 10 satisfying tolerance that keeps the company's best deviation at 0.45. A lower bound that exceeds the unconditional maximum is impossible. So this is not a missing proof step; the statement itself is wrong. The issue is exactly the term involving x10, which the tolerance constraint is supposed to capture but is over-counted.\n\nProposition 1 has a similar problem: the proof replaces s_max by s0 using 1/s_max <= 1/s0, which is the wrong direction for a lower bound; the bound can be invalid for s1>s0. Minor: the experimental section is honest about being illustrative, but the baselines and heuristics aren't the point.\n\nWho this is for: someone who wants to cite a clean version of the budget-only bound might get something, but they can derive it themselves. The alpha-tolerant result is the reason to read the paper, and it's broken. I'd desk-reject with a detailed note; a referee would come back with the same counterexample.\n\nBest.","headline":"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.","tokens_in":12835,"tokens_out":3038,"would_cite":false,"duration_ms":33517,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Finite-budget fairness audits cannot prevent a guaranteed post-audit bias increase.","keywords":["fairness auditing","demographic parity","post-audit manipulation","lower bounds","min-max game","audit budget","alpha-tolerant auditing"],"falsifier":"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.","tokens_in":11904,"feed_emoji":"⚖️","tokens_out":8148,"duration_ms":95665,"temperature":0.7,"pith_summary":"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.","feed_headline":"Finite fairness audits can't stop a guaranteed bias increase","feed_subtitle":"New lower bounds show exactly how much post-audit unfairness a strategic company can always keep.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"proves that black-box auditing cannot beat uniform random sampling for expressive hypothesis classes, the impossibility result this paper quantifies and extends","marker":"[15]"},{"why":"introduces manipulation-proof fairness auditing and the company-present-compliant-model-then-deploy-different-model setup used throughout","marker":"[21]"},{"why":"supplies the reductions-based method used in experiments to find the most biased classifier consistent with an audit set","marker":"[1]"},{"why":"supports the assumption that over-parameterized models can memorize arbitrary labelings, which justifies treating the company as computationally unbounded","marker":"[22]"}],"fun_headline_variants":["Guaranteed bias growth after any finite fairness audit","Finite audits leave a floor of post-audit unfairness","Audit budgets shrink bias but can't erase it","Lower bound: post-audit bias always remains","Strategic firms keep bias edge after audits"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Guaranteed bias growth after any finite fairness audit","Finite audits leave a floor of post-audit unfairness","Audit budgets shrink bias but can't erase it","Lower bound: post-audit bias always remains","Strategic firms keep bias edge after audits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000265,"raw_usage":{"total_tokens":1452,"prompt_tokens":762,"completion_tokens":690,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":506,"completion_tokens_details":{"reasoning_tokens":614}},"tokens_in":506,"tokens_out":690,"duration_ms":8261,"temperature":1.0,"reasoning_tokens":614,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T00:40:33.457107+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Godinot, E","cited_arxiv_id":null,"evidence_quote":"proves that black-box auditing cannot beat uniform random sampling for expressive hypothesis classes, the impossibility result this paper quantifies and extends"},{"cited_title":"Yan and C","cited_arxiv_id":null,"evidence_quote":"introduces manipulation-proof fairness auditing and the company-present-compliant-model-then-deploy-different-model setup used throughout"},{"cited_title":"Agarwal, A","cited_arxiv_id":null,"evidence_quote":"supplies the reductions-based method used in experiments to find the most biased classifier consistent with an audit set"},{"cited_title":"Zhang, S","cited_arxiv_id":null,"evidence_quote":"supports the assumption that over-parameterized models can memorize arbitrary labelings, which justifies treating the company as computationally unbounded"}],"review_version":1}