Definable Zero-Sum Stochastic Games
| العنوان: | Definable Zero-Sum Stochastic Games |
|---|---|
| المؤلفون: | Jérôme Bolte, Stéphane Gaubert, Guillaume Vigeral |
| المساهمون: | GREMAQ, Groupe de recherche en économie mathématique et quantitative (GREMAQ), Centre National de la Recherche Scientifique (CNRS)-École des hautes études en sciences sociales (EHESS)-Institut National de la Recherche Agronomique (INRA)-Université Toulouse 1 Capitole (UT1)-Centre National de la Recherche Scientifique (CNRS)-École des hautes études en sciences sociales (EHESS)-Institut National de la Recherche Agronomique (INRA)-Université Toulouse 1 Capitole (UT1), Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), Max-plus algebras and mathematics of decision (MAXPLUS), Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Mathématiques Appliquées - Ecole Polytechnique (CMAP), Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X), CEntre de REcherches en MAthématiques de la DEcision (CEREMADE), Université Paris Dauphine-PSL-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-École des hautes études en sciences sociales (EHESS)-Institut National de la Recherche Agronomique (INRA)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées, École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Centre National de la Recherche Scientifique (CNRS)-Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL), European Project: 264735,EC:FP7:PEOPLE,FP7-PEOPLE-2010-ITN,SADCO(2011), École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS)-École polytechnique (X)-Centre National de la Recherche Scientifique (CNRS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National de la Recherche Agronomique (INRA)-École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS), Université Paris Dauphine-PSL, Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Centre National de la Recherche Scientifique (CNRS) |
| المصدر: | Mathematics of Operations Research Mathematics of Operations Research, INFORMS, 2015, 40 (1), pp.171-191. ⟨10.1287/moor.2014.0666⟩ Mathematics of Operations Research, 2015, 40 (1), pp.171-191. ⟨10.1287/moor.2014.0666⟩ |
| بيانات النشر: | Institute for Operations Research and the Management Sciences (INFORMS), 2015. |
| سنة النشر: | 2015 |
| مصطلحات موضوعية: | Computer Science::Computer Science and Game Theory, Polynomial, Pure mathematics, General Mathematics, Structure (category theory), nonexpansive mappings, Management Science and Operations Research, 01 natural sciences, Separable space, 010104 statistics & probability, Operator (computer programming), Zero-sum stochastic games, FOS: Mathematics, uniform value, 0101 mathematics, Mathematics - Optimization and Control, Finite set, Mathematics, 010102 general mathematics, Stochastic game, Shapley operator, risk-sensitive control, Computer Science Applications, nonlinear Perron-Frobenius theory, o-minimal structures, Optimization and Control (math.OC), tropical geometry, Bounded function, definable games, [MATH.MATH-OC]Mathematics [math]/Optimization and Control [math.OC], Counterexample |
| الوصف: | International audience; 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. %Showing the definability of the Shapley operator in full generality appears thus as a complex and challenging issue. } 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. |
| تدمد: | 1526-5471 0364-765X |
| DOI: | 10.1287/moor.2014.0666 |
| DOI: | 10.1287/moor.2014.0666⟩ |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1954b004db5302950f78646102360c15 https://doi.org/10.1287/moor.2014.0666 |
| Rights: | OPEN |
| رقم الانضمام: | edsair.doi.dedup.....1954b004db5302950f78646102360c15 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 15265471 0364765X |
|---|---|
| DOI: | 10.1287/moor.2014.0666 |