# Chapter 6. Games
[ToC]

## 6.1 What is a Game?
* Basic Ingredients of a Game:
- 1. **Players**, a set of participants.
- 2. **Strategies**, a set of options for how to behave.
- 3. **Payoff**, depend on the selected strategies.

## 6.2 Reasoning about Behavior in a Game

### Underlying Assumptions
:::info

- Players only concerned with maximizing their **own** benefit.
- Players knows everything about the structure of the game.
- ***Rationality***
- A player beliefs his or her optimal strategy will also be used by the others.
- Each player succeeds in selecting the optimal strategy.
:::

### Example
Prisoner's Dilemma


* From **Suspect 1's** point of view
- 1. Suspect 2 confess
- Suspect 1 confess $\Rightarrow$ Receive -4
- Suspect 1 not confess $\Rightarrow$ Receive -10

- 2. Suspect 2 **not** confess
- Suspect 1 confess $\Rightarrow$ Receive 0
- Suspect 1 not confess $\Rightarrow$ Receive -1

**Better outcome?**
Both choose not to confess ?
No way under ***rationality*** !!!

**Arm races**
Two competitors use an increasingly dangerous arsenal of weapons to remain evenly matched.

## 6.3 Best Responses and Dominant Strategies

### Notation
:::info
If $S$ is a strategy chosen by **Player 1**, and $T$ is a strategy chosen by **Player 2**
* Write $(S,T)$ to denote the entry in the payoff matrix.
* Write $P_1(S,T)$ to denote the payoff to Player 1 as a result of this pair of strategy.
:::

***Best response***
Let $S \in S_{n},$ where $S_n$ is set of Player 1's strategies.
$\forall S' \in S_n - \{S\},$ if $P_1(S,T) \geq P_1(S',T)$,
then we say strategy $S$ for Player 1 is a ***best response*** to a strategy $T$ for Player 2.

***Dominant strategy***
If strategy $S$ of Player 1 is a best response to every strategy of Player 2
then we say $S$ is a ***dominant strategy*** for Player 1

***Common knowledge***

Firm 1's and Firm 2's market share.

In general we assume that all players know the structure of the entire game.

Notice that only Firm 1 has a strictly dominant strategy which is *Low-Priced*.
Thus Firm 2 can confidently predict Firm 1 will play *Low-Priced*, and since Upscale is strict best response by Firm 2 to *Low-Priced*

## 6.4 Nash Equilibrium
Even when there are no dominant strategies, we should expect players to
use strategies that are best responses to each other.
### Definition

:::info
We say that a pair of strategies $(S,T)$ is a ***Nash equilibrium*** if $S$ is a best response to $T$, and $T$ is a best response to $S$.
:::

### Example

Three-Client Game

For Firm 1, $A$ is a strict best response to $A$
For Firm 2, $A$ is a strict best response to $A$
so we can say that the pair of strategies $(A,A)$ forms a ***Nash equilibrium***

## 6.5 & 6.6 Multiple Equilibria

### A Coordination Game
Coordination Game

The game has two Nash equilibrium, $(Powerpoint,Powerpoint)$ and $(Keynote, Keynote)$.
Players have to follow convention or coordinate with each other to avoid receiving low payoffs.

### Variants on the Basic Coordination Game
Unbalanced Coordination Game


Schelling's theory of ***focal points*** : Schelling states that
> People can often concert their intentions or expectations with others if each knows that the other is trying to do the same.

</br>

Battle of Sexes

</br>

Stag Hunt Game

The structures are clearly different between Stag Hunt Game and Prisoner's Dilemma, since the latter has strictly dominant strategies. However, both have the property that players can benefit if they cooperate with each other.

</br>

Hawk-Dove Game


## 6.7 Mixed Strategy
:::info
**Theorem**
Every finite-player finite-strategy mixed-strtegy game has at least one equilibrium
:::

### Attack-Defend Game
The **attacker** chooses attack $A$ or attack $B$, and the **defender** chooeses defend against $A$ or $B$.

#### Matching Pennies
Player B predicts what player A chooses

| | H | T |
| -------- | -------- | -------- |
| H | -1,+1 | +1,-1 |
| T | +1,-1| -1,+1|

### Zero-Sum Game
The sum of the payoffs of two player is 0 in each outcome.

### Mixed Strategies
Rather than choosing one dirctly, player follow a *probability*

#### Pure Strategy
One choice is with probability $p=1$.

:::info
**Remark**
The unique Nash equilibrium of the mixed-strategy matching-pennies game is under probability $p=q=1/2$.

**Proof**
Given $q\neq 1/2$, the other has pure strategy in term of expectation, then contradiction.
:::

## 6.8 Mixed Strategies: Examples and Empirical Analysis

### The Run-Pass Game
| | Defend Pass | Defend Run |
| -------- | -------- | -------- |
| Pass | 0,0 | 10,-10 |
| Run | 5,-5| 0,0|

