{"id":"acf00050-4077-4620-829d-c16bd9b9372b","arxiv_id":"2506.01936","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Hiding the classifier and letting agents best respond to a discounted average of past classifiers multiplies the deterministic worst-case mistake bound by about 1/(1-gamma) or by the maximum in-degree of the manipulation graph.","lead":"Should decision makers hide their classifiers from people who game them? In a formal online learning model the answer is no: agents who estimate the current rule from past rules can force the decision maker to make many more mistakes than if the rule were revealed.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The k_in lower bound of Theorem 4.4 is proved only in the γ→0 limit, and the proof assumes agents best respond exactly to h_{t-1}; for any fixed γ∈(0,1) the advertised k_in-factor part of the central claim is not established.","rationale":"The reader's conditional verdict is appropriate. I agree that the central reduction arguments are largely sound and that the main comparison factors are plausible. My concern is more specific than the reader's weakest_assumption: the most load-bearing gap is not the choice of arbitrary tie-breaking per se, but the unquantified γ→0 limit in Theorem 4.4’s second lower bound. The proof explicitly replaces e-hat_t^γ with h_{t-1}, which is only true in the limit; no fixed-γ version is stated or proved. Since the abstract and Section 2.1 claim a k_in-factor deterioration as part of the main result, this is a genuine hole in the advertised central claim. The proposed test—either deriving a concrete small-γ condition or exhibiting a counterexample for a fixed γ—would settle whether the k_in lower bound can be repaired. I do not think the paper should be rejected; a conditional acceptance with a request to fix Theorem 4.4 and its proof is the right outcome, which matches the reader's verdict.","tokens_in":24459,"tokens_out":14352,"duration_ms":152149,"concrete_test":"Re-derive Part 1 of the B.3 lower bound with γ kept symbolic: state the exact condition under which the two-round adversary still forces a mistake when h_{t-2} differs from h_{t-1}, or exhibit a deterministic learner for γ=1/2 on the clique construction whose mistake count is o(k_in·k_out·d). If the condition exists, amend Theorem 4.4 to 'for γ ≤ γ0(k_in,k_out)' and recheck the constants; if it does not, the k_in lower bound should be withdrawn or replaced.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix B.3, Part 1 proves M_γ-Weighted = Ω(d·k_in·k_out) by asserting that \"for γ→0, best responding to e-hat_t^γ is equivalent to best responding to h_{t-1}\" and then running a two-round adversary driven only by h_{t-1} and h_t (cases 1–3). The model, however, fixes γ∈(0,1); for every such γ the estimate e-hat_t^γ is a strict convex combination in which h_{t-2} enters with weight proportional to γ, and older classifiers enter with geometrically decaying but nonzero weight. The case analysis does not bound this contamination. In case 3, for instance, the adversary needs all of {x0,x1,...,x_k1} to move to the same maximizer of h_{t-1}; if h_{t-2} labels some leaf 1, that leaf can receive e-hat value roughly γ/(1-γ^{t-1}), which for γ not very small can exceed the value at the chosen middle node and break the forced mistake. No sufficient smallness condition on γ is stated, so the second display of Theorem 4.4 is a limit statement rather than a bound for the actual γ-Weighted model. The general-γ lower bound in Part 2 (the star construction) only has k_in=k_out=2 and therefore cannot supply the missing k_in factor. Consequently the \"or k_in\" component of the abstract and Section 2.1 summary is not yet supported for any concrete γ, even if the (1−γ)^{-1} factor is correct. This is a formal gap in the central claim, not a disagreement with the modeling choice of adversarial tie-breaking.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies online strategic classification when the decision-maker may withhold the current classifier. It compares three agent-behavior models: the standard revealed classifier with stay-put tie-breaking (Revealed-Std), a revealed classifier with arbitrary tie-breaking (Revealed-Arb), and the paper's main setting in which agents cannot see h_t and instead best respond to a discounted weighted average of past classifiers, e-hat_t^gamma, with arbitrary tie-breaking (gamma-Weighted). The central claim is that hiding the classifier never helps in worst-case mistake bounds: relative to the transparent baseline, the gamma-Weighted setting costs an extra factor of roughly (1-gamma)^{-1} or k_in, where k_in is the maximum in-degree of the manipulation graph. The upper bounds are obtained by reducing Revealed-Arb to classical online learning (Algorithm 1 and Corollary 3.2) and then reducing gamma-Weighted to Revealed-Arb by waiting for a block of repeated mistakes (Algorithm 3 and Lemma 4.3). Lower bounds are claimed in Theorem 3.3 for Revealed-Arb and Theorem 4.4 for gamma-Weighted, with proofs in Appendices A.2 and B.3.","tokens_in":24797,"tokens_out":13360,"duration_ms":136669,"significance":"If the lower-bound claims were fully established, this would be a solid and timely contribution to the online strategic classification literature: it formalizes a natural notion of bounded agent memory and shows that hiding the classifier backfires in worst-case terms, and it isolates the role of arbitrary tie-breaking through the k_in factor. The algorithmic reductions are genuinely useful: Algorithm 1 has a clean weight-accounting argument, and Algorithm 3's block-update reduction is elegant and appears sound as an upper bound. The paper is also honest about the dependence of k_in on the tie-breaking model and about the open randomized and agnostic settings. The main weakness is that the lower-bound section, which carries half of the central claim, has load-bearing formal gaps: the k_in lower bound is only stated in a gamma-to-0 limit that is not a value of the model, and the general-gamma star lower bound contains internal label inconsistencies. These issues are fixable in principle, but they are not merely presentational.","major_comments":[{"comment":"The second display of Theorem 4.4 is a limit statement, not a bound for the model. The model fixes gamma in (0,1), but the theorem states 'in the special case of gamma -> 0'; the proof then asserts that best responding to e-hat_t^gamma is equivalent to best responding to h_{t-1} without giving any quantitative threshold. For any fixed gamma>0, e-hat_t^gamma is a strict convex combination in which h_{t-2} enters with weight at least gamma(1-gamma)/(1-gamma^{t-1}), and the case analysis in Part 1 never bounds the effect of this older-classifier contamination. In case 3, for example, if h_{t-2} labels some leaf 1, that leaf's e-hat value can exceed the value at the designated maximizer of h_{t-1} unless gamma is sufficiently small. No sufficient smallness condition on gamma is stated or derived, so the advertised 'or k_in' component of the central claim is not established for any concrete gamma in (0,1). This needs either a repaired theorem with an explicit gamma_0(k_in,k_out) threshold and a proof that the three-case adversary works for all gamma below it, or a restated claim.","section":"§4.2, Theorem 4.4; Appendix B.3, Part 1"},{"comment":"The general-gamma star lower bound has internal inconsistencies that prevent it from proving the stated result. In case 1(a), the adversary is said to pick x_t = x_i,B with y_t = 1 and to force a false-negative mistake when h_t(x_i,B)=0. But the hypothesis class is defined so that h_{i*}(x_i,B)=0 for every i, including i different from i*; hence no realizable sequence can have label 1 at x_i,B, and h_t(x_i,B)=0 would be a correct prediction rather than a mistake. Later in the same section the text says 'with probability over 1/2, the agent will manipulate to x_i,R', which introduces a probabilistic object into what is otherwise a deterministic adversarial tie-breaking lower bound. These errors affect the proof of the first display of Theorem 4.4, i.e., the Omega(min{d(1-gamma)^{-1}, |H|}) lower bound, so the (1-gamma)^{-1} factor is also not proven as written.","section":"Appendix B.3, Part 2 (first display of Theorem 4.4)"},{"comment":"The degree accounting for the modified construction in Figure 4 is not specified precisely enough to support the claimed parameters. The text says that adding a clique among x_1,...,x_k1 gives k_out = k_1 + k_2 and k_in = k_2, but with only that description the in-degrees of leaves and middle nodes depend on which cross-edges are present; a clique adds k_1-1 in- and out-neighbors to each first-layer node, which is not reflected in the stated counts unless additional edges are assumed. Because the lower bound uses the condition k_out >= (1 + Omega(1)) k_in to convert Omega(k_1 k_2) into Omega(k_in k_out), the edge set and degree computation must be made fully explicit.","section":"Appendix B.3, Part 1, Figure 4"}],"minor_comments":[{"comment":"There is a typo: 'determinisitc' should be 'deterministic'.","section":"§2.1"},{"comment":"The phrase 'special case of gamma -> 0' should be replaced by an explicit statement such as 'for all sufficiently small gamma > 0' with the threshold derived in the proof; as written, gamma -> 0 is not a value in the model's parameter space.","section":"Theorem 4.4"},{"comment":"The bound on k_out is inconsistent between the informal statement (k_in, k_out <= 3) and Observation C.1 (k_in, k_out <= 2), while the graph in Figure 5 has x_B connected to x_L, x_R, and itself, giving maximum out-degree 3 including the self-loop.","section":"Section 5 and Observation C.1"},{"comment":"The proof switches between the unnormalized weighted sum h^gamma_t and the normalized e-hat^gamma_t; the equivalence is true up to normalization but should be stated explicitly at the point of the switch to avoid confusion.","section":"Appendix B.3, Part 2"}],"recommendation":"major_revision","confidential_remarks":"The upper-bound half of the paper is in good shape and the reduction ideas are publishable. The lower-bound section, however, is not yet reliable: the k_in lower bound is a limit statement rather than a bound for any concrete gamma, and the star construction for general gamma contains straightforward label inconsistencies. I believe these are repairable within the scope of the paper, but the revision should be substantial and should include a fully formal treatment of the gamma dependence in Appendix B.3. I do not see a novelty or attribution problem; the prior-work citations are appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hamid —\n\nThe paper is worth reading, but the headline result oversells itself. The main claim, in the abstract and Section 2.1, is that hiding the classifier makes the learner suffer a factor of (1−γ)^{-1} or k_in more mistakes than the transparent baseline. The (1−γ)^{-1} half is proven for every γ∈(0,1) and I see no issue with it. The k_in half, however, is only proven as a γ→0 limit. For any fixed γ>0, the older classifiers enter the weighted average with weight proportional to γ, and the proof of Theorem 4.4 Part 1 simply asserts that best responding to the average is equivalent to best responding to h_{t−1}. No smallness condition on γ is stated and the case analysis does not control the contamination from h_{t−2} and beyond. So the 'or k_in' claim in the abstract is not supported by the current proof for any concrete γ. That is a formal gap in the central claim, not a modeling disagreement.\n\nWhat is genuinely new: the γ-Weighted model itself, the reduction from hidden-policy to revealed-arbitrary-tie-breaking (Algorithm 3), and the clean Revealed-Arb analysis that isolates the cost of adversarial tie-breaking. The upper bounds in Theorem 4.1 and the matching lower bound for the (1−γ)^{-1} factor appear sound. I checked the weight-accounting argument in Theorem 3.1; it is careful and correct.\n\nThe lower-bound section has smaller rough edges. The degree count after adding the clique in Figure 4 is inconsistent (k_in should be k1, not k2). One case in Appendix B.3 uses 'with probability over 1/2' in a deterministic adversarial model; the adversary should simply choose the tie-breaking deterministically. Neither of these is load-bearing, but they point to a proof that needs a careful rewrite.\n\nBottom line: this is a solid paper with a fixable flaw. A referee can ask the authors to either prove the k_in lower bound for sufficiently small γ, or state the result as a limit and adjust the abstract. The core question — whether withholding the classifier helps — is answered correctly for the (1−γ)^{-1} factor, and the model is likely to be reused. I'd send it to review and expect a revise-and-resubmit. I'd also bring it to a reading group; the gap analysis is instructive.","headline":"Solid upper bounds and an interesting question, but the k_in lower bound in the main theorem is only proven as a γ→0 limit, so the abstract's 'or k_in' claim is not yet supported for any fixed γ.","tokens_in":25310,"tokens_out":6276,"would_cite":true,"duration_ms":58195,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","91A80"],"pacs":[],"model":"deepseek-v4-flash","headline":"Concealing the current classifier never improves worst-case online strategic classification; with agents responding to a discounted average of past classifiers, mistakes grow by a factor of roughly (1−γ)^−1 or the graph's in-degree k_in.","keywords":["strategic classification","online learning","mistake bound","manipulation graph","classifier disclosure","discounted historical classifiers","Littlestone dimension","Stackelberg games"],"falsifier":"Re-run the lower-bound construction of Theorem 4.4 on the replicated star graph with $k_{\\mathrm{in}}=k_{\\mathrm{out}}=2$ and fixed $\\gamma\\in(0,1)$: if any deterministic learner keeps total mistakes below $\\Omega(\\min\\{d(1-\\gamma)^{-1}, |\\mathcal{H}|\\})$ on all strategically realizable sequences, Theorem 4.4 is false. In the $\\gamma\\to 0$ regime, apply the same check to the $\\Omega(d k_{\\mathrm{in}} k_{\\mathrm{out}})$ bound on the clique-extended graph.","tokens_in":24241,"feed_emoji":"🎭","tokens_out":14994,"duration_ms":138022,"temperature":0.7,"pith_summary":"The paper asks whether a decision-maker can reduce strategic manipulation by keeping the current classifier secret. It answers no: if agents respond to a discounted weighted average of previously deployed classifiers, a deterministic learner's worst-case mistakes grow by a factor of $(1-\\gamma)^{-1}$ or the maximum in-degree $k_{\\mathrm{in}}$ of the manipulation graph, relative to the transparent baseline. A matching upper bound holds up to logarithmic factors, and in the transparent setting with arbitrary tie-breaking the $k_{\\mathrm{in}}$ factor already appears. The message is that withholding classifiers backfires under worst-case analysis, and the price of secrecy is a concrete graph-theoretic quantity.","feed_headline":"Hiding classifiers multiplies worst-case mistakes by (1−γ)^−1 or k_in.","feed_subtitle":"Strategic agents who respond to remembered classifiers make (1−γ)^−1 or k_in times more errors than under full transparency.","key_machinery":"The machinery has three pieces: the manipulation graph $G=(X,E)$, whose maximum in-degree $k_{\\mathrm{in}}$ counts how many distinct feature vectors can be made to look like a single one; the agent's estimate $\\widehat{e}_t^\\gamma = (1-\\gamma)/(1-\\gamma^{t-1}) \\sum_{\\tau=0}^{t-2} \\gamma^\\tau h_{t-1-\\tau}$, a discounted average of past classifiers; and the reduction in Algorithm 3, which reuses a Revealed-Arb learner but updates it only after $\\Phi=\\lceil \\ln(1/3)/\\ln(\\gamma)\\rceil+1$ repeated mistakes. That threshold is the memory time needed for the current classifier's weight in the average to dominate, so after $\\Phi$ mistakes the agents effectively best respond to $h_t$ with arbitrary tie-breaking. The lower bound is carried by a replicated star graph in which each hypothesis labels one right leaf and all other left leaves, forcing the learner to pay $(1-\\gamma)^{-1}$ rounds of mistakes while agents' memory catches up after the learner switches to the correct hypothesis.","core_discovery":"The paper's central claim is Theorem 4.1 with Theorem 4.4: in the $\\gamma$-Weighted model, where agents cannot observe the current classifier $h_t$ and instead best respond to the discounted historical average $\\widehat{e}_t^\\gamma$ with arbitrary tie-breaking, deterministic learners face a worst-case mistake bound of $O(\\min\\{d(1-\\gamma)^{-1} k_{\\mathrm{in}} k_{\\mathrm{out}} \\ln(k_{\\mathrm{in}} k_{\\mathrm{out}}), |\\mathcal{H}|\\})$ and lower bounds of $\\Omega(\\min\\{d(1-\\gamma)^{-1}, |\\mathcal{H}|\\})$, plus an extra $\\Omega(d k_{\\mathrm{in}} k_{\\mathrm{out}})$ bound when $\\gamma\\to 0$. Stated plainly, concealing the classifier never improves the worst-case mistake count and can multiply it by the memory time $(1-\\gamma)^{-1}$ or by the in-degree $k_{\\mathrm{in}}$; the two factors are separately unavoidable in different parameter regimes.","pith_inferences":["A policy consequence the authors leave implicit: if hiding is unavoidable, release classifiers on a schedule with gaps of order $(1-\\gamma)^{-1}$, exactly the memory window after which agent estimates track the current hypothesis.","If tie-breaking is probabilistic or restricted to staying put on ties, the $k_{\\mathrm{in}}$ factor should vanish, leaving $(1-\\gamma)^{-1}$ as the pure cost of hiding; the paper already shows the memory part survives standard tie-breaking.","Since the upper-bound reduction uses only black-box access to a Revealed-Arb learner, it should transfer to randomized or agnostic extensions once such learners exist, an extension the paper leaves open."],"forward_implications":["Full disclosure is the best worst-case information policy among deterministic online protocols: hiding adds at least a multiplicative $(1-\\gamma)^{-1}$ or $k_{\\mathrm{in}}$ penalty in the mistake bound.","The $k_{\\mathrm{in}}$ penalty appears even with the classifier revealed when agents break ties arbitrarily, so the standard 'stay put' tie-breaking convention is load-bearing for transparent-setting guarantees.","In the one-step-memory limit $\\gamma\\to 0$, the mistake bound is $\\Omega(d k_{\\mathrm{in}} k_{\\mathrm{out}})$, so both the in-degree and out-degree of the manipulation graph enter the cost.","The proposed algorithms achieve $O(d(1-\\gamma)^{-1} k_{\\mathrm{in}} k_{\\mathrm{out}} \\ln(k_{\\mathrm{in}} k_{\\mathrm{out}}))$ mistakes in the $\\gamma$-Weighted setting, matching the lower bounds up to logarithmic factors and the gap between parameter regimes."],"supporting_citations":[{"why":"Supplies the transparent-setting mistake bound $O(k_{\\mathrm{out}}\\cdot \\mathrm{Ldim}(\\mathcal{H}))$ and lower bound that form the baseline this paper compares against.","marker":"Ahmadi et al. [2023]"},{"why":"Defines the online strategic classification framework with graph-based manipulations and the standard 'stay put' tie-breaking assumption that the $\\gamma$-Weighted model relaxes.","marker":"Cohen et al. [2024a]"},{"why":"Provides the SOA algorithm and Littlestone dimension used as the non-strategic subroutine inside the upper-bound reductions.","marker":"Littlestone [1988]"},{"why":"Introduced the manipulation graph model for feasible feature manipulations used throughout the paper.","marker":"Zhang and Conitzer [2021]"},{"why":"Introduced strategic classification as the learning problem where agents best respond to a classifier.","marker":"Hardt et al. [2016]"},{"why":"Gives improved transparent-setting bounds and supplies part of the lower-bound construction toolkit.","marker":"Ahmadi et al. [2024]"}],"fun_headline_variants":["Concealing classifiers multiplies mistakes by (1−γ)^−1 or k_in","Hiding classifiers raises worst-case cost by (1−γ)^−1 or k_in","Withholding classifiers multiplies errors by (1−γ)^−1 or k_in","Secrecy in classifiers: mistakes multiply by (1−γ)^−1 or k_in","Stay transparent: hiding multiplies mistakes by (1−γ)^−1 or k_in"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The result depends on allowing an agent, when several manipulations look equally good, to pick any of them, including a move that reveals nothing about the agent's true position; if ties are instead always broken by staying put, the in-degree factor disappears, and the paper's memory-based $(1-\\gamma)^{-1}$ lower bound is the part that survives.","fun_headline_variants_meta":{"raw":{"variants":["Concealing classifiers multiplies mistakes by (1−γ)^−1 or k_in","Hiding classifiers raises worst-case cost by (1−γ)^−1 or k_in","Withholding classifiers multiplies errors by (1−γ)^−1 or k_in","Secrecy in classifiers: mistakes multiply by (1−γ)^−1 or k_in","Stay transparent: hiding multiplies mistakes by (1−γ)^−1 or k_in"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000929,"raw_usage":{"total_tokens":4010,"prompt_tokens":1005,"completion_tokens":3005,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":621,"completion_tokens_details":{"reasoning_tokens":2889}},"tokens_in":621,"tokens_out":3005,"duration_ms":22417,"temperature":1.0,"reasoning_tokens":2889,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:31:39.444901+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Re-run the lower-bound construction of Theorem 4.4 on the replicated star graph with $k_{\\mathrm{in}}=k_{\\mathrm{out}}=2$ and fixed $\\gamma\\in(0,1)$: if any deterministic learner keeps total mistakes below $\\Omega(\\min\\{d(1-\\gamma)^{-1}, |\\mathcal{H}|\\})$ on all strategically realizable sequences, Theorem 4.4 is false. In the $\\gamma\\to 0$ regime, apply the same check to the $\\Omega(d k_{\\mathrm{in}} k_{\\mathrm{out}})$ bound on the clique-extended graph.","supporting_citations":[],"review_version":1}