DIMACS TR: 2005-13

Controlled Linear Programming for Infinite Games



Authors: Henrik Bjorklund, Ola Svensson and Sergei Vorobyov

ABSTRACT

We investigate the CONTROLLED LINEAR PROGRAMMING PROBLEM (CLPP), a new combinatorial optimization problem nicely merging linear programming with games. In a system of linear constraints of the form $x_i \leq p^j_i(\overline x) + w^j_i$ where $p^j_i$ are linear homogeneous polynomials with nonnegative coefficients and $w^j_i \in R$, some variables are distinguished as \emph{controlled} and we want to select \emph{exactly one} constraint for each controlled variable to make max$\sum x_i$, subject to the remaining constraints, as large as possible (over all possible such selections). We suggest a number of iterative strategy improvement policies, simplex­like and interior­point. For many important cases we prove optimality conditions (when a local optimum is global), describe a number of combinatorial randomized \emph{subexponential} algorithms, and show that the decision version of the problem is in $NP \bigcap coNP$.

It turns out that the well­known mean payoff, discounted payoff, simple stochastic, and parity games, as well as the recent Longest­Shortest Paths (LSP) problem [10] (all in $NP\bigcap coNP$, unknown to be in P) are easily reducible to the CLPP. This suggests a simplifying and unifying view of all these games as particular restricted instances of the CLPP, one of the "most general" problems in $NP \bigcap coNP$ to which all the known games in the class reduce (in certain sense "complete" in the class). We show that a slight generalization of the CLPP allowing for negative coefficients in the constraint polynomials $p^j_i$ is NP­hard. So are the controlled versions of many other polynomial optimization problems, like MAXIMUM FLOW.

The simple algebraic and combinatorial structure of the CLPP unifies and gives insights into algorithmic and complexity­theoretic properties of infinite games, and is amenable to the powerful tools from combinatorial and polyhedral optimization, as well as linear programming. In this paper we investigate boundedness, CLPP duality, stability, optimality conditions, correctness of subexponential algorithms, and conditions for $NP \bigcap coNP$­membership. In particular, strong duality implies $NP \bigcap coNP$­membership, polynomial optimality conditions, and strongly subexponential algorithms.

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

DIMACS Home Page