## Linear Complementarity Algorithms for Mean Payoff Games

### Authors: Henrik Bjorklund, Ola Svensson and Sergei Vorobyov

ABSTRACT

We suggest new pseudopolynomial and subexponential algorithms for Mean Payoff Games (MPGs). The algorithms are based on representing the MPGs decision problem in the forms of non-standard and standard LCPs, Linear Complementarity Problems (find $w,z\geq 0$ satisfying $w=Mz+q$ and $w^T\cdot z=0$), and monotonic iterative propagation of slack updates.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-05.ps.gz