莱姆克-豪森算法

莱姆克-豪森算法（英語：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_{i,1}x_{m+1}+\cdots +A_{i,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\}$，如果在顶点$w$处存在$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$个不同的纳什均衡，最初放弃标签的任何选择决定了最终由算法找到的均衡。