Pith. sign in

REVIEW 2 major objections 4 minor 22 references

This paper shows that against count-based learners in repeated games, optimal deceptive play can be computed exactly when the opponent's memory is small, approximated when memory is large, and is NP-hard to approximate against ERM even in z

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 03:52 UTC pith:W5W7Z45U

load-bearing objection Interesting model and some correct exact algorithms, but the approximation theorems are not proven as written and the additive-hardness proof has a circular step; worth serious refereeing with major revision. the 2 major comments →

arxiv 2607.23049 v1 pith:W5W7Z45U submitted 2026-07-25 cs.GT

On the Power of Deception in Repeated Games

Saba Ahmadi , Avrim Blum , Dimitar Chakarov , Melissa Dutz This is my paper
classification cs.GT MSC 91A2068Q1768W25
keywords deceptionrepeated gamescount-based learnersempirical risk minimizationdynamic programmingapproximation algorithmsNP-hardnesszero-sum games
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Deception in repeated games is modeled as playing a sequence of actions that shapes an opponent's empirical expectations before switching to profit. The paper defines the deception bonus—the payoff gain of the best deceptive sequence over the best fixed mixed strategy—and demonstrates it can be arbitrarily large, linear in the horizon, or zero depending on the game. Methodologically, it gives exact dynamic programs for optimizing against any count-based learner when the action space or opponent's memory is small, and approximation algorithms for large memory or long horizons. A central hardness result states that against the classic empirical-risk-minimization (ERM) opponent, even approximating the optimal deceptive payoff within a constant factor or a T^α additive error is NP-hard, even in zero-sum games. Experiments indicate the deception bonus is typically larger in random zero-sum games than general-sum ones.

Core claim

Against a count-based learner—an opponent whose action depends only on how often the optimizer has played each action in the past—the optimal deceptive sequence is obtained by a dynamic program that maximizes cumulative payoff over count vectors or over the last m actions. The paper formalizes the deception bonus and shows it can be arbitrarily large, can grow linearly with the horizon even with bounded payoffs, and can be absent. For large memories, block-decomposition and cycle-repetition algorithms provide approximate guarantees, while for an unknown count-based opponent a stochastic-bandit reduction yields an asymptotic 1/2-approximation. The central negative result is that against ERM—t

What carries the argument

Count-based learning rules f: counts → mixed action over opponent's actions; defining the optimizer's expected payoff per round by uA(a,f(counts)) reduces the problem to max-weight walks over states that are count vectors (full memory) or length-m action windows. Exact dynamic programs fill tables V[c] or V[t,(a1...am)] via simple recurrences. For large m, the algorithms reuse block-optimal sequences Sm, S2m, Sm+p and split the horizon into odd/even blocks to get a 1/2-approximation; for very long horizons, maximal-mean-weight cycles in a transition graph give OPT−O(kA^m H) additive guarantees. The hardness proof embeds a 3-SAT formula into the opponent's payoff matrix so that attaining a la

Load-bearing premise

The load-bearing premise for the 1/2-approximation theorems is that the global optimal payoff is bounded by the sum of independently optimized odd- and even-block payoffs (OPTe + OPTo ≥ OPT), and that repeating a block-optimal sequence preserves its optimized second-half payoff; this decomposition is asserted but not proved, so if it is false the approximation guarantees do not follow.

What would settle it