$10-10q=5q$, $5p-5=-10p$.
The equilibrium is $p=1/3,q=2/3$.

### The Penalty-Kick Game
足球射門
| | L | R |
| - | ---------- | ---------- |
| L | 0.58,-0.58 | 0.95,-0.95 |
| R | 0.93,-0.93 | 0.70,-0.70 |
The equilibrium is $p=0.39,q=0.42$.

### Principle for finding all equilibrium
- check pure strategy first
- second, check mixed strategy

| | PPT | HackMD |
| - | -------- | --- |
| PPT | 1,1 | 0,0 |
| HackMD | 0,0 | 2,2 |

## 6.9 Pareto Optimality and Social Optimality

### Pareto Optimality
A set of strategies is **Pareto Optimal** if no other strategies that
- all players recieve payoffs at least as high
- one player receives strictly higher payoffs.

白話就是
- maximal

### Social Optimality
A set of strategies is **Social Optimal** if it maximize the sum of payoffs.

:::info
**Property**
Social Optimality $\Rightarrow$ Pareto Optimality
**Proof**
Given a social optimal $A$, assume it is not Pareto optimal, then there exists $B$ strictly better than $A$. Thus $B$ has larger sum of payoffs than $A$, contradiction.
:::

## **6.10 Advanced Material: Dominated Strategies and Dynamic Games**

2 issues:
- Study the role of ***dominated strategies***. It can provide a way to make predictions even when no player has a ***dominant*** strategy.
- How to reinterpret the strategies and payoffs when strategic choices occur **sequentially** through time.

### **A. Multiplayer Games**
- A multiplayer game =
- a set of players: $1, 2, . . . , n$
- a set of strategies for each player: $S_i$
- a payoff to each player for each possible outcome: $P_i (S_1,\space S_2,\space . . . ,\space S_n)$ $\space\space\space\space\space$
- A strategy $S_i$ is a ***best response*** by player $i$ to a choice of strategies $(S_1, S_2, . . . , S_{i−1}, S_{i+1}, . . . , S_n)$ if $P_i (S_1,\space S_2,\space . . . ,\space S_{i−1},\space S_i,\space S{i+1},\space . . . ,\space S_n)\ge P_i (S_1,\space S_2,\space . . . ,\space S_{i−1},\space S^\prime_i,\space S_{i+1},\space . . . ,\space S_n)$for all other possible strategies $S^\prime_i$ .
- An outcome consisting of strategies $(S_1, S_2, . . . , S_n)$ is a ***Nash equilibrium*** if each $S_i$ is a ***best response*** to all the others.
### **B. Dominated Strategies and Their Role in Strategic Reasoning**
:::info
**Definition**
A strategy $S_i$ for player $i$ is ***strictly dominated*** if there is another strategy $S^\prime_i$ for player $i$ s.t.
$P_i (S_1,\space S_2,\space . . . ,\space S_{i−1},\space S^\prime_i,\space S{i+1},\space . . . ,\space S_n)\gt P_i (S_1,\space S_2,\space . . . ,\space S_{i−1},\space S_i,\space S_{i+1},\space . . . ,\space S_n)$
for all $(S_1,\space S_2,\space . . . ,\space S_{i−1},\space S_{i+1},\space . . . ,\space S_n)$.
i.e.
A strategy is ***strictly dominated*** if there is some other strategy available to the same player that produces a strictly higher payoff in response to every choice of strategies by the other players.
:::

- In the two-player, two-strategy games , a strategy is ***strictly dominated*** precisely when the other strategy available to the same player is ***strictly dominant***. However, if a player has many strategies, then it’s possible for a strategy to be ***strictly dominated*** without any strategy being dominant.

#### **The Facility Location Game**
- Two firms compete through their choice of locations
- 
- 
- Neither player has a dominant strategy.

#### **Dominated Strategies in the Facility Location Game**
- We can make progress by thinking about their ***dominated*** strategies.
- A is a ***strictly dominated*** strategy for Firm 1
- 
- F is a ***strictly dominated*** strategy for Firm 2
- 
- Therefore, A and F can be eliminated.
- 
- With A and F eliminated, strategies B and E now are strictly dominated, so we can eliminate them.
- 
- 
- The process is called the ***iterated deletion of strictly dominated strategies***.
- The prediction is natural.

