Ing. Tomáš Votroubek

Continuous games are multiplayer games in which strategy sets are compact and utility functions are continuous. These games typically have a highly complicated structure of Nash equilibria, and numerical methods for the equilibrium computation are known only for particular classes of continuous games, such as two-player polynomial games or games in which pure equilibria are guaranteed to exist. This contribution focuses on the computation and approximation of a mixed strategy equilibrium for the whole class of multiplayer general-sum continuous games. We vastly extend the scope of applicability of the double oracle algorithm, initially designed and proved to converge only for two-player zero-sum games. Specifically, we propose an iterative strategy generation technique, which splits the original problem into the master problem with only a finite subset of strategies being considered, and the subproblem in which an oracle finds the best response of each player. This simple method is guaranteed to recover an approximate equilibrium in finitely many iterations. Further, we argue that the Wasserstein distance (the earth mover’s distance) is the right metric for the space of mixed strategies for our purposes. Our main result is the convergence of this algorithm in the Wasserstein distance to an equilibrium of the original continuous game. The numerical experiments show the performance of our method on several classes of games including randomly generated examples.

In this paper, we study new classes of value operators for coalitional games with players organized into a boolean algebra. Coalitional games are cooperative models in which players can form coalitions to maximize profit. The basic solution concepts in such game scenarios are value operators, which assign a unique real value to every player, reflecting thus selected principles of economic rationality. Some value concepts were extended beyond the classic coalitional model where every coalition of players can form. In particular, the extension of Shapley value exists for coalitional games in which players are partially ordered, and the feasible coalitions are the corresponding down-sets. Interestingly, this game-theoretic framework was employed in the method called Information Attribution. This method aims to solve the information decomposition problem, which asks for a particular additive decomposition of the mutual information between the input and target random variables. In such information-theoretic games, the players are predictors, and their set has the natural structure of a boolean algebra. Motivated by the original problem, we consider coalitional games where the players form a boolean algebra, and the coalitions are the corresponding down-sets. This more general approach enables us to study various value solution concepts in detail. Namely, we focus on the classes of values that can represent alternatives to the solution of the information decomposition problem, such as random-order values or sharing values. We extend the axiomatic characterization of some classes of values that were known only for the standard coalitional games.

A separable network game is a multiplayer finite strategic game in which each player interacts only with adjacent players in a simple undirected graph. The utility of each player results from the aggregation of utilities in the corresponding two-player games. In our contribution, we extend this model to infinite games whose strategy sets are compact subsets of the Euclidean space. We show that Nash equilibria of a zero-sum continuous network game can be characterized as optimal solutions to a specific infinite-dimensional linear optimization problem. In particular, when the utility functions are multivariate polynomials, this optimization formulation enables us to approximate the equilibria using a hierarchy of semidefinite relaxations. We present a security game over a complete bipartite graph in which the nodes are attackers and defenders, who compete for control over given targets.