2018 FGame Theory Note - Text book PDF

Preview

Summary

Text book...

Description

Study Guide Accompanying Strategy by Joel Watson

August 20, 2018

Econ 3047 Game Theory

Spring 2015 1

Contents 1

2

3

Introduction

3

1.1

The Scope of Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.2

Examples: Two Parlor Games . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2.1

Hex . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2.2

Nim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.3

Non-Cooperative Games versus Cooperative Games . . . . . . . . . . . . . . .

9

1.4

A History of Game Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

Representation of Games

11

2.1

Extensive Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.2

Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.3

The Strategic Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.4

Extensive Forms and Strategic Forms . . . . . . . . . . . . . . . . . . . . . . . .

21

2.5

Expected Utility I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

Solution Concepts for Strategic Form games

29

3.1

Dominance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

3.2

Common Knowledge and Iterated Dominance . . . . . . . . . . . . . . . . . .

32

3.2.1

A location game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.3

Aside: Common Knowledge . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

3.4

Weakly Dominated Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

3.5

Rationalizability and Best Responses . . . . . . . . . . . . . . . . . . . . . . . .

39

3.5.1

A Partnership game . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

3.5.2

A Game Analyzing Social Unrest . . . . . . . . . . . . . . . . . . . . . .

43

Dominance and Best Response . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

3.6

U DiM

(and

BiM )

3.7

A procedure to find

. . . . . . . . . . . . . . . . . . . . . . . .

47

3.8

Congruous strategies and Nash equilibrium . . . . . . . . . . . . . . . . . . . .

53

3.8.1

Congruous Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.8.2

Nash equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

Cournot and Bertrand duopoly . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.9.1

Cournot Duopoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.9.2

Bertrand duopoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.9.3

The Median Voter Theorem . . . . . . . . . . . . . . . . . . . . . . . . .

59

3.10 Mixed Strategy Nash equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . .

63

3.9

Econ 3047 Game Theory

4

3.10.1 Two Finite Game Examples . . . . . . . . . . . . . . . . . . . . . . . . .

63

3.10.2 Duopoly with Capacity Constraints . . . . . . . . . . . . . . . . . . . .

65

3.11 Possible Interpretation of (mixed strategy) Nash equilibrium . . . . . . . . . .

70

3.12 Note: Pre-Play Negotiation and Correlated Equilibrium∗ . . . . . . . . . . . .

71

3.13 Strictly Competitive Games and Security Strategies∗ . . . . . . . . . . . . . . .

74

Extensive Form Games and Subgame Perfection

76

4.1

The Rules of Extensive Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

4.2

Backward Induction and Subgame Perfection . . . . . . . . . . . . . . . . . . .

82

4.3

Applications in Industrial Organization . . . . . . . . . . . . . . . . . . . . . .

88

4.3.1

Advertising and Competition . . . . . . . . . . . . . . . . . . . . . . . .

88

4.3.2

A Model of Limited Capacity . . . . . . . . . . . . . . . . . . . . . . . .

89

4.3.3

Dynamic Monopoly . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

The Moral Hazard Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

4.4.1

Risk Aversion and Expected Utility

. . . . . . . . . . . . . . . . . . . .

96

4.4.2

A Moral Hazard Problem . . . . . . . . . . . . . . . . . . . . . . . . . .

98

4.4

5

Spring 2015 2

Information

108

5.1

Random Events and Incomplete Information . . . . . . . . . . . . . . . . . . . 109

5.2

Bayesian Nash Equilibrium and Rationalizability . . . . . . . . . . . . . . . . . 115

5.3

An Adverse Selection Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

5.4

Auctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.4.1

The Second Price Auction . . . . . . . . . . . . . . . . . . . . . . . . . . 119

5.4.2

The First Price Auction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

5.5

Perfect Bayesian Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

5.6

Job Market signaling and Reputation . . . . . . . . . . . . . . . . . . . . . . . . 128 5.6.1

Jobs Market Signaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

5.6.2

A Model of Reputation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

5.6.3

Strategic Transmission of Informations: A Model of Cheap Talk . . . . 132

Econ 3047 Game Theory

1 1.1

Spring 2015 3

Introduction The Scope of Game Theory

Game theory is an abstract study of rational strategic interaction. This the foundation of game theory. By foundation we mean that all game theory concepts and analytic tools have to be justified and developed according to this principle. We explain

first. We refer all the possible actions that a person may take

