{"id":"e682f397-9ac6-42a8-a406-c119bfc2c3a3","arxiv_id":"2504.15568","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In most random dynamic Bayesian Stackelberg games, a leader can learn effectively from a fully strategic follower, and can nearly match the utility of direct communication.","lead":"In repeated leader-follower games where the follower's preferences are private, this paper argues that a leader can learn and profit from a fully strategic follower in most random settings, contrary to a famous negative result from dynamic pricing. It supplies a sufficient condition, an average-case analysis, a comparison with direct communication, and algorithms for near-optimal dynamic policies.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 1 does not follow from Theorem 3: 'no action is a universal best response' does not imply existence of a subgroup with disjoint best-response sets at the BSE.","rationale":"The reader's formal weakest-assumption field points to full commitment, but the reader's rationale independently flags the Corollary 1 proof gap as the decisive issue. Our stress-test agrees with that rationale: the most load-bearing concern is not the commitment assumption, which is standard and clearly stated, but the missing derivation from Theorem 3 to Corollary 1. The 3-type, 2-action configuration shows the logical implication used in the proof is not true, so the O(1/|Θ|) bound for Assumption 1 failing is not established by the arguments given. This does not refute Theorem 2 or the positive examples, and the paper could become acceptable if the proof is repaired, so the existing CONDITIONAL verdict remains appropriate.","tokens_in":39364,"tokens_out":9916,"duration_ms":92170,"concrete_test":"Independently re-derive the step from Theorem 3 to Corollary 1 in Appendix B.2. Concretely, attempt to prove: for fixed x*, if for every action i there exists θ with i∉BR(θ,x*), then there exists Θ′⊂Θ with BR(Θ′,x*)∩BR(Θ\\Θ′,x*)=∅ and BSE(Θ′)≠x*. Test the claimed implication on the m=n=2, |Θ|=3 configuration with BR(θ1)={a}, BR(θ2)={a,b}, BR(θ3)={b} at the BSE; all hypotheses of the implication hold but no subgroup satisfies Assumption 1. If the proof cannot supply an additional argument that excludes such configurations (or shows they have probability O(1/|Θ|)), Corollary 1 should be stated as a conjecture or its proof revised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The abstract's headline probability claim rests on Corollary 1, whose proof in Appendix B.2 contains an unproved inference. Theorem 3 only bounds the probability that some action i is a best response for every type at some leader strategy x. The proof then asserts that this implies, at the BSE x*, there is a subgroup Θ′ with BR(Θ′,x*)∩BR(Θ\\Θ′,x*)=∅ and BSE(Θ′)≠x*. That implication is not generally valid: with m=n=2 and |Θ|=3, take BR sets {a}, {a,b}, {b} at x*. No action is a best response for all types, but no subgroup has best-response set disjoint from its complement, so Assumption 1 fails. The subsequent argument that deleting a tied type θ* makes BSE(Θ′)≠x* is also incomplete: removing the hyperplane on which θ* is indifferent does not by itself show x* is no longer a BSE for the remaining types. Since Corollary 1 is the basis for the claim that learning is effective with probability 1−O(1/|Θ|), the central average-case result is unsupported as written. Theorem 2 and the worked examples still support the sufficient condition, but the prevalence claim requires a repaired proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies repeated Bayesian Stackelberg games in which a leader repeatedly interacts with a fully strategic follower of unknown, fixed type. The central claim is that, contrary to the dynamic-pricing folk theorem, the leader can 'learn effectively': by conditioning her strategy on the follower's observed history, she can strictly improve over the static BSE policy. The authors prove a sufficient condition (Assumption 1) for effective learning and then argue that this condition holds with probability 1 - O(1/|Theta|) under a generic random model of follower payoffs (Corollary 1). They also compare the dynamic equilibrium to a communication benchmark (RME), provide MILP-based algorithms for computing or approximating the DSE, and present experiments on structured and random games.","tokens_in":39565,"tokens_out":9385,"duration_ms":81726,"significance":"If the main claim is correct, the paper would be an important counterpoint to the No Learning Theorem, showing that dynamic pricing is an anomaly and that learning can be effective against a fully strategic follower when the leader can commit. The sufficient condition and the constructive policy in Theorem 2 are a valuable conceptual contribution, as are the MILP formulations and the RME comparison. However, the average-case prevalence result is the headline contribution of the abstract, and it rests on Corollary 1. Since the proof of Corollary 1 contains a genuinely invalid inference, the central prevalence claim is currently unsupported. The remaining results (Theorem 2, the RME bound, and the algorithms) are likely salvageable and interesting on their own, which is why the manuscript merits revision rather than outright rejection.","major_comments":[{"comment":"The proof of Corollary 1 does not establish that Theorem 3 implies the existence of a subgroup with disjoint best-response sets. Theorem 3 bounds the probability that some action i is a best response for every type at some leader strategy x. The proof then asserts that, at the BSE x*, there is a subgroup Θ′ with BR(Θ′,x*) ∩ BR(Θ\\Θ′,x*) = ∅ and BSE(Θ′) ≠ x*. This implication is not valid: with m=n=2 and |Θ|=3, take BR(θ1,x*)={a}, BR(θ2,x*)={a,b}, BR(θ3,x*)={b}. No action is a best response for all types, yet every subgroup has a best-response set intersecting that of its complement, so Assumption 1 fails. The subsequent argument that removing a tied type makes BSE(Θ′)≠x* is also incomplete, since deleting the hyperplane on which θ* is indifferent does not by itself show that x* ceases to be a BSE. Additionally, the vertex case of the proof bounds the wrong event: the event that, at a vertex x_i, all types share a single best response has probability n^{1-|Θ|}, whereas the proof bounds the event that there is an action j that is no type's best response. These flaws leave the O(1/|Θ|) claim unsupported.","section":"§3.2, Appendix B.2, Corollary 1"},{"comment":"The constructive proof of Theorem 2 contains an incorrect derivation of the threshold T*. For constraint (10), which prevents types outside Θ′ from mimicking the subgroup, the relevant margin is V_θ(x*, j*_θ(x*)) − max_{j∈BR(Θ′)} V_θ(x*, j), but the displayed T* and the surrounding sufficient condition use max_{j∉BR(Θ′)} V_θ(x*, j). With the displayed expression, the margin can be zero for a type outside Θ′, so the claimed T* need not exist. Similarly, the sufficient condition stated for constraint (9), namely (T−1)(V* − max) ≥ 1, does not follow from constraint (9); the inequality actually requires (T−2)(V* − max) + V(\\hat{x}, j*_θ(\\hat{x})) − max ≥ 0. While the theorem may still be true with a corrected bound, the proof as written does not establish the claimed threshold.","section":"Appendix B.1, proof of Theorem 2"}],"minor_comments":[{"comment":"The phrase 'converges to one linearly with the number of follower types' is imprecise; the proved (and intended) rate is 1 − O(1/|Θ|), i.e., a linear rate of decrease in the failure probability, not a linear rate of convergence of the success probability.","section":"Abstract"},{"comment":"The claim that the set of RMEs consists only of the two menus {1,(1,0)} and {1,(0,1)} is not fully justified, since the menu assigning (1,0) to type C0 and (0,1) to type C1 is not incentive compatible. The example would benefit from a short derivation of the RME value.","section":"Example 4, Section 4"},{"comment":"The tables report only 100 samples per configuration; stating the standard error or a confidence interval would help interpret the trends, especially in the cells with values near 50/100.","section":"Table 4 and Appendix B.3"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely to be of interest to the EC/SAGT community, but the central average-case claim needs a repaired proof. The authors should also correct the T* derivation in Theorem 2's proof. If the authors can fix these issues, the paper could be a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper proves a genuine positive result: in a repeated Bayesian Stackelberg game with a fully strategic follower and symmetric discounting, the leader can sometimes learn effectively, and Theorem 2 gives a clean sufficient condition and a constructive screening policy. That is a real break from the dynamic-pricing folk theorem and from the myopic-follower literature. Second, the paper's headline average-case claim, that learning is effective with probability 1 - O(1/|Theta|), does not follow from the proofs as written. The gap is in Corollary 1, and it is load-bearing.\n\nWhat is good. The examples are well chosen; Example 3 shows a small perturbation of the pricing game breaks the No Learning Theorem, which is exactly the right intuition. Section 4 is a solid addition: the DSE approximates the communication benchmark (RME) up to O(1/sqrt(T)) under a positive inducibility gap, and the learning-beats-communication example is clean. The MILP and First-k heuristics are useful practical contributions, though no code is released. Theorem 2's construction, play BSE and switch to a sub-group BSE in the final round, is sound and carefully argued.\n\nWhere it falls down. Corollary 1 rests on a non-sequitur. Theorem 3 bounds the probability that no follower action is a best response for every type. The proof then asserts that this implies, at x*, there is a subgroup Theta' with BR(Theta', x*) disjoint from BR(Theta \\ Theta', x*) and BSE(Theta') != x*. That implication is not established and is not true in general. A simple configuration with three types and best-response sets {a}, {a,b}, {b} at x* has no universal action but no subgroup with disjoint best-response sets. The follow-up argument, that deleting an indifferent type removes the hyperplane that keeps x* optimal, is also incomplete: removing a hyperplane does not show x* stops being a BSE for the remaining types. So the O(1/|Theta|) prevalence result is unsupported as written. The rest of the paper does not depend on this corollary; Theorem 2 and Section 4 stand on their own.\n\nThe commitment assumption is strong but standard, and the authors flag it. That is a boundary on scope, not a defect.\n\nWho should read this: anyone working on learning in Stackelberg games or dynamic mechanism design with commitment. It deserves a serious referee, but not acceptance in current form. I would send it out with a request to repair Corollary 1, or to restate the prevalence claim as conditional on Assumption 1 rather than as a probability bound.","headline":"A genuine new sufficient condition and a flawed headline prevalence claim; Corollary 1 needs repair before the average-case result can be trusted.","tokens_in":40095,"tokens_out":5092,"would_cite":false,"duration_ms":50315,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A65","91A26"],"pacs":[],"model":"deepseek-v4-flash","headline":"In random Bayesian Stackelberg games with many follower types, a leader who can credibly commit to a history-dependent policy can typically learn and exploit the follower's private type, beating the static Bayesian Stackelberg equilibrium.","keywords":["Bayesian Stackelberg games","effective learning","No Learning Theorem","dynamic pricing","average-case analysis","stochastic geometry","mixed-integer linear program","strategic follower"],"falsifier":"Fix $m=n=3$, draw each $C^\\theta_{i,j}$ independently from a continuous distribution satisfying Assumption 2, such as uniform on $[0,1]$, take the prior uniform over $\\Theta$ with $|\\Theta|=100$, and check numerically whether any leader action is a best response for every follower type simultaneously; Theorem 3 predicts this happens for at most an $O(1/100)$ fraction of draws, and if the empirical fraction does not shrink toward zero as $|\\Theta|$ grows, the average-case claim is wrong.","tokens_in":39101,"feed_emoji":"🎯","tokens_out":9771,"duration_ms":82109,"temperature":0.7,"pith_summary":"This paper asks whether a leader who faces the same privately informed follower over many rounds can do better than simply replaying the optimal one-shot strategy, when the follower is fully strategic and anticipates the leader's learning. In dynamic pricing, the answer is no, because the No Learning Theorem says no pricing policy beats the static optimal price, a negative result that has shaped the learning-in-games literature. The paper shows that the pricing conclusion does not transfer to general Bayesian Stackelberg games: for a random game with many follower types and non-degenerate follower payoffs, with probability $1-O(1/|\\Theta|)$ the leader can commit to a screening policy that conditions on the follower's history and strictly beats the static Bayesian Stackelberg equilibrium. It further shows that this gain is not merely a substitute for communication, because the optimal dynamic policy nearly matches, and sometimes beats, the best static menu with direct type reports. The paper also gives an exact mixed-integer linear program for the optimal dynamic policy and two faster heuristics.","feed_headline":"In most random Stackelberg games, learning a strategic follower works","feed_subtitle":"Contrary to dynamic pricing, a leader can screen a fully strategic follower and beat static play as type count grows.","key_machinery":"The load-bearing object is the best-response region $BR_\\theta(j)=\\{x\\in\\Delta^m : j\\in\\arg\\max_{j'}V_\\theta(x,j')\\}$, the set of leader mixed strategies for which follower type $\\theta$ would respond with action $j$. The paper's sufficient condition Assumption 1 requires that at the static equilibrium strategy $x^*$ there is a subgroup $\\Theta'\\subset\\Theta$ whose union of best-response regions is disjoint from the union for the remaining types; the constructed policy then runs the static BSE for $T-1$ rounds and, if the follower's responses stay inside the subgroup's region, switches to $BSE(\\Theta')$ on the final round, which the leader strictly prefers exactly when $BSE(\\Theta')\\neq x^*$. The average-case result is carried by a stochastic-geometry argument on the indifference hyperplanes $H^\\theta_{i,j}=\\{x: x\\cdot(C^\\theta_{\\cdot,i}-C^\\theta_{\\cdot,j})=0\\}$: when the generating distribution satisfies Assumption 2, these hyperplanes are in general position, and a generalized spherical quermassintegral, a measure of how often a random linear subspace intersects a cone, shows that the probability any single follower action is a best response for every type decays as $O(1/|\\Theta|)$, yielding the disjoint-subgroup condition with high probability.","core_discovery":"On its own terms, the paper's central claim is that effective learning, defined as the leader's history-contingent policy attaining strictly higher utility than the repeated Bayesian Stackelberg equilibrium (BSE), is the typical outcome in dynamic Bayesian Stackelberg games, not the exceptional one. The proof route is an average-case analysis: under Assumption 2, which says the follower payoff columns are drawn from an even distribution that gives zero mass to linear subspaces so that indifference hyperplanes are in general position, and with no dominant leader action, the probability that the sufficient condition Assumption 1 fails is $O(1/|\\Theta|)$ (Corollary 1). Assumption 1 asks only that at the BSE strategy there is a subgroup of types whose set of best responses is disjoint from the best responses of the complementary types; Theorem 2 converts this into a concrete $T$-round screening policy that plays the BSE for $T-1$ rounds and switches to the subgroup-optimal strategy in the last round only if the observed history is consistent with the subgroup. The paper also establishes that learning is not a stand-in for communication: the dynamic equilibrium utility is at least $U^{\\mathrm{RME}}-O(\\sqrt{\\log|\\Theta|/(T\\delta^2)})$, where $\\delta$ is the inducibility gap, and there are instances in which the dynamic policy beats the communication benchmark by an $\\Omega(1)$ gap.","pith_inferences":["The pricing game is a knife-edge case rather than a representative one: because the No Learning Theorem is tied to the indifference structure of posted prices, perturbing the leader's feasible action set slightly, as in Example 3, already restores effective learning, which suggests that no-learning failures occupy a measure-zero locus under generic payoff perturbations.","A testable extension is to compute, for fixed $m$ and $n$, the empirical frequency with which Assumption 1 holds as $|\\Theta|$ grows under different continuous distributions satisfying Assumption 2, and to check whether the convergence rate matches the $O(1/|\\Theta|)$ bound or depends measurably on $m$ and $n$.","The Theorem 2 construction suggests that a dynamic policy can act as a distributed implementation of a randomized menu: instead of reporting a type, the follower's accumulated response history selects the relevant submenu, which may be useful in settings where direct messages are unavailable but actions are observable.","A necessary-and-sufficient characterization of effective learning would likely replace Assumption 1's disjoint-region condition with a gap condition on dynamic incentive compatibility, since Example 3 is learnable without satisfying Assumption 1."],"forward_implications":["In any game satisfying Assumption 1 there is a horizon $T^*$ such that, for all $T\\ge T^*$, the leader has a dynamic policy that strictly outscores the repeated BSE while only changing her strategy at the final round.","For random games with many follower types and no dominant leader action, effective learning is not a rare phenomenon: the probability that the sufficient condition fails is $O(1/|\\Theta|)$, so screening typically becomes possible as the type space grows.","The optimal dynamic policy nearly closes the gap to the best static communication benchmark: with a positive inducibility gap $\\delta$ and $T$ sufficiently large relative to $\\log(|\\Theta|n)$, the dynamic equilibrium utility is within $O(\\sqrt{\\log|\\Theta|/(T\\delta^2)})$ of the randomized-menu equilibrium utility.","There are Bayesian Stackelberg games where the dynamic screening policy beats the randomized-menu benchmark by an $\\Omega(1)$ gap, so learning through repeated play can be strictly more powerful than a direct type report under commitment.","The exact dynamic equilibrium can be formulated as a mixed-integer linear program with $O(T|\\Theta|mn^T)$ continuous variables and $T|\\Theta|n$ integer variables, and the First-$k$ heuristic approximates it in time independent of the horizon for fixed $k$."],"supporting_citations":[{"why":"Supplies the No Learning Theorem for dynamic pricing, the negative baseline the paper's positive results are intended to overturn.","marker":"[57]"},{"why":"Provides the optimal-auction benchmark used in the reduction proving that no dynamic pricing policy beats the static optimum.","marker":"[45]"},{"why":"Defines the Bayesian Stackelberg equilibrium and establishes its NP-hardness, which the paper uses as the static benchmark and as the sub-group benchmark.","marker":"[18]"},{"why":"Supplies the random conical tessellation and quermassintegral results that the paper generalizes to bound the probability that Assumption 1 fails.","marker":"[35]"},{"why":"Supplies the uniform-approximation lemma used in Theorem 4 to round a randomized menu into a dynamic policy without destroying incentive compatibility.","marker":"[3]"},{"why":"Introduces the Randomized Menu Equilibrium used as the communication benchmark that the dynamic equilibrium is compared against in Theorem 4.","marker":"[26]"}],"fun_headline_variants":["In most Stackelberg games, learning a follower beats static play","Leaders can learn to screen strategic followers in Stackelberg games","Folk theorem fails: learning works against a strategic follower","Average-case proof: Stackelberg leaders improve via learning","Dynamic Stackelberg: learning a follower's type is typical"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the leader can credibly promise, before the first round, what she will do after every possible history of the follower's responses, and the follower trusts that promise; if commitment is absent or non-credible, the constructed screening policies and the positive learning results do not apply.","fun_headline_variants_meta":{"raw":{"variants":["In most Stackelberg games, learning a follower beats static play","Leaders can learn to screen strategic followers in Stackelberg games","Folk theorem fails: learning works against a strategic follower","Average-case proof: Stackelberg leaders improve via learning","Dynamic Stackelberg: learning a follower's type is typical"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000356,"raw_usage":{"total_tokens":2012,"prompt_tokens":1102,"completion_tokens":910,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":718,"completion_tokens_details":{"reasoning_tokens":824}},"tokens_in":718,"tokens_out":910,"duration_ms":7888,"temperature":1.0,"reasoning_tokens":824,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:24:40.943115+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix $m=n=3$, draw each $C^\\theta_{i,j}$ independently from a continuous distribution satisfying Assumption 2, such as uniform on $[0,1]$, take the prior uniform over $\\Theta$ with $|\\Theta|=100$, and check numerically whether any leader action is a best response for every follower type simultaneously; Theorem 3 predicts this happens for at most an $O(1/100)$ fraction of draws, and if the empirical fraction does not shrink toward zero as $|\\Theta|$ grows, the average-case claim is wrong.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the No Learning Theorem for dynamic pricing, the negative baseline the paper's positive results are intended to overturn."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the Bayesian Stackelberg equilibrium and establishes its NP-hardness, which the paper uses as the static benchmark and as the sub-group benchmark."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the random conical tessellation and quermassintegral results that the paper generalizes to bound the probability that Assumption 1 fails."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the uniform-approximation lemma used in Theorem 4 to round a randomized menu into a dynamic policy without destroying incentive compatibility."}],"review_version":1}