莱姆克-豪森算法

该算法需要输入两个参与者的博弈矩阵G，这些参与者分别有m和n个纯策略。G由两个m × n的博弈矩阵A和B组成，它们分别是参与者1和2在所有决策下的收益。在这一算法中，我们假设所有的收益都是正的。

G有两个相应的多胞形（称为最佳回应多胞形）${\displaystyle P_{1}}$ 和${\displaystyle P_{2}}$ ，分别为m维和n维，定义如下:

${\displaystyle P_{1}}$ 在集合${\displaystyle R^{m}}$ 中，其坐标用{${\displaystyle x_{1}}$ ,...,${\displaystyle x_{m}}$ }表示。并且${\displaystyle P_{1}}$ 的范围是被${\displaystyle x_{i}\geq 0}$ （其中${\displaystyle i\in \{1\cdots m\}}$ ）这${\displaystyle m}$ 个不等式以及${\displaystyle B_{1,j}x_{1}+\cdots +B_{m,j}x_{m}\leq 1}$ （其中${\displaystyle j\in \{1\cdots n\}}$ ）这${\displaystyle n}$ 个不等式所规定的。

${\displaystyle P_{2}}$ 在集合${\displaystyle R^{n}}$ 中，其坐标用{${\displaystyle x_{m+1}}$ ,...,${\displaystyle x_{m+n}}$ }表示。并且${\displaystyle P_{2}}$ 的范围是被${\displaystyle x_{m+i}\geq 0}$ （其中${\displaystyle i\in \{1\cdots n\}}$ ）这${\displaystyle n}$ 个不等式以及${\displaystyle A_{i,1}x_{m+1}+\cdots +A_{i,n}x_{m+n}\leq 1}$ （其中${\displaystyle j\in \{1\cdots m\}}$ ）这${\displaystyle m}$ 个不等式所规定的。

${\displaystyle P_{1}}$ 表示参与人1的${\displaystyle m}$ 个纯策略的非归一化概率分布集合，即参与人2的期望收益最多为1。前${\displaystyle m}$ 个约束条件要求概率是非负的，其他${\displaystyle n}$ 个约束条件要求参与人2的n个纯策略的期望收益不超过1，${\displaystyle P_{2}}$ 同理。

${\displaystyle P_{1}}$ 的每个顶点${\displaystyle v}$ 都与集合${\displaystyle j\in \{1\cdots m+n\}}$ 中的一组标签相关联。对于${\displaystyle i\in \{1\cdots m\}}$ ，如果在顶点${\displaystyle w}$ 处存在${\displaystyle x_{i}=0}$ ，顶点${\displaystyle v}$ 就会得到标签${\displaystyle i}$ 。对于${\displaystyle j\in \{1\cdots n\}}$ ，当${\displaystyle B_{1,j}x_{1}+\cdots +B_{m,j}x_{m}=1}$ 时，顶点${\displaystyle v}$ 就会得到标签${\displaystyle m+j}$ 。假设${\displaystyle P_{1}}$ 是非退化的，每个顶点都关联到${\displaystyle P_{1}}$ 的${\displaystyle m}$ 个刻面，并且有${\displaystyle m}$ 个标签。在这里需要注意的是，原点也是${\displaystyle P_{1}}$ 的一个顶点，它所拥有的标签集合是${\displaystyle \{1\cdots m\}}$ 。

同理，${\displaystyle P_{2}}$ 的每个顶点${\displaystyle w}$ 都与集合${\displaystyle j\in \{1\cdots m+n\}}$ 中的一组标签相关联。对于${\displaystyle j\in \{1\cdots n\}}$ ，如果在顶点${\displaystyle w}$ 处存在${\displaystyle x_{m+i}=0}$ ，顶点${\displaystyle w}$ 就会得到标签${\displaystyle m+i}$ 。对于${\displaystyle i\in \{1\cdots m\}}$ ，当${\displaystyle A_{i,1}x_{m+1}+\cdots +A_{i,n}x_{m+n}=1}$ 时，顶点${\displaystyle w}$ 就会得到标签${\displaystyle i}$ 。假设${\displaystyle P_{2}}$ 是非退化的，每个顶点都关联到${\displaystyle P_{2}}$ 的${\displaystyle n}$ 个刻面，并且有${\displaystyle n}$ 个标签。在这里需要注意的是，原点也是${\displaystyle P_{2}}$ 的一个顶点，它所拥有的标签集合${\displaystyle \{m+1\cdots m+n\}}$ 。

对于顶点对${\displaystyle (v,w)}$ ，其中${\displaystyle v\in P_{1}}$ 且${\displaystyle w\in P_{2}}$ ，如果满足${\displaystyle v}$ 与${\displaystyle w}$ 的并集包含集合${\displaystyle \{1\cdots m+n\}}$ 中所有的标签，那么我们可以定义这样一个顶点对是完全标记的。如果${\displaystyle v}$ 与${\displaystyle w}$ 分别为${\displaystyle P_{1}}$ 与${\displaystyle P_{2}}$ 的原点，那么顶点对${\displaystyle (v,w)}$ 是完全标记的。如果与${\displaystyle v\cup w}$ 包含了集合${\displaystyle \{1\cdots m+n\}}$ 中除${\displaystyle g}$ 之外的所有标签，我们就定义顶点对${\displaystyle (v,w)}$ 几乎完全标记，在这种情况下${\displaystyle v\cap w}$ 中存在一个标签。

主元运算如下所示：取某顶点对${\displaystyle (v,w)}$ ，用${\displaystyle P_{1}}$ 中某个与${\displaystyle v}$ 相邻的顶点替换${\displaystyle v}$ ，或者用${\displaystyle P_{2}}$ 中某个与${\displaystyle w}$ 相邻的顶点替换${\displaystyle w}$ 。这步操作的意义是在${\displaystyle v}$ 被替换的情况下用另一个标签替换${\displaystyle v}$ 的某个标签。被替换的标签就会立刻被丢弃。对于${\displaystyle v}$ 的任何标签，都可以通过移动到与${\displaystyle v}$ 相邻且不包含与该标签关联的超平面的顶点来删除该标签。

算法从由两个原点组成的完全标记对${\displaystyle (v,w)}$ 开始。

该算法最多能找到${\displaystyle n+m}$ 个不同的纳什均衡，最初放弃标签的任何选择决定了最终由算法找到的均衡。