Transcription
Introduction to Game TheoryThe mathematical area known as game theory is generally described something like this: the systematic study of situations ofconflict and cooperation. While the modern form of game theorywas initiated by the Hungarian-American mathematician John vonNeumann (1903–1957) in 1928, many of the underlying ideas hadbeen developed much earlier, dating back to the early 1700’s.As second key player in the development of game theory is theUS mathematician John Nash (1928–2015), subject of the movie ABeautiful Mind .1
For the purposes of game theory, a game is a situation with thefollowing properties: There are at least two players. A player may be an individual,but it may also be a more general entity such as a company, anation, a biological species etc. Each player has a range of possible strategies: courses of actionthat the player may follow. The strategies chosen by each player determine the outcome ofthe game. Associated to each possible outcome of the game is a collection of numerical payoffs, one to each player. These payoffsrepresent the value of the outcome to the different players.We’ll focus on zero-sum games, by which we mean games in whichone player’s gain is precisely the other player’s loss.Example 1. Our two players will be Rose and Colin. We’ll startwith a game in which Rose has three possible strategies A, B, andC, and Colin has two strategies A and B. Here and throughout,Rose-A isn’t necessarily the same as Colin-A and similarly for otherlabeling. The outcomes of the game will be as follows (Rose, Colin):Rose/ColinABCAB(10, 10) ( 25, 25)( 4, 4) (10, 10)( 39, 39) (66, 66)2
Since Colin’s payoffs are just the negative of Rose’s, we often express payoff tables entirely in terms of Rose’s payoffs. For thisgame, we would write:Rose/ColinABA10B 4 25C 391066A game like this is sometimes referred to as a matrix game. We’llsolve this game later in this section, but for now let’s play a fewrounds.3
We’ll assume Rose and Colin are both rational players, by whichwe mean simply that they make reasonable decisions. For example,in the above game Rose would like to win 66, so she might startwith strategy C, but as soon as Colin sees that Rose is consistentlyplaying strategy C, he will start playing strategy A. This will moveRose to strategy A, which will move Colin to strategy B. We cangraphically depict this scenario with an arrow diagram as follows:4
Example 2. Consider the following matrix game:Rose/ColinABCDA1210B5 117C324 20D 16005316
6
Definition. In a matrix game, if there is a value v so that Rosehas a strategy that guarantees that she will win at least v, andColin has a strategy that guarantees that Rose will win no morethan v, then v is called the value of the game.Saddle Point Principle. If a matrix game between two rationalplayers has at least one saddle point, then both players should playa strategy that contains a saddle point.Example 3. Consider the following matrix game:Rose/ColinABCDA1512B0 5 510C 2131D16170 102
Theorem.(i) Any two saddle points in a matrix game have the same value.(ii) If a matrix game has at least one saddle point, then its valueis the value of the game.8
Minimax MethodWhile the graphical (arrow diagram) method for locating saddlepoints can work in principle for any matrix game with at least onesaddle point, it’s convenient to have a more analytic approach thatcould be implemented numerically for large systems. For this, wesimply think through what the arrow diagram does.9
Example 2 cont. Consider again the following matrix game:Rose/ColinABDA120B5 1C32D 160101 20316
Introduction to Game Theory The mathematical area known as game theory is generally de-scribed something like this: the systematic study of situations of conflict and cooperation. While the modern form of game theory was initiated by the Hungarian-American mathematician John von Neum