as strategies. People are in a strategic interacting environment if their payoffs are mutually influential by their strategies. For example, consider two methods of class rolling calls. The first one is calling randomly and sequentially: if one that is called is present, pick another also randomly. The process ends if a randomly picked one is absent, in which case the one is awarded a zero grade. The second method called by a pre specified list. If one is absent, the calling stops and the absent one is awarded a zero grade. Obviously, each person’s decision/strategy is to come or not to come. Their payoffs are mutually influential because if the absence of a person may determine other persons’ payoff from his/her own strategies. : they act according to some

ordering over possible out-

comes. Here, the person should initial have ranking over a zero grade and a non-zero grade. To consider how to act in this situation, one may need to guess what other would do, since the strategies of the other persons determine outcome. In the first case, for example, if everyone other than me in present, I should be present, if I prefer a non-zero grade, for otherwise I would definitely receive a zero grade. If there are some persons that would not come, my chance of being called diminished, which would certainly influence my strategy. In the second case, everyone needs to know whether the persons before him/her in the list would come or not, which determine whether the person would be called or not. To determine what to do, one need to know others’ preferences, and as a consequence, to know others’ strategies. Since everyone has to guess others’ preferences and strategies. This is the essence of

.

We have actually explained almost all words in the definition of game theory:

,

Econ 3047 Game Theory

Spring 2015 4 ,

Formally, an abstract study means game theory is a theory because it defines and structures what is important and what should be omitted in a strategic interaction. Here, what are important from the view of game theory are strategies/possible actions, and preferences that depend on these strategies and nothing else. There are many different strategic interacting environments, say, there are many different types of chess or board games. The aim of game theory is to develop a unified theory to analyze them. Thus, game theory is a pure logic, just like mathematics. We abstract what are important in a situation, use a common analytic method, and then apply the result to predict outcome in the situation. Finally, rationality. There are two tiers in meaning. In the first tier, people are rational because they act according to their preferences and pursue the best satisfaction according to their preference. The second tier of meaning refers to a person knowledge and intelligent power. In laymen’s language: whether a person is smart enough. For example, as we proceed in the class, certain problems need the knowledge of calculus, so a primary school student may not be able to solve. Game theory defines rationality and develops a rank the degree of rationality in the second tier sense, and makes prediction, i.e. solve, a game by placing assumptions on rationality. Weaker rationality produces a stronger prediction; that is, the prediction should be always generated by a group of people since it requires less intelligent power. The formal term for abstraction is game forms, or representations of a game. There are two game forms. In each representation, depending on the rationality concept being assumed, there are different solution concepts. Briefly, if you want to know now, the solution concepts that will be introduced are (A) for strategic form games, (A1) Dominance, (A2) Rationalizability, (A3) Nash equilibrium, and (A4) a extremely brief mention of Correlated equilibrium, (B) for extensive form game with perfect information, (B1) Backward Induction and Subgame Perfection, and, (C) for games with imperfect/incomplete information, (C1) Bayesian Nash equilibrium, and (C2) Perfect Bayesian equilibrium.

Econ 3047 Game Theory

1.2 1.2.1

Spring 2015 5

Examples: Two Parlor Games Hex

In the game of Hex, two players move alternatively by marking a • or a ◦ at one of the n2 hexagons being parallel stacked, as shown below. At the beginning, two opposite sides of the board are marked with Black or White. This is called players’s original territories, and once a hexagon has been marked by a player, the hexagon becomes the player’s new territory. The first player who establishes a connected territory wins.

In this game, every player is rational in the sense that everyone wants to win. It is also certain that one player’s strategy could affect the other player’s winning odds, and hence the strategy he/she would use. A game theoretical study of the game consists of predicting who will win the game and suggesting a winning strategy. John Nash, whose name will be mentioned countless times in this course, first proved in Nex games the player who moves first has a winning strategy. So the first-moved player can win the game. This is not to say that the first player can always win the game no matter what he does; he can win the game only if he uses the winning strategy.

Econ 3047 Game Theory

Spring 2015 6

Nash’s argument, having been named as “strategy-stealing,” is a “proof by contradiction.” That is, we first suppose that P is true, and shown P implies ∼ P is true. Since this is impossible, so our original supposition must be false. This P is not true (and ∼ P is true). Now we start the proof: Suppose the second player (the black side) has a winning strategy, then the first player (the white side) can steal it by obeying the following instruction. 1. At the first move, choose a hexagon at random and label it with an ◦. 2. At any late move, pretend that the last hexagon with a ◦ is unlabeled. Next pretend the the remaining hexagons with a ◦ are all marked with a •, and the hexagons with a • are all with a ◦. You have now imagined yourself into a position to which the second player’s winning strategy applies. Pick the hexagon that the second player would choose in this position if she were to use her winning strategy. Label this with a ◦. The only possible snag is that this hexagon may be the hexagon you pretend it is unlabeled. If so, then you do not need to steal the second player’s winning strategy because you have already stolen it. Then just choose a free hexagon at random. This strategy must win for the first player because he is simply doing what supposedly guarantees the second player a win. Not only this, he does everything one move sooner that the second player would do it. The fact that he has an extra hexagon labeled with his emblem does not hurt him at all. Hence we proved that if the second player always has a winning strategy, then the first player always has a winning strategy. This is a contradiction.

