Existence of the Limit Value of Two Person Zero-Sum Discounted Repeated Games via Comparison Theorems
- PDF / 525,435 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 34 Downloads / 224 Views
Existence of the Limit Value of Two Person Zero-Sum Discounted Repeated Games via Comparison Theorems Sylvain Sorin · Guillaume Vigeral
Received: 17 July 2011 / Accepted: 21 September 2012 / Published online: 10 October 2012 © Springer Science+Business Media New York 2012
Abstract We give new proofs of existence of the limit of the discounted values for two person zero-sum games in the three following frameworks: absorbing, recursive, incomplete information. The idea of these new proofs is to use some comparison criteria. Keywords Stochastic games · Repeated games · Incomplete information · Asymptotic value · Comparison principle · Variational inequalities 1 Introduction The purpose of this article is to present a unified approach to the existence of the limit value for two person zero-sum discounted games. The main tools used in the proofs are – the fact that the discounted value satisfies the Shapley equation [1], – properties of accumulation points of the discounted values, and of the corresponding optimal strategies, Communicated by Irinel Chiril Dragan. S. Sorin Combinatoire et Optimisation, IMJ, CNRS UMR 7586, Faculté de Mathématiques, Université P. et M. Curie Paris 6, Tour 15-16, 1er etage, 4 Place Jussieu, 75005 Paris, France e-mail: [email protected] S. Sorin Laboratoire d’Econométrie, Ecole Polytechnique, Palaiseau, France G. Vigeral () CEREMADE, Université Paris-Dauphine, Place du Maréchal De Lattre de Tassigny, 75775 Paris Cedex 16, France e-mail: [email protected]
J Optim Theory Appl (2013) 157:564–576
565
– comparison of two accumulation points leading to uniqueness and characterization. We apply this program for three well known classes of games, each time covering the case where action spaces are compact. For absorbing games, the results are initially due to Kohlberg [2] for finitely many actions, later extended in Rosenberg and Sorin [3] for the compact case. An explicit formula for the limit was recently obtained in Laraki [4], and we obtain a related one. The case of recursive games was first handled in Everett [5], with a different notion of limit value involving asymptotic payoff on plays. It was later shown by Sorin [6] that these results implied also the existence of the limit value for two person zero-sum discounted games. The last class corresponds to games with incomplete information, where the results were initially obtained in Aumann and Maschler [7] and Mertens and Zamir [8] (including also the asymptotic study of the finitely repeated games). In that case, we follow a quite similar approach to Laraki [9].
2 Model, Notations and Basic Lemmas Let G be a two person zero-sum stochastic game defined by a finite state space Ω, compact metric action spaces I and J for player 1 and 2 (with mixed extensions X = (I ) and Y = (J ), respectively, where for a compact metric space C, (C) denotes the set of Borel probabilities on C, endowed with the weak- topology), a separately continuous real bounded payoff g on I ×J ×Ω and a separately continuous transition ρ from I × J ×
Data Loading...
