Discrete Mathematics and Optimization Seminar
RAHUL SAVANI |
University of Warwick
Monday October 8th at 4.30pm
Burnside 1205
Title. A simple P-matrix linear complementarity problem for
discounted games.
Abstract.
We consider zerosum discounted games, which are played by
two players on a finite directed graph with rewards on
vertices. The players' strategies together determine an
infinite path in the game graph. One player tries to
maximize, the other minimize the discounted sum of the
rewards encountered on the path. These games provide one of
the few natural problems - Is the value of a game greater
than k? - that are in NP interesct coNP, but for which no
polynomial-time algorithms are known. One of the main
algorithms for solving these games is "strategy
improvement", however its worst case complexity is not known
to be superpolynomial.
In this talk we present a simple reduction from discounted
games to the P-matrix linear complementarity problem (PLCP),
and discuss the application of known algorithms for PLCPs to
discounted games. In particular, we recover a variant of
strategy improvement. We also discuss the underlying
combinatorial framework, which is given by unique sink
orientations of cubes. Joint work with Marcin Jurdzinski.