莱姆克-豪森算法（）是一种计算双矩阵博弈的纳什均衡的算法，以其提出者卡尔顿·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个不同的纳什均衡，最初放弃标签的任何选择决定了最终由算法找到的均衡。
参考文献
评论 (0)