Game Theory - Lecture Notes PDF

Preview

Summary

Lecture Notes...

Description

Microeconomics II Game Theory Matthias Messner April 22, 2015

Introduction These lecture notes summarize some of the more advanced arguments regarding the chapter on Game Theory. The emphasis of these notes is not on spelling out in all details all the material that has been covered in class. Rather the aim is to provide the student with a concise summary of the technically and conceptually most difficult arguments. So these notes are not supposed to be a substitute for the textbook. Instead, they should be seen as a supplement to the recommended textbook. The text contains a number of ‘Remarks’. Typically, a remark explains some technical expression that has been used in the preceding paragraph (highlighted in italic characters). Essentially, they play the role of a ‘in-text footnote’.

What is a game? What is a game? We will not bother to give a general formal definition of the concept ‘game’. Doing so would require tons of notation and terminology. For our purposes it is enough to keep the following rather informal definition in mind: A game is a situation of interactive decision making; that is, a situation where multiple individuals have to take decisions which determine not only their own wellbeing but also the wellbeing of (a subset of) the other involved individuals. In what follows we will discuss different types of games. We will start out with the simplest ones and as we continue we will introduce ever more complex types of games.

1

Microeconomics 2 - Prof. Matthias Messner

2

Static games with complete information Defining a static game The standard way to represent a static game is by way of the so called normal form of the game. The normal form of a games is composed by the following elements • The set of players I = {1, 2, . . . I }. • A set of actions/strategies for each player i = 1, . . . , I, denoted by S i , (here we use the terms actions and strategies synonymously; we will see later that the two concepts coincide only in static games of complete information). Some more useful notation regarding strategies: A typical element of S i is denoted by si ; a vector s = (s1 , . . . , sI ) ∈ S 1 × . . . × S I is called a strategy profile or strategy combination; the set of all strategy combinations is denoted by S . For strategy combinations of all players except player i we write s−i ∈ S 1 × . . . × S i−1 × S i+1 × . . . × S I ; the set of all such combinations are S −i ; we use this notation to write (si , s−i ) for a complete strategy combination. • A payof f function for each player i = 1, . . . , I, ui : S 1 × . . . × S I → R; ui tells us what the payof f of player i is for each possible combination of strategies that the players might choose. In a static game all players choose simultaneously an action/strategy.1 Depending on the final combination of strategies that the players pick each one of them gets a payof f as specified by their payof f functions. The expression ‘complete information’ refers to the assumption that all aspects of the game (who are the other players, what can everyone do, what are everyone’s payoffs) are common knowledge among the players (everyone knows them, everyone knows that everyone knows them, everyone knows that everyone knows that everyone knows them etc.) When we describe a game through the three elements listed above (set of players, strategy sets, payof f functions) we also say that we are presenting the game in its normal form. The normal form representation has to be distinguished from the extensive form representation that we will discuss later. 1 Everything that we will have to say about static games applies also to games where players move sequentially but cannot observe each others actions.

3

Microeconomics 2 - Prof. Matthias Messner

Example: The prisoner’s dilemma

C DC

C −5, −5 −20, 0

DC 0, −20 − 1, − 1

Dominant and dominated strategies, iterated elimination of dominated strategies What should we expect players to do when the payof f from their actions depends on what the other players do? The answer to this is straightforward only if the best action that I can take does not depend on what the others do. We say that a strategy si′ of player i (strictly) dominates the strategy si′′ if he is strictly better of f by playing si′ than by playing si′′ no matter what the other players do. Formally: ui (si′, s−i ) > ui (s′′ i , s−i )

for all s−i ∈ S −i

In this case we also say that s′′i is dominated by s′i . The strategy si′ is said to be dominant if it dominates every other strategy of player i, i.e. when the above condition does not only hold for s′′i but for all si ∈ S i \{s′i }. If every player has a dominant strategy, then we should expect that everyone uses it. Notice that in the prisoners’ dilemma game the strategy ‘C’ dominates the strategy ‘CD’. Thus, the outcome that we should expect to obtain in that game is (C, C). ′ Conversely, if player i has a strategy s′′ i that is dominated by a strategy si then we can conclude that this player should never use the strategy si′′ . While this may not allow us to say what exactly the player will do, it at least tells us what he will certainly not do.

