Processing math: 0%
跳到主要內容

Nash Equilibrium & Best Responce Function (BRF) In Continuous Strategies

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

關於例子可以參考網頁 : 按這

[以上純為學術經驗交流知識分享,如有錯誤或建議可留言~~] 
by Plus & Minus 2017.08

留言

這個網誌中的熱門文章

Linear Regression By Using Linear Programming

當拿到一筆資料準備玩統計,往往會想要做線性迴歸( Linear Regression ),找出一個模型( mathematical model )來解釋變數間的關係,一般都是使用平方距離,但是如果我們採用絕對值距離呢?? 而剛好在工業工程( Industrial Engineering ),作業研究( Operation Research ) 領域,發展成熟的線性規劃( Linear Programming ) 恰好可以來解決,是一個跨領域的應用 !! 已經存在有許多商業或open source 軟體,如: Gurobi , Cplex , Xpress , Mosek , SCIP  可以輕易求解大型的線性規劃問題。而不僅如此也可以利用整數規劃( Integer Programming )來做特徵選擇 ( Feature Selection ),甚至可以偵測離群值( Detect Outlier ) !! 本文只介紹最小絕對值和,關於 Feature Selection , Detect Outlier 可以參考 Mixed-Integer Linear Programming Robust Regression with Feature Selection , Oleksii Omelchenko , 2010 的論文。 [Data Fitting Problem] 給定n筆實數型訓練資料 (training data) \{(x^{k},y^{k})\}^{n}_{k=1} = \mathcal{D} , x^{k} =(x^{k}_1,x^{k}_2, ... , x^{k}_{p})\in \mathbb{R}^{p} , y^{k} \in \mathbb{R} , 我們目標是想要找到一個函數 f_{\mathcal{D}} : \mathbb{R}^p \rightarrow \mathbb{R} 使得  \forall x \in \mathbb{R}^{p} , f_{\mathcal{D}}(x) \approx y , 精確來說: $$ \text{Find } f_{\mathcal{D}} \text{ such that } f_{\mathcal{D}}(x)\...

Chain Rule & Identity Function Trick

本文為筆者學習微積分,函數概念與Chain Rule 的時候,遇到的一些概念大坑。本文一一澄清一些個人看法,並分享 Chain Rule 廣義的樣子,以及對於遞迴系統該如何計算...等等看法。 [坑1 : 變數/值符號的認識] 一切從 y = f(x) 開始,我們習慣把 Input 變數用"括號"刮起來,Output y 代表值,f 代表函數。或是可以想成這樣:    x \overset{f}{\longrightarrow} y 這種表示法概念上很嚴謹,但缺點是你必須要用三個符號 xyf 而在微分方程領域出現這種寫法 y = y(x)  (把 f 換成 y) ,這種寫法就頗簡潔,Chain Rule 通常都是這類表示法。缺點是心裡要能確實明白在哪個場合 y 到底是給定的"值"還是"函數"(註: 通常大多代表函數 y,值的話通常會這樣寫 y(x_{0}),y_{0}) ============================================================== [Bonus] y=y(x)這種表示法還有一個好處,如果允許 f 是一對多,那麼 y(x) 就是 y \text{ is depend on } x 的意思,如果你喜歡用集合論來表示可以先定義f 的定義域/對應域 f : X \rightarrow Y 然後 y(x) 可以寫成這樣 y \in Y_{x},其中值域為 f(X):=\bigcup_{x \in X}Y_{x} \subseteq Y ============================================================== [坑2 : Input 的變數到底是哪些] 這邊舉兩個例子提醒: (Ex1) 代換法會重新改變函數的 Input 例如 : y = f(x) = x+1 , z = g(y) = 2y  可以代換一下,寫成 z = g[f(x)] = 2(x+1) 如果你用簡記你會發現 $y(x) , z(y) , z(y(x)) \equiv z...