An extensive form game, unlike a regular one-shot-game, has the element of sequential or repeated movement. Chess for example, is an extensive form game. However, we will see that our mathematical definition of “game” will be much broader, so models we construct can be applied to problems in economics, computer science, and engineering—not just chess.

We will explore what it means to “solve” a game where players make back to back moves. We will also go over games where players pick their moves at the same time but play over and over. There will be a review of basic definitions from Game Theory Part 1, and we will introduce some new terms which will help us with extensive forms.

At the end, we can hopefully look at some interesting applications.

Note: this builds on the first Game Theory talk given in Fall 2016. If you need to review important concepts or you couldn’t attend, a webpage with definitions and basic information is available here. We’ll do a brief review so don’t worry too much! If you didn’t come to the first session, you should be able to understand everything here regardless.

Walkthrough

• The ultimatum game

• What is a game? What is an extensive game? A repeated game?

• What is a “strategy” in an extensive game?

• How do you “solve” an extensive game? How is it different from solving a regular one-shot game?

  • Nash vs. Subgame perfect equilibrium

  • Backward induction

• Infinite games: what happens when these games go on forever? How can we solve them?

  • One-shot deviation principle

  • Using sequences

  • Example: repeated prisoner’s dilemma

• Applications: bargaining theory, price matching, power control in a wireless network, etc.