To test the 1/2-approximation, search over small games for a counterexample where the optimal sequence requires interleaving actions from odd and even blocks, and check whether OPTe+OPTo < OPT; if found, the theorem's proof is invalid. To test the hardness claim, set up the 3-SAT-derived zero-sum game from the proof, run an exact solver for T=n+1, and verify that a high-payoff sequence exists iff the formula is satisfiable.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • If a count-based learner has bounded memory m, the paper's DP computes the optimal deceptive sequence in time O(kA^{m+2} kB T), so small-m games can be solved exactly.
  • For large memory m, the 1/2-approximation runs in time polynomial in m, providing a practical fallback when exact DP is infeasible.
  • If the opponent's rule is unknown but belongs to a small family with memory m, the optimizer can still get an asymptotic 1/2-approximation up to O(sqrt(|F| m T)+m) regret.
  • Against ERM, the paper's hardness theorem rules out efficient constant-factor or T^α additive approximations in zero-sum games, unless P=NP.
  • In random games, deception bonuses are empirically larger in zero-sum than in general-sum games and grow roughly linearly with the horizon.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • A testable extension is to verify the odd/even block-decomposition property behind the 1/2-approximation on adversarial random games; the paper does not report such a check.
  • The same count-based deception model could be adapted to study detector evasion in machine learning, where the classifier is the count-based learner and the optimizer seeks a sequence that manipulates its predictions.
  • Since ERM hardness holds even for zero-sum games, a natural next question is whether randomization or different tie-breaking rules can break the hardness; the model's deterministic tie-breaking is a lever.
  • The 'blank action' assumption in the unknown-opponent algorithm could be relaxed in practice by using exploration sequences that reset memory, a direct extension.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper proposes a model of deception in repeated two-player normal-form games in which the opponent is a count-based learner, i.e., a learner whose behavior depends only on the empirical counts of the optimizer's past actions. It defines the deception bonus as the advantage of the best adaptive action sequence over the best announced fixed mixed strategy. The main contributions are: structural results showing that the deception bonus can be arbitrarily large, can be Ω(T) with bounded payoffs, and can also be zero (Propositions 1–5); exact dynamic programs for optimizing against any count-based learner and against memory-limited variants (Theorems 1–2); approximation algorithms for large memory or horizon, including a claimed 1/2-approximation (Theorem 4), a (1−ε)(OPT−mH) guarantee (Theorem 5), an additive-loss cyclic strategy (Theorem 6), and a bandit-based algorithm for an unknown count-based learner (Theorem 7); and NP-hardness of approximating the optimal payoff against ERM even in zero-sum games, including a T^α-additive inapproximability claim (Theorem 8). The paper closes with experiments measuring the deception bonus in random zero-sum and general-sum games.

Significance. If the results are established, the paper gives a clean formal treatment of multi-stage deception against count-based learners and extends prior hardness work from general-sum to zero-sum games and from constant additive error to T^α additive error. The exact DP characterizations are natural, the structural propositions are informative, and the availability of reproducible experimental code is a strength. However, two central proofs are not valid as written: the T^α-additive hardness proof uses a self-referential choice of parameters, and the proof of the 1/2-approximation theorem (together with its analogue in the unknown-learner section) relies on an unjustified block-optimization claim. Both issues appear repairable, but they must be fixed before the theorems can be accepted as proved.

major comments (2)
  1. [Appendix F, Theorem 8 Part 2] The additive-hardness proof defines T = c(n+1) and then says 'we can set c = ⌈T^α⌉.' This is circular: substituting gives c = ⌈(c(n+1))^α⌉, which has only bounded solutions for fixed n and α. The construction therefore cannot produce arbitrarily large T, so the claimed NP-hardness of T^α-additive approximation is not established as written. The issue is local and repairable: choose c = n^q (or any polynomial in n) and set L > (n+1)(2n−2) + T^α/c. Since T^α/c = (n+1)^α c^{α−1} → 0 for α<1, L can remain polynomial in n and the gap cL − T(2n−2) exceeds T^α. The proof should be rewritten with this parameterization.
  2. [Section 5.1 / Appendix B, Theorem 4; Section 6.1 / Appendix E, Theorem 7] The proof of Theorem 4 asserts that the two strategies in Algorithm 1 achieve max(OPTe, OPTo) and that OPTe+OPTo ≥ OPT. The inequality is defensible if OPTe/OPTo are the maxima over the two alternating m-step block positions, but the claim that the algorithm attains max(OPTe, OPTo) is not. Let S2m = (P,Q), where Q is the optimized second half. When the even strategy repeats S2m, the sequence is P,Q,P,Q,..., so every Q-block is preceded by P and earns the optimized payoff, but every P-block is preceded by Q and is not optimized; the odd strategy has the same limitation. Thus the odd strategy does not optimize odd-numbered blocks. A correct proof can instead count Q-blocks: if W is the maximum payoff of any m-step block over all possible m-step prefixes, the even strategy earns at least ⌊T/(2m)⌋W while any strategy can earn at most O(T/m·W), giving the claimed constant factor after a bound
