Lemke's algorithm for discounted games

Marcin Jurdzinski

(Warwick University)

The performance of a pivoting algorithm due to Lemke is considered on linear complementarity problems (LCPs) that arise from discounted games. The algorithm has not been previously studied in the context of infinite games, and it offers an alternative to the classical strategy-improvement algorithms. The algorithm is described purely in terms of discounted games, thus bypassing the reduction from the games to LCPs, and hence facilitating a better understanding of the algorithm when applied to games. A family of discounted games is given on which the algorithm runs in exponential time, indicating that in the worst case it performs no better for discounted games than it does for general P-matrix LCPs.
Tuesday 20th April 2010, 14:00
Board Room
Department of Computer Science