The idea of eliminating dominated strategies can be pushed further. In particular, we can do the following: we eliminate from everyone’s strategy set the strategies that are dominated. Doing so will give us a new game with reduced strategy sets. For this new game we can then go on and ask if any player has any dominated strategies in this new game. To see what this means, consider the following game:

U

L 1, 4

M 2, 3

R 3, 2

C D

−2, 0 2, 1

−1, 2 1, 0

4, 1 0, − 1

Regarding this game we can make the following observations: i) No player has a dominant strategy; ii) Player 1 has no dominated strategy; for player 2 the strategy R is dominated by M. We can therefore conclude that he would never use the strategy R.

4

Microeconomics 2 - Prof. Matthias Messner

If we eliminate R from the picture, we obtain a reduced game that looks as follows:

U

L 1, 4

M 2, 3

C D

−2, 0 2, 1

− 1, 2 1, 0

In this reduced game, still no player has a dominant strategy. But Player 1’s strategy C is now dominated by both of his other two strategies, U and D. Thus, Player 1 should never use C and so we can eliminate it. Doing so leaves us with the following game

U D

L 1, 4 2, 1

M 2, 3 1, 0

In this game Player 1 has no dominant strategy. Player 2 instead now has a dominant strategy, namely L. But if Player 1 knows that Player 2 will play L, then it is optimal for him to play D. So the final outcome of the game is the strategy profile (D, L). When the above described procedure of iterated elimination of dominated strategies leads to a unique prediction, then we say that the game is dominance solvable.

Nash Equilibrium Unfortunately, there are many games that are not dominance solvable. Just consider the following example

U D

L 10, 10 0, 0

R 0, 0 1, 1

