In classical game theory, we often assume agents are "Nash equilibrators"—perfectly rational actors who can calculate the optimal move by assuming everyone else is also perfectly rational, ad infinitum. However, real-world behavior, from human drivers at an intersection to players in a social deduction game, rarely follows this path of infinite recursion. Instead, agents exhibit bounded rationality, operating within a finite hierarchy of strategic depth.
This research direction focuses on modeling agents through Cognitive Hierarchies or Level-$k$ reasoning. Rather than solving for a complex equilibrium, these models assume that an agent’s strategy is a best response to a simplified model of their opponent’s reasoning.
The Hierarchy of "I Think That You Think"
The core intuition of this framework is that strategic reasoning can be decomposed into discrete levels. Each level represents a step deeper into the recursive "I think that you think" logic:
- Level-0 ($L_0$): The non-strategic baseline. These agents act according to simple heuristics, fixed preferences, or even random choice. They do not consider the mental states of others.
- Level-1 ($L_1$): These agents assume their opponents are $L_0$. They optimize their actions against a world of non-strategic actors.
- Level-k ($L_k$): An agent at level $k$ assumes their opponent is at level $k-1$ (or a distribution of levels from $0$ to $k-1$).
As James R. Wright and Kevin Leyton-Brown demonstrate in Beyond Equilibrium: Predicting Human Behavior in Normal-Form Games, this hierarchical approach is a significantly better predictor of human behavior than Nash equilibrium. Humans typically plateau at very low levels of recursion—often just one or two steps—making models that account for these cognitive bounds far more accurate in practice.
Anchoring the Hierarchy: The Importance of Level-0
The entire tower of recursive reasoning rests on the $L_0$ baseline. If the model of the "naive" agent is wrong, every subsequent level of reasoning will be misaligned.
Historically, $L_0$ was often modeled as uniform randomness. However, James R. Wright and Kevin Leyton-Brown argue in Models of Level-0 Behavior for Predicting Human Behavior in Games that $L_0$ behavior is actually driven by non-strategic features like fairness, safety, or salience. By accurately modeling this "ground floor," researchers can better predict how sophisticated agents will try to exploit or cooperate with those baseline tendencies.
From Theory to Planning: I-POMDPs
To move from predicting behavior to active planning, researchers use Interactive Partially Observable Markov Decision Processes (I-POMDPs). Introduced by Prashant Doshi and Piotr J. Gmytrasiewicz in A Framework for Sequential Planning in Multi-Agent Settings, I-POMDPs incorporate models of other agents directly into an agent's state space.
Instead of treating other agents as random environmental noise, an I-POMDP agent maintains beliefs about the models other agents are using. This allows for sophisticated coordination and anticipation. For example, in Target Surveillance in Adversarial Environments Using POMDPs, Mykel J. Kochenderfer and colleagues use this recursive depth to allow a surveillance agent to anticipate and avoid the traps of an intelligent adversary.
Strategic Depth as a Computational Phenotype
The level of strategic depth an individual employs isn't just a mathematical curiosity; it appears to be a fundamental trait of social cognition. Ting Xiang, Peter Dayan, and P. Read Montague have explored this in Computational Phenotyping of Two-Person Interactions Reveals Differential Neural Response to Depth-of-Thought.
By using a "Theory of Mind" hierarchy to categorize subjects, they found that a person's reasoning level correlates with how their brain processes social errors. This suggests that "depth-of-thought" can serve as a computational phenotype for understanding psychiatric disorders and social behavior.
Applications: Security, Traffic, and Deception
Modeling strategic depth has immediate practical applications in environments where agents must interact with adaptive, but boundedly rational, counterparts:
- Cyber-Physical Security: Anibal Sanjab and Walid Saad show in On Bounded Rationality in Cyber-Physical Systems Security that defenders can protect systems more effectively by anticipating that attackers have limited computational power or incomplete knowledge.
- Autonomous Driving: In dense traffic, merging is a social negotiation. Zhiyu Huang and Chen Lv use GameFormer to iteratively refine vehicle trajectories through multiple levels of reasoning, mimicking the "I'll go if you slow down" logic of human drivers.
- Deception: In the game Avalon, Shenzhi Wang and colleagues used Recursive Contemplation (ReCon) to help LLMs handle deception. They found that first-order reasoning helps detect lies, while second-order reasoning—thinking about how one is perceived—is essential for maintaining a disguise.
The Diminishing Returns of Depth
A recurring finding across these papers is that more depth is not always better. Debajyoti Ray and Peter Dayan note in Bayesian Model of Behaviour in Economic Games that highly strategic agents can sometimes perform worse than moderately strategic ones. Over-analyzing an opponent's potential for defection can lead to "cynical" behavior that misses out on cooperative gains.
Effective performance often requires being just one step ahead of the adversary. As Víctor Gallego and David Ríos Insua suggest in Reinforcement Learning under Threats, infinite recursive chains are unnecessary; the goal is to find the "sweet spot" of strategic depth that balances predictive power with computational feasibility.