пожалуйста, возвращайтесь позднее
пожалуйста, возвращайтесь позднее
ECON-159: GAME THEORY
Lecture 15 - Backward Induction: Chess, Strategies, and Credible Threats [October 29, 2007]
Chapter 1. First and Second Mover Advantages: Zermelo's Theorem [00:00:00]
Professor Ben Polak: So last time we finished up by playing the game of Nim and you'll remember, I hope, that the game of Nim was a game where there was two piles of stones — we made do with lines on the board — and the winner was the person who picked up the last stone. Remember you had to pick piles. I want to use the game of Nim to make a transition here. So what we had pointed out about the game of Nim was it illustrated very nicely for us that games can have first mover advantages or they can have second mover advantages. A very small change in the game, essentially a very small change in where we started from, could switch a game from a game with a first mover advantage to a game with a second mover advantage.
Now today, I want to just draw a slightly grander lesson out of that game. So not only was it the case that the game sometimes has first mover advantages and sometimes has second mover advantages, but moreover, we could tell when it had a first mover advantage and we could tell when it had a second mover advantage. Is that right? When we actually looked at the initial set up of those stones, we knew immediately that's a game in which Player 1 is going to win, or alternatively, we knew immediately that's a game which Player 2 is going to win. Now it turns out that that idea is very general and actually has a name attached to it, and that name is Zermelo. So today we'll start off by talking about a theorem due to a guy called Zermelo, and the idea of this theorem is this.
We're going to look at games more general than just Nim, and we're going to ask the question, under what circumstances would you know about a game either that Player 1, the person who goes first, can force a win, or that Player 2 can force a win, or will allow a third possibility, which is it's going to be a tie. So here's the theorem, suppose there are two players in this game, like the games that we looked at last time, and suppose — I won't define this formally now — but suppose the game is a game of perfect information. So what do I mean by perfect information? I'll define this later on in the class, but for now all I mean is, that whenever a player has his turn to move, that player knows exactly what has happened prior in the game.
So, for example, all these sequential move games we've been looking at are moves of perfect information. When I get to move I know exactly what you did yesterday, I know what I did the day before yesterday and so on. So it's a game of perfect information. I'm going to assume that the game has a finite number of nodes. So two things here, it can't go on forever, this game, and also there's no point in which it branches in an infinite way. So there's a finite number of nodes, and we'll assume that the game has three possible outcomes. Actually there's a more general version of this theorem but this will do for now.
The three possible outcomes are either a win for Player 1, so I'll call it W1, or a loss for Player 1, which is obviously a win for Player 2, or a tie. So the game — like Nim last time, that only had two outcomes. So here we're going to look up to three outcomes or three or fewer outcomes I should say. So these are the conditions and here's the result. So I said three, it could be three but it could also be two here, I'm just allowing for three. (One is trivial.)