Clearly, for Player 1 it is optimal to choose U if Player 2 plays L. But if Player 2 chooses R than it is better for Player 1 to go with D. A perfectly analogous argument shows that Player 2’s optimal strategy depends on what Player 1 does. What should we do in such situations? John Nash (‘A beautiful mind’) has argued that a ‘solution’ for such a game should have the property that it is self-enforcing. That is, if every player thinks that the other players will behave according to what the solution prescribes, then no one should have an incentive to deviate from what he should do according to this solution. Formally, this leads us to the following solution concept Definition 1. A strategy combination (s∗1 , . . . , sI∗) constitutes a Nash Equilibrium if for every i and every si ∈ S i we have ∗ ∗ ui (s∗i , s−i ). ) ≥ ui (si , s−i

5

Microeconomics 2 - Prof. Matthias Messner

The idea behind this concept is as follows: Since no player knows what the other players do they all form expectations about what the others do and then act optimally in accordance with their expectations. According to Nash a strategy profile s∗ should be considered a reasonable outcome of the game only if it is the case that every player i is indeed happy to choose s∗i when ∗. he correctly guesses that the other players are choosing s−i What is the NE in the above described game? We have observed earlier that Player 1 wants to pick U if Player 2 chooses L. Conversely, Player 2 wants to take L if he thinks that Player 1 chooses U. Thus, the strategy combination (U, L) is a NE. But notice that this is not the only NE. It is easy to verify that also the combination (D, R) constitutes a NE. So from this simple example we immediately see that there need not be a unique NE. Relation between the concept of Nash equilibrium and dominance arguments If every player i has a dominant strategy s∗i , then the strategy profile (s1∗, . . . , sI∗) is the unique NE of the game. Conversely, if (s∗1 , . . . , sI∗) is a NE of some game, then all strategies si∗ survive the iterative elimination of dominated strategies. Calculating Nash equilibria when players have a continuum of strategies A NE is a strategy combination with the property that each player is responding optimally to the equilibrium strategies of the other players. In all games that we have encountered so far, all players had only a finite number of (pure) strategies at their disposal. In economic applications it is often more natural to assume that the set of strategies of a player is a continuum (economic agents often choose objects like quantities or prices or investment levels etc., i.e. things that are finely divisible). We will encounter such games in the chapter on Market Power (monopoly, oligopoly). There we will also see how we can find the Nash equilibria of such games with ‘large’ strategy spaces. Existence of Nash Equilibrium and mixed strategies Does there always exist a NE? Before we answer this question, let us consider the game played between a goalkeeper and a field player who face each other in a penalty kick. The goalkeeper chooses the row, while the field player chooses the column.

L R

L 2, 0 0, 2

R 0, 2 2, 0

Clearly none of the strategy combinations (L,L), (L,R), (R,L) or (R,R) constitute a NE. Does this mean that there is no NE. The answer is Yes and No. The answer is Yes if we do not allow

Microeconomics 2 - Prof. Matthias Messner

6

the players to randomize between their pure strategies. If we allow them to randomize then a Nash equilibrium does exist. By a random, or mixed, strategy we mean that they can make choices of the type ‘I go left with probability p and right with probability 1 − p’. Allowing for such randomizations means that we increase the sets of strategies that the players have at their disposal. Suppose that both players mix with probability 1/2 between their strategies. It is straightforward to check that this is a NE in the game where we allow for mixed strategies. To see this consider Player 1. What is this player’s payof f from playing L if he thinks that Player 2 mixes fifty-fifty between his two strategies? He will get 2 with probability 1/2 and 0 with probability 1/2. Thus in expectation he gets 1. But the same happens if he plays R. So he is completely indifferent between his two strategies if the other player mixes fifty-fifty. If that is the case then that means that he would get the same payof f of 1 also if he mixes himself with an arbitrary probability p. In particular, he gets payof f 1 when he adopts a fifty-fifty mixing. Since for Player 2 the same observations apply, it follows that both players mixing with 1/2 probability is a NE. The crucial message from this example is that by allowing for mixed strategies we have found an equilibrium in a game that does not allow for a NE in pure strategies. This trick always works in games where every player has only finitely many pure strategies at his disposal. Proposition 1. Every normal form game with finitely many players and finite strategy sets admits at least one NE in either pure or mixed strategies.

A final remark on mixed strategy equilibria. Suppose we have some equilibrium of a normal form game where player i is randomizing over the two pure strategies si and si′ with probabilities p and p′ , respectively (of course p + p′ = 1). The payof f from the mixed strategy is given by the p times the payof f that playing si yields, plus p′ times the payof f that playing is′ yields. Therefore, mixing can be an optimal choice only if player i is indifferent between the two pure strategies. Thus, whenever in equilibrium a player is mixing over some set of pure strategies, it must be the case that every pure strategy in that set would yield him the same payoff.

Dynamic games of complete information In many situations of strategic interaction the players do not choose their actions simultaneously at a single point of time. Instead the interaction may continue over multiple stages and players might have the opportunity to make a choice at several of those stages. When we describe such games we therefore need to specify the order in which players interact and what

7

Microeconomics 2 - Prof. Matthias Messner

actions they can take at each instant where they have to make a choice. Furthermore, it will be necessary to specify what players know about the actions of their predecessors (i.e. are they able to observe what actions have been played so far or are those actions not observable?). Combining these additional elements of the description of the game with the elements that we already know from the normal form representation we obtain the so called extensive form representation of a game.

Game tree, perfect vs. imperfect information Graphically dynamic games are most conveniently described with the help of a game tree. A game three is a collection of nodes that are connected through arcs (branches of the tree). Each node represents either an instant where some player has to take a decision (decision node) or it represents a situation where the game ends (terminal nodes). The tree starts from a single initial decision node. The branches that emanate from a given node represent the actions that the player who has to choose at that node can take. A branch that emanates from a given decision node can never lead back to this node or to any earlier decision node. From each given node there is exactly one way to get back to the initial node (i.e. once two branches of the tree separate they never grow together anymore). The terminal nodes represent situations where the game is finished. For each of the possible endings of the game we have to specify what the players get. Thus each terminal node is associated with the players’ final payoffs. The following example represents a simple two player game. At the initial node it is P1 (Player 1) who has to take an action. In particular he has to decide between L and R. After P1 is done, it is P2’s turn. That is, P2 has to choose at both of the other two decision nodes. At the first one of his nodes he can either play l or r; in the second case his choice is between l′ and r′ . With P2’s action the game ends. The numbers associated to the four terminal nodes correspond to the payoffs of the two players. For instance, if player 1 chooses L and player two plays l then the first player gets a payof f a while the second player receives b.

L✟✟ ✟ 2✟ ✟ r l ❅ r

 r

a, b

❅ ❅r

c, d

1❜ ✟❍

❍ R ❍ ❍

❍❍2r l ❅ r ′ ❅  ❅r  r ′

e, f

g, h

Figure 1: A simple extensive form game of perfect information The above game is a game of perfect information. That is, it is a game where players at the moment where they have to move can observe perfectly what actions have been chosen by their predecessors. In this case the game has only two stages. The player who has to move at

8

Microeconomics 2 - Prof. Matthias Messner

the second stage, P2, knows which action P1 has chosen before him. Games of imperfect information are games where players cannot always perfectly observe what their predecessors have done. As an example consider the following game: 1

✏ ❜PP ✏✏ PP R L ✏ PP ✏✏ ✏ ✏ ♣r✏ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ 2♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣ P ♣ ♣P ♣P ♣ r ❅ ❅ l l ❅r ❅r  ❅  ❅  ♣ ♣ ♣ ♣ ♣ ♣ ♣ ♣1♣ ♣ ♣ ♣ ♣ ❅ ♣❅ ♣ r r r♣ ♣ ♣ ♣ ♣ ♣ ♣ 1♣ ♣ ♣ ♣ ♣ ♣ ❅ ♣❅♣ r ✁❆ ✁❆ ✁❆ ✁❆ L′′ ✁ ❆ R′′ L′′ ✁ ❆ R′′ L′ ✁ ❆ R′ L′ ✁ ❆ R′ ✁ ❆ ✁ ❆ ✁ ❆ ✁ ❆ ✁ ❆ ✁ ❆ ✁ ❆ ✁ ❆ ❆r ❆r ❆❆r ❆r ✁r r✁ r✁ r✁

a, b

c, d

e, f

g, h

j, k

m, n

o, p

q, s

Figure 2: A simple extensive form game of imperfect information In the above example P2 does not know what action P1 has chosen on the first stage. Thus, he is not able to distinguish the two decision nodes at which he has to move. We indicate this through the dashed line that connects the two nodes. In the same way, when P1 has to choose at the third stage he cannot observe what P2 has done on the second stage. He only knows what he himself has done on the first stage. Thus he can distinguish the first two decision nodes from the third and the fourth. But he cannot distinguish between the first two and between the last two. If a player cannot distinguish two decision nodes, then that means that he cannot condition his actions on those nodes. A set of decision nodes that a player cannot distinguish is called an information set. In a game with perfect information every decision node constitutes an information set. In a game with imperfect information, the number of information sets is smaller than the number of decision nodes. Strategies and normal form representation of dynamic games: In dynamic games we have to distinguish carefully between actions and strategies. Consider again the first one of the above two games. There P2 has two actions at his disposal at each one of the decision nodes where he has to make a move. At the first node he can choose between the actions l and r and at the second one he has to pick between l′ and r′ . So an action is what a player can do at a certain decision node. A strategy is a complete contingent plan of actions that the agent intends to implement at each one of his information sets. Since P2 has to choose at two information sets (he is able to distinguish the two decision nodes at which he has to make a move and so they each constitute an information set) and at each of the two information sets he has two actions to pick from, he

9

Microeconomics 2 - Prof. Matthias Messner has four different strategies: (l, l′ ), (l, r′ ), (r, l′ ), (r, r′ ).

How many strategies does P1 have? P1 moves only at the initial node where he can choose one of two actions (L or R). Since he has only one information set where he has two actions it follows that he has only two strategies which coincide with his two actions. In the second game it is P2 who has only one information set. Thus his set of strategies coincides with the set of actions that he can choose from at this information set. P1 has three information sets and at each one of them he has two actions at his disposal. Thus, he has 23 = 8 strategies. Once we have determined the set of strategies that each player has at his disposal in the dynamic game, we may also represent the game in normal form. The normal form of the game represented in Figure 1 is

L R

ll′ a, b e, f

lr ′ a, b g, h

rl′ c, d e, f

rr′ c, d g, h

For the game in Figure 2 instead we obtain the following normal form

′ ′′
...