Korean, Edit

Chapter 2. Game Theory

Recommended reading: Microeconomics — Microeconomics Table of Contents

1. Overview

2. Simultaneous Games

3. Sequential Games

4. Mixed Strategy Games

5. Bayesian Games

6. The Economics of Commitment

► The Two-Pan Balance Problem and Game Theory

🕹️ The Evolution of Trust

1. Overview

⑴ Player: an economic agent participating in the game (e.g., firms, consumers).

⑵ Strategy: a plan describing what action each player will take.

⑶ Payoff: the utility each player obtains as a result of the strategy choices (i.e., the game outcome).

① $u_i$: the utility (payoff) of player $i$

② $s_i$: the strategy of player i

③ $s_{-i}$: the strategies of players $1, 2, …, i-1, i+1, n$.

④ Typically represented in a table form, i.e., a payoff matrix.

⑷ Strategy profile: the tuple $(s_1, …, s_n)$

⑸ Game: the set consisting of players, all feasible strategies, and payoffs.

⑹ Game theory: the theory of finding strategy profiles.

⑺ BR (best response)

① Definition: for one player, fixing the other players’ strategies, a strategy that maximizes that player’s utility.

② A player may have multiple best responses (ties), so a BR need not be unique.

⑻ Nash equilibrium (NE)

① Definition: a strategy profile where every player’s strategy is a best response.

② In other words, no player can benefit by unilaterally changing their choice.

③ John Nash: winner of the 1994 Nobel Prize in Economic Sciences; protagonist of the movie A Beautiful Mind.

⑼ Dominant strategy equilibrium (DSE)

① Definition: a strategy profile where all players choose their dominant strategies.

② A drawback is that it is not common in reality.

③ Dominant strategy: a strategy that maximizes a player’s utility regardless of the other players’ strategies.

④ Theorem 1. DSE ⊂ NE

⑤ Theorem 2. Even if a dominant strategy equilibrium does not exist, a Nash equilibrium may still exist.

○ Reason: the conditions for Nash equilibrium are weaker (less restrictive).

⑽ Optimization theory vs. game theory

Table 1. Optimization theory vs. game theory

2. Simultaneous Games

⑴ Assumptions: cooperation is impossible, and the game is played only once.

⑵ Representation 1. Normal-form representation

① Example 1. Match / mismatch game

Table 2. Match / mismatch game

○ In each cell “#, #”, the first number is player 1’s utility, and the second number is player 2’s utility.

○ $\pi_i(s_i, s_{-i})$ denotes the utility player $i$ gets when player $i$ chooses $s_i$ and the other players choose $s_{-i}$.

○ Check all best responses (BRs) and mark them in the table as follows.

Table 3. Match / mismatch game with BRs marked

○ $BR_1(A \in S_2) = B \in S_1$

○ $BR_1(B \in S_2) = A \in S_1$

○ $BR_2(A \in S_1) = A \in S_2$

○ $BR_2(B \in S_1) = B \in S_2$

○ Since there is no cell where both payoffs are underlined, there is no Nash equilibrium.

② Example 2. Duopoly pricing game

Table 4. Duopoly pricing game

○ In each cell “#, #”, the first number is player 1’s utility, and the second number is player 2’s utility.

○ $\pi_i(s_i, s_{-i})$ denotes the utility player $i$ gets when player $i$ chooses sᵢ and the other players choose $s_{-i}$.

○ Underlining method: check all BRs and underline accordingly.

Table 5. Duopoly pricing game with BRs marked

○ $BR_1(L \in S_2) = L \in S_1$

○ $BR_1(H \in S_2) = L \in S_1$

○ $BR_2(L \in S_1) = L \in S_2$

○ $BR_2(H \in S_1) = L \in S_2$

○ Nash equilibrium: $(s_1, s_2) = (L, L)$

○ DSE: $(s_1, s_2), (L, L)$

○ Player 1’s dominant strategy is $L$ ($\because BR_1(L \in S_2) = L \in S_1,\ BR_1(H \in S_2) = L \in S_1$)

○ Player 2’s dominant strategy is $L$ ($\because BR_2(L \in S_1) = L \in S_2,\ BR_2(H \in S_1) = L \in S_2$)

⑶ Representation 2. Game tree (extensive form): each node is called a decision node.

Figure 1. Extensive-form of a simultaneous game

Setting is the same as the duopoly game.

3. Sequential Games

⑴ Overview

① Feature 1. Single-agent decision problem

○ Definition: a situation where one player can determine their strategy completely independently of what the other player does.

○ In a typical simultaneous game, a player is affected by the other player’s strategy, so it does not fit the definition.

○ In a sequential game, the first mover has the initiative, so it corresponds to a single-agent decision problem.

○ A simultaneous game can also be a single-agent decision problem if one side’s strategy plays no role.

② Feature 2. Unlike simultaneous games, sequential games distinguish actions from plans of actions.

⑵ Example

① Normal-form representation of a sequential game: may include unrealistic Nash equilibria.

Table 6. Normal-form representation of a sequential game

○ Situation: The Hardware company moves first, followed by the Software company.

○ Meaning of $(HH, HS)$: One of the Software company’s strategies: choose $H$ if the Hardware company chooses $H$, and choose $H$ if the Hardware company chooses $S$.

