---
# System prepended metadata

title: 課程｜賽局理論
tags: [課程]

---

# 賽局理論
## 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**
        - ![](https://i.imgur.com/O4lYVpr.png)
        - $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\}$
        - ![](https://i.imgur.com/VSCmdZ9.png)
            - 有三個 **Nash**
    - **警衛與小偷**
        - ![](https://i.imgur.com/w1YwrSU.png)
        - $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\}$
        - ![](https://i.imgur.com/DBawFwx.png)
## 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
    - ![](https://i.imgur.com/ZReNIdO.png)
- **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** 的凸組合。
    - 例子：
        - ![](https://i.imgur.com/2dlfFCW.png)
        - ![](https://i.imgur.com/eo7thNa.png)
        - ![](https://i.imgur.com/F5It0uR.png)
## 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
    - ![](https://i.imgur.com/sWzZHmn.png)
    - 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煞車$
    - ![](https://i.imgur.com/pzGgZbC.png)
## 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$：
        - 兩策略高標等價 → 中標等價
        - 兩策略中標等價 → 低標等價
- 高標：![](https://i.imgur.com/ywHHvvt.png) 中低標：![](https://i.imgur.com/9MNd5b2.png)
- **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
