Computing a quasi-perfect equilibrium of a two-player game |
| |
Authors: | Peter Bro Miltersen Troels Bjerre Sørensen |
| |
Institution: | (3) Center for Applied Optim., Dept. Industrial and Systems Engin. Univ. Florida, Gainesville, FL 32611, USA |
| |
Abstract: | Refining an algorithm due to Koller, Megiddo and von Stengel, we show how to apply Lemke’s algorithm for solving linear complementarity
programs to compute a quasi-perfect equilibrium in behavior strategies of a given two-player extensive-form game of perfect
recall. A quasi-perfect equilibrium is known to be sequential, and our algorithm thus resolves a conjecture of McKelvey and
McLennan in the positive. A quasi-perfect equilibrium is also known to be normal-form perfect and our algorithm thus provides
an alternative to an algorithm by von Stengel, van den Elzen and Talman. For the case of a zero-sum game, we devise variants
of the algorithm that rely on linear programming rather than linear complementarity programming and use the simplex algorithm
or other algorithms for linear programming rather than Lemke’s algorithm. We argue that these latter algorithms are relevant
for recent applications of equilibrium computation to artificial intelligence. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|