December 21, Tuesday 12:15, room 665 Education Building

** 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.