Source author record

Guillaume Vigeral

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.OC Computer Science and Game Theory math.CA math.DS math.MG

Catalog footprint

Research overview

8works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Operator approach to values of stochastic games with varying stage duration

We study the links between the values of stochastic games with varying stage duration $h$ , the corresponding Shapley operators $\bf{T}$ and ${\bf{T}}\_h$ and the solution of $\dot f\_t = ({\bf{T}} - Id )f\_t$ . Considering general non expansive maps we establish two kinds of results, under both the discounted or the finite length framework, that apply to the class of "exact" stochastic games. First, for a fixed length or discount factor, the value converges as the stage duration go to 0. Second, the asymptotic behavior of the value as the length goes to infinity, or as the discount factor goes to 0, does not depend on the stage duration. In addition, these properties imply the existence of the value of the finite length or discounted continuous time game (associated to a continuous time jointly controlled Markov process), as the limit of the value of any time discretization with vanishing mesh.

preprint2016arXiv

Semi-algebraic sets and equilibria of binary games

Any nonempty, compact, semi-algebraic set in [0, 1] n is the projection of the set of mixed equilibria of a finite game with 2 actions per player on its first n coordinates. A similar result follows for sets of equilibrium payoffs. The proofs are constructive and elementary.

preprint2013arXiv

A Zero-Sum Stochastic Game with Compact Action Sets and no Asymptotic Value

We give an example of a zero-sum stochastic game with four states, compact action sets for each player, and continuous payoff and transition functions, such that the discounted value does not converge as the discount factor tends to 0, and the value of the n-stage game does not converge as n goes to infinity.

preprint2013arXiv

Definable zero-sum stochastic games

Definable zero-sum stochastic games involve a finite number of states and action sets, reward and transition functions that are definable in an o-minimal structure. Prominent examples of such games are finite, semi-algebraic or globally subanalytic stochastic games. We prove that the Shapley operator of any definable stochastic game with separable transition and reward functions is definable in the same structure. Definability in the same structure does not hold systematically: we provide a counterexample of a stochastic game with semi-algebraic data yielding a non semi-algebraic but globally subanalytic Shapley operator. Our definability results on Shapley operators are used to prove that any separable definable game has a uniform value; in the case of polynomially bounded structures we also provide convergence rates. Using an approximation procedure, we actually establish that general zero-sum games with separable definable transition functions have a uniform value. These results highlight the key role played by the tame structure of transition functions. As particular cases of our main results, we obtain that stochastic games with polynomial transitions, definable games with finite actions on one side, definable games with perfect information or switching controls have a uniform value. Applications to nonlinear maps arising in risk sensitive control and Perron-Frobenius theory are also given

preprint2011arXiv

A maximin characterization of the escape rate of nonexpansive mappings in metrically convex spaces

We establish a maximin characterisation of the linear escape rate of the orbits of a non-expansive mapping on a complete (hemi-)metric space, under a mild form of Busemann's non-positive curvature condition (we require a distinguished family of geodesics with a common origin to satisfy a convexity inequality). This characterisation, which involves horofunctions, generalises the Collatz-Wielandt characterisation of the spectral radius of a non-negative matrix. It yields as corollaries a theorem of Kohlberg and Neyman (1981), concerning non-expansive maps in Banach spaces, a variant of a Denjoy-Wolff type theorem of Karlsson (2001), together with a refinement of a theorem of Gunawardena and Walsh (2003), concerning order-preserving positively homogeneous self-maps of symmetric cones. An application to zero-sum stochastic games is also given.

preprint2010arXiv

A uniform Tauberian theorem in optimal control

In an optimal control framework, we consider the value $V_T(x)$ of the problem starting from state $x$ with finite horizon $T$ , as well as the value $V_λ(x)$ of the $λ$ -discounted problem starting from $x$ . We prove that uniform convergence (on the set of states) of the values $V_T(\cdot)$ as $T$ tends to infinity is equivalent to uniform convergence of the values $V_λ(\cdot)$ as $λ$ tends to 0, and that the limits are identical. An example is also provided to show that the result does not hold for pointwise convergence. This work is an extension, using similar techniques, of a related result in a discrete-time framework \cite{LehSys}.

preprint2010arXiv

Asymptotic Properties of Optimal Trajectories in Dynamic Programming

We prove in a dynamic programming framework that uniform convergence of the finite horizon values implies that asymptotically the average accumulated payoff is constant on optimal trajectories. We analyze and discuss several possible extensions to two-person games.

preprint2009arXiv

Evolution equations in discrete and continuous time for nonexpansive operators in Banach spaces

We consider some discrete and continuous dynamics in a Banach space involving a non expansive operator $J$ and a corresponding family of strictly contracting operators $Φ(λ,x):=λJ(\frac{1-λ}λx)$ for $λ\in]0,1]$ . Our motivation comes from the study of two-player zero-sum repeated games, where the value of the $n$ -stage game (resp. the value of the $λ$ -discounted game) satisfies the relation $v_n=Φ(\frac{1}{n},v_{n-1})$ (resp. $v_λ=Φ(λ,v_λ)$ ) where $J$ is the Shapley operator of the game. We study the evolution equation $u'(t)=J(u(t))-u(t)$ as well as associated Eulerian schemes, establishing a new exponential formula and a Kobayashi-like inequality for such trajectories. We prove that the solution of the non-autonomous evolution equation $u'(t)=Φ(\bmλ(t),u(t))-u(t)$ has the same asymptotic behavior (even when it diverges) as the sequence $v_n$ (resp. as the family $v_λ$ ) when $\bmλ(t)=1/t$ (resp. when $\bmλ(t)$ converges slowly enough to 0).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.