莱姆克-豪森算法

Template:Translating 莱姆克-豪森算法（Template:Lang-en）是一种计算双矩阵博弈的纳什均衡的算法，以其提出者卡尔顿·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\ge 0$（其中$i\in \{1\cdots m\}$）这$m$个不等式以及$B_{1,j}{x}_1+\cdots +B_{m,j}{x}_m\le 1$（其中$j\in \{1\cdots n\}$）这$n$个不等式所规定的。

$P_2$在集合$R^n$中，其坐标用{$x_{m+1}$,...,$x_{m+n}$}表示。并且$P_2$的范围是被$x_{m+i}\ge 0$（其中$i\in \{1\cdots n\}$）这$n$个不等式以及$A_{i,1}{x}_{m+1}+\cdots +A_{i,n}{x}_{m+n}\le 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$个不同的纳什均衡，最初放弃标签的任何选择决定了最终由算法找到的均衡。