Lecture 2. Game Theory (game theory)
Recommended reading: Microeconomics — Microeconomics Table of Contents
1. Overview
6. The Economics of Commitment
► The Two-Pan Balance Problem and Game Theory
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ᵢ: the utility (payoff) of player i
② sᵢ: the strategy of player i
③ s₋ᵢ: 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₁, ···, sₙ).
⑸ 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.
③ (Note) 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 (simultaneous game)
⑴ 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.
○ πᵢ(sᵢ, s₋ᵢ) denotes the utility player i gets when player i chooses sᵢ and the other players choose s₋ᵢ.
○ Check all best responses (BRs) and mark them in the table as follows.Table 3. Match / mismatch game with BRs marked
○ BR₁(A ∈ S₂) = B ∈ S₁
○ BR₁(B ∈ S₂) = A ∈ S₁
○ BR₂(A ∈ S₁) = A ∈ S₂
○ BR₂(B ∈ S₁) = B ∈ S₂○ 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.
○ πᵢ(sᵢ, s₋ᵢ) denotes the utility player i gets when player i chooses sᵢ and the other players choose s₋ᵢ.
○ Underlining method: check all BRs and underline accordingly.Table 5. Duopoly pricing game with BRs marked
○ BR₁(L ∈ S₂) = L ∈ S₁
○ BR₁(H ∈ S₂) = L ∈ S₁
○ BR₂(L ∈ S₁) = L ∈ S₂
○ BR₂(H ∈ S₁) = L ∈ S₂○ Nash equilibrium: (s₁, s₂) = (L, L)
○ DSE: (s₁, s₂) = (L, L)○ Player 1’s dominant strategy is L (because BR₁(L ∈ S₂) = L ∈ S₁ and BR₁(H ∈ S₂) = L ∈ S₁)
○ Player 2’s dominant strategy is L (because BR₂(L ∈ S₁) = L ∈ S₂ and BR₂(H ∈ S₁) = L ∈ S₂)
⑶ 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 (sequential game)
⑴ 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.
○ (Note) 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
○ Setting: the Hardware firm moves first; the Software firm moves afterward.
○ Meaning of (HH, HS): one Software strategy—choose H if Hardware chooses H, and choose H if Hardware chooses S.
○ (S, (SH, SS)) is an unrealistic solution (because the Hardware firm 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
③ (Comment) 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.
② (Note) 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.
○ (Comment) 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.
① 1st. Find all NEs.
○ In the above example, you can find (H, (HH, HS)), (H, (HH, SS)), (S, (SH, SS)).
② 2nd. 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.
① 1st. In the extensive-form sequential game, start from the leaves and move upward to find the first singleton information set.
② 2nd. Find the NE in each proper subgame.
③ 3rd. Move up to the second singleton information set.
④ 4th. Find the NE in each proper subgame and mark it appropriately.
⑤ 5th. 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−ω.
② 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 ω.
④ 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₁(t), s₂) 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
○ If t = −1, Player 1 should always choose S: discard strategies involving H₋₁.
○ BNE candidates: ((S₋₁, H₃), H), ((S₋₁, H₃), S), ((S₋₁, S₃), H), ((S₋₁, S₃), S)
○ ((S₋₁, H₃), H): best response (OK)
○ ((S₋₁, H₃), S): better to switch to ((S₋₁, S₃), S)
○ ((S₋₁, S₃), H): better to switch to ((S₋₁, H₃), H)
○ ((S₋₁, S₃), S): best response (OK)⑥ Determining Player 2’s best response
○ Evaluate ((S₋₁, H₃), H)
○ Evaluate ((S₋₁, S₃), S)⑦ Conclusion: the BNEs are ((S₋₁, H₃), H) and ((S₋₁, S₃), S).
6. The Economics of Commitment (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.
Posted: 2020-04-22 13:27