{"id":"8abf7d73-2f90-49fa-a9f3-a8ebf497cf20","arxiv_id":"2501.15634","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Across all models within a small accuracy loss of the best classifier, an intentionally chosen fair model can be far fairer than a random one, and individual flip likelihoods follow a simple logistic curve.","lead":"The paper studies the set of all models that match a base classifier's accuracy within a small margin, and shows these models can differ sharply in fairness, so choosing fairly on purpose matters. It gives formulas for how often individual predictions flip across the set, how large the set is, and fast ways to find fairer models.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The asymptotic flip-probability and set-size formulas are not actually proven: Appendix C assumes the rate function it is trying to derive, then uses it to prove itself.","rationale":"The reader's weakest assumption, that the framework uses all 2^N labelings including non-functional ones, is a real limitation but it is explicitly acknowledged in Section 3 and Appendix C; it bounds the policy reach but does not threaten the mathematical claims about the largest possible Rashomon set. The Algorithm 1 exactness issue is concrete but secondary to the headline formulas. The circularity in Appendix C is the most load-bearing concern because Theorems 5.1, 6.1, and 6.2, which are the claimed new quantitative results, all depend on it. If the rate-function limit or its derivative does not exist, the closed forms are unsupported. The paper has genuine independent support: experiments on three datasets, a robustness check with XGBoost, and a transparent statement of the idealized model class. For these reasons, the conditional verdict is appropriate, and I do not recommend changing it; rejection is not warranted because the formulas are likely correct and an independent large-deviations proof may close the gap.","tokens_in":41367,"tokens_out":14157,"duration_ms":144849,"concrete_test":"Re-derive Theorem 6.1 from first principles via Cramer's theorem on i.i.d. pairs (w_i, theta_i) with theta_i Bernoulli(1/2), without ever invoking Lemma C.5's pre-assumed limit. In particular, compute the rate function sup_{lambda>=0}[lambda*eps - log E[(1+e^{lambda*w})/2]] and check that the optimizer satisfies eps = E[w/(1+e^{lambda*w})] and that the integral of the optimizer with respect to eps reproduces log B(eps). If this independent re-derivation fails or yields a different B(eps), the central formulas are not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central asymptotic claims (Theorems 5.1, 6.1, and 6.2) rest on a circular derivation in Appendix C. Lemma C.5 defines log B(eps)=lim_N log|R_N(eps)|/N, asserts this limit exists, and differentiates it with respect to eps to derive pairwise independence. Lemma C.6 then uses pairwise independence to obtain q(w)=1/(1+exp(Cw)), and Lemma C.7 uses that same C to 'prove' the limit for log|R_N(eps)|/N. Thus the existence and differentiability of log B are assumed before they are established, and the identities C(eps)=g^{-1}(eps) and B(eps)=exp(integral_0^eps C(x)dx) have no independent derivation in the paper. If the true rate function differs from the assumed one, the flip-probability formula, the exponential set-size law, and the full-tolerance saturation result all fail together, since each is derived from the same C. The formula is plausible and matches a standard Gibbs-conditioning/large-deviations calculation, but the paper as written does not supply that argument, so the quantitative claims are not yet supported by the proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the 'largest possible Rashomon set' for binary classification: all 2^N labelings of N i.i.d. records whose expected accuracy is within an error tolerance epsilon of the Bayes-optimal classifier. It contributes efficient algorithms for optimizing statistical parity and error-rate balance over this set, a Gibbs sampler for uniform sampling, and asymptotic formulas for individual flip probabilities, set size, and the average fraction of error tolerance used. These results are used to argue that intentionally searching for fair models within the Rashomon set yields much larger fairness gains than random sampling, and to draw policy conclusions about LDA searches. Experiments on German Credit, Adult, and Heritage Health support the qualitative findings.","tokens_in":1744,"tokens_out":1701,"duration_ms":211334,"significance":"If the theoretical results are correct, this is a significant contribution to the predictive-multiplicity literature: it provides the first general quantitative characterization of individual flip probabilities, exponential set size, and average error usage for the maximal Rashomon set, along with practical O(N log N) optimization algorithms and an efficient sampler. The paper is clearly written, is unusually candid about the limitations of the 'largest possible' model space, and includes extensive experiments with a robustness check. However, the three central asymptotic theorems rest on a circular derivation in Appendix C, and Algorithm 1 does not in fact solve the claimed exact optimization problem; both issues must be repaired before the results can be relied upon.","major_comments":[{"comment":"The central asymptotic results are not independently proven. Lemma C.5 defines log B(epsilon) = lim_N log|R_N(epsilon)|/N, assumes this limit exists and is differentiable, and uses that assumption to prove pairwise independence of flip probabilities. Lemma C.6 then derives the logistic form q(w)=1/(1+exp(Cw)) from this pairwise independence, and Lemma C.7 uses that same logistic form to 'prove' the existence and formula for log B(epsilon). Corollary C.10 derives C(epsilon)=g^{-1}(epsilon) from Theorem C.9, which itself relies on Lemmas C.6 and C.7. Thus Theorems 5.1, 6.1, and 6.2 all depend on the very limit whose existence and differentiability they are supposed to establish. The formulas are plausible and match a standard large-deviations/Gibbs-conditioning calculation, but the paper does not supply that argument. A non-circular proof is required, for example by proving a large-deviation principle for the empirical mean of the weights under independent Bernoulli(1/2) flips and then applying the Gibbs conditioning principle to obtain the tilted product measure.","section":"Appendix C, Lemmas C.5-C.7, Corollary C.10, Theorems 5.1, 6.1, 6.2"},{"comment":"Algorithm 1 does not find the exact fairest model for PPR disparity as claimed. The algorithm maximizes k_A/|A| + k_B/|B|, the total disparity reduction, without capping this reduction at the initial disparity id. If the maximum feasible reduction exceeds id, the resulting model overshoots and the absolute disparity |id - (k_A/|A| + k_B/|B|)| is not minimized; a smaller undershooting reduction can produce a strictly fairer model. Consequently the claim of exact optimality in Section 4.1.1 and the optimal-disparity curves in Figure 1 are not justified. The algorithm should minimize |id - reduction| (equivalently, stop flipping once disparity reaches zero) and the experiments should be rerun with the corrected objective.","section":"Section 4.1.1, Algorithm 1"},{"comment":"The closed-form expression for g(C) is incorrect as written. The stated formula g(C) = ∫_0^1 w/(1+e^{Cw})dw = 12 Li_2(-e^{-C}) - 12 C log(e^{-C}+1) + pi^2/(12C^2) is dimensionally inconsistent and diverges as C->0, whereas the integral tends to 1/4. The correct expression is g(C) = [Li_2(-e^{-C}) - C log(1+e^{-C}) + pi^2/12]/C^2, or equivalently Li_2(-e^{-C})/C^2 - log(1+e^{-C})/C + pi^2/(12C^2). This error affects the claimed exact value for uniformly distributed weights in Corollary C.14 and the corresponding curve in Figure 3(left).","section":"Corollary C.11"},{"comment":"The definition of a model is internally inconsistent. Section 3 defines a predictive model as a mapping from input features x_i to decisions, which implies deterministic functions of x, while Appendix C states that the classifier can be probabilistic and that two records with identical x_i may receive different predictions. Since the entire theoretical framework counts arbitrary labelings of the N records as distinct models, the paper should define a model as an assignment of labels to the N records (an element of {0,1}^N) rather than as a function of x. This would also make the 'largest possible Rashomon set' assumption explicit from the outset.","section":"Section 3 vs. Appendix C"}],"minor_comments":[{"comment":"The assumption that the weight distribution f(w) is continuous and positive on [0,1] is stated as 'reasonable' for the three datasets, but no diagnostic is provided. A histogram of the estimated weights, or a sensitivity analysis showing that the conclusions are robust to discretization, would make the application of the large-sample theorems to finite datasets more credible.","section":"Section 5.1, Assumption (2)"},{"comment":"The Gibbs sampler's uniform stationary distribution is argued heuristically, but no mixing-time bound or convergence diagnostics (e.g., trace plots, Gelman-Rubin statistic) are reported. The 950 samples used in the experiments may therefore be correlated; adding diagnostics or a rigorous ergodicity statement for this down-closed state space would strengthen the empirical claims.","section":"Appendix B"},{"comment":"Several policy takeaways are phrased for companies performing LDA searches without repeating the caveat that the quantitative results apply to the largest possible Rashomon set of all 2^N labelings, not to restricted model classes. The paper should state in the abstract and conclusion that the computed set sizes and flip probabilities are upper bounds for practical model classes, as the linear-model experiments in Section 6.4 already demonstrate.","section":"Sections 4.4 and 6.4"},{"comment":"There are several typographical issues, including 'q_N.j' in the proof of Lemma C.5, an apparent stray '0 0' in Section 5.2, and inconsistent use of 'FPR' vs. 'FPR disparity' in the appendix. These should be cleaned up before final submission.","section":"General typography"}],"recommendation":"major_revision","confidential_remarks":"The circularity in Appendix C is the primary obstacle: the three headline asymptotic theorems are currently not proven. I believe the intended results are correct and a standard large-deviations argument would fix the gap, so I recommend major revision rather than rejection. The Algorithm 1 overshoot issue is also load-bearing and must be corrected, since it affects the experimental optimality claims. The paper is otherwise well motivated and clearly written, and I would be willing to review a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the useful parts. The paper gives a clean setup for the largest possible binary-classification Rashomon set based on expected accuracy, a Gibbs sampler that empirically samples it uniformly, and two knapsack algorithms that are genuinely efficient (O(N log N)) and improve on Laufer et al.'s O(N^3) approach. The experiments on German, Adult, and Health clearly show that optimizing fairness inside the set beats random sampling, and that full disparity removal is often possible at very small epsilon. That qualitative result is important and will be cited. The flip-probability asymmetry between groups is also a nice, policy-relevant observation.\n\nThe soft spots are real, though. The big one is the proof of Theorems 5.1, 6.1, and 6.2. Appendix C assumes the limit log B(eps) = lim log|R_N(eps)|/N exists and is differentiable in Lemma C.5, uses that to prove pairwise independence and the logistic form q(w) = 1/(1+exp(C w)), then Lemma C.7 'derives' the same limit from that logistic form. That is circular. The constants C(eps) and B(eps) are plausible—this looks like a standard conditioning/large-deviations calculation—but the paper does not supply that argument. As written, the quantitative claims are unsupported by the proofs. Second, Algorithm 1 does not cap its knapsack value at the initial disparity, so it can select flips that overshoot zero disparity; the exactness claim for PPR is not justified. Third, the model class is the set of all 2^N labelings, including non-functional ones; the paper is explicit about this, but the flip probabilities are for an idealized set, not for trainable models, and that limitation should be in the abstract.\n\nWhat holds up: the qualitative conclusion that intentional search matters does not depend on the asymptotic theorems, and the algorithms are useful even if the PPR exactness claim needs a fix. The experimental design is transparent.\n\nRecommendation: send to peer review, but the authors need to repair the circular proof—either provide a genuine rate-function argument or demote the theorems to conjectures and focus the contribution on the algorithms and experiments. A serious referee can help them get there.","headline":"The empirical message on intentional fairness is well supported and the algorithms are useful, but the headline asymptotic theorems are not actually proven as written: the derivation of the rate function is circular.","tokens_in":42105,"tokens_out":4613,"would_cite":false,"duration_ms":44414,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The largest possible set of equally accurate models has closed-form size, per-person flip odds, and a large fairness gap between random and best picks.","keywords":["model multiplicity","Rashomon set","fairness","statistical parity","flip probability","predictive multiplicity","less discriminatory alternatives","model arbitrariness"],"falsifier":"On a synthetic dataset with known Bayes-optimal probabilities $p_i$ (so $w_i$ and the weight density $f(w)$ are exactly known), enumerate the full Rashomon set for moderate $N$ by checking all $2^N$ flip vectors, and compare the exact flip probability $q_{N,i}$, the exact size $|R_N(\\varepsilon)|$, and the average error use to the asymptotic formulas $q(w)=1/(1+\\exp(C(\\varepsilon)w))$, $B(\\varepsilon)^N$, and $\\varepsilon$; a systematic gap that does not shrink as $N$ grows would falsify the large-sample claims.","tokens_in":41063,"feed_emoji":"⚖️","tokens_out":10216,"duration_ms":75269,"temperature":0.7,"pith_summary":"The paper asks whether, among models of nearly equal accuracy, deliberately searching for a fairer model is worth the trouble. It answers yes, and backs the answer with an asymptotic theory of the Rashomon set, the set of all binary classifiers whose expected accuracy is within a tolerance $\\varepsilon$ of the Bayes-optimal model. Treating every record as a binary decision that may be flipped, the authors show that each record's probability of changing prediction across the set has the closed form $q(w)=1/(1+\\exp(C(\\varepsilon)w))$, that the set's size grows as $B(\\varepsilon)^N$, and that for large datasets almost every model in the set uses the full error tolerance. These formulas let practitioners compute individual arbitrariness, group-level flip disparities, and the maximum fairness available in the set, suggesting that fairness gains require an intentional search and that companies setting the tolerance should expect it to be fully consumed.","feed_headline":"One formula gives each person's flip odds among equal-accuracy models","feed_subtitle":"Closed-form flip odds, set size, and fairness limits—plus why an intentional search beats random sampling.","key_machinery":"The machinery is the flip-vector representation $\\theta\\in\\{0,1\\}^N$: every model is described by which records differ from the Bayes-optimal prediction, and membership in the Rashomon set becomes a single knapsack constraint $\\theta\\cdot W_N/N\\le\\varepsilon$, where $W_N$ holds the per-record weights $w_i=|2p_i-1|$. The same representation carries all five contributions: a 0-1 knapsack (for statistical parity) and a fractional knapsack (for FPR/TPR) find fair models in $O(N\\log N)$; a Gibbs sampler over the constraint set samples models uniformly; and the integral equation $g(C)=\\int_0^1 \\frac{w f(w)}{1+\\exp(Cw)}dw=\\varepsilon$ pins down the asymptotic flip probabilities, from which the exponential growth base $B(\\varepsilon)=\\exp(\\int_0^\\varepsilon C(x)dx)$ and the full-tolerance-usage result follow.","core_discovery":"On its own terms, the paper's central claim is that the largest possible Rashomon set, the $2^N$ binary labelings of $N$ i.i.d. records within $\\varepsilon$ of optimal expected accuracy, has a tractable large-sample geometry. As $N\\to\\infty$, the uniform distribution over the set gives each record $i$ a flip probability $q(w_i)=1/(1+\\exp(C(\\varepsilon)w_i))$, where $w_i=|2p_i-1|$ is the Bayes-optimal classifier's confidence and $C(\\varepsilon)$ is the unique solution of $\\int_0^1 \\frac{w f(w)}{1+\\exp(Cw)}dw=\\varepsilon$. The set's cardinality converges to $|R_N(\\varepsilon)|=B(\\varepsilon)^N$ with $B(\\varepsilon)=\\exp(\\int_0^\\varepsilon C(x)dx)$, and the average model spends the entire tolerance, so $\\mathrm{acc}(\\theta_0)-\\mathrm{acc}(R_N(\\varepsilon))\\to\\varepsilon$. For fairness, the flip-vector representation turns optimization of statistical parity into an $O(N\\log N)$ knapsack problem with an exact solution, and error-rate-balance optimization into a fractional knapsack with $O(1/N)$ suboptimality, starkly contrasting with the NP-hardness of searching over restricted model classes. Across three benchmark datasets, the gap between the fairest model and a uniformly random one is large, and disparities can often be eliminated with $\\varepsilon$ below half a percent.","pith_inferences":["Because the theory characterizes the largest possible Rashomon set, its flip probabilities and fairness maxima are upper bounds for any realistic model class; for restricted classes (like the paper's linear baselines) the same quantities are likely smaller, so real LDA searches would need re-calibration rather than direct use of these formulas.","The $q(w)$ formula implies that flip chance is a function of confidence only, so any two individuals with the same distance from the decision boundary have the same arbitrariness risk; if confidence estimates are miscalibrated, flip probabilities will inherit the miscalibration.","One could turn the flip-probability formula into a disclosure requirement for algorithmic systems: an individual could be told not just the prediction but the probability that the prediction would change across equally accurate models, making arbitrariness concrete per person.","The full-tolerance result suggests a caution for LDA policies: if regulators require firms to search the Rashomon set, firms will exploit the full $\\varepsilon$ cap, so policy should not only set the tolerance but also monitor the accuracy actually delivered by the deployed model."],"forward_implications":["Fairness within equal-accuracy sets is a design choice: a randomly chosen model sits far from the fairest one, so deploying any high-accuracy model without an explicit fairness search forgoes most of the achievable disparity reduction.","Per-person flip probabilities are computable in closed form, so arbitrariness can be audited per individual and per group before deployment, without sampling any models.","The Rashomon set grows as $B(\\varepsilon)^N$, so each small increase in the allowed error tolerance multiplies the number of equally accurate alternatives; the same result shows the average model consumes the full tolerance, so a wider search comes with the certainty that the deployed model will sit at the edge of the accuracy budget.","For statistical parity the fairest model can be found exactly in $O(N\\log N)$ time, and for error-rate balance within $O(1/N)$ of optimal, giving practical less-discriminatory-alternative search algorithms for the largest possible Rashomon set."],"supporting_citations":[{"why":"Establishes the NP-hardness baseline for fairness search over the Rashomon set that the paper's O(N log N) algorithms contrast with.","marker":"[21]"},{"why":"Provides the legal less-discriminatory-alternative doctrine that motivates the question of how much fairness can be gained by intentional search.","marker":"[3]"},{"why":"Defines predictive multiplicity, the phenomenon the paper formalizes through flip probabilities and set size.","marker":"[22]"},{"why":"Introduces the Rashomon effect term for multiple equally accurate models, the object studied here.","marker":"[7]"},{"why":"Empirically shows that different individuals have different chances of prediction change across equivalent models, which the paper's Theorem 5.1 makes exact.","marker":"[9]"},{"why":"Supplies the Gibbs sampling framework used for uniform sampling from the Rashomon set.","marker":"[14]"},{"why":"Frames model multiplicity's opportunities and concerns, and the arbitrariness consequences the paper quantifies.","marker":"[5]"}],"fun_headline_variants":["Exact flip odds formula: pick fair models from equal-accuracy sets","Why random choice is unfair: Rashomon set flip probabilities","Fairness by design: closed forms for model multiplicity","Intentional search beats sampling in equally accurate models","The math of fair model selection in the Rashomon set"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole theory assumes the Rashomon set—the set of equally accurate models—is every possible assignment of predictions to the observed records, even assignments that treat identical people differently and that no training procedure could produce; if the models a company can actually build form a much smaller set, the computed flip chances, set sizes, and fairness gains are ceilings, not predictions.","fun_headline_variants_meta":{"raw":{"variants":["Exact flip odds formula: pick fair models from equal-accuracy sets","Why random choice is unfair: Rashomon set flip probabilities","Fairness by design: closed forms for model multiplicity","Intentional search beats sampling in equally accurate models","The math of fair model selection in the Rashomon set"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000352,"raw_usage":{"total_tokens":2002,"prompt_tokens":1114,"completion_tokens":888,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":730,"completion_tokens_details":{"reasoning_tokens":807}},"tokens_in":730,"tokens_out":888,"duration_ms":8386,"temperature":1.0,"reasoning_tokens":807,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T14:05:45.001956+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On a synthetic dataset with known Bayes-optimal probabilities $p_i$ (so $w_i$ and the weight density $f(w)$ are exactly known), enumerate the full Rashomon set for moderate $N$ by checking all $2^N$ flip vectors, and compare the exact flip probability $q_{N,i}$, the exact size $|R_N(\\varepsilon)|$, and the average error use to the asymptotic formulas $q(w)=1/(1+\\exp(C(\\varepsilon)w))$, $B(\\varepsilon)^N$, and $\\varepsilon$; a systematic gap that does not shrink as $N$ grows would falsify the large-sample claims.","supporting_citations":[{"cited_title":"What Constitutes a Less Discriminatory Algorithm?","cited_arxiv_id":"2412.18138","evidence_quote":"Establishes the NP-hardness baseline for fairness search over the Rashomon set that the paper's O(N log N) algorithms contrast with."},{"cited_title":"L., Kim, P., Barocas, S., and Hsu, M","cited_arxiv_id":null,"evidence_quote":"Provides the legal less-discriminatory-alternative doctrine that motivates the question of how much fairness can be gained by intentional search."},{"cited_title":"T., du Pin Calmon, F., and Ustun, B","cited_arxiv_id":null,"evidence_quote":"Defines predictive multiplicity, the phenomenon the paper formalizes through flip probabilities and set size."},{"cited_title":"Statistical modeling: The two cultures (with comments and a rejoinder by the author), 2001","cited_arxiv_id":null,"evidence_quote":"Introduces the Rashomon effect term for multiple equally accurate models, the object studied here."},{"cited_title":"F., Lee, K., Choksi, M","cited_arxiv_id":null,"evidence_quote":"Empirically shows that different individuals have different chances of prediction change across equivalent models, which the paper's Theorem 5.1 makes exact."},{"cited_title":"Stochastic relaxation, gibbs distributions, and the bayesian restoration of images","cited_arxiv_id":null,"evidence_quote":"Supplies the Gibbs sampling framework used for uniform sampling from the Rashomon set."},{"cited_title":"Model multiplicity: Opportunities, concerns, and solutions","cited_arxiv_id":null,"evidence_quote":"Frames model multiplicity's opportunities and concerns, and the arbitrariness consequences the paper quantifies."}],"review_version":1}