Efficient Computation of Equilibria for Extensive Two-Person Games
Efficient Computation of Equilibria for Extensive Two-Person Games
复制标题
DOI：
10.1006/game.1996.0051
复制
发表时间：
1996-06
影响因子：
1.1
通讯作者：
D. Koller;N. Megiddo;B. Stengel
中科院分区：
文献类型：
--
作者：
D. Koller;N. Megiddo;B. Stengel
摘要二人非零和对策的纳什均衡是一类线性互补问题的解。为了使用这个方法来解决一个扩展形式的博弈，这个博弈必须首先转换成一个策略描述，比如标准形式。然而，经典的范式在博弈树的大小上通常是指数级的。如果博弈具有完美回忆，则线性大小的策略描述是序列形式。对于由此产生的小LCP，我们表明，平衡有效地找到Lemke的算法，推广的Lemke-Howson方法。经济文献分类号：C72。
Abstract The Nash equilibria of a two-person, non-zero-sum game are the solutions of a certain linear complementarity problem (LCP). In order to use this for solving a game in extensive form, the game must first be converted to a strategic description such as the normal form. The classical normal form, however, is often exponentially large in the size of the game tree. If the game has perfect recall, a linear-sized strategic description is the sequence form. For the resulting small LCP, we show that an equilibrium is found efficiently by Lemke's algorithm, a generalization of the Lemke–Howson method. Journal of Economic Literature Classification Number: C72.