Topic 7 Sequential games without perfect information PDF

Preview

Summary

Topic 7 Sequential games without perfect information...

Description

Topic 7. Sequential Games without perfect information Combining Sequential and Simultaneous Moves -

We have considered games of purely sequential nature (extensive forms) and games of purely simultaneous nature (normal forms). Subgame perfect Nash equilibrium o Coincides with BIE in sequential games with perfect information o Coincides with NE in simultaneous move games

From extensive to normal form: -

Consider the senate race game analyzed in topic 2: an incumbent senator (Alice) decides whether to use a preemptive campaign against a potential challenger (Bob) who chooses whether to enter or not the race.

-

We will now write the game in normal form by specifying, players, sets, and function of each player. o There are two players, the senator and the challenger o Alice has two strategies: advertise or not. o Bob’s situation is more complicated as he has two decision nodes. A strategy is a complete contingent plan so an action has to be planned for each decision node. (Four possible strategies for Bob: (enter, enter), (enter, retire), (retire, enter), (retire, retire). o The senate game in normal form will have 2 rows and four columns.

-

We must fill each cell in the matrix with the payoffs that result from the strategy profile corresponding to the cell.

-

Let’s determine the payoffs of the strategy profile (do not advertise, (retire, enter)). This strategy profile is depicted in the figure by the red colored actions.

-

This strategy profile induces the path (or sequence of moves) where Alice does not advertise, and Bob will enter, and the resulting payoffs are (2, 4), which is what we have to put in the cell at row not advertise and column (retire, enter).

Alice / Bob

(enter, enter)

(enter, retire)

(retire, enter)

(retire, retire)

Advertise

1, 1

1, 1

3, 3

3, 3

Not advertise

2, 4

4, 2

2, 4

4, 2

Matching Pennies revisited -

-

-

Consider again the Matching Pennies Game: two players, A and B, decide secretly (or simultaneously) whether to put a penny or not in their hands. If players’ decisions are the same then A wins (payoffs are (1, -1)). Otherwise, B wins (payoffs are (-1,1)) A/B

Penny

Nothing

Penny

1, -1

-1, 1

Nothing

-1, 1

1, -1

To represent Matching Pennies in extensive form we must introduce a new idea: the concept of information set. Since the game is played simultaneously, player B does not observe A’s decision and therefore cannot identify from which decision line between the two decision nodes of B. These two decision nodes belong to the same information set:

An information set is a subset of decision nodes that: o Belong to the same player o Have the same available actions

-

-

o The player cannot distinguish (due to hidden actions in previous steps) Since the player cannot distinguish between nodes in the same information set, he must choose the same action for all nodes belonging to the same information. The definition of strategy must be generalized: a strategy is a specification of an action for each information set. In perfect information games each information set consists of a single node. When there is at least one information set that contains more than one decision node we say that there is imperfect information. Each game can be represented in normal-form as well as in extensive-form. However, we will see that the normal form contains less strategic information.

Liar’s Poker -

-

A deck of cards consists of 50% aces and 50% Kings. Player 1 is dealt one card. Player 1 can either bet, A, stating that he has an Ace, or pass, K, stating that he has a King. If player 1 bets, player 2 can either believe it, b, or object, o. o If player 2 believes it, the game is over and player 1 pays 10€ to player 1. o If player 2 objects, player 1 turns over his card (the shutdown) If player 1 has an Ace, player 2 pays 20€ to player 1. But if player 1 lies and is caught the he pays 40€ to player 2. If player 1 passes, the game is over and player 1 pays 10€ to player 2.

Liar’s Poker with imperfect information -

-

Player 1 is dealt the card face down so that he can look at it but his opponent cannot see it. 2 believes if an Ace is dealt and objects if a King is dealt. 1 beats if he gets an Ace and passes if gets a King Backward induction equilibrium (BIE): ((A, K), (b,o)) Expected payoffs in BIE (0,0). Player 1 is dealt the card face down so that no player can see it. We cannot solve it by backward induction since there are hidden actions. 1/2

o

b

A

-10*, 10*

10*, -10

K

-10*, 10*

-10, 10*

Both players have a weakly dominated strategy (K and b are weakly dominated9 There are two pure strategy Nash Equilibria: (A, o) and (K, o) The expected payoffs in both equilibria are (-10, 10) It Is not a good thing to be first player.

Represent it first in normal form and then solve it. Player 1 has two information sets and four possible strategies. 1. 2. 3. 4. -

(A, A) always bet (A, K) tell the truth: bet if you have an Ace and pass if you have a king. (K, A) lie systematically: pass if you have an Ace and bet if you have a King. (K, K) always pass. The second player has only one information set and two possible strategies o and b.

-

-

-

S1 = {(A, A), (A, K), (K, A), (K, K)} S2 = {o, b} The fact that this is a zero sum game simplifies the computation of the payoffs: it suffices to compute the payoff for one agent. As an example, we provide the calculation details for some strategy profiles.

There are no pure strategy Nash equilibria. Eliminate the dominates strategies: (K, A) is dominated by (A, A) and (K, K) is dominated by (A, K). We are left with a 2x2 matrix, for which we can calculate all NE in mixed strategies. The game has a unique Nash Equilibrium in mixed strategies: ((1/5, 4/5, 0, 0), (2/5, 3/5) with expected payoffs (2, -2). It is better to be player 1 in this case.

The information structure of a game makes a significant difference and leads to different equilibrium outcomes.

Nash equilibria in perfect information sequential games Consider the simple entry game in extensive form we analyzed in topic 2 and represented again in the figure. The backward induction equilibrium is easily computed: the potential firm A will enter and the incumbent B will accommodate. -

The equilibrium profile is (e, a), the equilibrium path e-a, and the equilibrium payoffs (7,10) Is this prediction a Nash equilibrium? In order to answer the question we put the game in normal form and determine the Nash equilibria.

-

-

-

A/B

a

r

E

7*, 10*

-3, 0

n

5, 20*

5*, 20*

The backward induction equilibrium in a perfect information game is a Nash equilibrium in the corresponding normal form game. In this case (e,a) However, here there is also another Nash equilibrium: (n, r) with payoffs (5, 20). In this equilibrium, player 2 plays a weakly dominated strategy.

Given that B chooses to retaliate, A is choosing the best response. It is better for A not to enter since A would get -3 instead of 5. Similarly, given that A chooses not to enter, it is a best response for B to retaliate since B gets 20 in any case. Strategy r is a successful threat because it is not actually played as it is off the equilibrium path. However, retaliating is not a credible threat because in a sequential game, once A decides to enter, B would not gain anything by retaliating. At the stage it is not optimal for B to choose to retaliate and carry out his threat.

Games with both simultaneous and sequential moves -

-

Most real games that you will encounter will consist of numerous smaller components. Each of these components will entail simultaneous or sequential play. The full game requires you to be familiar with both. Consider the following more complex sequential game with imperfect information. It is an entry game in which after the first stage, where the entry decision is taken, there is a second stage in which the two firms play simultaneous move. “cournot game”. At the first stage the potential entrant, B, decides whether to enter the market e or not n. If B enters, there is a second stage. Both firms, A and B, decide to accommodate, a, by producing the Cournot duopoly quantity, or retaliate, r, producing large quantities driving down prices.

A Cournot Entry Game

Nash Equilibria of the Cournot Entry Game -

We see that there are three pure strategy nash equilibrium

- We see that retaliation is a dominated strategy for both players. There is a unique Nash equilibrium in the subgame.

-

-

In short, in the first equilibrium of the complete game, the incumbent A is threatening with retaliation in the subgame, but this threat is a dominated strategy in the subgame. In other words, the first Nash equilibrium of the complete game says that the players make irrational decisions in a subgame. The above shows that it can happen that some NE of the complete game are not reasonable. Let’s set up a procedure to get rid of these unreasonable NE.

Subgame - A game is a set of nodes connected with branches - a subgame is a subset of these nodes and branches such that: 1. it starts with a chance node or an information set containing a single decision node 2. it contains all the successors of each node in the subgame 3. if contains one node of an information set, then it contains all the other nodes of this information set. - The whole game is considered a subgame of itself.

Subgame Perfect Nash Equilibrium (SPNE) -

We extend the concept of backward induction equilibrium to games of imperfect information to rule out non-credible threats as in the Courtnot Entry Game Instead of “choosing optimally at each information set”. As before, “anticipating that others will be playing optimally too”. Formally, a strategy profile is a subgame perfect Nash equilibrium (SPNE) if and only if it induces a Nash equilibrium in each of the subgames. Note: in the case of extensive-form games with perfect information the SPN coincides with the backward induction equilibria. As under backward induction (BI) start at the end of the three In contrast to BI, do not choose the last decision node but choose the last subgame: a subgame that does not contain another smaller subgame. Write up the normal form game corresponding to this subgame and find a NE. Replace the subgame by the outcome of the NE you found above and act as if the three ends there. Now repeat the previous steps for the new tree.

Important: as some subgames may have multiple NE, you may have to repeat the above multiple times, each time selecting a different NE.

-

Consider first the simultaneous move subgame and put it in normal form.

-

The subgame has a unique Nash equilibrium with profile (a, a). We know that if the simultaneous move game is played then the players will obtain payoffs (3,1) We indicate this by a small payoff vector just above player B’s second decision node in the complete game

-

A/B

a

r

a

3*,1*

-2, -1

r

1, 0*

-1*, -1

Mutual Assured Destruction (MAD) - MAD is a doctrine of military strategy based on the theory of deterrence. Since each state has enough nuclear weapons to destroy the other (even if attacked first), any state beginning a nuclear war will cause the destruction of both itself and its opponent this will deter any attack. -

The atomic confrontation is modelled as follows Two superpowers, 1 and 2, have engaged in a provocative incident. The game starts with superpower 1’s choice to either ignore the incident I resulting in the payoffs (0,0) or to escalate the situation, E. Following escalation by superpower 1, superpower 2 can back down, B, causing it to lose face resulting in payoffs (2, -2), or it can choose to proceed to an atomic confrontation situation A.

Upon this latter choice ¡, the teo superpowers play the following simultaneous move game: 1. They can either retreat R or choose doomsday D in which the world is destroyed. 2. If both choose to retreat, then they suffer a small loss and payoffs are (-1, -1) 3. If either chooses doomsday then the world is destroyed, and payoffs are (-K, -K), where K is a very large number.

Cross shareholding

1/2 H L

H 40, 30 50*, 0

L 10, 40* 20*, 10*

-

Two firms are collaborating in a huge joint project and the are facing a prisoners’ dilemma problem: putting a low effort is a dominant strategy for both of them.

-

The unique NE is (L,L) with payoffs (20, 10) Before starting the project they have the opinion of buying 30% of the other firm. This can only happen if both of them agree. They have to decide this simultaneously If they agree to cross shareholding the new payoffs will be B’1 = 0.7B1 + 0.3B2 and B’2 = 0.3B1 + 0.7B2

-...