This is an example of the generalization that game theory wants to achieve. We prove that the first player has a winning strategy without knowing what the strategy is! And it applied to any n2 games, for finite n’s. With this result, the focus, from forming an instructional viewpoint, is to find a winning strategy since you know there is always one.

Exercises 1. What is the winning strategy for a 22 game? 2. What is the winning strategy for a 33 game?

Econ 3047 Game Theory 1.2.2

Spring 2015 7

Nim

It begins with several piles of matches. Two players take alternative moves. On his or her move, a player selects one of the piles and removes at least one match from that pile. The last player to remove a match wins.

Econ 3047 Game Theory

Spring 2015 8

Figure 1: A Nim Game Call a game of Nim is balanced if each column of the binary representation has an even number of 1’s, and unbalanced otherwise (see below). It is easy to verify that any admissible move in Nim converts a balanced game into an unbalanced game.

8

4

2

1

2

0

0

1

0

3

0

0

1

1

5

0

1

0

1

1

0

0

0

1

Figure 2: An Unbalanced Nim The player who moves first in a balanced game cannot win on his first move. The reason is that a balanced game has matches in at least two piles. The player moving therefore cannot pick up the last match immediately because he/she is allowed to take matches from only one pile at a time. It follows that one of the players has a winning strategy of which the crucial feature is that an unbalanced game should always be converted into a balanced situation. The reason such a strategy wins is that it ensures that the opponent cannot win on the next

Econ 3047 Game Theory

Spring 2015 9

move. Since this is true at every stage in the game, it follows that the opponent cannot win at all. But, someone must pick up the last match. If it is not my opponent, it must be me. Exercise Who would win a game of Nim with n ≥ 2 piles of matches of which the kth pile contains 2k−1 matches?

1.3

Non-Cooperative Games versus Cooperative Games

In game theory, cooperativeness is rather referred to an important assumption regarding enforcement. We call a situation is cooperative if the players in the situation can communicate, and sign contracts, and enforce the contracts. If any of the three conditions is failed, we call the situation non-cooperative. This is certainly different from the common usage of the term “cooperative.”’ Cooperation is often used to describe behaviors. Behaviors are outcome of choices and is certain not an objective condition. For example, if I say our cooperation goes well, I usually mean that we can communicate and coordinate our actions well. Certainly, without the possibility of communication, we cannot cooperative well. But then we should say that we want to cooperate but the environment prevents us from doing so. So remember, in a non-cooperative environment, it does not mean that people will not cooperate; they can always choose to cooperate (i.e. coordinate their strategies) if they find a way to communicate. Also, in a cooperative environment, people still have to possibility to be non-cooperative. This distinction is important when we cover solution concepts for both cooperative and non-cooperative games. I feel it is very unfortunate that game theory pioneers use cooperative-non-cooperative to describe environment. We will cover mainly non-cooperative games. This is not to say that the individuals in our games do not cooperate. Instead, they can choose whether to cooperate or not, depending on their strategic considerations. We will return to this issue when we begin our study of cooperative games (Chapter 18) and repeated games.

Spring 2015 10

1944

A History of Game Theory 1.4

Econ 3047 Game Theory

Early John von Neumann Contributors Oscar Morgenstern

Theory of Games and Economic Behavior: Zero-sum games Cooperative Game vs. Non-Cooperative Games Extensive Forms vs. Strategic Forms Minmax solutions Stable Sets

1947-1950 John Nash: Nash Equilibrium Nash Bargaining Problem

1950’s Harold Kuhn Perfect Recall Behavior Strategy

1974 Refinements Reinhard Selton Sugame Perfection David Kreps and

Thomas Schelling uses game theory to analyze internation relations in The Strategy of Conflict

1972-73 John Harsanyi Bayesian games

John Wilson Sequential equilibrium Signaling Games Myerson Proper equilibrium

Mathematicians developed solution concepts for cooperative Games, among them, the most famous are core, bargaining set, and Shapley Value.

Kohlberg and Merton Stable equilibrium Repeated Game

1940’s

1950-1960’s

1970’s

1980’s

Evulutionary Games

Econ 3047 Game Theory

2

Spring 2015 11

Representation of Games

2.1

Extensive Forms

Game theory regards...