Simultaneous-Move Games

#economics #micro

Oh, Hyunzi. (email: wisdom302@naver.com)
Korea University, Graduate School of Economics.
2024 Spring, instructed by prof. Cho, Wonki.

Strict Dominance

Dominant Pure Strategy

Definition (strict dominance in pure strategies).

A strategy is strictly dominating in game , if regarding all other player's every possible strategy, gives strictly greater payoff than the other strategy of the player .

strictly dominates if
is strictly dominated if
is strictly dominant if it strictly dominates every other strategy. i.e.

Example (prisoner's dilemma).

	c	nc
C	(-4, -4)	(-1, -6)
NC	(-6, -1)	(-2, -2)

Two individuals player 1(row) and 2(column) are arrested for allegedly engaging a serious crime and are held in separate cells. The district attorney(DA) tries to extract a confession from each prisoner. Each is privately told that if he is the only one to confess, then he will be rewarded with a light sentence of 1 year, while the recalcitrant prisoner will go to jail for 10 years. If both confess, they will both be sown some mercy, each for 5 years. Finally, if neither confesses, it will be possible to convict of a lesser crime of 2 years sentence.

Proof. For the both players, is strictly dominant.
For player 1, thus .

For player 2, thus . □

Dominant Mixed Strategy

Definition (strict dominance in mixed strategies).

A mixed strategy is strictly dominating in game , if regarding all other player's every possible strategy, gives strictly greater payoff than the other strategy of the player .

strictly dominates if
is strictly dominated if
is strictly dominant if it strictly dominates every other strategy. i.e.

Proposition (dominated pure is sufficient with other's pure strategy).

Player 's pure strategy is strictly dominated in game if and only if the following holds:

Here, ^1fee79 Proposition 4 (dominated pure is sufficient with other's pure strategy) can be extended to the case for every other .

Corollary (dominated mixed is sufficient with other's pure strategy).

Player 's mixed strategy is strictly dominated in game if and only if the following holds:

Proof.First we show the only if part, and then we show the if part.
() Assume that is strictly dominated. i.e. since this holds for all , by letting , we have the desired result of () Assume that for given , Now take any , then we have Thus is strictly dominated. □

The above ^271a3f Corollary 5 (dominated mixed is sufficient with other's pure strategy) implies that to prove one's strategy is strictly dominating, it is sufficient enough to consider only for the case when the opponents play the pure strategy.

Proposition (mixed strategy is dominated if its support is dominated).

Let player 's pure strategy is strictly dominated in the game . Then mixed strategy is also strictly dominated if for such pure strategy.

Proof.Suppose is player 's strictly dominated by the strategy . Now let is a mixed strategy that plays with a strictly positive probability, i.e. .
WTS is strictly dominated by , where , , while .
Therefore, we have Therefore, is strictly dominated. □

Elimination of Strictly Dominated Strategy

Proposition (Iterated Elimination of Strictly Dominated Strategy).

The IESDS(Iterated Elimination of Strictly Dominated Strategy) solutions is the strategy profiles that survives the following IESDS poricess:

, find and eliminate strictly dominated strategy for the player . And let be the set of remaining strategies.
, assume that the remaining player plays only the strategies from . Now find and eliminate strictly dominated strategies for the player . Let be the set of remaining strategies.
Proceed similarly until no strategies can be eliminated. Then the surviving the IESDS process are called IESDS solutions.

Remark that the IESDS solutions can be multiple.

Example (IESDS on 3 by 3 two players game ).

	l	c	r
U	(1, 3)	(4, 2)	(3, 5)
M	(2, 4)	(2, 0)	(2, 2)
D	(4, 2)	(1, 4)	(2, 0)

Solve the given game using the elimination of strictly dominated strategy.

Proof.We apply ^296965 Proposition 7 (Iterated Elimination of Strictly Dominated Strategy) step by step.

For the player 1, . Thus is eliminated (since 1 is rational): Since we have .
For the player 2, for . Thus is eliminated (since 2 knows that 1 is rational): Since has been eliminated, ISTS the cases for . Suppose that 1 plays , then thus must hold. Now suppose that 1 plays , then thus . Therefore, for , we have .
For the player 1, . Thus is eliminated (since 1 knows that 2 knows that 1 is rational): Since and have been eliminated, we have
For the player 2, . Thus is eliminated (since 2 knows that 1 knows that 2 knows that 1 is rational): since Therefore, the IESDS solution is . □

Nash Equilibria

Definition (pure Nash Equilibrium).

A strategy profile is a pure Nash Equilibrium(NE) at the game if the following holds: which states there is no profitable unilateral deviation, i.e.

Example (New York Game).

	es	gc
ES	(100, 100)	(0, 0)
GC	(0, 0)	(100, 100)

Mr. Thomas(row player, player 1) and Mr.Schelling(column player, player 2) each have two choices. They can meet either at noon at the top of the Empire State Building(ES, or es), or at the clock in Grand Central Station(GC, gc). There are two Nash equilibria: (ES, es) and (GC, gc), ignoring the randomization.

From the ^23b292 Example 10 (New York Game), note that NE can have multiple equilibria.

Remark (discussions on NE).

A NE has the following implications:

NE is a self-enforcing agreement.
NE is a stable social convention.
NE is a consequence of rational inference.

Notice that,

Players can engage in nonbinding communication prior to playing the game. However, players cannot bind themselves to their agreed-upon strategies. Thus, a Nash equilibrium must be purely a self-enforced agreement.
If the game is played repeatedly, then some stable social convention can emerges.
Rationality need not lead player's forecasts to be correct.

Before moving on, we formally define Nash Equilibrium including mixed strategies.

Definition (mixed Nash Equilibrium).

A mixed strategy profile is a mixed Nash Equilibrium(NE) at the game if the following holds: which states there is no profitable unilateral deviation, i.e.

Observations on Nash Equilibria

Remark (support).

A support of is the set of pure strategy that has a strictly positive probability of being played in , i.e.

Proposition (indifference among support of NE).

A strategy profile is a Nash equilibrium in game if and only if for all , the following two conditions hold:

, .
, , .

The ^a7ac82 Proposition 14 (indifference among support of NE) implies that among pure strategies in the support, the payoff is same in NE.

Proof.First we prove the only if part, and then we prove the if part.
() Assume that is NE, i.e. there exists no profitable unilateral deviation from .
RTA: suppose for some , either the condition or is violated. Then, where .
Now let be a mixed strategy that is same as except that plays whenever prescribes playing . Then, can profitably deviate to , which is a contradiction to the first assumption that is NE.
Therefore, both condition and must hold.

() Suppose the both condition and hold.
RTA: suppose that is not a NE, i.e. there exists a profitable unilateral deviation from .
Thus we have, Remark that, by Introduction to Game Theory > ^8bab16 Introduction to Game Theory > Definition 6 (payoff function for mixed strategy), Thus, we have Then we have the two cases when and .
If , then by the condition , for all . This will lead to , which is a contradiction.
If , then by the condition , for all . Then we have . Thus leads to a contradiction.

Therefore, must be a NE. □

Proposition (strictly dominated strategy in NE).

A strictly dominated strategy is never played in a Nash Equilibrium. i.e. for a pure strategy s.t., then .

Proof.Let be strictly dominated, and be NE. Then, by ^cf4318 Definition 3 (strict dominance in mixed strategies), we have RTA: suppose .
Let be the mixed strategy such that where , , while whenever plays , it plays . Then, we have Thus is not NE. which is a contradiction.
Therefore, must hold. □

Rationalizable Strategies

Definition (best response).

A strategy is a best response to in a game , if it is an optimal choice when player conjectures that his opponents will play . i.e. Note that is a best response correspondence.

Proposition (convexity of the best-response).

The best response correspondence is convex for all . i.e.

Proof.Assume . Then by ^fcce88 Definition 16 (best response), we have Now for an arbitrarily given , let . Then, we have Therefore . □

Given the ^fcce88 Definition 16 (best response) and ^c508fb Definition 12 (mixed Nash Equilibrium), the following Remark trivially follows.

Remark (NE is br).

The strategy profile is a Nash equilibrium of game if and only if for all .

Therefore, it is sufficient to show that the strategy profile is a conjugate of best responses for every player, to show that it is a Nash equilibrium.

Example (2 by 2 two players game).

	l	r
T	(1, 2)	(3, 4)	p
B	(2, 7)	(2, 6)	1-p
	q	1-q

where the player 1 plays with the probability of , and the player 2 plays with the probability of .
Find all the Nash Equilibrium using the best-response correspondence.

Proof.Using the result of ^a7ac82 Proposition 14 (indifference among support of NE), we first derive each player's best response.

(player 1's best response) First assume player 2 plays with the probability of . Then, As and must have the same utility on NE, we have Therefore, the best response of player 1 is the function of , where

(player 2's best response) Similarly, assume player 1 plays with the probability of . Then, As and must have the same utility on , we have Thus, the best response of player 2 is the function of , where

(NE) Lastly, we find intersections of and . In the below graph, the horizontal axis refers to , and the vertical axis refers to . And the red line is , while the blue line is .

We can see that there are three purple dots of the intersections, , , and . The dots located in the corner of the graph shows the pure strategy profile, while the inner one indicates the mixed strategy profile. Using the strategies given in the question, we have:

pure NE strategy profile: , .
mixed NE strategy profile: .

Therefore, we have three NEs: two pure, and one mixed. □

Existence of Nash Equilibria

Lemma (properties of best-response correspondence).

Let the sets be nonempty, compact and convex. And let be continuous in and quasiconcave in . Then the player 's best-response correspondence is nonempty, convex-valued, and upper hemicontinuous.

Proof.The Lemma directly follows from Introductory Analysis > ^936f0c Introductory Analysis > Theorem 38 (Berges's Maximum Theorem). Since by ^fcce88 Definition 16 (best response), thus is the set of maximizers of the continuous function on the compact set . Thus is nonempty, convex-valued, and upper hemicontinuous. □

Proposition (existence of pure Nash equilibria).

A Nash equilibrium exists in game if for all , the following two both hold:

is a nonempty, convex, and compact subset of some Euclidean space .
is continuous in and quasiconcave in .

Proof.Define a correspondence by Note that is a nonempty, convex-valued, and upper hemicontinuous correspondence, since all are nonempty, convex-valued, and upper hemicontinuous.
Thus, as is a nonempty, compact, convex set and is nonempty, convex-valued, and upper hemicontinuous, by Introductory Analysis > ^f6db84 Introductory Analysis > Theorem 40 (Kakutani's Fixed Point Theorem), has a fix point. i.e., there exists a strategy profile such that .
Furthermore, the strategies at the fixed point constitutes a Nash equilibrium, because we have for all . □

Theorem (existence of mixed Nash Equilibria).

The game in which the sets have a finite number of elements has a mixed strategy Nash Equilibrium.

Proof.The game can be viewed as a game with strategy sets and payoff functions for all , satisfies all the assumptions of ^2933fd Proposition 21 (existence of pure Nash equilibria). Thus it is a direct corollary of the previous result. □

Trembling-Hand Perfection

Weak Dominance

Definition (weak dominance in pure strategies).

A strategy is weakly dominating in game , if regarding all other player's every possible strategy, gives greater than or equal to the other strategy of player , while it strictly dominates for some strategy profile.

weakly dominates if
is weakly dominated if
is weakly dominant if it weakly dominates every other strategy. i.e.

Example (3 by 2 two players game).

	l	r
U	(5, 1)	(4, 0)
M	(6, 0)	(3, 1)
D	(6, 4)	(4, 4)

Proof.For player 1, Thus is weakly dominating. i.e. and are weakly dominated by . □

Definition (weak dominance in mixed strategies).

A mixed strategy is weakly dominating in game , if regarding all other player's every possible strategy, gives strictly greater than or equal to the other strategy of the player .

weakly dominates if
is weakly dominated if
is weakly dominant if it weakly dominates every other strategy. i.e.

Example (3 by 3 two player game).

	L	M	R
U	(5, 1)	(4, 4)	(2, 3)
C	(3, 2)	(3, 3)	(3, 7)
D	(2, 2)	(4, 1)	(5, 0)

Find all the pure and mixed NE.

Proof.First, We eliminate the strictly dominated strategies.

Step 1) For player 1, is eliminated since .
First we denote the player 2 plays where Then the payoff for the player 1 is Then for the mixed strategy of and , therefore, for every , we have which makes as strictly dominated strategy, and be eliminated.

Step 2) For player 2, is eliminated since .
This is trivial since Therefore is strictly dominated by .

Step 3) For the remaining strategy, we denote Then, the payoff for the player 1 assuming is Thus, player 1's best response is Next, the payoff for the player 2 assuming is Thus, player 2's best response is

Therefore,
desmos-graph (3).svg

Where the pure NE is and the mixed NE is Therefore, we have weakly dominant mixed NE. □

Perturbed Game

Definition (perturbed game).

For a normal game , define a perturbed strategy set for all player as where , and , and .
By letting , a perturbed game is defined as

Note that denotes an unavoidable probability that a player plays by mistake, which is given arbitrarily.

Definition (convergence of perturbed game).

A sequence of perturbed games converges to normal form game , if

Definition (Trembling-hand Perfect Nash Equilibrium).

A Nash Equilibrium of is trembling-hand perfect if there is some sequence of perturbed games converging to , for which there is some associated sequence of Nash Equilibrium that converges to , i.e.

Note that THP-NE(Trembling-hand Perfect Nash Equilibrium) is the subset of set of NEs.

Example (THP-NE for 2 by 2 two player game ).

	l	r
T	(1, 1)	(0, -3)	p
B	(-3, 0)	(0, 0)	1-p
	q	1-q

derive THP NE.

Proof.First we derive best response for normal form game. Let be the probability that the player 1 plays , and let be the probability that the player 2 plays . Then we have Therefore, the best response function is Thus we have
desmos-graph (1).svg
where the Nash Equilibrium is and .

Now consider a perturbed game where and therefore, we have Assuming that the player 1 trying to maximize knowing that the player 2 is trembling hand, the utility function is Since by , we have , meaning that the player 1 will try to maximize . Thus the best response for the player 1 is Similarly, for the player 2, the best response is

Thus we have
desmos-graph (2).svg
where the purple dot is the only NE of , where Furthermore, since Therefore, is THP NE, while is not THP NE. □

Properties of THP-NE

Here we further analysis the property of THP-NE.

Proposition (conditions to be THP-NE).

Let be a Nash Equilibrium of the game . Then is trembling-hand perfect if and only if the exists some sequence of totally mixed strategies such that both

holds.

Notice that is totally mixed strategies if , , meaning that plays all pure strategies with strictly positive probability.

Example (THP-NE for 2 by 2 two player game -2).

	l	r
T	(1, 1)	(0, -3)	p
B	(-3, 0)	(0, 0)	1-p
	q	1-q

Proof.Using the proof for ^1d585a Example 30 (THP-NE for 2 by 2 two player game), we have the best responses of Then applying the ^f7a496 Proposition 31 (conditions to be THP-NE), we have and Therefore THP-NE is , which equals to . □

Proposition (THP-NE and weakly dominance).

Let be the Trembling-hand Perfection Nash equilibrium for the game . Then for every player , does not play any weakly dominated strategy with strictly positive probability.

Remark that the set of THP-NE is a strict subset of the set of NE without weakly dominated strategies. This means that while ^4cb792 Proposition 33 (THP-NE and weakly dominance) holds, the inverse of the proposition does not hold always.

Bayesian Nash Equilibrium

Bayesian Game

In Bayesian game, we talk about a game under the incomplete information. Note that this differs to the definition of Introduction to Game Theory > ^ecb882 Introduction to Game Theory > Definition 11 (perfect or imperfect information), where

incomplete information: private information that exists even before the game starts.
imperfect information: private information that came out after the game begins.

Before formally defining the Bayesian game, we first look through the Harsanyi's approach to understand the basic concept of the incomplete information game.

Proposition (Harsanyi's approach).

Each player's preferences type are determined by the realization of random variable.
The player can only observe the realization of her own type, not other's.
While other player's actual type unknown to others, its ex ante probability distribution is assumed to be common knowledge.
This ex-ante common knowledge is called belief.

Through this interpretation, now the situation of incomplete information becomes an imperfect information.

Now we define the Bayesian Game.

Definition (Bayesian Game).

The Bayesian game is a list where

: set of players, .
: type space for all players .
- : player 's type space, .
- : type profile
: joint (common prior) probability distribution of type profiles.
- .
- .
: set of player 's actions, .
- : set of player 's (pure) strategies. .
- : player 's action to play when her type is .
- : strategy profile.
: player 's payoff function from given her type .
: player 's ex ante expected payoff from .

Bayesian Nash Equilibrium

Definition (pure Bayesian Nash Equilibrium).

A pure strategy Bayesian Nash equilibrium(BNE) for the Bayesian game is a profile of strategies that constitutes a Nash Equilibrium of non Bayesian game . That is,

Note that the Bayesian Nash Equilibrium can be obtained as a concept of normal Nash Equilibrium Nash Equilibrium.

In the following proposition, it shows that a (pure strategy) BNE can be obtained through the every player's best responses to the conditional distribution of her opponents' strategies for each type that he might end up having.

Proposition (best response for BNE).

A strategies profile is a Bayesian Nash Equilibrium in Bayesian Game if and only if for all player and for all type occurring with positive probability where the expectation is taken over realizations of the other player's random variables conditional on player 's realization of his type .

Proof.The result can be driven directly from the ^ada00b Definition 36 (pure Bayesian Nash Equilibrium), where Therefore we have the result of ^4ad1db Proposition 37 (best response for BNE). □

Entry Deterrence Game

Example (BNE for Entry Deterrence Game).

	L	R
U	(-1, 2)	(1, 1)
D	(0, 4)	(0, 3)

and

	L	R
U	(-1, -1)	(1, 1)
D	(0, 0)	(0, 3)

where and . Find Bayesian Nash Equilibrium.

Proof.Let , and . Then, player 1's expected payoff is

Thus, we haveTherefore,

Next, player 2's expected payoff given is and Thus, Therefore, since and , we have . Thus . i.e. . Then, the (pure) BNE is . □

R&D Determination Game

Example (two firm R&D determination).

	D	N
D	()	()
N	()	(0, 0)

where is a cost for the development, and is each firm 's benefit from the new technology. Note that the probability distribution of teach firm's type is , and and are independent.

Proof.Consider a strategy profile , and let . Then, firm 1's expected payoff is, then we have Thus, firm 1's best response is Similarly, firm 2's expected payoff is, Thus, firm 2's best response is Remark that . As we have where two are symmetric. we can let . Then we have, Therefore, the equilibrium cutoff is Therefore, the BNE is, , for all .

Now check for the general BNE. For the cutoff , we have Using the previous results, we have If , then . thus . Otherwise, .
Similarly, if , then . thus . Otherwise, .

Therefore, we have
desmos-graph (4).svg
Where the only BNE is . □

Auction Theory

First Price Auction

Exercise (first price auction with uniform distribution).

: An object is auctioned off to bidders.
: Every bidder submit their bids simultaneously.
: Bidder 's valuation of the object is , where .
The bidder with the highest bids wins and gets the object by paying his own bids. If the winner is multiple, then they get the object with equal probability.

Proof.Let the strategy of bidder be denoted as a function , where . Also, since , if the bidder bids , then he wins with the probability of .

Denote the payoff function of the bidder as Then, the optimal is F.O.C. This results implies:

(bid shading): the bidder bids , which is smaller than his true valuation.
If , then .

Finally, we calculate the maximized payoff. If all other players bids , then the probability that player wins by bidding is Therefore, the maximized payoff is The BNE is . □

Exercise (first price auction with square distribution).

Consider a first price auction from ^9322db Exercise 40 (first price auction with uniform distribution), where follows distribution of .

Proof.Consider every bidder bids with the same strategy , where Then, for some arbitrary distribution function , the objective (payoff) function is, Remark that , and the chain rule of

F.O.C. where the last equality holds since .

Note that we have Therefore, the BNE is which completes the proof. □

Second Price Auction

Exercise (second price auction).

: An object is auctioned off to bidders.
: Every bidder submit their bids simultaneously.
: Bidder 's valuation of the object is .
The bidder with the highest bids wins and gets the object by paying the second highest bids. If the winner is multiple, then they get the object with equal probability.

Proof.Denote the highest bidding except as , and there exists bidders that submits . Then, the payoff matrix is as follows.

(if )	bids vs	(if )	bids vs

Thus, bidding is weakly dominating strategy in every cases. □

All-Pay Auction

Exercise (all-pay auction with strictly increasing strategy).

: An object is auctioned off to bidders.
: Every bidder submit their bids simultaneously.
: Bidder 's valuation of the object is , where .
The bidder with the highest bids wins and gets the object by paying his own bids, however, every other bidder must also pay their own bids. If the winner is multiple, then they get the object with equal probability.

Proof.Denote the payoff function of the bidder as and assume is strictly increasing.

Note that where the second equality holds since is strictly increasing. Also, is an arbitrary distribution function of , where its first derivative function is denoted as .

Then, the objective payoff function for bidder is, F.O.C. thus, the BNE is If , then we have which result is equals to ^9322db Exercise 40 (first price auction with uniform distribution). □