Groupe d’études et de recherche en analyse des décisions

Thinking ahead: an approach to game playing

Adrian Vetta Professeur agrégé, Département de mathématiques et statistiques, Université McGill, Canada

My work focuses on algorithms and complexity and their applications. In this talk I will focus on one application in game theory. With Vahab Mirrokni (Google) and Nithum Thain (U. of Oxford), I gave a theoretical examination of perhaps the most natural and widely used game playing strategy: lookahead search. To determine a strategy play, each agent predicts multiple levels of possible re-actions to her move (via the use of a search tree), and then choses 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. Furthermore, the type of search tree chosen by computationally-constrained agent can vary. We focused on the case where agents that can evaluate only a bounded number of moves into the future, namely k-lookahead search, and applied our method to five examples: industrial organization; AdWord auctions; congestion games; valid-utility games and basic-utility games; cost-sharing network design games. We had two main goals. 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? I will discuss some of our results in this talk.