#### **Iterated Deletion of Dominated Strategies: The General Principle**
- The process of ***iterated deletion of strictly dominated strategies***:
- Finding and deleting all the ***strictly dominated*** strategies.
- Continuing process until none of ***strictly dominated*** can be found.
- The set of ***Nash equilibria*** of the original game coincides with the set of ***Nash equilibria*** for the final reduced game.
- To show the set of ***Nash equilibria*** does not change after one round of deleting.
- Any ***Nash equilibrium*** of the original game is a ***Nash equilibrium*** of the reduced game.
- Suppose there is a ***Nash equilibrium*** of the original game involving a strategy $S$ that was deleted. But it means $S$ is ***strictly dominated*** by some other strategy $S^\prime$ and therefore $S$ is not a ***best response***. Hence, $S$ cannot be part of a ***Nash equilibrium*** of the original game.
- Any ***Nash equilibrium*** of the reduced game is also a ***Nash equilibrium*** of the original game.
- Suppose there exists a ***Nash equilibrium*** $E$ of the reduced game, but $E$ isn't a ***Nash equilibrium*** of the original game. So there exists a strategy $S^\prime_i$ that was deleted from the original game, but it means $S^\prime_i$ was ***strictly dominated*** by at least one other strategy. We can find a strategy $S^{\prime\prime}_i$ that strictly dominated it and was not deleted, contradicting our assumption that $E$ is a Nash equilibrium of the reduced game.

#### **Weakly Dominated Strategies**
:::info
**Definition**
A strategy $S_i$ for player $i$ is ***weakly dominated*** if there is another strategy $S_i$ for player i such that
$P_i (S_1,\space S_2,\space . . . ,\space S_{i−1},\space S^\prime_i,\space S{i+1},\space . . . ,\space S_n)\ge P_i (S_1,\space S_2,\space . . . ,\space S_{i−1},\space S_i,\space S_{i+1},\space . . . ,\space S_n)$
for all choices of strategies by the other players, and
$P_i (S_1,\space S_2,\space . . . ,\space S_{i−1},\space S^\prime_i,\space S{i+1},\space . . . ,\space S_n)\gt P_i (S_1,\space S_2,\space . . . ,\space S_{i−1},\space S_i,\space S_{i+1},\space . . . ,\space S_n)$
for at least one choice of strategies by the other players.
i.e.
a strategy is ***weakly dominated*** if there is another strategy that does at least as well in all condition, and does strictly better against some joint strategy of the other players.
:::

- ***Weakly dominated strategies*** can't be deleted in previous process.
- 
- Hunt Stag is a ***weakly dominated strategy***.
- Nevertheless, the outcome in which both players choose Hunt Stag is a ***Nash equilibrium***.

### **C. Dynamic Games**
- Many games are played over time. Such games are called ***dynamic games***
- board games and card games
- negotiations
- auction
#### **Normal and Extensive Forms of a Game**
- ***normal-form***: previous representation e.g. payoff matrices
- ***extensive-form***: To describe a dynamic game, we require a richer representation.
- A simple example - game tree
- 
- Total profit in region A: 12, B: 6.
- If firm 2 ...
- follows Firm 1 into the same region, then Firm 1 takes $\frac23$ of the profit in that region, while Firm 2 will only get $\frac13$.
- moves into the other region, then each firm gets all the profit in their respective region.

#### **Reasoning about Behavior in a Dynamic Game**
- By game tree. Bottom up.
- 

- By normal-form representation
- e.g. Game in Figure 6.24.
- Firm 2 has four possible plans for playing the game:
(A if A, A if B), (A if A, B if B), (B if A, A if B), and (B if A, B if B),
or
$(AA, AB), (AA, BB), (BA, AB), and (BA, BB)$.
- 
- For Firm 1, A is ***strictly dominant***. Firm 2 does not have a strictly dominant strategy, the best response is $(BA, AB)$ or $(BA, BB)$.

#### **A More Complex Example: The Market Entry Game**
- In previous game, both representations led to essentially identical conclusions.
- As games get larger, extensive forms are representationally more streamlined.
- Sometimes, normal form lose some structure implicit in the dynamic game.
- Example(Market Entry game)
- Also played between two competing firms.
- Consider a region where Firm 2 is currently the only participant, and Firm 1 is considering whether to enter the market.
- The first move is made by Firm 1.
- If Firm 1 chooses to stay out, then the game ends, with Firm 1 getting 0 and Firm 2 keeping the payoff from the entire market.
- If Firm 1 chooses to enter, then the game continues to a second move by Firm 2
- If Firm 2 cooperates, then each firm gets half payoff.
- If Firm 2 retaliates, then each firm gets a negative payoff.

#### Subtle Distinctions Between Extensive- and Normal-Form Representations
- By extensive form:
- If firm 1 enters, firm 2 cooperates.
- Given this, firm 1 chooses to enter.
- So, firm 1 enters and firm 2 cooperates.
- By normal form:
- 
- In normal form, we discover two Nash equilibria: $(E, C)$ and $(S, R)$.
- How to explain $(S, R)$?
- The premise behind translation: each player commits ahead of time to a complete plan for playing the game

#### Relationship to Weakly Dominated Strategies
- R for Firm 2 is weakly dominated
- Consider a different condition
- 
- R and E are weakly dominated
- we have 3 Nash equilibria, no weakly dominated strategies can be deleted.