Level-k Distinguishable Mechanisms for Evaluating Bounded Rationality in LLMs

Binchi Zhang; Atrisha Sarkar

cs.MAAug 21, 2026

Level-k Distinguishable Mechanisms for Evaluating Bounded Rationality in LLMs

Authors: Binchi Zhang, Atrisha Sarkar

Organizations: University of Western Ontario

Abstract

Strategic depth of reasoning is essential for human interaction of Large Language Models (LLMs) operating in boundedly rational environments. However, existing evaluations are primarily based on canonical games prevalent in pretraining corpora, making it difficult to disentangle true strategic reasoning from memorisation. To address this, we formalise a necessary level-K distinguishability condition for strategic depth inference and construct a suite of novel game structures that meet this standard. Using these games, we evaluate strategic depth in LLMs from both the Chain-of-Thought tokens and actual actions under recursive reasoning and an inductive trace of opponent game-play data. Across experimental trials spanning four LLMs, four game structures, and ten levels of iterated reasoning, we find that model models maintain accurate strategic depth under recursive reasoning, with strong internal consistency between stated reasoning and actions at every level. Errors arise from using the wrong number of iterated depth of reasoning steps, not from computing best responses incorrectly. However, inductive inference from opponent play degrades accuracy sharply and unevenly across games, and explicit strategic mentalizing in the chain of thought substantially improves overall performance.

Figures & tables

	11–20 (Mod.)	All-Pay Auction	Nash Demand	Ring 11–20
Players	2	2	2	5 (ring)
Strategy space $S$	$\{50,\dots,70\}$	$\{0,\dots,10\}$	$\{1,\dots,20\}$	$\{1,\dots,20\}$
Payoff	$u_{i}(s_{i},s_{j})=s_{i}$ $+\,24\,\mathbf{1}[s_{i}=s_{j}-2]$ $+\,8\,\mathbf{1}[s_{i}=s_{j}-1]$	$u_{i}(s_{i},s_{j})=12\,\mathbf{1}[s_{i}>s_{j}]$ $+\,6\,\mathbf{1}[s_{i}=s_{j}]-s_{i}$	$u_{i}(s_{i},s_{j})=s_{i}\,\mathbf{1}[s_{i}+s_{j}\leq 20]$ $+\,0.8\,s_{i}\,\mathbf{1}[s_{i}+s_{j}>20]\,\mathbf{1}[s_{i}<s_{j}]$	$u_{i}(s_{i},\mathbf{s}_{-i})=s_{i}$ $+\,10\,\mathbf{1}[s_{i}=s_{i-1}-3]$ $+\,3\,\mathbf{1}[s_{i}=s_{i+1}+7]$
$a^{(0)}$	70	0	20	20
IDR sequence	Decreasing	Increasing	Decreasing	Periodic
$K_{\max}$	10	10	10	9

Table 1: Summary of the game structures with level-

k

distinguishability.

Panel of Figure 1 — Figure 1: The Ring 11–20 game (player indices modulo 5). Solid arrows point from each player $i$ to the left neighbor $i-1$ carrying the primary $+10$ bonus ( $s_{i}=s_{i-1}-3$ ); dashed arrows point to the right neighbor $i+1$ carrying the secondary $+3$ bonus ( $s_{i}=s_{i+1}+7$ ).

Figure 2: Recursive condition: Depth limit—linguistic and behavioral signals as a function of target depth. Each panel is one model; solid lines and markers show $K_{B}$ (behavioral depth), dashed lines show $K_{L}$ (linguistic depth), and the gray dashed diagonal marks where $K$ equals target $k$ .

Figure 3: Inductive condition: Depth limit—linguistic and behavioral signals as a function of target depth. Columns are models and rows are the sampling precision $\lambda$ ; solid lines and markers show $K_{B}$ (behavioral depth), dashed lines show $K_{L}$ (linguistic depth), and the gray dashed diagonal marks where $K$ equals target $k$ .

	11–20 (Mod.)		All-Pay Auction		Nash Demand		Ring 11–20
Model	Rec.	Ind.	Rec.	Ind.	Rec.	Ind.	Rec.	Ind.
Sonnet 4.6	49.0 (99.0)	81.0 (81.0)	54.0 (100.0)	14.0 (86.0)	49.0 (91.0)	2.0 (6.0)	41.1 (97.8)	61.1 (61.1)
Qwen 3.6 27B	91.0 (95.5)	90.5 (90.5)	92.5 (100.0)	10.0 (80.0)	83.5 (94.0)	1.0 (1.0)	86.0 (98.3)	64.4 (64.4)
Gemma 4 31B	88.5 (96.5)	90.0 (90.0)	87.5 (95.5)	14.0 (77.5)	88.0 (89.5)	2.5 (4.0)	71.1 (80.6)	65.6 (71.1)
DeepSeek v4 Pro	89.5 (99.5)	80.5 (90.5)	91.0 (100.0)	18.0 (89.5)	86.5 (89.0)	0.5 (0.5)	86.7 (89.4)	55.0 (56.1)

