## 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, simplexlike and interiorpoint. 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 wellknown mean payoff, discounted payoff, simple stochastic,
and parity games, as well as the recent LongestShortest 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 NPhard. 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 complexitytheoretic 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