# 賽局理論
## Strategic games
- An n-player strategic game is a pair $G=(A,u)$
- $A=A_1\times A_2\times...\times A_n$
- 每一個 $A_i$ 是可以選擇的策略
- $u=(u_1,u_2,...,u_n)$
- 每一個 $u_i:A\rightarrow \mathcal{R}$ 是 payoff function
- A play of game G assumes all choices are **simultaneous and independent**.
- 同時不一定獨立，獨立也不一定同時
- 基本上許多game都可轉換成等價的 Strategic games
- Auction
- **First-Price Auction**
- $u_i(a)=\begin{equation}\left\{
\begin{array}{**lr**}
v_i-a_i & \text{if } i=min\{j\in N:a_j=\max\limits_{k\in N}a_k\}\\0 & \text{otherwise}
\end{array}\right.\end{equation}$
- 如果 $v_1\ge v_2\ge...\ge v_n$， 則 $a$ 是 Nash $\iff$
- (1) $a_1\in[v_1,v_2]$
- (2) $a_1\ge a_i$ for all $i$
- (3) $a_1=a_i$ for some $i$
- **Second-Price Auction**
- $u_i(a)=\begin{equation}\left\{
\begin{array}{**lr**}
v_i-max\{a_j:j\ne i\} & \text{if } i=min\{j\in N:a_j=\max\limits_{k\in N}a_k\}\\0 & \text{otherwise}
\end{array}\right.\end{equation}$
- William Vickery 證明 dominant strategy 為每個人都出自己的估價。
## Nash equilibrium
- $a^*\in A$ 是 **Nash Equilibrium** 的定義為： 對所有 $i\in N$ 和 $t\in A_i$
- $u_i(a^*)\ge u_i(a_{-i}^*,t)=u_i(a_1^*,...,a_{i-1}^*,t,a_{i+1}^*,...,a_n^*)$
- 沒有任何人願意單方面改變策略的策略
- 一個賽局可能有 0 個、 1 個、或是多個 Nash。
## Two player zero sum game 雙人零和賽局
- 一個零和遊戲的每一個 strategy profile ，兩個玩家的 payoff 總和為零。
- 只用 player 1 的 payoff 來描述。
- von Neumann 開啟零和賽局研究，John Nash 推廣到一般的賽局
- 實數完備性：
- 當集合是 finite：
- $inf： 最大下界~\leftrightarrow~\min$
- $sup： 最小上界~\leftrightarrow~\max$
- 任意實數子集合 $S$
- 有上界就有最小上界 $\sup S$。
- 有下界就有最大下界 $~\inf S$。
- 對任意實數 $x<\sup S$，存在 $y\in S$ 使得 $x<y<\sup S$
- 對任意實數 $x>~\inf S$，存在 $y\in S$ 使得 $x>y>~\inf S$
- 給定 $X$ 和 $Y$ 兩集合
- $x<y$ 對所有 $x\in X,y\in Y$ 都成立 $\iff$ $\sup X\le\inf Y$
- **Upper/Lower Value of Game：不同順序下 player 1 可以保證的 payoff。**
- Lower Value of G ： player 1 先
- $\underline\lambda=\sup\limits_{a_1}\inf\limits_{a_2}u_1(a_1,a_2)=\sup\limits_{a_1}\underline\Lambda(a_1)$
- $\underline\lambda=\max\limits_{a_1}\min\limits_{a_2}u_1(a_1,a_2)=\max\limits_{a_1}\underline\Lambda(a_1)$
- player 1 選一個最大的 row，player 2 在固定 row 下找最小值。
- Upper Value of G ： player 2 先
- $\overline\lambda=\inf\limits_{a_2}\sup\limits_{a_1}u_1(a_1,a_2)=\inf\limits_{a_2}\overline\Lambda(a_2)$
- $\overline\lambda=\min\limits_{a_2}\max\limits_{a_1}u_1(a_1,a_2)=\min\limits_{a_2}\overline\Lambda(a_2)$
- player 2 選一個最小的 column，player 1 在固定 column 下找最大值。
- 定理：$\underline\lambda\le\overline\lambda$
- $\underline\Lambda(a_1)\le u_1(a_1,a_2)\le\overline\Lambda(a_2)$
- $\underline\lambda=\sup\limits_{a_1}\underline\Lambda(a_1)\le\inf\limits_{a_2}\overline\Lambda(a_2)=\overline\lambda$
- **Strictly Determined Game**： $\underline\lambda=\overline\lambda$
- **Optimal Strategy**
- $V=\underline\Lambda(a_1)$，則 $a_1$ 是 optimal
- $V=\overline\Lambda(a_2)$，則 $a_2$ 是 optimal
- 每個玩家可能會有 0 個、 1 個、或是多個 Optimal Strategy。
- **如果雙方的 strategy set 都是 finite**
- $\underline\lambda=\max\limits_{a_1}\underline\Lambda(a_1)=\underline\Lambda(a_1^*)$ $~\rightarrow~$ $a_1^*$ 是 optimal strategy
- $\overline\lambda=\min\limits_{a_2}\overline\Lambda(a_2)=\overline\Lambda(a_2^*)$ $~\rightarrow~$ $a_2^*$ 是 optimal strategy
- **如果雙方的 strategy set 是 infinite**
- 反例一：$G=((0,1)\times(0,1),u_1)\text{ with }u_1(a_1,a_2)=a_1\cdot a_2$
- $\underline\lambda=\sup\limits_{a_1}\underline\Lambda(a_1)=\sup\limits_{a_1}0=0$
- $\overline\lambda=\inf\limits_{a_2}\overline\Lambda(a_2)=\inf\limits_{a_2}a_2=0$
- $\underline\Lambda(a_1)=0$ $~\rightarrow~$ $a_1$ 是 optimal strategy
- $\overline\Lambda(a_2)=a_2$ $~\rightarrow~$ $a_2$ 不是 optimal strategy
- 反例二：$G=((0,1)\times(1,2),u_1)\text{ with }u_1(a_1,a_2)=a_1\cdot a_2$
- $\underline\lambda=\sup\limits_{a_1}\underline\Lambda(a_1)=\sup\limits_{a_1}a_1=1$
- $\overline\lambda=\inf\limits_{a_2}\overline\Lambda(a_2)=\inf\limits_{a_2}a_2=1$
- $\underline\Lambda(a_1)=a_1$ $~\rightarrow~$ $a_1$ 不是 optimal strategy
- $\overline\Lambda(a_2)=a_2$ $~\rightarrow~$ $a_2$ 不是 optimal strategy
- 雙人零和賽局的 **Nash Equilibrium**
- 定義：
- $u_1(a_1,a_2^*)\le u_1(a_1^*,a_2^*)\le u_1(a_1^*,a_2)$
- $\sup\limits_{a_1}u_1(a_1,a_2^*)\le u_1(a_1^*,a_2^*)\le \inf\limits_{a_2}u_1(a_1^*,a_2)$
- 觀察一、二：
- $G$ 有 Nash Equilibrium $(a_1^*,a_2^*)$ $\iff$
- 1.$G$ 有 Game value $V$
- 2.$a_1^*$ 是 optimal strategy
- 3.$a_2^*$ 是 optimal strategy
- 因此可知：**找 Nash = 找 Optimal Strategy**
- 練習題(觀察一、二的應用)：如果 $(a_1,a_2)$ 及 $(a_1^*,a_2^*)$ 皆為 Nash Equilibrium，則
- 1.$(a_1,a_2^*)$ 和 $(a_1^*,a_2)$ 也是 Nash Equilibrium
- 2.$u_1(a_1,a_2)=u_1(a_1,a_2^*)=u_1(a_1^*,a_2)=u_1(a_1^*,a_2^*)$
## Mixed Extension 有限賽局的混合延伸
- 定義：
- 如果 $|A_i|$ 是 finite
- $A_i$ 的每一個成員叫做一個 pure strategy ( **action** ).
- $A_i$ 的每一個機率分布叫做一個 mixed strategy ( **strategy** ).
- **The mixed extension of finite game** $G=(A,u)$ 定義為 $E(G)=(S,u)$
- $S_i=\Delta(A_i)$ 為 $A_i$ 上的所有機率分布
- $u_i(s)=\sum\limits_{a\in A}u_i(a)s(a)$
- $s(a)=\prod s_i(a_i)$ 表示其發生機率
- **Matching Pennies 的 Mixed Extension**
- -|1|g|0
-|-|-|-
1|1|2g-1|-1
r|2r-1|4rg-2r-2g+1|1-2r
0|-1|1-2g|1
- $u_1(r,c)=4rg-2r-2g+1$
- Upper Value： $\overline\lambda=\inf\limits_{g\in[0,1]}\overline\Lambda(g)=\inf\limits_{g\in[0,1]}|2g-1|=0$
- Lower Value：$\underline\lambda=\sup\limits_{r\in[0,1]}\underline\Lambda(r)=\sup\limits_{r\in[0,1]}-|2r-1|=0$
- Game Value = 0
- 紅兔有唯一的優勝策略 $r=0.5$
- 綠兔有唯一的優勝策略 $g=0.5$
- 觀察二告訴我們有 Nash ，觀察一告訴我們只有一個 Nash。
- **Nash's Theorem**
- 任意有限賽局的混合延伸 $E(G)$，必定存在 **Nash**。
- **Brouwer's Fixed Point**
- 任意 disk to disk 的連續函數，必定有固定點
- **Kakutani's Fixed Point**
- [**Nash Theorem**](https://pdfs.semanticscholar.org/ffd7/c0ad6edb6ca69a43786c39cd01569e35b8a2.pdf)
- 一定存在某個 $s$ ，使得 $s\in BR(s)$，那樣的 $s$ 即為 **Nash**。
## Bimatrix games 雙人有限賽局的延伸
- **Bimatrix Game**
- 雙人有限賽局 的 Mixed Extension
- 給定 $(r,c)$ 是 Mixed Strategy
- Best Reply 最佳回應策略
- $BR(r,c)=BR_1(c)\times BR_2(r)$
- Pured Best Reply 單純最佳回應策略
- $PBR(r,c)=PBR_1(c)\times PBR_2(r)$
- Support 支撐策略
- $S(r,c)=S(r)\times S(c)$
- 定理與觀察：
- 觀察一： $(r,c)\in BR(r,c)\iff~(r,c)$ 是 **Nash**。
- 觀察二： $r\in BR_1(c)\iff S(r)\subseteq PBR_1(c)$
- 觀察三： $c\in BR_1(r)\iff S(c)\subseteq PBR_2(r)$
- **定理一： $(r,c)$ 是 $E(G)$ 的 Nash $\iff$ $S(r,c)\subseteq PBR(r,c)$**。
- $~~~~~~~~~~~\text{Nash 均衡}$
- $\iff$ $(r,c)\in BR(r,c)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\text{//鞍點性質}$
- $\iff$ $r\in BR_1(c)$ 而且 $c\in BR_2(r)~~~~~~~~~~~~~~~~~~~~\text{//定義}$
- $\iff S(r)\subseteq PBR_1(c)$ 而且 $S(c)\subseteq PBR_2(r)~~\text{//最佳解的凸組合}$
- $\iff S(r,c)\subseteq PBR(r,c)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\text{//定義}$
- **關鍵利器：Nash = $B_1\cap B_2$**
- $B_1=\{(r,c)|S(r)\subseteq PBR_1(c)\}$
- $B_2=\{(r,c)|S(c)\subseteq PBR_2(r)\}$
- [**Lemke–Howson algorithm**](https://en.wikipedia.org/wiki/Lemke%E2%80%93Howson_algorithm)
- **各只有兩種選擇**。
- $r=(x,1-x)\in R$ 縮寫成 $x\in[0,1]$
- $c=(y,1-y)\in C$ 縮寫成 $y\in[0,1]$
- **Battle Of Sexes**
- 
- $B_1=\{(r,c)|S(r)\subseteq PBR_1(c)\}$
- $y=1/4$ 時，$PBR_1(y)=\{0,1\}$
- $y>1/4$ 時，$PBR_1(y)=\{1\}$
- $y<1/4$ 時，$PBR_1(y)=\{0\}$
- $B_2=\{(r,c)|S(c)\subseteq PBR_2(r)\}$
- $x=3/4$ 時，$PBR_2(x)=\{0,1\}$
- $x>3/4$ 時，$PBR_2(x)=\{1\}$
- $x<3/4$ 時，$PBR_2(x)=\{0\}$
- 
- 有三個 **Nash**
- **警衛與小偷**
- 
- $B_1=\{(r,c)|S(r)\subseteq PBR_1(c)\}$
- $y=\frac{P}{P+J}$ 時，$PBR_1(y)=\{0,1\}$
- $y>\frac{P}{P+J}$ 時，$PBR_1(y)=\{1\}$
- $y<\frac{P}{P+J}$ 時，$PBR_1(y)=\{0\}$
- $B_2=\{(r,c)|S(c)\subseteq PBR_2(r)\}$
- $x=\frac{R}{R+F+M}$ 時，$PBR_2(x)=\{0,1\}$
- $x>\frac{R}{R+F+M}$ 時，$PBR_2(x)=\{0\}$
- $x<\frac{R}{R+F+M}$ 時，$PBR_2(x)=\{1\}$
- 
## Matrix Game 雙人零和有限賽局的延伸
- 基本想法：
- 沒有零和的時候，只能處理雙方各有兩招的情形。
- 如果加入零和的條件，我們可以用**子方陣法**處理雙方任意有限招。
- Nash Theorem：有限賽局的延伸必定有 Nash Equilibrium
- **Game 有 Value**
- **雙方有最佳策略**
- Lower Value： $\underline{\lambda}=\max\limits_{r\in\Delta R}\min\limits_{c\in\Delta C}\sum\limits_{i\in R}\sum\limits_{j\in C}a_{ij}r_ic_j=\max\limits_{r\in\Delta R}\min\limits_{j\in C}\sum\limits_{i\in R}a_{ij}r_i$
- Upper Value： $\overline{\lambda}=\min\limits_{c\in\Delta C}\max\limits_{r\in\Delta R}\sum\limits_{i\in R}\sum\limits_{j\in C}a_{ij}r_ic_j=\min\limits_{c\in\Delta C}\max\limits_{i\in R}\sum\limits_{j\in C}a_{ij}c_j$
- **2-Rows**
- $r=(x,1-x)\in R$ 縮寫成 $x\in[0,1]$
- $V=\underline{\lambda}$ $=\max\limits_{r\in\Delta R}\min\limits_{c\in\Delta C}\sum\limits_{i\in R}\sum\limits_{j\in C}a_{ij}r_ic_j\\=\max\limits_{x\in[0,1]}\min\limits_{c\in\Delta C}\sum\limits_{j\in C}(a_{1j}x+a_{2j}(1-x))c_j\\=\max\limits_{x\in[0,1]}\min\limits_{j\in C}a_{1j}x+a_{2j}(1-x)\\=\max\limits_{x}\min\limits_{j}(a_{2j}+(a_{1j}-a_{2j})x)$
- 紅兔只要選定 mixed strategy $(x,1-x)$
- 綠兔就會回應 pure strategy 使得 payoff 越小越好
- $\rightarrow$ 紅兔的 OPT strategy 是 **lower envelope 的最大值** 對應的 mixed strategy
- $V=\overline{\lambda}$ $=\min\limits_{c\in\Delta C}\max\limits_{r\in\Delta R}\sum\limits_{i\in R}\sum\limits_{j\in C}a_{ij}r_ic_j$
- 綠兔只要選定 pure strategy 的凸組合對應的 mixed strategy
- 紅兔就會回應 mixed strategy 使得 payoff 越大越好
- $\rightarrow$ 綠兔的 OPT strategy 是 **可以使凸組合落在 $V$ 下方** 對應的 mixed strategy
- 
- **2-Columns**
- 用 coulumn player 的角度想，把矩陣共軛轉置，就和 **2-Rows** 討論完全相同。
- **General Matrix**
- 給定一個 $(r,c)$，判定是否為 **Nash** 的方法。
- 1.$\min\limits_{j\in C}\sum\limits_{x\in R}r_xa_{xj} = \max\limits_{i\in R}\sum\limits_{y\in C}c_ya_{iy}$
- 2.$r$ 和 $c$ 都是 optimal strategy.
- 性質一： $(r,c)$ 是 **Nash** $\iff$ $\min\limits_{j\in C}\sum\limits_{x\in R}r_xa_{xj} = \max\limits_{i\in R}\sum\limits_{y\in C}c_ya_{iy}$
- $r$ 和所有 column 內積最小值 $\ge$ $c$ 和所有 row 內積最大值
- $\underline\lambda \ge \underline\Lambda(r)=\min\limits_{j\in C}\sum\limits_{x\in R}r_xa_{xj} = \max\limits_{i\in R}\sum\limits_{y\in C}c_ya_{iy}=\overline\Lambda(c) \ge \overline\lambda$
- 性質二：$(r,c)$ 是 **Nash** $\iff$ $(r,c)$ 是 **Nash Extreme Equilibria 的凸組合**
- 性質三：$(r,c)$ 是 **Nash Extreme Equilibria** $\iff$ $(r,c)$ 是 **Nash** 且可由以下方法得到
- $A$ 的某個可逆子方陣 $B$
- $B$ 的餘因子矩陣 $B^*$
- 行列式值 $\times$ 反矩陣轉置
- $B^*$ 對應到 $(r_1,...,r_n)$ 及 $(c_1,...,c_n)$
- $r'=\frac{1}{r_1+...+r_n}(r_1,...,r_n)$ 及 $c'=\frac{1}{c_1+...+c_n}(c_1,...,c_n)$
- $r,c$ 在對應位置補 0，升級成和 $A$ 一樣大的項數
- **子方陣法：**
- 1.對於每一個 $A$ 的可逆子方陣 $B$，用性質三的公式得到對應的 $r,c$
- 如果 $(r,c)$ 不是合法的 mixed strategy，結束。
- 如果性質一檢查 $(r,c)$ 不是 Nash，結束。
- 否則， $(r,c)$ 是 **Nash Extreme Equilibria**
- 2.性質二知，**Nash** 即為所有 **Nash Extreme Equilibria** 的凸組合。
- 例子：
- 
- 
- 
## Correlated Game 允許公開訊號
- Strategy v.s. Action
- Action：任何一個 pure strategy，也就是 $A_i$ 裡的元素
- Strategy：任何一個 mixed strategy，也就是 $A_i$ 上的機率分布
- 原本假設所有玩家同時與獨立做決定，現在要放寬到允許公開的隨機信號
- $\Omega$ 是所有信號所形成的樣本空間
- action profile 數量：$|A_1|\times...\times|A_n|$
- correlated strategy profile 數量：$(|A_1|\times...\times|A_n|)^{|\Omega|}$
- 簡化版：
- Correlated Strategy $\tau_i$：任何一個從 $\Omega$ 到 $A_i$ 的 mapping
- Correlated Strategy Profile： $\tau=(\tau_1,...,\tau_n)$
- Expected payoff：$E(u_i(\tau))=\sum\limits_{w\in\Omega}p(w)u_i(\tau(w))$
- Correlated Nash Equilibrium：$\tau^*$ 是 **Nash** $\iff$
- $\sum\limits_{w\in\Omega}p(w)u_i(\tau^*(w))\ge\sum\limits_{w\in\Omega}p(w)u_i(\tau^*_{-i}(w),\tau_i(w))$
- 把 Correlated Strategy Profile 的第 i 項換掉。
- $\tau_i^*$ 就是 $\tau_{-i}^*$ 的 best reply
- 重要觀察：
- Exptected payoff：任一個 mixed strategy profile $s$，可以對應到 correlated strategy profile $\tau$，使得 $u_i(s)=u_i(\tau)$ 對所有玩家成立。
- 在特定機率分布的特定 $\Omega$ 上。
- 證明：
- $u_i(s)=\sum\limits_{a\in A}(~\prod\limits_{j=1}^{n} s_j(a_j)~)u_i(a)$
- $u_i(\tau)=\sum\limits_{w\in\Omega}p(w)u_i(\tau(w))$
- 設定 $\Omega=A$, $\tau(a)=a$, 和 $p(a)=\prod\limits_{j=1}^{n} s_j(a_j)$
- 想一想之一：
- 如果 $\tau^*$ 的 mapping 滿足對應過去的每一格都是 **pure Nash**，則 $\tau^*$ 本身是 **Correlated Nash Equilibrium**。
- 證明：$u_i(\tau^*)\\=\sum\limits_{w\in\Omega}p(w)u_i(\tau^*(w))\\\ge\sum\limits_{w\in\Omega}p(w)u_i(\tau^*_{-i}(w),\tau_i(w))\\=u_i(\tau^*_{-i},\tau_i)$
- 想一想之二：
- 如果 $\tau^*$ 本身是 **Correlated Nash Equilibrium**，則 $\tau^*$ 對應過去的每一格都是 **pure Nash**。
- 證明：反證法，假設某一格不是 **pure Nash**，第 i 個玩家單方面改變策略會更好，則修改 $\tau_i^*\rightarrow\tau_i$
- $u_i(\tau^*)\\=\sum\limits_{w\in\Omega}p(w)u_i(\tau^*(w))\\<\sum\limits_{w\in\Omega}p(w)u_i(\tau^*_{-i}(w),\tau_i(w))\\=u_i(\tau^*_{-i},\tau_i)~\text{which leads to contradiction.}$
- 正式版：
- Information Partion：$\Omega_i$ 是 $\Omega$ 的一個 partition
- 當 signal 產生，player 只知道是在哪一個 information set，而不知道是確切哪一個 signal。
- Correlated Strategy $\tau_i$：任何一個從 $\Omega_i$ 到 $A_i$ 的 mapping
- Correlated Strategy Profile： $\tau=(\tau_1,...,\tau_n)$
- Expected payoff：$E(u_i(\tau))=\sum\limits_{w\in\Omega}p(w)u_i(\tau(w))$
- Correlated Nash Equilibrium：$\tau^*$ 是 **Nash** $\iff$
- $\sum\limits_{w\in\Omega}p(w)u_i(\tau^*(w))\ge\sum\limits_{w\in\Omega}p(w)u_i(\tau^*_{-i}(w),\tau_i(w))$
- 重要觀察：
- Expected Payoff and Nash Equilibrium：任一個 mixed strategy equilibrium $s$，可以對應到 correlated strategy equilibrium $\tau$，使得 $u_i(s)=u_i(\tau)$ 對所有玩家成立。
- 在特定機率分布的特定 $\Omega$ 上。
- 在特定的 information partion $\pi=(\pi_1,...,\pi_n)$ 上。
- 證明：
- $u_i(s)=\sum\limits_{a\in A}(~\prod\limits_{j=1}^{n} s_j(a_j)~)u_i(a)$
- $u_i(\tau)=\sum\limits_{w\in\Omega}p(w)u_i(\tau(w))$
- 設定 $\Omega=A$, 和 $p(a)=\prod\limits_{j=1}^{n} s_j(a_j)$
- 設定 $\Omega_i$ 把 $\Omega=A$ 拆成 $|A_i|$ 個 information set，第 $j$ 個 inforation set 包含所有 action profile 滿足第 $i$ 個元素是 $A_i$ 的第 $j$ 個 action
- 設定 $\tau_i$ 把第 $j$ 個 inforation set 對應到 $A_i$ 的第 $j$ 個 action
- 舉例來說 Chicken
- 
- Mixed Nash Equilibrium
- $(0,1)\Rightarrow payoff=(7,2)$
- $(1,0)\Rightarrow payoff=(2,7)$
- $(\frac{2}{3},\frac{2}{3})\Rightarrow payoff=(\frac{14}{3},\frac{14}{3})$
- 簡化版的 Correlated Nash Equilibrium
- **pure Nash** 的某種凸組合
- 正式版的 Correlated Nash Equilibrium
- $\Omega_1=\{\{紅燈\},~\{黃燈,綠燈\}\}$
- $\Omega_2=\{\{紅燈,黃燈\},~\{綠燈\}\}$
- $\Rightarrow payoff=(5,5)$
- 紅兔：$紅燈\Rightarrow直衝$，$非紅燈\Rightarrow煞車$
- 綠兔：$綠燈\Rightarrow直衝$，$非綠燈\Rightarrow煞車$
- 
## Extensive Game (擴展)樹狀結構賽局
- **Extensive Game**
- $P_0$ 是 nature，只會隨機選擇。
- $n$ 個玩家的 extensive game $\Gamma=(X,E,P,W,C,p,U)$
- $X$：遊戲樹的點
- $E$：遊戲樹的邊
- $P$：把所有 internal node 拆成 $P=(P_0,P_1,...,P_n)$
- $W$：把所有 $P_i$ 拆分成 $W_i$
- $C$：$C_w$ 表示在 information set $w$ 時的所有可能選擇。
- $p$：$P_0$ 決定上的機率分布
- $U$：每個玩家對每個 leaf node 的效用函數
- **Perfect Information**：每一個 information set 都只有一個 node
- **Perfect Recall**：每個玩家在做決定時，完全記得**自己先前 inforamtion set** 所做的決定
- 有 perfect information → 有 perfect recall ，反之未必
## Extensive Strategy 擴展策略
- **Strategies**
- Pure Strategy $a_i\in A_i$
- 為每一個 information set $w\in W_i$ 選一個 choice $a_i(w)\in C_w$
- Behavior Strategy $b_i\in B_i$
- 為每一個 information set $w\in W_i$ 選一個 $C_w$ 的機率分布
- Mixed Strategy $s_i\in S_i$
- $A_i$ 上的一個機率分布
- Expected payoff
- $q\in Q=Q_1\times...\times Q_n$ 其中 $Q_i=A_i\cup S_i\cup B_i$
- $u_i(q)=\sum\limits_{z\in Z}p(z,q)U_i(z)$
- 每一個 Extensive Game $\Gamma$ 都有對應的 Strategy Game $G_\Gamma=(A,u)$
- $A$ 是 $\Gamma$ 所有的 pure strategy profile
- $u$ 是每一個 pure strategy profile 所對應的 leaf node 分數
- **Equivalence of Strategies**
- 廣義來說 (沒有 perfect recall)：
- $A\subseteq B$：每一個 information set 的機率分布都唯一指定 choice
- $A\subseteq S$：$S$ 是 $A$ 上的機率分布
- $B\not\subseteq S$：可構造反例
- $S\not\subseteq B$：可構造反例
- 在 perfect recall 時，探討 $b_i$ 和 $s_i$ 對應關係：
- **高標等價：pure strategy equivalence**
- 定義：對所有 pure strategy $a_i$，都有 $s_i(a_i)=b_i(a_i)=\prod\limits_{w\in W_i}b_i(a_i(w))$
- $B\subsetneq S$：只要不經過同一個 information set 兩次
- **中標等價：realization equivalence**
- 定義：對所有 mixed strategy profile $s_{-i}$，及所有節點 $x$，都有 $p(x,(s_{-i},s_i))=p(x,(s_{-i},b_i))$
- **低標等價：payoff equivalence**
- 定義：對所有 mixed strategy profile $s_{-i}$，都有 $u_i(s_{-i},s_i)=u_i(s_{-i},b_i)$
- 在 perfect recall 時，給定 mixed strategy $s_i$ 及 behavior strategy $b_i$：
- 兩策略高標等價 → 中標等價
- 兩策略中標等價 → 低標等價
- 高標： 中低標：
- **Kuhn Theorem 庫恩定理**
- 定理：在 perfect recall 時，每一個 mixed strategy $s_i$ 都有對應 behavior strategy $b_i$，使得中(低)標等價。
- 以下說明給定 $s_i$，則任意點在同一 information set $中的機率分布一定相同。
- 一些定義與條件機率：
- $A_i(x)\subseteq A_i$ 是第 $i$ 個玩家可以走到節點 $x$ 的 pure strategy 集合
- $s_i(a_i|_x)$：給定 mixed strategy $s_i$，在節點 $x$ 被走到的情況下，$a_i$ 被 $s_i$ 選出的條件機率。
- $p(c,x,s_i)=\sum\limits_{a_i\in A_i(x')}s_i(a_i|_x)$：給定 mixed strategy $s_i$，在節點 $x$ 被走到的情況下，$c$ (通往節點 $x'$) 被選出的條件機率。
- 關鍵步驟：
- 觀察：如果第 $i$ 個玩家從 $root$ 到兩節點 $x,y$ 所經過的選擇都相同，則 $s_i(a_i|_x)=s_i(a_i|_y)$
- 推論：如果賽局是 **perfect recall**，且 $x,y$ 在相同的 information set 中，則 $s_i(a_i|_x)=s_i(a_i|_y)$。
- 引理：如果賽局是 **perfect recall**，且 $x,y$ 在相同的 information set 中，則 $p(c,x,s_i)=p(c,y,s_i)$。
- 證明：
- 1.設定 $b_i(c)=p(c,x,s_i)$
- 2.證明相等：$p(x,(s_{-i},s_i))=p(x,(s_{-i},b_i))$
## Extensive Nash 擴展均衡
- **Pure Nash**：$a^*$
- 定義：$u_i(a^*)\ge u_i(a^*_{-i},a_i)$
- **Mixed Nash**：$s^*$
- 定義：$u_i(s^*)\ge u_i(s^*_{-i},s_i)$
- **Behavior Nash**：$b^*$
- 定義：$u_i(b^*)\ge u_i(b^*_{-i},b_i)$
- 觀察一：
- 如果賽局 $\Gamma$ 是 perfect recall，且 $a^*$ 是一個 pure strategy。則：
- $a^*$ 是 pure Nash $\iff$ $a^*$ 是 mixed Nash $\iff$ $a^*$ 是 behavior Nash
- 證明：Mixed → Behavior → Pure → Mixed
- 觀察二：
- 如果賽局 $\Gamma$ 是 perfect recall，則至少有一個 Mixed Nash $s^*$ 和 Behavior Nash $b^*$
- Nash Theorem 保證有 Mixed Nash $s^*$
- Kuhn Theorem 保證有 Behavior Nash $b^*$
## Subgame Perfect Nash 子賽局完美均衡
- 定義：若 $\Gamma$ 是一個 extensive game
- **Subgame Perfect Nash**：$b^*$
- 每一個可以 decompose 的點 $x$ ， $b^*_x$ 都是 $\Gamma_x$ 的 Behavior Nash。
- **Decomposed** at $x$ ：每一個 information set 包含的點，全在 $\Gamma_x$ 裡/外
- $\Gamma_x$：從 $x$ 開始玩的 subgame
- $a_x$：從 $x$ 開始玩的 sub strategy profile
- $\Gamma_{-x}(a_x)$：把 $\Gamma_x$ 根據 $a_x$ (開始玩的 payoff)縮成一個點的 subgame
- 定理一：如果賽局 $\Gamma$ 是 perfect information，則 $\Gamma$ 至少有一個 **Pure Subgame Perfect Nash $a^*$**
ㄑ- 數學歸納法
- 定理二：如果賽局 $\Gamma$ 是 perfect information，則
- $b$ 是一個 Subgame Perfect Nash $\iff$ 沒有 profitable 的 one-shot deviation
- 定理三：如果賽局 $\Gamma$ 是 perfect recall，則 $\Gamma$ 至少有一個 **Subgame Perfect Nash $b^*$**
## Sequential Nash 序貫均衡
- 定義：若 $\Gamma$ 是一個 extensive game
- **Assessment** $(b,\mu)$：
- $b$ 是 behavior strategy profile
- $\mu$ 是 system of belief
- **Belief**：每一個 information set 上各有一個機率分布
- **Sequential Nash** $(b,\mu)$：
- $(b,\mu)$ 是 Sequential Rational
- $(b,\mu)$ 是 Consistency
- **Sequential Rational**：根據 belief，對每一個 information set 開始玩 subgame 加權，任何玩家都是局部最好的
- **Consistency**：
- 對每一個 information set $w$，$b$ 和 $\mu$ 到達 $w$ 的機率分布相同
- 存在 completed mixed 策略序列 $\{b^n\}_{n\in N}$ 使得，$\lim\limits_{n\rightarrow \infty}(b^n,\mu^{b^n})=(b,\mu)$
- **Complete Mixed**：每一個 information set 的每一個 choice 都有正機率
- 觀察一：如果 $(b,\mu)$ 是 **Sequential Nash**，則 $b$ 是 **Subgame Perfect Nash**
- 觀察二：如果賽局 $\Gamma$ 是 perfect information，$\mu$ 分配機率 1 給所有點。則 $b$ 是 **Subgame Perfect Nash** $\iff$ $(b,\mu)$ 是 **Sequential Nash**
- 定理三：如果賽局 $\Gamma$ 是 perfect recall，則 $\Gamma$ 至少有一個 **Sequential Nash $b^*$**
- 無厘頭
- Backward induction：可以被 Sequential Nash 排除
- Forward induction：超出本書討論範圍
## Bayesian game 貝式賽局
- 完備資訊
- Perfect Information：對於賽局的開始到現在，完全了解所有玩家決定
- Complete Information：完全了解賽局的設定
- 跨年賽局：
- 簡化版：
- n 個玩家的 Bayesian Game 是一個 4-tuple $BG=(\theta,\rho,A,u)$
- $\theta=(\theta_1,...,\theta_n)$：表示每個玩家的可能表現型
- Common Prior $\rho$ 是 $\theta$ 上的機率分布
- $A=A_1\times...\times A_n$
- $u=(u_1,...,u_n)$ 把 $\theta\times A$ 對應到 $R$
- 策略：
- Pure Strategy $\hat{a_i}\in \hat{A_i}$：從 $\theta_i$ 到 $A_i$ 的對應關係
- Mixed Strategy $s_i\in S_i$：$\hat{A_i}$ 上的機率分布
- Behavior Strategy $b_i\in B_i$：從 $\theta_i$ 到 $\Delta A_i$ 的對應關係
- Payoff：$\hat{u_i}(\theta_i,\hat{a})=\sum\limits_{\theta_{-i}}\rho(\theta_{-i}|\theta_i)u_i(\theta,\hat{a}(\theta))$
- Nash Equilibrium：
- $\hat{u_i}(\theta_i,\hat{a})\ge\hat{u_i}(\theta_i,\hat{a}_{-\theta_i},a_i)$：第 i 個玩家的型態 $\theta_i$ 單方面變動 action
- 正式版：
- n 個玩家的 Bayesian Game 是一個 6-tuple $BG=(\Omega,\theta,f,\rho,A,u)$
- $\Omega$：表示世界上可能的 states
- $\theta=(\theta_1,...,\theta_n)$：表示每個玩家的可能的 signal
- Signal Function $f$：$\Omega$ 到 $\theta_i$ 的對應關係
- Belief System $\rho=(\rho_1,...,\rho_n)$ ：表示每個玩家對於 $\Omega$ 上有的機率分布
- $A=A_1\times...\times A_n$
- $u=(u_1,...,u_n)$ 把 $\Omega\times A$ 對應到 $R$
- 策略：
- Pure Strategy $\hat{a_i}\in \hat{A_i}$：從 $\theta_i$ 到 $A_i$ 的對應關係
- Mixed Strategy $s_i\in S_i$：$\hat{A_i}$ 上的機率分布
- Behavior Strategy $b_i\in B_i$：從 $\theta_i$ 到 $\Delta A_i$ 的對應關係
- Payoff：$\hat{u_i}(\theta_i,\hat{a})=\sum\limits_{\omega}\rho(\omega|\theta_i)u_i(\omega,\hat{a}(f(\omega)))$
- Nash Equilibrium：
- $\hat{u_i}(\theta_i,\hat{a})\ge\hat{u_i}(\theta_i,\hat{a}_{-\theta_i},a_i)$：第 i 個玩家的型態 $\theta_i$ 單方面變動 action
Sign in with Wallet
Connect another wallet