經濟學重要的賽局理論(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
留言
張貼留言