Efficient Computation of Equilibria for Extensive Two-Person Games

详细信息    查看全文

• 作者：Koller ; Daphne ; Megiddo ; Nimrod ; von Stengel ; Bernhard
• 刊名：Games and Economic Behavior
• 出版年：1996
• 出版时间：June, 1996
• 年：1996
• 卷：14
• 期：2
• 页码：247-259
• 全文大小：133 K

文摘

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 LiteratureClassification Number: C72.