經濟學重要的賽局理論(Game Theory)領域，用數學描述人與人之間的理性互動，最重要的就是尋找奈許均衡(Nash equilibrium)，本篇介紹其數學規劃與非線性方程組!!
假設有 $p$ 名玩家(player $i$)，$i=1,2,3,4,5,....p$ ，
正在玩一場遊戲(Game)~~，完全不合作，各自獨立作決策
每個人有決策向量 $x_i \in \Omega_i \subseteq R^{n_i}$ (有$n_i$個決策變數)
定義長向量: $\underbrace{x = (x_1,x_2,x_3,....x_p)}_{\# \text{ of } \sum^{p}_{i=1}n_i \text{ variables }} \in \prod^{p}_{i=1} \Omega_i = \Omega $
對於每個 player $i$ ，長向量可以寫成 $x = (x_i , x_{-i})$ ，$x_{-i}$ 代表其他人(不是 player $i$) 能做的決策向量。
所有人各自作決策後，每個人都會個自的存在報酬效用函數 $f_i (x) \in \mathbb{R} $ (報酬函數皆為公開已知資訊)
假設每位玩家是理性人(會極大化自己效用)
即 $$\forall i = 1,2,3,4....p \qquad \underset{x_i \in \Omega_i}{\text{max }}f_i(x) $$
[註: 如果為合作可視為多目標規劃問題(multiobjective)，即 $x_1,x_2,...x_p$ 可以由領導人一起決定]
[註: 如果為合作而且把效用加總，即目標式變成 $\sum_{i=1}^{p} f_i(x)$ ，可能對集體效益有更大的幫助，但是如何分配效益給 ( player $i$ )會是個議題，可以查關鍵字 fair optimization ]
我們可以定義每個 player i 的 Best Response Function (BRF) or Best Reponce Set $S_i(x_{-i}) \subset \Omega_i$
$$ S_i(x_{-i}) := \underset{x_i \in \Omega_i}{\text{argmax }}f_i(x) $$
$$ = \{ x_i \in \Omega_i : f(x_i,x_{-i}) \geq f_i(y,x_{-i}) \forall y \in \Omega_i \} $$
代表當其他人決定 $x_{-i}$ 後，你能做的最好回應的選擇 !!
而奈許均衡(Nash Equilibrium)的定義是:
$(x^{*}_1,x^{*}_2,...,x^{*}_p) \in \Omega \text{ s.t } x^{*}_i \in S_i(x^{*}_{-i}) \forall i =1,2,3,...p$
記做 $(x^{*}_1,x^{*}_2,...,x^{*}_p) \in NE $
因為 global maxima respect to $x_i \Longrightarrow $ 一次微分(Gradient) = 0
$$ S_i(x_{-i}) \subseteq \{ x_i \in \Omega_i: \bigtriangledown_{x_i} f_i(x) = 0 \}$$
我們可以推得$ NE \subseteq \{ x \in \Omega: \bigtriangledown_{x_i} f_i(x) = 0 , \forall i =1,2,3,...p\} $
所以我們要先用演算法求解以下 Nonlinear System 共有 $\sum^{p}_{i=1} n_i$ 個方程式的所有解，再尋找納許均衡 !!
$$\left\{\begin{array}{c}
\bigtriangledown_{x_1} f_1(x) = 0 \\
\bigtriangledown_{x_2} f_2(x) = 0 \\
\bigtriangledown_{x_3} f_3(x) = 0 \\
\bigtriangledown_{x_4} f_4(x) = 0 \\
\bigtriangledown_{x_5} f_5(x) = 0 \\
\bigtriangledown_{x_6} f_6(x) = 0 \\
.... \\
\bigtriangledown_{x_p} f_p(x) = 0 \\
\end{array}\right.$$
$|NE| = 1$ 選擇 NE 是大家"理性"預期的結果 (絕頂聰明)
$|NE| \geq 2$ 則需要找焦點 Focal Point
關於例子可以參考網頁 : 按這
假設有 $p$ 名玩家(player $i$)，$i=1,2,3,4,5,....p$ ，
正在玩一場遊戲(Game)~~，完全不合作，各自獨立作決策
每個人有決策向量 $x_i \in \Omega_i \subseteq R^{n_i}$ (有$n_i$個決策變數)
定義長向量: $\underbrace{x = (x_1,x_2,x_3,....x_p)}_{\# \text{ of } \sum^{p}_{i=1}n_i \text{ variables }} \in \prod^{p}_{i=1} \Omega_i = \Omega $
對於每個 player $i$ ，長向量可以寫成 $x = (x_i , x_{-i})$ ，$x_{-i}$ 代表其他人(不是 player $i$) 能做的決策向量。
所有人各自作決策後，每個人都會個自的存在報酬效用函數 $f_i (x) \in \mathbb{R} $ (報酬函數皆為公開已知資訊)
假設每位玩家是理性人(會極大化自己效用)
即 $$\forall i = 1,2,3,4....p \qquad \underset{x_i \in \Omega_i}{\text{max }}f_i(x) $$
[註: 如果為合作可視為多目標規劃問題(multiobjective)，即 $x_1,x_2,...x_p$ 可以由領導人一起決定]
[註: 如果為合作而且把效用加總，即目標式變成 $\sum_{i=1}^{p} f_i(x)$ ，可能對集體效益有更大的幫助，但是如何分配效益給 ( player $i$ )會是個議題，可以查關鍵字 fair optimization ]
我們可以定義每個 player i 的 Best Response Function (BRF) or Best Reponce Set $S_i(x_{-i}) \subset \Omega_i$
$$ S_i(x_{-i}) := \underset{x_i \in \Omega_i}{\text{argmax }}f_i(x) $$
$$ = \{ x_i \in \Omega_i : f(x_i,x_{-i}) \geq f_i(y,x_{-i}) \forall y \in \Omega_i \} $$
代表當其他人決定 $x_{-i}$ 後，你能做的最好回應的選擇 !!
而奈許均衡(Nash Equilibrium)的定義是:
$(x^{*}_1,x^{*}_2,...,x^{*}_p) \in \Omega \text{ s.t } x^{*}_i \in S_i(x^{*}_{-i}) \forall i =1,2,3,...p$
記做 $(x^{*}_1,x^{*}_2,...,x^{*}_p) \in NE $
因為 global maxima respect to $x_i \Longrightarrow $ 一次微分(Gradient) = 0
$$ S_i(x_{-i}) \subseteq \{ x_i \in \Omega_i: \bigtriangledown_{x_i} f_i(x) = 0 \}$$
我們可以推得$ NE \subseteq \{ x \in \Omega: \bigtriangledown_{x_i} f_i(x) = 0 , \forall i =1,2,3,...p\} $
所以我們要先用演算法求解以下 Nonlinear System 共有 $\sum^{p}_{i=1} n_i$ 個方程式的所有解，再尋找納許均衡 !!
$$\left\{\begin{array}{c}
\bigtriangledown_{x_1} f_1(x) = 0 \\
\bigtriangledown_{x_2} f_2(x) = 0 \\
\bigtriangledown_{x_3} f_3(x) = 0 \\
\bigtriangledown_{x_4} f_4(x) = 0 \\
\bigtriangledown_{x_5} f_5(x) = 0 \\
\bigtriangledown_{x_6} f_6(x) = 0 \\
.... \\
\bigtriangledown_{x_p} f_p(x) = 0 \\
\end{array}\right.$$
$|NE| = 1$ 選擇 NE 是大家"理性"預期的結果 (絕頂聰明)
$|NE| \geq 2$ 則需要找焦點 Focal Point
關於例子可以參考網頁 : 按這
[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~]
by Plus & Minus 2017.08
留言
張貼留言