doc. Ing. Tomáš Kroupa, Ph.D.

Strategic and other game forms with infinite action spaces are notoriously difficult to solve. Only basic existential results are available for equilibria in games whose utility functions are sufficiently well-behaved, such as continuous or convex/concave functions over compact strategy spaces. Algorithms for computations of (approximate) equilibria have been designed in the last decades for only special classes of such games. For example, polynomial optimization methods based on Lasserre's hierarchy of semidefinite programs can be directly applied to polynomial zero-sum games. However, computing equilibria in zero-sum games for continuous games remains to be a difficult task. This has spurred a recent interest in gradient and iterative methods for finding and approximating equilibria in infinite games. The focus of the thesis will be on the design and the analysis of such methods. Specifically, the convergence rate of the double oracle algorithm will be thoroughly studied and compared to other numerical approaches, such as fictitious play. The emphasis will be on the efficient implementation of designed methods in existing optimization frameworks.

Games with infinite action spaces are a suitable framework for several problems in adversarial machine learning. Continuous games are very hard to solve and the computational behavior of iterative methods is mostly unexplored in this context. Algorithms for solving zero-sum polynomial games based on semidefinite programming were formulated only relatively recently. The thesis will focus on new computational methods for equilibria of large-scale games appearing in adversarial machine learning. Specifically, the Ph.D. candidate will study the properties of iterative methods, such as an infinite version of the Double Oracle algorithm, or other techniques employing the best response calculation. This study will ideally lead to finding theoretical guarantees of convergence to equilibria. In a parallel research line, the doctoral candidate will explore the families of infinite games appearing in the applications with the goal of describing their equilibria.