minor comments (4)
  1. [Section 5.2, Algorithm 2] The summation limits in lines 2 and 7 appear reversed: Σ from min(⌈m/ε⌉,T) to min(m+1,T) should presumably be from min(m+1,T) to min(⌈m/ε⌉,T), since ⌈m/ε⌉ is normally larger than m+1. Please clarify.
  2. [Appendix F, Theorem 8 Part 1] The proof begins by assuming a polynomial-time algorithm A 'for finding the optimal sequence,' but the theorem concerns constant-factor approximation; the later threshold L > 2n^2/α indicates an α-approximation was intended. Please make the assumption consistent with the statement.
  3. [Appendix F, Theorem 8 Part 2] The tie-breaking order for the c-block game is not specified. The per-block argument requires the opponent to break ties first by block index (block 1 columns, then block 2 columns, etc.) and within each block by the original order; otherwise the score comparisons in the proof may not hold as written.
  4. [General] There are a few typographical issues in the displayed DP runtimes (e.g., Theorem 1's O(kA^{2kB} T^{kA}) can be misread as kA^{2kB T^{kA}}); please ensure the exponents are typeset unambiguously.

Circularity Check

1 steps flagged

Theorem 8 Part 2 defines T and c mutually (T=c(n+1), c=ceil(T^α)), so the T^α-hardness claim rests on a self-referential parameterization; no other circularity found.

specific steps
  1. self definitional [Appendix F, Proof of Theorem 8 (Part 2), after 'Let T = c(n + 1)' and before 'To see where the T^α additive bound comes from...']
    "Given a 3-SAT formula F, we set up a game matrix G′ composed of an arbitrarily large number (c) of copies of the game G ... Let T = c(n + 1). ... To see where the T^α additive bound comes from, we can set c=⌈Tα⌉."

    T is defined as c(n+1), so c is the number of diagonal blocks and T is determined by c. Setting c = ceil(T^α) then makes c depend on T, while T depends on c. Substituting gives c = ceil((c(n+1))^α), i.e. c^{1−α} ≈ (n+1)^α. For fixed n and 0<α<1 this forces c to be bounded by a constant, so T is bounded and the reduction cannot produce instances with arbitrarily large T. The claimed 'even a T^α-additive approximation for any 0<α<1' hardness therefore does not follow from the written proof; the hardness parameter is defined in terms of itself rather than by a valid growth choice.

full rationale

Most of the paper is self-contained: the exact DPs (Thms 1–2) are direct recurrences over count/state spaces; the 1/2-approx (Thm 4) is a block decomposition, and the cycle-based additive algorithms (Thms 6, 9, 10) use standard max-mean-cycle facts; the experiments measure a defined quantity. There are no fitted constants later called predictions, and no load-bearing self-citations. The one circular step is in Appendix F, Part 2: T is defined as c(n+1), then c is 'set' to ceil(T^α). This makes c a function of T while T is a function of c; substituting yields a bounded c for fixed n and 0<α<1, so the construction cannot produce arbitrarily large T and the claimed T^α-additive hardness is not derived. The flaw is localized and may be repairable (e.g., choose c as a growing polynomial and use L > T(2n−2)+T^α), but the written proof is circular in its parameterization. Score reflects one localized, load-bearing self-definitional step, not global circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 0 invented entities

The central claims rest on the count-based learner model and on two unproved block-averaging assumptions in the approximation proofs; no free parameters are fitted.

axioms (6)
  • domain assumption The opponent's behavior is a count-based learning rule f: N^{k_A} → Δ(B), a function only of empirical action counts (or last-m window counts).
    Definition 2; the entire model of deception and all algorithms assume this summary-statistic dependence.
  • domain assumption ERM and ERM_m break ties deterministically according to a fixed order.
    Definition 3; hardness reductions rely on the specific tie-breaking order (X1,...,Xn,C1,...,Cm,Done in Appendix F).
  • domain assumption For the approximation algorithms, the optimizer's payoffs are in [0,H].
    Section 5 opening: 'All three algorithms assume that player A's payoffs lie in [0,H].'
  • domain assumption For the unknown-opponent algorithm, a 'blank' action exists with zero payoff for both players that clears memory, and optimizer payoffs lie in [0,1].
    Section 6: 'We assume there exists a blank action... and that all payoffs for the optimizer lie in [0,1].'
  • ad hoc to paper The block-averaging lemma: max payoff in even blocks plus max payoff in odd blocks upper-bounds the global optimum, and repeating an optimal 2m block preserves its performance.
    Used in proofs of Theorems 4 and 5 (Appendices B and C); not proven and appears false in general.
  • standard math Standard complexity-theoretic assumption P ≠ NP for hardness.
    NP-hardness reductions in Section 7.

pith-pipeline@v1.3.0-alltime-deepseek · 89 in / 30606 out tokens · 263035 ms · 2026-08-01T03:52:12.134522+00:00 · methodology

0 comments
Cite this review

Pith. "Pith review of On the Power of Deception in Repeated Games." pith.science (2026). https://pith.science/paper/W5W7Z45U

@misc{pith2026260723049,
  author       = {Pith},
  title        = {Pith review of: On the Power of Deception in Repeated Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W5W7Z45U}},
  note         = {Machine review of arXiv:2607.23049}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

In repeated games, opponents often predict what we'll do next by looking at what we have done so far. This allows us to deceive them: we can deliberately behave one way for a period of time to shape their expectations, then switch strategies to profit from the induced response. We study deception in repeated two-player normal-form games against count-based learners, whose behavior depends only on how often we have played each action in the past. We formalize deceptive and non-deceptive play, and introduce the notion of a deception bonus, the payoff gain of the best deceptive strategy over the best fixed mixed strategy. We establish structural results on deception in general-sum games. We design exact dynamic programs for optimizing against any count-based learner when the action space or opponent's memory is small, and develop approximation algorithms for settings where the opponent's memory or the time horizon is large. We also provide an approximation algorithm for learning to deceive an opponent whose count-based learning rule is unknown. To complement our algorithmic results, we show that approximating the optimal deceptive payoff against the classic Empirical Risk Minimization (ERM) learning rule is NP-hard, including obtaining any constant-factor approximation or even a $T^\alpha$-additive approximation for any $0 < \alpha < 1$. Finally, we empirically measure the deception bonus in random games with i.i.d. payoffs.

Figures

Figures reproduced from arXiv: 2607.23049 by Avrim Blum, Dimitar Chakarov, Melissa Dutz, Saba Ahmadi.

Figure 1
Figure 1. Figure 1: Deception bonus vs. number of actions for T = 25 rounds. Error bars show standard error over 500 trials. 25 50 75 100 125 150 175 200 Number of Rounds (T) 0 10 20 30 40 50 60 Average Deception Bonus Zero-sum General-sum [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Utility function u B(a, b) u B (a, b) =    0 b is Xi and a ∈ {XiT , XiF } −n + 1 b is Xi and a ∈ {XjT , XjF }, j ̸= i −2n + 2 b is Cj , a is XiT and xi ∈ cj −2n + 2 b is Cj , a is XiF and ¬xi ∈ cj −n + 3 b is Cj , a is XiT and xi ∈/ cj −n + 3 b is Cj , a is XiF and ¬xi ∈/ cj 0 b is not Done and a is Done −n + 2 b is Done and a is not Done −L b is Done and a is Done Given … view at source ↗
Figure 4
Figure 4. Figure 4: Opponent’s payoffs given example clauses c1 = v1 ∨ ¬v2 ∨vn, cm = ¬v1 ∨v2 ∨vn Assignments Clauses X1 ... Xn C1 ... Cm Done X1T 0 −n + 1 −2n + 2 −n + 3 −n + 2 X1F 0 −n + 1 −n + 3 −2n + 2 −n + 2 X2T −n + 1 −n + 1 −n + 3 −2n + 2 −n + 2 X2F −n + 1 −n + 1 −2n + 2 −n + 3 −n + 2 . . . . . . . . . . . . . . . . . . . . . . . . XnT −n + 1 0 −2n + 2 −2n + 2 −n + 2 XnF −n + 1 0 −n + 3 −n + 3 −n + 2 Done 0 ... 0 0 ... … view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 1 canonical work pages

  1. [1]

    In: Deceptive AI (DeceptAI)

    Aitchison, M., Benke, L., Sweetser, P.: Learning to deceive in multi-agent hidden role games. In: Deceptive AI (DeceptAI). pp. 55–75. Springer (2021)

    2021

  2. [2]

    In: NeurIPS (2024)

    Assos, A., Dagan, Y., Daskalakis, C.: Maximizing utility in multi-agent environments by anticipating the behavior of other learners. In: NeurIPS (2024)

    2024

  3. [3]

    In: COLT

    Assos, A., Dagan, Y., Rajaraman, N.: Computational intractability of strategizing against online learners. In: COLT. pp. 169–199. PMLR (2025)

    2025

  4. [4]

    In: COLT

    Audibert, J.Y., Bubeck, S.: Minimax policies for adversarial and stochastic bandits. In: COLT. pp. 217–226 (2009)

    2009

  5. [5]

    In: AAMAS

    Balcan, M.F., Blum, A., Chen, S.T.: Diversified strategies for mitigating adversarial attacks in multiagent systems. In: AAMAS. pp. 407–415 (2018)

    2018

  6. [6]

    NeurIPS33, 20624– 20635 (2020)

    Birmpas, G., Gan, J., Hollender, A., Marmolejo, F., Rajgopal, N., Voudouris, A.: Optimally deceiving a learning leader in stackelberg games. NeurIPS33, 20624– 20635 (2020)

    2020

  7. [7]

    Braverman, M., Mao, J., Schneider, J., Weinberg, M.: Selling to a no-regret buyer. In: EC. pp. 523–538 (2018)

    2018

  8. [8]

    Brown, W., Schneider, J., Vodrahalli, K.: Is learning in games good for the learners? NeurIPS36, 54228–54249 (2023)

    2023

  9. [9]

    Carminati, L., Zhang, B.H., Farina, G., Gatti, N., Sandholm, T.: Hidden-role games: Equilibrium concepts and computation. In: EC. pp. 106–107 (2024)

    2024

  10. [10]

    Infor- mation Processing Letters127, 21–22 (2017)

    Chaturvedi, M., McConnell, R.M.: A note on finding minimum mean cycle. Infor- mation Processing Letters127, 21–22 (2017)

    2017

  11. [11]

    arXiv preprint arXiv:2302.11829 (2023)

    Chen, Y., Deng, X., Gan, J., Li, Y.: Learning to manipulate a commitment optimizer. arXiv preprint arXiv:2302.11829 (2023)

    Pith/arXiv arXiv 2023

  12. [12]

    IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems17(10), 889–899 (2002)

    Dasdan, A., Gupta, R.K.: Faster maximum and minimum mean cycle algorithms for system-performance analysis. IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems17(10), 889–899 (2002)

    2002

  13. [13]

    NeurIPS 32(2019)

    Deng, Y., Schneider, J., Sivan, B.: Strategizing against no-regret learners. NeurIPS 32(2019)

    2019

  14. [14]

    In: STOC

    Fortnow, L., Whang, D.: Optimality and domination in repeated games with bounded players. In: STOC. pp. 741–749 (1994)

    1994

  15. [15]

    In: FOCS

    Freund, Y., Kearns, M., Mansour, Y., Ron, D., Rubinfeld, R., Schapire, R.E.: Efficient algorithms for learning to play repeated games against computationally bounded adversaries. In: FOCS. pp. 332–341. IEEE (1995)

    1995

  16. [16]

    Gan, J., Xu, H., Guo, Q., Tran-Thanh, L., Rabinovich, Z., Wooldridge, M.: Imitative follower deception in stackelberg games. In: EC. pp. 639–657 (2019)

    2019

  17. [17]

    Discrete Mathematics23(3), 309–311 (1978)

    Karp, R.M.: A characterization of the minimum cycle mean in a digraph. Discrete Mathematics23(3), 309–311 (1978)

    1978

  18. [18]

    Kuhn, H.W.: A Simplified Two-Person Poker, pp. 97–104. Princeton University Press, Princeton (1951). https://doi.org/10.1515/9781400881727-010

    work page doi:10.1515/9781400881727-010 1951

  19. [19]

    In: Loh, P.L., Raginsky, M

    Mansour, Y., Mohri, M., Schneider, J., Sivan, B.: Strategizing against learners in bayesian games. In: Loh, P.L., Raginsky, M. (eds.) COLT. PMLR, vol. 178, pp. 5221–5252 (2022)

    2022

  20. [20]

    In: IJCAI

    Nguyen, T., Xu, H.: Imitative attacker deception in stackelberg security games. In: IJCAI. pp. 528–534 (2019)

    2019

  21. [21]

    best arm

    Nguyen, T.H., Butler, A., Xu, H.: Tackling imitative attacker deception in repeated bayesian stackelberg security games. In: ECAI. pp. 187–194 (2020) On the Power of Deception in Repeated Games 19 A Proofs from Section 4 Proof (Proof of Theorem 1).For t = 1, each count vector is a one-hot vector representing a single actionai being played once. The best p...

    2020

  22. [22]

    The addedT α rules out an additiveT α approximation

    + T α makes obtaining L necessary for obtaining an optimal payoff. The addedT α rules out an additiveT α approximation. L > T(2n− 2) + T α also ensures opponent will not play Doneb if the optimizer has playedDoneb in the past (the maximum negative score of any column besidesDoneb is T (−2n + 2), and the−L score for the Doneb column in this case will be st...