Table 2: Accuracy of reaching target strategic depth across games and condition. Parenthesised: within-one-level accuracy,

|K_{B}-k_{\text{target}}|\leq 1

. Rec. = recursive condition; Ind. = inductive condition at

\lambda=10

, the sampling precision at which the opponent’s level is reliably recoverable from the observed history. Full

\lambda

sweep in Appendix C.2 .

Figure 4: Per-step best-response consistency and chain length against target depth $k$ , over recursive-condition trials, one panel per model. The solid line with markers is per-step consistency on the left axis—the share of adjacent steps in a model’s written run that are exact best responses—with 95% confidence intervals. The heavy dotted line is mean chain length on the right axis, and the grey dashed diagonal is the target length, $m=k$ . Plotting convention: both series break between $k=4$ and $k=5$ , where the form of the opponent description changes: chain length is drawn as two separate segments, and the consistency line runs from $k=3$ straight to $k=5$ , with $k=4$ hung off it on fine dotted spurs.

Model	Mentalizing	Accuracy
Model	Mentalizing	with	without
Sonnet 4.6	6.0%	40.3%	19.3%
Qwen 3.6 27B	28.3%	29.6%	12.4%
Gemma 4 31B	39.3%	20.6%	15.7%
DeepSeek v4 Pro	65.7%	21.4%	10.4%

Table 3: Strategic theory-of-mind mentalizing under the inductive condition. Mentalizing is the share of trials whose chain of thought states that the opponent reasons about the model’s own choice; the two accuracy columns split those trials from the rest.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Game	$\operatorname{br}(a)$	Range of $a$	Role
11–20 (Mod.)	$a-2$	$a\geq 52$	generating
11–20 (Mod.)	$70$	$a\leq 51$	closes the cycle
All-Pay Auction	$a+1$	$a\leq 9$	generating
All-Pay Auction	$0$	$a=10$	closes the cycle
Nash Demand	$a-1$	$a\geq 12$	generating (undercut)
Nash Demand	$20-a$	$a\leq 11$	concede; $L_{10}$ onward

Appendix

Table 4: The best-response map of each game in closed form, checked against every action in

S

. Branches marked generating are those the IDR sequence uses; the remaining branches return the sequence to a value it has already visited and therefore set

K_{\max}

Game		Text
11–20 (Mod.)	Rules	I am playing a two-player game. My opponent and I each simultaneously choose an integer from 50 to 70. My payoff equals my chosen number, plus a bonus of 24 if my number is exactly 2 less than my opponent’s, or a bonus of 8 if my number is exactly 1 less than my opponent’s. I want to maximize my payoff. What integer should I choose?
	$L_{0}$	Your opponent plays naively. They have no strategic awareness and simply try to maximize their own base payoff without considering how your choice might interact with theirs.
	$L_{1}$	Your opponent is a basic strategic thinker. They assume you will naively maximize your own base payoff, and they choose the action that best responds to a base-payoff maximizer.
	$L_{2}$	Your opponent is a moderately sophisticated thinker. They assume you are a basic strategist who best-responds to naive base-payoff maximizers, and they choose the action that best responds to that level of reasoning.
	$L_{3}$	Your opponent is a deeply strategic thinker. They assume you are moderately sophisticated --- someone who best-responds to basic strategists --- and they choose the action that best responds to that deeper level of reasoning.
All-Pay Auction	Rules	I am playing a two-player all-pay auction. My opponent and I each simultaneously choose a bid from 0 to 10 (integers only). Both of us pay our bid regardless of the outcome. If my bid is strictly higher, I win a prize of 12. If we tie, I receive 6. If my bid is lower, I receive nothing. My payoff is: prize (if any) minus my bid. I want to maximize my payoff. What integer should I bid?

Appendix

Table 5: Rules text and

L_{0}

–

L_{3}

opponent descriptions for 11–20 (Mod.) and the All-Pay Auction, reproduced verbatim. The

L_{0}

description is also substituted into the template used for

L_{4}

–

L_{9}

Item	Specification
Models	Called through OpenRouter by slug: google/gemma-4-31b-it , qwen/qwen3.6-27b , anthropic/claude-sonnet-4-6 , deepseek/deepseek-v4-pro
Reasoning mode	Default effort requested for gemma-4 and qwen3.6 ; no reasoning parameter sent for the other two, which ran at the provider default. The resolved configuration is recorded per trial
Decoding	Temperature 0.2 and max_tokens 8192 sent on every request, and reported as sent: a provider may ignore or clamp them
Routing	Provider fallback enabled, so consecutive requests may be served by different upstream providers; the serving provider is recorded per turn. Pin a single provider to reproduce a run exactly
Tools	submit_action takes the final chosen number and is called once after reasoning. query_opponent_history takes no arguments and returns 30 integers; its one-call limit is stated in the description but not enforced, and the call count is recorded
Turn cap	10 turns per trial

