萊姆克-豪森算法

萊姆克-豪森算法（英語：Lemke–Howson algorithm）是一種計算雙矩陣博弈的納什均衡的算法，以其提出者卡爾頓·E·萊姆克和J.T.豪森的名字命名。據說它是「尋找納什均衡的組合算法中最著名的算法」。

說明

該算法需要輸入兩個參與者的博弈矩陣G，這些參與者分別有m和n個純策略。G由兩個m × n的博弈矩陣A和B組成，它們分別是參與者1和2在所有決策下的收益。在這一算法中，我們假設所有的收益都是正的。

G有兩個相應的多胞形（稱為最佳回應多胞形）$P_{1}$和$P_{2}$，分別為m維和n維，定義如下:

$P_{1}$在集合$R^{m}$中，其坐標用{$x_{1}$,...,$x_{m}$}表示。並且$P_{1}$的範圍是被$x_{i}\geq 0$（其中$i\in \{1\cdots m\}$）這$m$個不等式以及$B_{1,j}x_{1}+\cdots +B_{m,j}x_{m}\leq 1$（其中$j\in \{1\cdots n\}$）這$n$個不等式所規定的。

$P_{2}$在集合$R^{n}$中，其坐標用{$x_{m+1}$,...,$x_{m+n}$}表示。並且$P_{2}$的範圍是被$x_{m+i}\geq 0$（其中$i\in \{1\cdots n\}$）這$n$個不等式以及$A_{j,1}x_{m+1}+\cdots +A_{j,n}x_{m+n}\leq 1$（其中$j\in \{1\cdots m\}$）這$m$個不等式所規定的。

$P_{1}$表示參與人1的$m$個純策略的非歸一化概率分布集合，即參與人2的期望收益最多為1。前$m$個約束條件要求概率是非負的，其他$n$個約束條件要求參與人2的n個純策略的期望收益不超過1，$P_{2}$同理。

$P_{1}$的每個頂點$v$都與集合$j\in \{1\cdots m+n\}$中的一組標籤相關聯。對於$i\in \{1\cdots m\}$，如果在頂點$v$處存在$x_{i}=0$，頂點$v$就會得到標籤$i$。對於$j\in \{1\cdots n\}$，當$B_{1,j}x_{1}+\cdots +B_{m,j}x_{m}=1$時，頂點$v$就會得到標籤$m+j$。假設$P_{1}$是非退化的，每個頂點都關聯到$P_{1}$的$m$個刻面，並且有$m$個標籤。在這裏需要注意的是，原點也是$P_{1}$的一個頂點，它所擁有的標籤集合是$\{1\cdots m\}$。

同理，$P_{2}$的每個頂點$w$都與集合$j\in \{1\cdots m+n\}$中的一組標籤相關聯。對於$j\in \{1\cdots n\}$，如果在頂點$w$處存在$x_{m+i}=0$，頂點$w$就會得到標籤$m+i$。對於$i\in \{1\cdots m\}$，當$A_{i,1}x_{m+1}+\cdots +A_{i,n}x_{m+n}=1$時，頂點$w$就會得到標籤$i$。假設$P_{2}$是非退化的，每個頂點都關聯到$P_{2}$的$n$個刻面，並且有$n$個標籤。在這裏需要注意的是，原點也是$P_{2}$的一個頂點，它所擁有的標籤集合$\{m+1\cdots m+n\}$。

對於頂點對$(v,w)$，其中$v\in P_{1}$且$w\in P_{2}$，如果滿足$v$與$w$的併集包含集合$\{1\cdots m+n\}$中所有的標籤，那麼我們可以定義這樣一個頂點對是完全標記的。如果$v$與$w$分別為$P_{1}$與$P_{2}$的原點，那麼頂點對$(v,w)$是完全標記的。如果與$v\cup w$包含了集合$\{1\cdots m+n\}$中除$g$之外的所有標籤，我們就定義頂點對$(v,w)$幾乎完全標記，在這種情況下$v\cap w$中存在一個標籤。

主元運算如下所示：取某頂點對$(v,w)$，用$P_{1}$中某個與$v$相鄰的頂點替換$v$，或者用$P_{2}$中某個與$w$相鄰的頂點替換$w$。這步操作的意義是在$v$被替換的情況下用另一個標籤替換$v$的某個標籤。被替換的標籤就會立刻被丟棄。對於$v$的任何標籤，都可以通過移動到與$v$相鄰且不包含與該標籤關聯的超平面的頂點來刪除該標籤。

算法從由兩個原點組成的完全標記對$(v,w)$開始。

特點

該算法最多能找到$n+m$個不同的納什均衡，最初放棄標籤的任何選擇決定了最終由算法找到的均衡。