線性規劃中的互補樞軸理論與Lemeke-Howson算法——Nash，PPAD與PSPACE的又一塊拼圖

接下來，我們讀一篇如何求解NE的文章，并考慮以文中的算法為模型建構PPAD。

Complementary Pivot Theory of Mathematical Programming

線性規劃和雙人非零和博弈意味着我們需要考慮以下的基本問題：

給定一個p維向量q和一個p*p實矩陣M，尋找向量w,z滿足條件：

w = q + M z , w ⩾ 0 , z ⩾ 0 z T w = 0 \begin{aligned} w &=q+M z, \quad w \geqslant 0, \quad z \geqslant 0 \\ z^T w &=0 \end{aligned} wzTw​=q+Mz,w⩾0,z⩾0=0​

接下來我們解釋為什麼要解決這個基本問題：

首先我們證明von-Neumann的經典規劃問題可以轉化為基本問題：

原始（primal）線性規劃：找一個向量x滿足下列條件并且使得 z ˉ \bar{z} zˉ最小：

A x ⩾ b , x ⩾ 0 , z ˉ = c T x A x \geqslant b, \quad x \geqslant 0, \quad \bar{z}=c^Tx Ax⩾b,x⩾0,zˉ=cTx

對偶（dual）線性規劃：找一個向量y滿足下列條件并使得 z ‾ \underline{z} z​最大：

y T A ⩽ c , y ⩾ 0 , z ‾ = y T b y^T A \leqslant c, \quad y \geqslant 0, \quad \underline{z}=y^Tb yTA⩽c,y⩾0,z​=yTb

線性規劃的對偶定理指出：當我們有上述兩個系統時， min ⁡ z ˉ = max ⁡ z ‾ \min \bar{z}=\max \underline{z} minzˉ=maxz​.由于 z ‾ = y T b ⩽ y T A x ⩽ c T x = z ˉ \underline{z}=y^T b \leqslant y^T A x \leqslant c^T x=\bar{z} z​=yTb⩽yTAx⩽cTx=zˉ，在取等時，我們應該有： y T b = c T x y^Tb=c^Tx yTb=cTx

我們注意到，以上不等式可以通過引入變量轉化為一個比較規則的形式：

A x − v = b , v ⩾ 0 , x ⩾ 0 A T y + u = c , u ⩾ 0 , y ⩾ 0 \begin{array}{ll} A x-v=b, & v \geqslant 0, \quad x \geqslant 0 \\ A^{T} y+u=c, & u \geqslant 0, \quad y \geqslant 0 \end{array} Ax−v=b,ATy+u=c,​v⩾0,x⩾0u⩾0,y⩾0​

再做一步形式變換：

( u v ) − ( c − b ) + ( 0 − A T A 0 ) ( x y ) , u ⩾ 0 , v ⩾ 0 x ⩾ 0 , y ⩾ 0 \left(\begin{array}{l} u \\ v \end{array}\right)-\left(\begin{array}{c} c \\ -b \end{array}\right)+\left(\begin{array}{cc} 0 & -A^{T} \\ A & 0 \end{array}\right)\left(\begin{array}{l} x \\ y \end{array}\right), \quad \begin{aligned} &u \geqslant 0, \quad v \geqslant 0 \\ &x \geqslant 0, \quad y \geqslant 0 \end{aligned} (uv​)−(c−b​)+(0A​−AT0​)(xy​),​u⩾0,v⩾0x⩾0,y⩾0​

并且， x T u + y T v = x T ( c − A T y ) + y T ( A x − b ) = x T c − y T b x^T u+y^T v=x^T(c-A^Ty)+y^T(Ax-b)=x^Tc-y^Tb xTu+yTv=xT(c−ATy)+yT(Ax−b)=xTc−yTb，根據上面的取等條件，要求其等于0.

同時，如果我們令

