Abstracts

Asarin et al. (2016) introduced the notion of entropy game, in which one player (called Despot) wishes to minimize the growth rate of a matrix product, measuring the “freedom” of a half-player (called People), whereas the opponent of Despot (called Tribune) wishes to maximize it. We develop an operator approach to entropy games. We first show that these games can be cast as stochastic mean payoff games in which payments are given by a relative entropy. Then, we establish the existence of the value by o-minimality arguments. We also characterize the value by a Collatz-Wielandt formula. When specialized to the one player case, this leads to a convex programming characterization of the value. Using the latter characterization, together with separation bounds between algebraic numbers, we show that entropy games in which the number of states belonging to Despot is fixed can be solved in polynomial time. Finally, we use this operator approach to solve general entropy games by a policy iteration algorithm, which we compare with the spectral simplex algorithm developed by Protasov (2015).

This talk is based on a work with Stéphane Gaubert, Julien Grand-Clément, and Jérémie Guillaud (in Proceedings of STACS 2017, extended version in arXiv:1904.05151, to appear in AMC Trans. on Comput. Systems).

McEneaney’s max-plus basis method allows one to approximate the value function of a deterministic optimal control problem by a supremum of elementary functions like quadratic forms. Recently, Ahmadi et al. developed an approximation method for Barabanov norms of switched linear systems, relying also on the approximation by suprema of quadratic forms. Related methods were developed in computer science, they allow one to compute program invariants, represented as intersections or unions or ellipsoids. In all these approaches, the solution of large scale linear matrix inequalities by semidefinite programming methods is the computational bottleneck. We will show that the recourse to semidefinite programming can be avoided by expressing piecewise quadratic invariant generation and value function approximation as a fixed point problem in the space of positive semidefinite matrices.

To do so, we introduce “noncommutative” analogues of Bellman operators, acting on spaces of matrices, instead of spaces of functions. The minima and maxima of functions are now replaced by selections of minimal upper bounds and maximal upper bounds, with respect to the Loewner order. By a theorem of Kadison, such selections are not unique. They are also not order preserving. However, the Bellman type operators which arise in this way retain a remarkable structure. Indeed, they appear as the tropicalizations of the completely positive maps representing quantum channels, and the convergence of numerical schemes can be established by exploiting metric properties of the cone of positive definite matrices. This allows us to obtain relaxed solutions for very large scale instances (e.g., approximations of the joint spectra radius in dimension 500). We finally refine this approach in the special case of positive switched linear systems; then, the tropical Kraus map is replaced by a risk sensitive ergodic operator, whose eigenvalue bounds the joint spectral radius. This talk is based on joint work with Nikolas Stott.

Recently nonnegative tensors, i.e. nonnegative matrices with two or more indices, have attracted a lot of attention. After recalling different types of eigenvector and singular vector problems of nonnegative tensors, we present a general formulation which unifies their study, namely eigenvectors of order presering multi-homogeneous mappings on the product of cones. We then discuss generalizations of classical results of nonlinear Perron-Frobenius theory for multi-homogeneous mappings about existence and uniqueness of positive eigenvectors, convergence of the iterates and a Collatz-Wielandt formula.

In the theory of zero-sum repeated games, the operator approach consists in studying the dynamic programming operator (a.k.a. Shapley operator) of a game to infer asymptotic properties of the latter. In this talk we present an approach that goes in the opposite direction: our aim is to study a nonlinear order-preserving and positively homogeneous map acting on the open orthant by analyzing the dynamics of an ad hoc two-player game. Thus, by constructing a stochastic game that only depends on the behavior of the map at infinity, we can characterize combinatorially the existence of an eigenvector for every uniform perturbations of the map. The criterion is fomulated in terms of dominions, i.e., subsets of states that can be made invariant by one player. With a similar construction, but based on the local behavior near an eigenvector, we characterize the uniqueness of the latter. We illustrate these results with two specific classes of maps: Shapley operators (thus making the round trip between game theory and nonlinear Perron-Frobenius theory) and nonnegative tensors.

We give necessary and sufficient conditions for a nonexpansive map on a finite dimensional normed space to have a nonempty, bounded set of fixed points. These conditions amount to an algorithm for detecting the presence of such fixed points. As an application, a nonlinear Perron-Frobenius theorem is presented for order-preserving homogeneous maps on the cone of entry-wise positive vectors in $\mathbb{R}^n$.

We will present results on Bonsall’s and lower cone spectral radius of positively homogeneous, bounded or Lipschitz and suprema preserving mapping on max cones in normed vector lattices and its approximate point spectrum. Related results for cone linear mappings on normal cones will also be presented.

This is joint work with Vladimir Müller, Prague.

We study the links between the values of stochastic games with varying stage duration $h$, the corresponding Shapley operators $T$ and $T _h= hT + (1-h ) Id$, and the solution of the evolution equation $\dot f_t = (T - Id )f_t$. Considering general non expansive maps we establish two kinds of results, under both the discounted or the finite duration framework, that apply to the class of “exact” stochastic games. On the one hand, for a fixed horizon or discount factor, the value converges as the stage duration go to 0. On the other hand, the asymptotic behavior of the value as the horizon goes to infinity, or as the discount factor goes to 0, does not depend on the stage duration.

Finally these properties imply the existence of the value of the finite duration or discounted continuous time game (associated to a continuous time jointly controlled Markov process), as the limit of the value of any discretization with vanishing mesh.

We are interested in knowing, which pairs of ordered vector spaces have the property that all order isomorphisms between them are automatically affine? Here, an order isomorphism means a bijection that is order preserving in both directions.

In finite dimension, it is known that this property holds as long as the cone of positive elements of each space does not have a $1$-dimensional factor. There are extensions of this result to infinite dimension, but they typically make strong assumptions on the set of extreme vectors of the cone. However, many interesting spaces have cones with few or no extreme vectors. Our approach is to instead look at the dual cone. Our setting is that of order unit spaces that are complete with respect to their order unit norm. We present a necessary and sufficient condition, in terms of the geometry of the dual cone, for all order isomorphisms between two such spaces to be affine.