Technical Report 2001-008

Parity Games: Interior-Point Approach

Viktor Petersson and Sergei Vorobyov

May 2001

We introduce and investigate continuous optimization techniques for solving Parity Games, based on the interior-point paradigm, combining barrier functions and quasi-Newton methods. These have been proven very successful for Linear and Convex Programming. The basic step is to leave the boundary (i.e. the stationary strategies in which such games can be solved) and to cut through the interior (i.e. probabilistic strategies) of the many-dimensional hypercube of strategies.

Available as compressed Postscript (117 kB, no cover)

Download BibTeX entry.