w = ( u v ) , q = ( c − b ) , M = ( 0 − A T A 0 ) , z = ( x y ) w=\left(\begin{array}{l} u \\ v \end{array}\right), \quad q=\left(\begin{array}{c} c \\ -b \end{array}\right), \quad M=\left(\begin{array}{cc} 0 & -A^{T} \\ A & 0 \end{array}\right), \quad z=\left(\begin{array}{l} x \\ y \end{array}\right) w=(uv​),q=(c−b​),M=(0A​−AT0​),z=(xy​)

則問題轉化為基本問題的形式：

w = q + M z , w ⩾ 0 , z ⩾ 0 z T w = 0 \begin{aligned} w &=q+M z, \quad w \geqslant 0, \quad z \geqslant 0 \\ z^T w &=0 \end{aligned} wzTw​=q+Mz,w⩾0,z⩾0=0​

然後，我們證明兩人非零和博弈的均衡求解也可以轉化為基本問題。

考慮一個雙人博弈 Γ ( A , B ) \Gamma(A,B) Γ(A,B)，其中A,B為行,列玩家的支付矩陣，大小為m*n，兩個玩家的混合政策為行向量x,y，并且：

x = ( x 1 , … , x m ) ⩾ 0 , ∑ i = 1 m x i = 1 , y = ( y 1 , … , y n ) ⩾ 0 , ∑ j = 1 n y j = 1 \begin{array}{ll} x=\left(x_{1}, \ldots, x_{m}\right) \geqslant 0, & \sum_{i=1}^{m} x_{i}=1, \\ y=\left(y_{1}, \ldots, y_{n}\right) \geqslant 0, & \sum_{j=1}^{n} y_{j}=1 \end{array} x=(x1​,…,xm​)⩾0,y=(y1​,…,yn​)⩾0,​∑i=1m​xi​=1,∑j=1n​yj​=1​

根據Nash的結論，一個對 ( x 0 , y 0 ) (x^0,y^0) (x0,y0)是一個納什均衡點當且僅當下式成立：

x 0 A y 0 T ⩽ x A y 0 T , all mixed strategies  x , x 0 B y 0 T ⩽ x 0 B y T , all mixed strategies  y . {x^{0}} A {y^{0}}^T \leqslant x A {y^{0}}^T , \quad\text{all mixed strategies $x$},\\ x^{0} B {y^{0}}^T \leqslant x^{0} B y^T , \quad\text{all mixed strategies $y$}. x0Ay0T⩽xAy0T,all mixed strategies x,x0By0T⩽x0ByT,all mixed strategies y.

由于我們對A和B同時加一個常數，Nash均衡不變（平移不變性），是以我們可以不妨設A,B>0，并且如果令 e k e_k ek​表示第k個元素值全為1的向量，那麼在兩邊同時乘一個機關向量：

( x 0 A y 0 T ) e m ⩽ A y 0 ( A > 0 ) ( x 0 B y 0 T ) e n ⩽ B T x 0 ( B > 0 ) \begin{array}{ll} \left(x^{0} A {y^{0}}^T \right) e_{m} \leqslant A y^{0} & (A>0) \\ \left(x^{0} B {y^{0}}^T \right) e_{n} \leqslant B^{T} x^{0} & (B>0) \end{array} (x0Ay0T)em​⩽Ay0(x0By0T)en​⩽BTx0​(A>0)(B>0)​

考慮以下的形式轉化：

u = A y − e m , u ⩾ 0 , y ⩾ 0 v = B T x − e n , v ⩾ 0 , x ⩾ 0 x u + y v = 0 \begin{gathered} u=A y-e_{m}, \quad u \geqslant 0, \quad y \geqslant 0 \\ v=B^{T} x-e_{n}, \quad v \geqslant 0, \quad x \geqslant 0 \\ x u+y v=0 \end{gathered} u=Ay−em​,u⩾0,y⩾0v=BTx−en​,v⩾0,x⩾0xu+yv=0​

