On the Implications of Lookahead Search in Game Playing

Details On the Implications of Lookahead Search in Game Playing On the Implications of Lookahead Search in Game Playing

2012-02-19

arxiv.org/abs/1202.4134v1

Computer Science

Computer Science and Game Theory

Scientific paper

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?

Affiliated with

Also associated with

No associations

Rating

On the Implications of Lookahead Search in Game Playing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Implications of Lookahead Search in Game Playing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Implications of Lookahead Search in Game Playing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-419281