Controlled Linear Programming for Infinite Games

Abstrakt:

The controlled linear programming problem (CLPP) is a combinatorial optimization problem. An instance consists of a number of linear constraints of a certain form. A controller is allowed to select and discard constraints according to simple rules, with the goal of maximizing the optimal solution to the resulting linear program.

The CLPP captures and generalizes parity, mean payoff, discounted payoff, and simple stochastic games. For its most general version, the exact complexity is still unknown, but several rich subclasses can be shown to belong to NP intersection coNP. In this talk we use linear algebra to characterize the properties of such subclasses, and prove a number of new results. We also identify sufficient conditions for a class to be solvable in randomized subexponential time.