那麼，這個方程組的解如果記做 u ∗ , v ∗ , x ∗ , y ∗ u^{*}, v^{*}, x^{*}, y^{*} u∗,v∗,x∗,y∗，則 ( x 0 , y 0 ) = ( x ∗ x ∗ e m , y ∗ y ∗ e n ) \left(x^{0}, y^{0}\right)=\left(\frac{x^{*}}{x^{*} e_{m}}, \frac{y^{*}}{y^{*} e_{n}}\right) (x0,y0)=(x∗em​x∗​,y∗en​y∗​)即為所求的解，且如果 x 0 , y 0 x^0,y^0 x0,y0為Nash的解，則 ( x ∗ , y ∗ ) = ( x 0 x 0 B y 0 , y 0 x 0 A y 0 ) \left(x^{*}, y^{*}\right)=\left(\frac{x^{0}}{x^{0} B y^{0}}, \frac{y^{0}}{x^{0} A y^{0}}\right) (x∗,y∗)=(x0By0x0​,x0Ay0y0​)為方程的解，由此可知方程的解等價于Nash的解。

本質：巧妙地把x和 x ∗ x^* x∗中分量和為1的性質寫入了方程内部。

而後面這個系統在代換：

w = ( u v ) , q = ( − e m − e n ) , M = ( 0 A B T 0 ) , z = ( x y ) w=\left(\begin{array}{l} u \\ v \end{array}\right), \quad q=\left(\begin{array}{c} -e_{m} \\ -e_{n} \end{array}\right), \quad M=\left(\begin{array}{cc} 0 & A \\ B^{T} & 0 \end{array}\right), \quad z=\left(\begin{array}{l} x \\ y \end{array}\right) w=(uv​),q=(−em​−en​​),M=(0BT​A0​),z=(xy​)

下恰好也有基本形式：

w = q + M z , w ⩾ 0 , z ⩾ 0 z T w = 0 \begin{aligned} w &=q+M z, \quad w \geqslant 0, \quad z \geqslant 0 \\ z^T w &=0 \end{aligned} wzTw​=q+Mz,w⩾0,z⩾0=0​

對于基本問題的疊代求解

考慮基本問題這個線性方程組的形式：

w = q + M z , w ⋅ z = 0 , w , z ≥ 0 w=q+Mz, w\cdot z=0,w,z\geq 0 w=q+Mz,w⋅z=0,w,z≥0

其中，p維向量q和p*p階矩陣M是任意的，但是一旦標明後就固定了，我們要求解z和w。

我們稱對應的分量wi,zi互補，那麼由于 w i , z i ≥ 0 w_i,z_i\geq 0 wi​,zi​≥0，我們必須有： w i z i = 0 w_iz_i=0 wi​zi​=0

然後，我們定義一個解是幾乎互補的，如果它在某一個分量之外的所有分量上滿足： w i z i = 0 w_iz_i=0 wi​zi​=0

我們的思路是找到一個恰當的幾乎互補路徑：在這個路徑上，每個節點都是一個幾乎互補的解，并且說明它一定會在某個互補的解上終止，這樣我們就能用疊代的方法找到一個終止解。

在一般的問題中，找到一個初始解并不是那麼容易，但是在Nash中，有一個特殊的性質：M>0，我們将會看到這個性質在給定初值中有什麼樣的作用。

在這條路徑上的疊代過程可以如下表示：在幾乎互補解P_i中，第 β \beta β個分量是不互補的（乘積不為0），則其它都是互補的。我們可以證明，通過改變 z β z_\beta zβ​或者 w β w_\beta wβ​，可以得到P_i的兩個鄰點，分别對應P_i-1和P_i+1，具體操作：注意到，當我們改變 z β z_\beta zβ​時，w也會産生正相關的變化。如果我們恰當地減少 z β z_\beta zβ​直到有一個 w s w_s ws​=0的情形，那麼我們就得到了一個新的互補對。矩陣M的非退化假設保證了隻會出現一個這樣的s。

這條路有下列性質：

1. 内部無環：這條路隻能是一個環，而不能在内部産生環，因為如果内部有環的話就會出現一個三度點，沖突！
2. 如果開始點取度數為1，那麼道路隻能一直向前延伸，直到遇到度數為1的另一個點。

很顯然，這個做法恰好對應了我們在求解Nash中的PPAD方法，隻不過Lemeke算法本身是PSPACE的，因為它沿着一條路走到黑。