In this paper we identify and systematically explore the combinatorial structure underlying parity and simple stochastic games. We introduce the class of Completely LG (local-global) functions with nice structural properties pertinent to games and allowing for efficient optimization by iterative improvement local search style algorithms. We demonstrate several important combinatorial properties of Completely LG functions, allowing for many optimization algorithms, and establish a relation with the subclass of Completely Unimodal functions, studied by Hammer et al.  Williamson Hoke , and Wiedemann . We also describe a new, compared to our recent [STACS'2003], subexponential randomized algorithm for CU-functions, CLG-functions, parity, and simple stochastic games, and establish a relation with the class of LP-type problems introduced and investigated by Sharir \& Welzl  and Matousek, Sharir \& Welzl .
Available as compressed Postscript (304 kB) and Postscript (870 kB)
Download BibTeX entry.