Theory Seminar

Strategies for Extensive Form Games

Richard StearnsUniversity at Albany


An extensive form game is a game carried out in a sequence of steps where each player has only a partial knowledge of the state of the game. Think poker where the state of the game is the hands dealt and the betting so far, but each player knows only his own cards.

We provide simple answers to the following questions using linear equations:

(1) What strategies need to be considered?

(2) What is the effect of a strategy on the outcome of the game?

(3) How can a strategy be implemented?

Answers to these questions are well-known for the case called "perfect recall". We show how the techniques for perfect recall can be generalized to the general case.

Richard Edwin Stearns is a prominent computer scientist who, with Juris Hartmanis, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory" (Hartmanis and Stearns, 1965). In 1994 he was inducted as a Fellow of the Association for Computing Machinery.

Stearns earned his PhD from Princeton University in 1961. His PhD thesis adviser was Harold W. Kuhn. Stearns is now Distinguished Professor Emeritus of Computer Science at the University at Albany, which is part of the State University of New York.

Sponsored by