{"id":"514fd695-cd9d-4f95-bd25-f7378be3f984","arxiv_id":"2507.20711","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Fairness is treated as a runtime property over coin-toss sequences, yielding a taxonomy of when monitoring or enforcement is possible.","lead":"This paper frames algorithmic fairness as a runtime property, modeled with sequences of biased coin tosses whose biases evolve over time. It unifies existing monitoring and enforcement results into one taxonomy and adds new guaranteed algorithms for several settings.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Problem 1 is trivially solved by the constant monitor returning [0,1], so the impossibility claim in Sec. 3.4.2 and the 'no one-size-fits-all' central thesis do not follow from the formal definitions.","rationale":"The reader's weakest assumption concerned the coin-toss abstraction's external validity, which is a legitimate but non-formal concern. The stress-test reveals a more fundamental, internal defect: the formal Problem 1 is vacuous because the constant monitor is always sound. This directly invalidates the paper's headline negative result and the central thesis that no one-size-fits-all monitor exists, unless the problem statement is augmented with a formal nontriviality or optimality criterion. This is not a disagreement with scientific consensus; it is a mismatch between the definitions and the claims. The appendix also contains a local error in Theorem 7's assumptions (Assumptions 10 and 12 vs. 5, 9, and 10), as the reader noted, but that is secondary and correctable. The trivial-monitor issue is load-bearing because the classification of monitoring problems into 'trivial,' 'impossible,' and 'solvable under assumptions' is the paper's stated contribution. The paper is salvageable: adding a formal notion of interval quality, or explicitly requiring monitors to be non-vacuous (e.g., interval length must decay to zero almost surely), would likely restore the impossibility result. However, as written, the central claim is not correct under the paper's own formalization, and the paper should not be relied upon as a reference until this is fixed.","tokens_in":20593,"tokens_out":8820,"duration_ms":100349,"concrete_test":"Verify that the constant monitor M(u) = [0,1] satisfies Eqs. (7) and (8) for the instance (Θ, φO, ∞, δ) used in the Sec. 3.4.2 impossibility claim. Since ρ^∞_t(W; φO) = Eθ(lim_{k→∞} (1/k) Σ_{i=1}^k X_i | w_{1:t}) is almost surely in [0,1] whenever the limit exists, the probability that ρ^∞_t ∈ [0,1] is 1, so both soundness inequalities hold. The impossibility proof then cannot go through using only the stated definitions; it requires an additional assumption, such as requiring the monitor's interval to be a strict subset of [0,1] or to converge in width to 0, which is not part of Problem 1.","verdict_should_be":"REJECT","load_bearing_attack":"The formal monitoring problem (Problem 1, Sec. 3.1) asks for a pointwise or uniformly sound monitor M : X* → I([0,1]) satisfying Eq. (7) or Eq. (8). The soundness conditions only require that the true runtime fairness value ρ^h_t(W; φ) lie in the output interval with probability at least 1−δ. For every finite outcome sequence u, the constant monitor M(u) = [0,1] satisfies both conditions trivially: because each φ is defined as an average of outcomes, an average of biases, or a single bias, all values lie in [0,1], and conditional expectations of [0,1]-valued random variables remain in [0,1]. Thus the event ρ^h_t(W; φ) ∈ [0,1] has probability 1 for every θ, t, h, φ. This constant monitor therefore solves Problem 1 for every instance (Θ, φ, h, δ), directly contradicting the paper's statement in Sec. 4 that 'There does not exist a monitor capable of solving Problem 1 in full generality.' The counterexample in Sec. 3.4.2 only shows that no monitor can infer the limit fairness value from finite prefixes; it does not show that no sound interval can be produced. The gap is internal: Sec. 3.3 explicitly defers any definition of interval quality or optimality, so the formal problem has no nontriviality constraint. The impossibility and the resulting taxonomy of feasible versus infeasible monitoring are actually claims about an unstated, stronger problem in which the monitor must, for instance, produce intervals that shrink to a point or otherwise exclude some values.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a runtime perspective on algorithmic fairness, modeling each step as a biased coin toss whose bias evolves under a history-dependent dynamics function. It defines three fairness measures (outcome, bias, and current fairness), lifts them to stochastic processes via conditional expectations, and poses two problems: monitoring fairness within a confidence interval and enforcing fairness within target intervals. The paper surveys existing monitoring results for static, Markovian, hidden Markovian, and additive dynamics, and existing enforcement results for static known dynamics, adding new results: a static-coin monitor with uniform confidence sequences, process-agnostic enforcement theorems (Theorems 1 and 2), and a probabilistic finite-window enforcer (Theorem 7). The central claim is that feasibility of monitoring and enforcement is fully determined by environment dynamics, prediction horizon, and confidence threshold, with no one-size-fits-all solution.","tokens_in":20913,"tokens_out":6259,"duration_ms":69430,"significance":"If the framework and taxonomy are made rigorous, the paper would provide a useful unified presentation of runtime fairness monitoring and enforcement, with clearly parametrized problem statements and a structured survey of recent results. The paper's strengths include explicit problem definitions, self-contained proofs for the new lemmas and theorems, correct use of established concentration inequalities (Hoeffding, Howard et al.) for static-coin monitoring, and honest discussion of scope limitations, including the admission in Section 7.1 that full generality of group fairness requires a richer state space. The paper also includes a valuable comparison of pointwise versus uniform soundness and of finite versus periodic enforcement windows. However, the formal monitoring problem as stated is currently degenerate: the constant monitor returning [0,1] solves every instance, so the claimed impossibility results and the associated taxonomy are not yet supported.","major_comments":[{"comment":"Problem 1 is trivially solvable in full generality by the constant monitor M(u)=[0,1]. For every φ∈{φ_O,φ_B,φ_C}, the runtime fairness value ρ^h_t(W;φ) is a conditional expectation of a [0,1]-valued random variable, hence lies in [0,1] almost surely under every dynamics θ, every t, h, and δ. Therefore both pointwise soundness (Eq. 7) and uniform soundness (Eq. 8) are satisfied. Section 3.3 explicitly states that aggregating interval quality is out of scope, so no nontriviality or tightness constraint is part of Problem 1. The counterexample in Section 3.4.2 shows only that no monitor can converge to the limit fairness value from finite prefixes, not that no sound interval can be produced. Consequently, the opening claim of Section 4 that \"There does not exist a monitor capable of solving Problem 1 in full generality\" and the ✗ entries in Table 1 are false as stated. The problem definition must be modified, for example by requiring the monitor to produce intervals that shrink with t, or by adding an explicit quality objective, before the infeasibility taxonomy can be sustained.","section":"Sec. 3.1 and Sec. 4"},{"comment":"Theorem 7 is stated under Assumptions 5, 9, and 10, but its proof in Appendix A.6 states that it holds under Assumptions 10 and 12, where Assumption 12 fixes δ=0. This is a substantive inconsistency: the main text presents Theorem 7 as a probabilistic guarantee for general δ∈(0,1), while the proof as written claims an almost-sure setting. The proof itself actually establishes a stronger statement for arbitrary δ under a feasibility condition P(t,h)>0, so the mismatch is fixable by aligning the assumption list and clarifying the quantifier over δ in both the statement and the proof.","section":"Sec. 5.1.1 and App. A.6"}],"minor_comments":[{"comment":"In the sentence \"P ⊆ [0,1] is a subset set of all coins,\" the word \"set\" is duplicated; it should read \"a subset of all coins.\"","section":"Sec. 2.2"},{"comment":"The sentence \"we only consider enforcers that overwrite bias our outcome, but not both\" contains a typo: \"our\" should be \"or.\"","section":"Sec. 3.3"},{"comment":"The expression ψ = p(1)θ(p,x)(p(1)) + p(2)θ(p,x)(p(1)) repeats p(1) in the second term; it should be p(2)θ(p,x)(p(2)).","section":"Sec. 4.2, Example 1"},{"comment":"The proof lists the two dangerous cases as \"φO(x1:(t−1)) ≤ p and xt = 0, or with φO(x1:(t−1)) ≤ p and xt = 0\"; the second case should be φO(x1:(t−1)) > p and xt = 1. In the same proof, the final displayed inequality in the second case should be φO(x1:t) ≤ p + 1/t, not > p + 1/t.","section":"App. A.1, Proof of Theorem 2"},{"comment":"Problem 1 defines the prediction horizon as h∈N, while the runtime fairness definition in Eq. (6) and several assumptions such as Assumption 2 allow h=∞. The definition of Problem 1 should be aligned to h∈N∪{∞}.","section":"Sec. 3.1"},{"comment":"The sentence \"for a sequence w1:t with t coins and h tails\" uses h for tails, but h was defined earlier as the number of heads; please correct the terminology to avoid confusion.","section":"App. A.6, Eq. (20)"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about the constant monitor is correct and blocks the central claim as currently stated. The fix is local to the problem definition—adding a nontriviality or quality requirement to Problem 1—so major revision rather than rejection is appropriate. The self-citation pattern is substantial, but this paper is explicitly positioned as a survey of the authors' own prior results, so I do not see it as an ethical concern. The Appendix statement of Theorem 7 should also be reconciled with the main text before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. The paper gives the runtime-fairness community a useful common vocabulary — unified problem statements for monitoring and enforcement, pointwise vs uniform soundness, a taxonomy of what is known under which dynamics assumptions. The new algorithms (Theorem 3's static-coin monitor with time-uniform confidence sequences, Theorem 7's probabilistic finite-window enforcer) are genuine and, aside from typos, correct. But the formal monitoring problem, Problem 1, is vacuous as written: the constant monitor that always outputs [0,1] satisfies both the pointwise and uniform soundness conditions for every instance, because every runtime fairness value is a conditional expectation of [0,1]-valued quantities and therefore always lies in [0,1]. That means the paper's headline claim — 'There does not exist a monitor capable of solving Problem 1 in full generality' — is false. The counterexample in Section 3.4.2 only shows that no monitor can infer the limit fairness from finite prefixes, not that no sound interval exists. The 'no one-size-fits-all' thesis for monitoring does not follow from the definitions.\n\nThis is not a nitpick. The problem statement is what the entire taxonomy in Table 1 hangs on. If [0,1] is a valid answer, then every monitoring cell is solvable, and the interesting content has to be smuggled back in through an unstated requirement that intervals be tight, shrink, or exclude some values. Section 3.3 explicitly punts on defining interval quality, so the gap is real and load-bearing. The fix is straightforward — add a nontriviality or quality condition to Problem 1 — but it needs to be done before the results are relied upon.\n\nWhat the paper does well: the survey portions faithfully restate prior work by Henzinger et al. and Cano et al., and the self-citation is legitimate since those results are peer-reviewed. The simple enforcers in Section 3.4 are correct. The new proofs are short and basically sound, though Theorem 7 has an inconsistency between the main-text assumptions (5, 9, 10) and the appendix proof (10 and 12), and Theorem 2's proof has a copy-paste typo in the second case.\n\nBottom line: this is a useful roadmap, worth serious refereeing, but the central formal claim needs major revision. I'd like to see a version with a proper nontriviality condition and fixed typos. As is, I wouldn't cite it for the impossibility result.","headline":"Useful survey and two new algorithms, but the monitoring problem is trivially solvable by the constant [0,1] monitor, so the central impossibility claim is false as stated.","tokens_in":21462,"tokens_out":3678,"would_cite":false,"duration_ms":43224,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q60","60J20","68T01"],"pacs":[],"model":"deepseek-v4-flash","headline":"Fairness can be studied as a runtime property of sequential decisions, and the feasibility of monitoring or enforcing it is determined entirely by the environment dynamics, prediction horizon, and confidence threshold.","keywords":["runtime fairness","runtime monitoring","runtime enforcement","biased coin processes","Markov chains","confidence intervals","conditional expectation","algorithmic fairness"],"falsifier":"Take a real logged decision stream, such as loan acceptances over several years, and estimate at each step the next-decision probability from the full history; if two prefixes with approximately the same scalar bias $p_t$ yield systematically different next-outcome probabilities, or if the monitor's confidence intervals exclude the empirical acceptance rate more often than $\\delta$, the coin-process representation of runtime fairness is falsified.","tokens_in":20370,"feed_emoji":"⚖️","tokens_out":6048,"duration_ms":66356,"temperature":0.7,"pith_summary":"This paper argues that fairness in AI is not a one-time static property but a runtime property of a sequential process, and it models each decision as a coin toss whose bias can evolve over time. Within this model it poses two problems: monitoring fairness by outputting a high-confidence interval, and enforcing fairness by intervening to keep it in a target interval. The paper's central finding is that neither problem has a universal solution; whether a monitor or enforcer exists, and how to build one, is fully determined by the environment dynamics, the prediction horizon, and the confidence level. Under no assumptions, infinite-horizon outcome fairness cannot be monitored at all, while finite-horizon outcome fairness is trivial; under static, Markovian, hidden-Markovian, or additive dynamics, monitoring becomes possible, and under weak interval assumptions, enforcement is always feasible. The payoff is a roadmap and a unified parameter space in which existing results are placed and new algorithms are given.","feed_headline":"Runtime fairness has no one-size-fits-all monitor","feed_subtitle":"A coin-toss model maps when fairness monitoring and enforcement are possible, trivial, or impossible.","key_machinery":"The central object is a sequence $w=(p_t,x_t)_{t\\in\\mathbb{N}^+}$ of coin biases and outcomes, together with a dynamics function $\\theta:W^*\\to\\Delta(P)$ that samples the next bias from the history. Runtime fairness is the conditional expectation $\\rho_t^h(W;\\varphi)=\\mathbb{E}_\\theta(\\varphi(W_{1:t+h})\\mid w_{1:t})$ of one of three measures (outcome average, bias average, current bias) over a prediction horizon $h$. The machinery carries the argument in two ways: monitoring reduces to maintaining a register that estimates the relevant expectation and wrapping it in confidence intervals obtained from concentration inequalities (Hoeffding-type bounds for pointwise soundness, time-uniform confidence sequences for uniform soundness); enforcement reduces to a shield that decides whether to overwrite a bias or outcome, with cost measured by a history-dependent cost function. The examples show that the same register-and-interval template specializes to static, Markovian, hidden-Markovian, and additive dynamics by changing only the error-bound computation.","core_discovery":"Runtime fairness should be understood as the conditional expectation, given the observed history, of a fairness measure over a prediction horizon, rather than as a static average over a fixed dataset. In the coin setting, a stochastic process $W=(P_t,X_t)_{t\\in\\mathbb{N}^+}$ is generated by a dynamics function $\\theta:W^*\\to\\Delta(P)$; at each step the bias is drawn from $\\theta$ conditioned on history and the outcome is a Bernoulli trial. The paper claims that for the two core problems—monitoring (output an interval containing $\\rho_t^h(W;\\varphi)$ with probability $1-\\delta$) and enforcement (intervene to keep the property inside target intervals)—feasibility is determined by the class of dynamics, fairness measure, horizon, and confidence threshold. It exhibits the boundary cases: with unrestricted dynamics, infinite-horizon outcome fairness is unmonitorable, whereas with a single static coin, every measure and horizon is monitorable; for enforcement, any fairness property can be enforced with high confidence under mild interval assumptions, and cost-optimal enforcement is achievable in static known-dynamics settings. The paper thereby unifies scattered results into one taxonomy and adds a probabilistic finite-window enforcer with fewer restrictions than prior work.","pith_inferences":["Read as a design principle, the paper implies that a runtime fairness system should first classify its environment (static, Markovian, hidden, additive, or unknown) and only then select an algorithm; the taxonomy effectively serves as a decision tree for practitioners.","The paper's own future-work suggestion points to discounting as a way to interpolate between current fairness and cumulative bias fairness; a concrete testable extension would be a discounted measure $\\sum\\gamma^{t-i}p_i$ and a monitor whose error bound depends on $\\gamma$.","The claim that group fairness properties reduce to differences of coin biases suggests a practical falsification test: run the proposed monitors on logged data from a real lending or hiring pipeline and check whether the confidence intervals cover the acceptance-probability gap; failures would indicate that per-decision Bernoulli independence is the wrong model.","Combining monitoring and enforcement for unknown dynamics, which the paper lists as open, could be approached by treating the monitor's confidence intervals as a partial observation for the enforcer, yielding an adaptive shield with self-tuned intervention thresholds."],"forward_implications":["For deployed systems, the impossibility result means that asking for a monitor of long-run outcome fairness in an unconstrained environment is asking for something that cannot exist; constraints on the environment are a prerequisite, not an optimization.","When the environment is a single unknown coin, every fairness measure and every horizon can be monitored with the same register update, so simple deployed systems can get runtime fairness verdicts inexpensively.","Under observable or hidden Markovian dynamics, fairness monitoring is sound but has an explicit cost in waiting time, since the hidden-chain error bound depends on the mixing time and verdicts must be delayed until the chain has mixed.","For enforcement, weak conditions on the target intervals suffice: bias fairness can be enforced by pinning the bias to a common intersection point, and outcome fairness by a threshold rule that flips outcomes when the running average drifts the wrong way.","In static systems with known bias, finite-window enforcement can be made cost-optimal, and the paper's new probabilistic enforcer works under a less restricted setting than previous cost-optimal enforcers, at the price of a confidence guarantee rather than an almost-sure one."],"supporting_citations":[{"why":"Supplies the static-coin monitoring algorithm for pointwise soundness that the paper extends to uniform soundness.","marker":"[3]"},{"why":"Provides the monitor for fairness expressions over observable irreducible Markov chains used in Section 4.2.","marker":"[24]"},{"why":"Provides the hidden-Markov monitor whose mixing-time-dependent error bound is reused for limit-average properties.","marker":"[27]"},{"why":"Provides the additive-dynamics monitor whose two-register estimator is adapted to bias fairness.","marker":"[25]"},{"why":"Supplies the cost-optimal finite- and periodic-window shields that the paper extends to a probabilistic enforcer and dynamic systems.","marker":"[13]"},{"why":"Hoeffding's inequality gives the pointwise error bound for the static-coin monitor.","marker":"[29]"},{"why":"Time-uniform confidence sequences give the uniform soundness error bound for the static-coin monitor.","marker":"[30]"},{"why":"Shows value functions for enforcement can be computed efficiently when dynamics are encoded as counter automata, supporting the dynamic-system extension.","marker":"[12]"},{"why":"The ergodic theorem for Markov chains justifies replacing limit averages by the stationary expectation in the hidden-Markov proof.","marker":"[41]"}],"fun_headline_variants":["Runtime fairness: no universal monitor or enforcer","Fairness over time: coin-toss model maps monitorability","Fairness as a runtime property: boundaries of monitoring","Sequential fairness: when monitoring is impossible","Runtime fairness: a taxonomy of monitor and enforce"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that real-world fairness dynamics can be represented as a history-dependent sequence of independent biased coin tosses, with the fairness-relevant quantity being a function of the biases or outcomes; the paper explicitly notes that full generality would require the bias to depend on the entire process including the customer, group, and classifier decision.","fun_headline_variants_meta":{"raw":{"variants":["Runtime fairness: no universal monitor or enforcer","Fairness over time: coin-toss model maps monitorability","Fairness as a runtime property: boundaries of monitoring","Sequential fairness: when monitoring is impossible","Runtime fairness: a taxonomy of monitor and enforce"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000155,"raw_usage":{"total_tokens":1202,"prompt_tokens":924,"completion_tokens":278,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":540,"completion_tokens_details":{"reasoning_tokens":204}},"tokens_in":540,"tokens_out":278,"duration_ms":3646,"temperature":1.0,"reasoning_tokens":204,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T13:19:36.036470+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a real logged decision stream, such as loan acceptances over several years, and estimate at each step the next-decision probability from the full history; if two prefixes with approximately the same scalar bias $p_t$ yield systematically different next-outcome probabilities, or if the monitor's confidence intervals exclude the empirical acceptance rate more often than $\\delta$, the coin-process representation of runtime fairness is falsified.","supporting_citations":[{"cited_title":"Journal of the American Statistical Association58(301), 13–30 (1963)","cited_arxiv_id":null,"evidence_quote":"Hoeffding's inequality gives the pointwise error bound for the static-coin monitor."},{"cited_title":"In: Proceedings of the Conference on Fairness, Accountability, and Transparency","cited_arxiv_id":null,"evidence_quote":"Supplies the static-coin monitoring algorithm for pointwise soundness that the paper extends to uniform soundness."},{"cited_title":"In: Proceedings of the International Computer Aided Verification (CAV)","cited_arxiv_id":null,"evidence_quote":"Provides the monitor for fairness expressions over observable irreducible Markov chains used in Section 4.2."},{"cited_title":"In: International Conference on Runtime Verification (RV)","cited_arxiv_id":null,"evidence_quote":"Provides the hidden-Markov monitor whose mixing-time-dependent error bound is reused for limit-average properties."},{"cited_title":"Proceedings of the AAAI Conference on Artificial Intelligence39(15), 15659–15668 (2025)","cited_arxiv_id":null,"evidence_quote":"Supplies the cost-optimal finite- and periodic-window shields that the paper extends to a probabilistic enforcer and dynamic systems."},{"cited_title":"The Annals of Statistics49(2), 1055–1080 (2021)","cited_arxiv_id":null,"evidence_quote":"Time-uniform confidence sequences give the uniform soundness error bound for the static-coin monitor."},{"cited_title":"In: International Conference on Formal Structures for Computation and Deduction (FSCD)","cited_arxiv_id":null,"evidence_quote":"Shows value functions for enforcement can be computed efficiently when dynamics are encoded as counter automata, supporting the dynamic-system extension."},{"cited_title":"Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press (1997)","cited_arxiv_id":null,"evidence_quote":"The ergodic theorem for Markov chains justifies replacing limit averages by the stationary expectation in the hidden-Markov proof."}],"review_version":1}