On the Implications of Lookahead Search in Game Playing

Vahab S. Mirrokni, Nithum Thain, Adrian Vetta

TL;DR

This paper provides a theoretical analysis of "lookahead search," a common strategy where agents anticipate future moves to make better decisions. The authors investigate how different levels of foresight (k-lookahead) impact social welfare and game dynamics across various economic and game theory settings, finding that increased foresight can be beneficial but also, surprisingly, detrimental in certain scenarios.

What Problem Does This Paper Address?

While lookahead search is a ubiquitous strategy in game playing, from chess to economic interactions, its theoretical implications for social outcomes and interactive behaviors have been underexplored. The paper aims to bridge this gap by systematically analyzing how agents using k-lookahead search (predicting k moves ahead) perform in diverse game settings. The core questions are: does increased foresight improve the overall "social quality" of outcomes, and what novel interactive behaviors emerge? This is particularly relevant for understanding boundedly rational agents who cannot compute perfect foresight due to computational constraints.

Methods

The authors formalize k-lookahead search, where an agent builds a search tree of depth k to evaluate potential moves. They analyze outcomes using two primary frameworks:

  • Equilibria: They define "lookahead equilibria" where no player can improve their outcome by unilaterally changing their strategy based on their k-lookahead evaluation. The "coordination ratio" (or price of anarchy) measures how far these equilibria are from the optimal social outcome.
  • Dynamics: They study "lookahead dynamics" by analyzing random walks on the state graph, where players iteratively update their strategies to their k-lookahead best response. The coordination ratio here measures the expected social value along these walks.

They apply these methods to five distinct game types: AdWord auctions, Cournot competition, congestion games, valid-utility games, basic-utility games, and Shapley network design games.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and uses established game models rather than empirical datasets.

Key Insights and Ideas

  • Foresight is a Double-Edged Sword: While increased foresight often leads to better social outcomes (e.g., in AdWord auctions and Cournot competition), it can surprisingly lead to worse outcomes in certain games like basic-utility games, challenging the intuitive assumption that more foresight is always better.
  • Myopic Behavior is Often Suboptimal: In many scenarios, particularly AdWord auctions, myopic (1-lookahead) play can result in arbitrarily poor equilibrium outcomes, highlighting the value of even limited foresight.
  • Emergence of Novel Behaviors: Lookahead search can induce behaviors not typically seen in simpler models, such as Stackelberg leader-follower dynamics (when agents have asymmetric computational power) and "uncoordinated" cooperative behavior in network design games.
  • Game Structure Matters: The impact of lookahead search is highly dependent on the specific game's structure, including its payoff functions and the nature of interactions.

Key Results

  • AdWord Auctions: 2-lookahead search leads to optimal or near-optimal social outcomes, a significant improvement over myopic play which can be arbitrarily poor.
  • Cournot Competition: 2-lookahead leads to a 12.5% increase in output and a 5.5% increase in social surplus compared to myopic play. Optimal foresight for social welfare is found to be k=2.
  • Congestion Games: Lookahead search provides constant-factor qualitative guarantees, similar to myopic play.
  • Basic-Utility Games: While myopic play offers constant-factor guarantees, 2-lookahead can lead to arbitrarily bad social welfare outcomes in the leaf model.
  • Shapley Network Design Games: Lookahead search can encourage cooperative behavior without explicit coordination mechanisms.

Limitations and Future Work

  • Focus on Specific Models: The paper primarily analyzes the "leaf model" (payoffs only at the end of the game) and the "path model" (accumulated payoffs over time), and assumes agents use max/min functions for evaluation. It doesn't explore more complex evaluation functions or risk-averse behaviors in depth.
  • Computational Complexity: While the paper assumes bounded computational power (k-lookahead), it doesn't delve deeply into the computational complexity of these strategies themselves.
  • Asymmetric Information: The analysis largely assumes complete information, though it touches upon asymmetric computational power.
  • Future Work: The authors suggest further investigation into which game structures benefit most from longer foresight and which lead to detrimental outcomes. Exploring the impact of asymmetric information and more complex agent behaviors would also be valuable.

Summary updated

Abstract

Lookahead search is perhaps the most natural and widely used game playing strategy. Given the practical importance of the method, the aim of this paper is to provide a theoretical performance examination of lookahead search in a wide variety of applications. To determine a strategy play using lookahead search}, each agent predicts multiple levels of possible re-actions to her move (via the use of a search tree), and then chooses the play that optimizes her future payoff accounting for these re-actions. There are several choices of optimization function the agents can choose, where the most appropriate choice of function will depend on the specifics of the actual game - we illustrate this in our examples. Furthermore, the type of search tree chosen by computationally-constrained agent can vary. We focus on the case where agents can evaluate only a bounded number, $k$, of moves into the future. That is, we use depth $k$ search trees and call this approach {\em k-lookahead search}. We apply our method in five well-known settings: AdWord auctions; industrial organization (Cournot's model); congestion games; valid-utility games and basic-utility games; cost-sharing network design games. We consider two questions. First, what is the expected social quality of outcome when agents apply lookahead search? Second, what interactive behaviours can be exhibited when players use lookahead search?
BibTeX
@inproceedings{mirrokni2012implications,
  author = {Vahab S. Mirrokni and Nithum Thain and Adrian Vetta},
  title = {{On the Implications of Lookahead Search in Game Playing}},
  booktitle = {SAGT},
  year = {2012},
  doi = {10.1007/978-3-642-33996-7\_22},
}
Figure