December 21, Tuesday 12:15, room 665
** NOTE SPECIAL DAY, TIME, AND PLACE **
Bridging game-theory and AI: Lessons from Interdisciplinary Research
Lecturer : Inon Zuckerman
Lecturer homepage : http://www.cs.umd.edu/~inon/
Affiliation : Institute for Advanced Computer Studies, University of Maryland
The popularity of game theory can be witnessed through the widespread application of its models to different research areas. However, the application of game theoretical models is often done with limited consideration to the underlying assumptions of the models. In this talk I present two problem domains and show how such inherited assumptions limit the accuracy and usefulness of the solutions. The first domain comes form mainstream AI, game-tree search. Game-tree search algorithms are heavily based on theoretical results that assume both unbounded computational resources and rational players. In reality, for most games, players cannot search the entire tree due to computational limitations. As such, algorithms use various techniques to increase their search horizon under a common assumption that deeper search yields more accurate decisions. However, it was shown more than 30 years ago that there exist a class of games, namely Pathological games, in which this assumption is incorrect. In this research I show that game-tree pathology is a local phenomena that might exist in *all* games. I will then present an algorithm that recognizes pathological sub-trees and adapts its decision procedure accordingly. The second problem is the evolution of cooperation, an interdisciplinary problem from AI and Theoretical Biology. To study this problem researchers often use the Prisoner's dilemma game to model the interactions between players. Most of the existing works use the selfish, self-maximizing player model that was inherited from game theoretical analysis. However, theories from the social and behavioral sciences show that people explicitly consider the payoff of other players when making decisions. As such, we utilize the Social Value Orientation theory to present a new player model which provide a more accurate description of human behavior. With this new model we were able to gain new insights on the evolution of cooperative societies.