Games through the lens of ALgebra and geometry of OPtimization – GALOP

Shapley introduced stochastic games in 1953 and since then they are a subject of intensive study. They model dynamic interactions in an environment that changes in response to the behavior of the players. Their applications include industrial organization, resource economics, market games, communication networks. For many families of stochastic games we can describe the equilibrium strategies and the payoffs of the players using systems of polynomial equations and inequalities. In this interplay, one challenge is to close the gap between upper and lower bounds in the computation of equilibria and to obtain precise complexity estimates. Another challenge is to exploit the structure of the underlying systems and derive efficient algorithms and software packages to solve them. Particular instances of continuous stochastic games rely on optimizing a linear function restricted to a convex set defined by linear matrix inequalities. It is not clear what is the optimal algebraic formulation in this setting. We solve such optimization problems using interior point methods. These methods follow a curve inside the feasible region. Unfortunately, since we do not know the algebraic and geometric properties of this curve, we can not estimate the bit complexity of the interior point methods, and thus we can not obtain precise estimates for the algorithms for continuous games.
Besides stochastic games, systems of polynomial equations arise naturally in many research areas. They are used, both in theory and practice, to model and simulate complex phenomena: notably in optimization, computational geometry, statistics, biology, and control. The real roots of the polynomial systems are in the center of interest as they correspond to sets or solutions with a physical meaning for the underlying problem; for example the feasible set of optimization problems, the equilibria and players’ strategies in games. Most of the algorithms for polynomial system solving are designed with the generic case in mind and do not fully exploit the structure and the geometry of the problem at hand.
GALOP brings original and innovative algebraic tools, based on symbolic-numeric computing, that exploit the geometry and the structure and complement the state-of-the-art. We support our theoretical tools with a highly efficient open-source software for solving polynomials. Using our algebraic tools we study the geometry of the central curve of (semi-definite) optimization problems. The algebraic tools and our results from the geometry of optimization shape a new mathematical and algorithmic framework that we use to introduce novel algorithms and precise bounds for stochastic games. Our methodology
(i) depends on the actual number of solutions and performs computations with the number of bits needed to represent the output [output sensitive],
(ii) produces always the correct numerical, geometrical, or combinatorial result [certified], and
(iii) exploits the structure of the input, like sparsity, symmetries, geometry of the solution set [structure].
GALOP is structured in three tasks. In “Stochastic Games”, we target algorithms and precise bounds for computing the values of stochastic games, using techniques from computational real algebraic geometry, and we introduce a new arsenal of algebraic and geometric tools in computational game theory. In “Geometry of Optimization”, we study the central curve of SDP to deepen our understanding on the problem and to trigger new semi-numerical algorithms. Finally, in “Algebraic Tools” we focus on separation bounds of polynomial systems that admit a special structure and on solving univariate polynomials. We provide efficient, certified, open-source software for real solving univariate polynomials. It is usable as stand-alone tool, through FLINT, or through general computer algebra systems. We integrate it with the best Gro¨bner basis engine, FGb, to provide a state-of-the-art tool for solving exactly 0-dimensional polynomial systems.