Appendix

Table 7: Models, decoding, and protocol.

Group	Cond.	Fields
Anchor	rec.	anchor_present , anchor_value , anchor_concept
Chain	rec.	chain[] , entries $(\texttt{value},\texttt{attributed\_to},\texttt{quote})$ ; iteration_verbalized
History	ind.	history_referenced , cited_statistics[] , noise_acknowledged , claimed_n
Belief	both	final_belief_point with final_belief_ambiguous and final_belief_candidates ; belief_is_distribution , belief_support[]
Decision	both	claimed_br , payoff_computations[]
Mentalizing	rec.	opponent_models_me

Appendix

Table 8: The judge fields that feed the reported results.

Explore similar work

Mar 19, 2026

Evaluating Counterfactual Strategic Reasoning in Large Language Models

We evaluate Large Language Models (LLMs) in repeated game-theoretic settings to assess whether strategic performance reflects genuine reasoning or reliance on memorized patterns. We consider two canonical games, Prisoner's Dilemma (PD) and Rock-Paper-Scissors (RPS), upon which we introduce counterfactual variants that alter payoff structures and action labels, breaking familiar symmetries and dominance relations. Our multi-metric evaluation framework compares default and counterfactual instantiations, showcasing LLM limitations in incentive sensitivity, structural generalization and strategic reasoning within counterfactual environments.

Dimitrios Georgousis, Maria Lymperaiou, Angeliki Dimitriou +2

National Technical University of Athens

Strategic Reasoning Risks in Language Models LLM Evaluation Counterfactual Reasoning in Language Models Counterfactual Evaluation

Ask PDF

May 22, 2026

GENSTRAT: Toward a Science of Strategic Reasoning in Large Language Models

Large language models (LLMs) are increasingly deployed as economic agents in marketplaces, auctions, and bidding settings. Anticipating their behavior in any specific deployment is hard. Existing strategic-reasoning benchmarks evaluate models on fixed canonical games. These benchmarks may saturate as the frontier improves, and they do not allow evaluators to generalize with confidence from benchmark performance to the varied and messy strategic environments that actual deployments involve. We introduce GENSTRAT, which uses procedurally generated strategic environments to address these challenges. Concretely, we generate a distribution of two-player zero-sum imperfect-information card games. The generator can draw fresh games on demand, allowing for evergreen evaluation and resistance to contamination. We pair the game distribution with a capability-profile methodology that decomposes model competence across six axes (state space, temporal depth, information sensitivity, opponent modeling, risk, and brittleness). We also introduce a jaggedness measure of within-distribution smoothness that detects when a model's advantage jumps unpredictably between strategically similar games. We sample 50 benchmark games from a 2,000-game generated pool and evaluate nine frontier and open-weight LLMs in a head-to-head tournament with over 36,000 matches. Newer frontier-tier models score higher on average. Beyond that average, models with near-identical overall strength show qualitatively different capability profiles, and two of the top three leaderboard models (gpt-5 and claude) are noticeably more locally volatile than the third (gemini-3.1-pro), despite being close in overall strength. Together, the capability profile and the jaggedness measure give a deployment-relevant diagnostic that the overall ranking alone cannot provide.

Vartan Shadarevian, Kia Ghods, Alex Kenich +1

Princeton University · Google

LLM Evaluation Imperfect-Information Games Game Theory Zero-Sum Games Strategic Reasoning Risks in Language Models AI Agent Benchmarks+2

Ask PDF

Feb 22, 2026

Reasoning Capabilities of Large Language Models. Lessons Learned from General Game Playing

This paper examines the reasoning capabilities of Large Language Models (LLMs) from a novel perspective, focusing on their ability to operate within formally specified, rule-governed environments. We evaluate four LLMs (Gemini 2.5 Pro and Flash variants, Llama 3.3 70B and GPT-OSS 120B) on a suite of forward-simulation tasks-including next / multistep state formulation, and legal action generation-across a diverse set of reasoning problems illustrated through General Game Playing (GGP) game instances. Beyond reporting instance-level performance, we characterize games based on 40 structural features and analyze correlations between these features and LLM performance. Furthermore, we investigate the effects of various game obfuscations to assess the role of linguistic semantics in game definitions and the impact of potential prior exposure of LLMs to specific games during training. The main results indicate that three of the evaluated models generally perform well across most experimental settings, with performance degradation observed as the evaluation horizon increases (i.e., with a higher number of game steps). Detailed case-based analysis of the LLM performance provides novel insights into common reasoning errors in the considered logic-based problem formulation, including hallucinated rules, redundant state facts, or syntactic errors. Overall, the paper reports clear progress in formal reasoning capabilities of contemporary models.

Maciej Świechowski, Adam Żychowski, Jacek Mańdziuk

Grail Team Warsaw, Poland · Warsaw University of Technology Warsaw, Poland · AGH University of Krakow Cracow, Poland

LLM Reasoning LLM Evaluation

Ask PDF