查看“︁莱姆克-豪森算法”︁的源代码

{{Translating|[[:en:Lemke–Howson algorithm]]||tpercent=50|time=2022-01-15T03:48:32+00:00}}
'''莱姆克-豪森算法'''（{{lang-en|Lemke–Howson algorithm}}）<ref>{{cite journal
| author = C. E. Lemke and J. T. Howson
| title = Equilibrium points of bimatrix games
| journal = SIAM Journal on Applied Mathematics
| volume = 12
| issue = 2
| year = 1964
| pages = 413–423
| doi=10.1137/0112033}}</ref>是一种计算双矩阵博弈的[[纳什均衡]]的算法，以其提出者卡尔顿·E·莱姆克和J.T.豪森的名字命名。据说它是“寻找纳什均衡的组合算法中最著名的算法”。<ref>{{cite book
 |last1=Nisan 
 |first1=Noam 
 |author1-link=Noam Nisan 
 |last2=Roughgarden 
 |first2=Tim 
 |last3=Tardos 
 |first3=Éva 
 |author3-link=Éva Tardos 
 |last4=Vazirani 
 |first4=Vijay V. 
 |author4-link=Vijay Vazirani 
 |isbn=978-0-521-87282-9 
 |page=33 
 |location=Cambridge, UK 
 |publisher=Cambridge University Press 
 |title=Algorithmic Game Theory 
 |url=http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf 
 |year=2007 
 |url-status=dead 
 |archiveurl=https://web.archive.org/web/20150211022745/http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf 
 |archivedate=2015-02-11 
}}</ref>
==说明==
该算法需要输入两个参与者的博弈矩阵'''G'''，这些参与者分别有m和n个纯策略。G由两个m × n的博弈矩阵A和B组成，它们分别是参与者1和2在所有决策下的收益。在这一算法中，我们假设所有的收益都是正的。

G有两个相应的[[多胞形]]（称为最佳回应多胞形）<math>P_1</math>和<math>P_2</math>，分别为m维和n维，定义如下:
:<math>P_1</math>在集合<math>R^{m}</math>中，其坐标用{<math>x_1</math>,...,<math>x_m</math>}表示。并且<math>P_1</math>的范围是被<math>x_i\geq 0</math>（其中<math>i \in \{ 1\cdots m \}</math>）这<math>m</math>个不等式以及<math>B_{1,j}x_1+\cdots +B_{m,j}x_m\leq 1</math>（其中<math>j \in \{ 1\cdots n \}</math>）这<math>n</math>个不等式所规定的。
:<math>P_2</math>在集合<math>R^{n}</math>中，其坐标用{<math>x_{m+1}</math>,...,<math>x_{m+n}</math>}表示。并且<math>P_2</math>的范围是被<math>x_{m+i}\geq 0</math>（其中<math>i \in \{ 1\cdots n \}</math>）这<math>n</math>个不等式以及<math>A_{i,1}x_{m+1}+\cdots +A_{i,n}x_{m+n}\leq 1</math>（其中<math>j \in \{ 1\cdots m \}</math>）这<math>m</math>个不等式所规定的。

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

<math>P_1</math>的每个顶点<math>v</math>都与集合<math>j \in \{ 1\cdots m+n \}</math>中的一组标签相关联。对于<math>i \in \{ 1\cdots m\}</math>，如果在顶点<math>w</math>处存在<math>x_i = 0</math>，顶点<math>v</math>就会得到标签<math>i</math>。对于<math>j \in \{ 1\cdots n\}</math>，当<math>B_{1,j}x_1+\cdots +B_{m,j}x_m= 1</math>时，顶点<math>v</math>就会得到标签<math>m + j</math>。假设<math>P_1</math>是非[[退化 (數學)|退化]]的，每个顶点都关联到<math>P_1</math>的<math>m</math>个刻面，并且有<math>m</math>个标签。在这里需要注意的是，原点也是<math>P_1</math>的一个顶点，它所拥有的标签集合是<math>\{ 1\cdots m\}</math>。

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

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

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

算法从由两个原点组成的完全标记对<math>(v,w)</math>开始。

==特点==
该算法最多能找到<math>n + m</math>个不同的纳什均衡，最初放弃标签的任何选择决定了最终由算法找到的均衡。

==参考文献==
{{reflist}}

[[Category:博弈论]]