○ $(S, (SH, SS))$ is an unrealistic outcome ($\because$ the Hardware company would naturally choose $H$).

② Extensive-form representation of a sequential game: does not include unrealistic Nash equilibria.

Figure 2. Extensive-form of a sequential game

③ An important feature is that, unlike simultaneous games, these two representation methods can differ for sequential games.

⑶ Proper subgame

① Information set: the set of nodes where a player could be.

○ In Figure 1, Player 2’s information set consists of a single node.
○ In Figure 2, Player 2’s information set consists of two nodes.

② Proper subgame: in an extensive-form game, a subtree whose root is a singleton information set.

○ That is, an independent game contained within a larger game.
○ Figure 2 has three proper subgames in total.

③ Feature 1. Any game contains itself as a subgame.

④ Feature 2. A simultaneous game has only one subgame.

⑤ Feature 3. Since the root decision-maker is a single player, it is a special case of a single-agent decision problem.

⑷ SPE (subgame-perfect equilibrium)

① Definition: a strategy profile that is a Nash equilibrium in every proper subgame.

② For simultaneous games, the NE concept is relevant; for sequential games, the perfect equilibrium concept is relevant.

③ Feature 1. An SPE must be an NE.

④ Feature 2. An NE need not be an SPE.

○ Reason: proper subgames eliminate unrealistic Nash equilibria.

○ Proper subgames can be seen as a method of solving via the extensive form, thus avoiding unrealistic outcomes.

⑸ Forward induction: a top-down method to find SPE.

① 1^st. Find all NEs.

○ In the above example, you can find $(H, (HH, HS)), (H, (HH, SS)), (S, (SH, SS))$.

② 2^nd. Check whether each is an NE in every proper subgame.

○ $(H, (HH, HS))$: inappropriate because in the subgame following Hardware choosing $S$, Software chooses $H$. ○ $(H, (HH, SS))$: this is an SPE.
○ $(S, (SH, SS))$: inappropriate because in the subgame following Hardware choosing $H$, Software chooses $S$.

⑹ Backward induction: a bottom-up method to find SPE.

① 1^st. In the extensive-form sequential game, start from the leaves and move upward to find the first singleton information set.

② 2^nd. Find the NE in each proper subgame.

③ 3^rd. Move up to the second singleton information set.

④ 4^th. Find the NE in each proper subgame and mark it appropriately.

⑤ 5^th. Repeat steps ③–④ until reaching the root of the game.

⑥ Example

Figure 3. Example of backward induction

$(H, (HH, SS))$ is the SPE.

4. Mixed Strategy Games

⑴ Definition: strategies are chosen probabilistically.

⑵ Feature: the best response changes depending on the probability parameters.

⑶ Example

Table 7. Example of a mixed strategy game

① Condition 1. Player 1 chooses H with probability ω and S with probability $1−\omega$.

② Condition 2. Player 2 chooses H with probability h and S with probability $1−h$.

③ BR (best response): understand that it is a response to the opponent’s parameter $h$ or $\omega$.

④ There are three Nash equilibrium solutions in total.

5. Bayesian Games

⑴ Overview

① Incomplete information: at least one player does not know the payoffs for all possible cases of the other players.

② Bayesian game: a game based on incomplete information.

○ A mixed strategy game assigns probability to actions, whereas a Bayesian game uses probability to infer information.

③ BNE (Bayesian Nash equilibrium): for two players, a strategy profile $(s_1^(t), s_2^)$ satisfying:

○ Condition 1. Player 1, who knows t, must choose a best response.

○ Condition 2. Player 2, who does not know t, must choose based on expected values.

⑵ Example

① Problem setting: with probability 1/3, $t = −1$; with probability 2/3, $t = 3$. Only player 1 knows the value of $t$ (singleton).

② Normal-form representation

Table 8. Normal-form representation of a Bayesian game

③ Extensive form: the root node is called a chance node. Note that it is singleton only for Player 1.

Figure 4. Extensive-form of a Bayesian game

④ Strategy profile notation: if t = −1 implies choosing H, write it as H₋₁ (or H1 in the original notation), etc.

⑤ Determining Player 1’s best response

○ Player 1 must choose $S$ when $t=-1$: Eliminate all strategies involving $H1$.

○ BNE candidates: $((S1,H3),H)$, $((S1,H3),S)$, $((S_1,S_3),H)$, $((S1,S3),S)$

○ $((S1,H3),H)$: Both players are playing best responses.

○ $((S1,H3),S)$: Player 1 prefers to switch to $(S1,S3)$.

○ $((S1,S3),H)$: Player 1 prefers to switch to $(S1,H3)$.

○ $((S1,S3),S)$: Both players are playing best responses.

⑥ Determining Player 2’s best response

○ Evaluate $((S1, H3), H)$

○ Evaluate $((S1, S3), S)$

⑦ Conclusion: the BNEs are $((S1, H3), H), ((S1, S3), S)$

6. The Economics of Commitment

⑴ Definition: actions taken to demonstrate a credible intention to carry out one’s threat.

⑵ The purpose is to convince the opponent that you must follow through on the threatened action even though it will obviously harm you as well.

⑶ Policy Game Theory

Posted: 2020-04-22 13:27