跳转到内容

莱姆克-豪森算法

维基百科,自由的百科全书

莱姆克-豪森算法(英语:Lemke–Howson algorithm[1]是一种计算双矩阵博弈的纳什均衡的算法,以其提出者卡尔顿·E·莱姆克和J.T.豪森的名字命名。据说它是“寻找纳什均衡的组合算法中最著名的算法”。[2]

说明

[编辑]

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

G有两个相应的多胞形(称为最佳回应多胞形),分别为m维和n维,定义如下:

在集合中,其坐标用{,...,}表示。并且的范围是被(其中)这个不等式以及(其中)这个不等式所规定的。
在集合中,其坐标用{,...,}表示。并且的范围是被(其中)这个不等式以及(其中)这个不等式所规定的。

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

的每个顶点都与集合中的一组标签相关联。对于,如果在顶点处存在,顶点就会得到标签。对于,当时,顶点就会得到标签。假设是非退化的,每个顶点都关联到个刻面,并且有个标签。在这里需要注意的是,原点也是的一个顶点,它所拥有的标签集合是

同理,的每个顶点都与集合中的一组标签相关联。对于,如果在顶点处存在,顶点就会得到标签。对于,当时,顶点就会得到标签。假设是非退化的,每个顶点都关联到个刻面,并且有个标签。在这里需要注意的是,原点也是的一个顶点,它所拥有的标签集合

对于顶点对,其中,如果满足的并集包含集合中所有的标签,那么我们可以定义这样一个顶点对是完全标记的。如果分别为的原点,那么顶点对是完全标记的。如果与包含了集合中除之外的所有标签,我们就定义顶点对几乎完全标记,在这种情况下中存在一个标签。

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

算法从由两个原点组成的完全标记对开始。

特点

[编辑]

该算法最多能找到个不同的纳什均衡,最初放弃标签的任何选择决定了最终由算法找到的均衡。

参考文献

[编辑]
  1. ^ C. E. Lemke and J. T. Howson. Equilibrium points of bimatrix games. SIAM Journal on Applied Mathematics. 1964, 12 (2): 413–423. doi:10.1137/0112033. 
  2. ^ Nisan, Noam; Roughgarden, Tim; Tardos, Éva; Vazirani, Vijay V. Algorithmic Game Theory (PDF). Cambridge, UK: Cambridge University Press. 2007: 33. ISBN 978-0-521-87282-9. (原始内容 (PDF)存档于2015-02-11).