---
title: Game Theory 筆記
description: 參考 "A Course in Game Theory", M. J. Osborne, A. Rubinstein, MIT, 1994., 配合上課 ppt 而統整的筆記
tags: Game Theory
lang: zh_tw
---

# Game Theory 筆記
[TOC]

# Intro
> Game theory is a bag of analytical tools designed to help us understand
the phenomena that we observe when decision-makers interact. The basic assumptions that underlie the theory are that decision-makers pursue
well-defined exogenous objectives (they are rational) and take into account their knowledge or expectations of other decision-makers’ behavior
(they reason strategically).

賽局理論, 也稱博弈論
- **是個分析工具**, 用來分析決策者之間的各種抉擇
- **人性捉摸不定**, 但賽局理論假設**決策者是理性的**

## Game 的定義
> A game is a description of strategic interaction that includes the constraints on the actions that the players can take and the players’ interests, but does not specify the actions that the players do take
>
賽局是指對於決策者之間的互動, 而每個決策者都只會作出最優的決策

所謂最優的決策是指考慮上了
- 作出此決策的得失
- 基於其他決策者也會作出對其而言最優決策, 考慮其作的決策與自己的決策之間的交互作用

最為經典的例子就是[**囚徒困境**](https://zh.wikipedia.org/wiki/%E5%9B%9A%E5%BE%92%E5%9B%B0%E5%A2%83)

| | **B 沉默** | **B 認罪** |
| -------- | -------- | -------- |
| **A 沉默** | 兩人服刑半年 | A 服刑十年, B 獲得釋放 |
| **A 認罪** | B 服刑十年, A 獲得釋放 | 兩人服刑五年 |

站在 A 的角度思考
- 若對方沉默、我背叛會讓我獲釋，所以會選擇背叛。
- 若對方背叛指控我，我也要指控對方才能得到較低的刑期，所以也是會選擇背叛。

二人面對的情況一樣，所以二人的理性思考都會得出相同的結論——選擇背叛。

## Game Model 的種類
此書為 Game 建立四種 Model 分開研究討論
1. **`Strategic games`**
2. **`Extensive games with perfect information`**
3. **`Extensive games without perfect information`**
4. **`Coalitional games`**

分類的根據是基於三個差異點
### Noncooperative and Cooperative Games
賽局中的玩家們是各自作決策, 或是一起作決策

| Type | Model |
| -------- | -------- |
| Noncooperative | 1, 2, 3 |
| Cooperative | 4 |
(Model 編號請參照上一節)

### Strategic Games and Extensive Games
- `Strategic Games`
每個玩家的決策是同時作出的, 在作出決策之前是無法先知道其他玩家的決策
- `Extensive Games`
每個玩家的決策並不同時作出, 也不必在賽局一開始就馬上作出決策, 而是在賽局中仍能調整策略

### Games with Perfect and Imperfect Information
這裡的 `Information` 是指**其他玩家的行動**

這個差異點的意思就是**能否完全知道其他玩家的行動**

## Bounded Rationality
現階段的賽局理論是假設玩家是**完全理性**的

但這個假設明顯與現實不符

更貼近現實的情況是假設玩家是**有限理性**的

這就要去假設玩家的能力

這邊提及此概念, 顯示出目前賽局理論的關鍵缺失

# Nash Equlibrium
每個玩家都選擇了其中一個策略, 會形成一組策略

當一組策略中, 其中任意一名玩家改變策略, 並不會得到更多好處, 則此組策略稱為 Nash Equlibrium

而一場 Game 中有機會有多組 Nash Equlibrium

## Strictly Competitive Game (Zero-sum Game)
> A strategic game $\langle\{1, 2\},(A_i),(≿_i)\rangle$ is strictly competitive if for any $a \in A$ and $b \in A$ we have $a ≿_1 b$ if and only if $b ≿_2 a$

首先解釋一下各個符號(我的理解)
- $\{1, 2\}$
玩家的集合
- $(A_i)$
動作的集合
- $≿$
偏好, 就是偏好
具體來說, 此符號是 binary operator, 也就是兩邊要有東西才有意義
$a ≿ b$ 表示說動作 $a$ 帶來的結果比動作 $b$ 帶來的結果好
- $≿_i$
偏好的集合
- $a ≿_1 b$
對於玩家 1 來說, 動作 $a$ 帶來的結果比動作 $b$ 帶來的結果好
- $b ≿_2 a$
對於玩家 2 來說, 動作 $b$ 帶來的結果比動作 $a$ 帶來的結果好

也就是說這兩個玩家若都想得到對各自最好的利益, 那麼一定會有衝突
- 選 $a$ 就是對玩家 1 好, 對玩家 2 不好
- 選 $b$ 就是對玩家 1 不好, 對玩家 2 好

又稱**零和賽局**(Zero-sum Game)
- 選 $a$ 玩家 1 造成 +1 分, 對玩家 2 造成 -1 分
- 選 $b$ 玩家 1 造成 -1 分, 對玩家 2 造成 +1 分
- 不管選何者, 兩玩家的分數相加為 0, 玩家 1 損失的就是玩家 2 得到的, 反之亦同

# Rationalizability and Iterated Elimination of Dominated Actions

## One-shot & Repeated games
> If the players participate repeatedly in the situation that the game models then they can obtain this knowledge from the steady state behavior that they observe. However, if the game is a one-shot event in which all players choose their actions simultaneously then it is not clear how each player can know the other players’ equilibrium actions
>
- One-shot Game
同時要決定, 不知道對方的決策
- Repeated Game
有過往的狀態這份資訊可以納入考量

# Others
## Pareto efficient/optimal
書上這樣定義

> Let $N$ be a finite set and let $X \subseteq \mathbb{R}^N$
>
> Then $x \in X$ is **Pareto efficient** if there is no $y \in X$ for which $y_i > x_i$ for all $i \in N$
>

我的理解是

- $\mathbb{R}^N$
是所有 $N$ 維向量的集合
- $X$
也是 $N$ 維向量的集合 ($i \in N$), 但小於 $\mathbb{R}^N$
- $x, y$
是 $N$ 維向量, 在 $X$ 集合中
- $y_i > x_i$ for all $i \in N$
是指 $y$ 每個維度的數值都大於 $x$ 對應維度的數值

而老師的 ppt 上是寫

> State where a systems resource are distributed in the most efficient manner. One person’s / group’s situation cannot be improved without making another person’ / group’s situation worse
>

我的理解是
- 若可以在不讓其他人的狀況更糟的前提下優化自己的狀況, 則這就不是 **Pareto efficient**

(在 B 不能往左掉的前提下, A 還能往上升, 就不是 **Pareto efficient**)
(在邊緣的線上時, 要讓 A 繼續上升的話, 只能讓 B 往左掉, 所以這條邊緣線上的點都是 **Pareto efficient**)

以[**囚徒困境**](https://zh.wikipedia.org/wiki/%E5%9B%9A%E5%BE%92%E5%9B%B0%E5%A2%83)來解釋

| | **B 沉默** | **B 認罪** |
| -------- | -------- | -------- |
| **A 沉默** | 兩人服刑半年 | A 服刑十年, B 獲得釋放 |
| **A 認罪** | B 服刑十年, A 獲得釋放 | 兩人服刑五年 |

改寫成數字

| | **B 沉默** | **B 認罪** |
| -------- | -------- | -------- |
| **A 沉默** | (0.5, 0.5) | (10, 0) |
| **A 認罪** | (0, 10) | (5, 5) |

以書上的定義解釋：

$N = \{A的刑期, B的刑期\}$
$\mathbb{R}^N = \mathbb{R}^2$
$X = \{(0.5, 0.5), (0, 10), (10, 0), (5, 5)\}$

- $x = (0.5, 0.5)$
存在 $y = (5, 5)\in X$ for which $y_i > x_i$ for all $i \in N$
所以 $x = (0.5, 0.5)$ 不是 **Pareto efficient**

- $x = (0, 10)$
不存在 $y \in X$ for which $y_i > x_i$ for all $i \in N$
所以 $x = (0, 10)$ 是 **Pareto efficient**

- $x = (10, 0), x = (5, 5)$ 也都是 **Pareto efficient**

以老師的 ppt 解釋：
$(0.5, 0.5)$ 這個點還可以優化成 $(5, 5)$, 在不讓 B 的數字往下掉的前提下讓 A 的數字往上升, 那此點就不是 **Pareto efficient**

$(0, 10)$ 在不讓 B 的數字往下掉的前提下無法再讓 A 的數字往上升, 所以是 **Pareto efficient**

另外兩點用一樣的方式說明是 **Pareto efficient**

# TBD.
- Actions vs Strategies
- saddle point (relationship to Nash Equlibrium)
- MinMax & MaxMin
- Affine Transformations
- Bayesian game
- Evolutionary equilibrium

# Reference
- *A Course in Game Theory*, M. J. Osborne, A. Rubinstein, MIT, 1994.