Ebook: Stochastic Games and Applications

This volume is based on lectures given at the NATO Advanced Study Institute on "Stochastic Games and Applications," which took place at Stony Brook, NY, USA, July 1999. It gives the editors great pleasure to present it on the occasion of L.S. Shapley's eightieth birthday, and on the fiftieth "birthday" of his seminal paper "Stochastic Games," with which this volume opens. We wish to thank NATO for the grant that made the Institute and this volume possible, and the Center for Game Theory in Economics of the State University of New York at Stony Brook for hosting this event. We also wish to thank the Hebrew University of Jerusalem, Israel, for providing continuing financial support, without which this project would never have been completed. In particular, we are grateful to our editorial assistant Mike Borns, whose work has been indispensable. We also would like to acknowledge the support of the Ecole Poly tech­ nique, Paris, and the Israel Science Foundation. March 2003 Abraham Neyman and Sylvain Sorin ix STOCHASTIC GAMES L.S. SHAPLEY University of California at Los Angeles Los Angeles, USA 1. Introduction In a stochastic game the play proceeds by steps from position to position, according to transition probabilities controlled jointly by the two players.

---

1. Stochastic games; L.S. Shapley.2. From Markov chains to stochastic games; A. Neyman.3. Classification and basic tools; S. Sorin.4. Stochastic games and stationary strategies; O.J. Vrieze.5. Discounted stochastic games: The finite case; S. Sorin.6. Real algebraic tools in stochastic games; A. Neyman.7. Zero-sum stochastic games with borel state spaces; A.S. Nowak.8. N-person stochastic games: extension of the finite case and correlation; A.S. Nowak.9. A measurable "measurable choice" theorem; J.F. Mertens.10. Equilibria for discounted stochastic games; J.F. Mertens, T. Parthasarathy.11. Existence of the value and the minmax; A. Neyman.12. The big match and the paris match; F. Thuijsman.13. Repeated games with absorbing states; F. Thuijsman.14. Stochastic games, practical motivation and the orderfield property for special classes; O.J. Vrieze.15. Finite-step algorithms for single-controller and perfect information stochastic games; T.E.S. Raghavan.16. Recursive games; F. Thuijsman.17. Perturbations of Markov chains with applications to stochastic games; E. Solan.18. Two-player non-zero-sum games: A reduction; N.Vieille.19. On a class of recursive games; N. Vieille.20. Uniform equilibrium: more than two players; E. Solan.21. Symmetric incomplete information games as stochastic games; S. Sorin.22. Absorbing games with a signalling structure; J.-M. Coulomb.23. Stochastic Games with lim sup Payoff; A. Maitra, W. Sudderth.24. Stochastic games with borel payoffs; A. Maitra, W. Sudderth.25. Stochastic games with incomplete information; S. Sorin.26. Stochastic games and nonexpansive maps; A. Neyman.27. The operator approach to zero-sum stochastic games; S. Sorin.28. Games with a recursive structure; J.-M. Coulomb.29. Stochastic games in economics: The lattice-theoretic approach; R. Amir.30. Stochastic games in economics and related fields: an overview; R. Amir.

---

1. Stochastic games; L.S. Shapley.2. From Markov chains to stochastic games; A. Neyman.3. Classification and basic tools; S. Sorin.4. Stochastic games and stationary strategies; O.J. Vrieze.5. Discounted stochastic games: The finite case; S. Sorin.6. Real algebraic tools in stochastic games; A. Neyman.7. Zero-sum stochastic games with borel state spaces; A.S. Nowak.8. N-person stochastic games: extension of the finite case and correlation; A.S. Nowak.9. A measurable "measurable choice" theorem; J.F. Mertens.10. Equilibria for discounted stochastic games; J.F. Mertens, T. Parthasarathy.11. Existence of the value and the minmax; A. Neyman.12. The big match and the paris match; F. Thuijsman.13. Repeated games with absorbing states; F. Thuijsman.14. Stochastic games, practical motivation and the orderfield property for special classes; O.J. Vrieze.15. Finite-step algorithms for single-controller and perfect information stochastic games; T.E.S. Raghavan.16. Recursive games; F. Thuijsman.17. Perturbations of Markov chains with applications to stochastic games; E. Solan.18. Two-player non-zero-sum games: A reduction; N.Vieille.19. On a class of recursive games; N. Vieille.20. Uniform equilibrium: more than two players; E. Solan.21. Symmetric incomplete information games as stochastic games; S. Sorin.22. Absorbing games with a signalling structure; J.-M. Coulomb.23. Stochastic Games with lim sup Payoff; A. Maitra, W. Sudderth.24. Stochastic games with borel payoffs; A. Maitra, W. Sudderth.25. Stochastic games with incomplete information; S. Sorin.26. Stochastic games and nonexpansive maps; A. Neyman.27. The operator approach to zero-sum stochastic games; S. Sorin.28. Games with a recursive structure; J.-M. Coulomb.29. Stochastic games in economics: The lattice-theoretic approach; R. Amir.30. Stochastic games in economics and related fields: an overview; R. Amir.
Content:
Front Matter....Pages i-ix
Stochastic Games....Pages 1-7
From Markov Chains to Stochastic Games....Pages 9-25
Classification and Basic Tools....Pages 27-36
Stochastic Games and Stationary Strategies....Pages 37-50
Discounted Stochastic Games: The Finite Case....Pages 51-55
Real Algebraic Tools in Stochastic Games....Pages 57-75
Zero-Sum Stochastic Games with Borel State Spaces....Pages 77-91
N—Person Stochastic Games: Extensions of the Finite State Space Case and Correlation....Pages 93-106
A Measurable “Measurable Choice” Theorem....Pages 107-130
Equilibria for Discounted Stochastic Games....Pages 131-172
Stochastic Games: Existence of the Minmax....Pages 173-193
The Big Match and the Paris Match....Pages 195-204
Repeated Games with Absorbing States....Pages 205-213
Stochastic Games, Practical Motivation and the Orderfield Property for Special Classes....Pages 215-225
Finite-Step Algorithms for Single-Controller and Perfect Information Stochastic Games....Pages 227-251
Recursive Games....Pages 253-264
Perturbations of Markov Chains with Applications to Stochastic Games....Pages 265-280
Two-Player Non-Zero-Sum Games: A Reduction....Pages 281-292
On a Class of Recursive Games....Pages 293-307
Uniform Equilibrium: More than Two Players....Pages 309-321
Symmetric Incomplete Information Games as Stochastic Games....Pages 323-334
Absorbing Games with a Signalling Structure....Pages 335-355
Stochastic Games with Lim Sup Payoff....Pages 357-366
Stochastic Games with Borel Payoffs....Pages 367-373
Stochastic Games with Incomplete Information....Pages 375-395
Stochastic Games and Nonexpansive Maps....Pages 397-415
The Operator Approach to Zero-Sum Stochastic Games....Pages 417-426
Games with a Recursive Structure....Pages 427-442
Stochastic Games in Economics: The Lattice-Theoretic Approach....Pages 443-453
Stochastic Games in Economics and Related Fields: An Overview....Pages 455-470
Back Matter....Pages 471-473

---

1. Stochastic games; L.S. Shapley.2. From Markov chains to stochastic games; A. Neyman.3. Classification and basic tools; S. Sorin.4. Stochastic games and stationary strategies; O.J. Vrieze.5. Discounted stochastic games: The finite case; S. Sorin.6. Real algebraic tools in stochastic games; A. Neyman.7. Zero-sum stochastic games with borel state spaces; A.S. Nowak.8. N-person stochastic games: extension of the finite case and correlation; A.S. Nowak.9. A measurable "measurable choice" theorem; J.F. Mertens.10. Equilibria for discounted stochastic games; J.F. Mertens, T. Parthasarathy.11. Existence of the value and the minmax; A. Neyman.12. The big match and the paris match; F. Thuijsman.13. Repeated games with absorbing states; F. Thuijsman.14. Stochastic games, practical motivation and the orderfield property for special classes; O.J. Vrieze.15. Finite-step algorithms for single-controller and perfect information stochastic games; T.E.S. Raghavan.16. Recursive games; F. Thuijsman.17. Perturbations of Markov chains with applications to stochastic games; E. Solan.18. Two-player non-zero-sum games: A reduction; N.Vieille.19. On a class of recursive games; N. Vieille.20. Uniform equilibrium: more than two players; E. Solan.21. Symmetric incomplete information games as stochastic games; S. Sorin.22. Absorbing games with a signalling structure; J.-M. Coulomb.23. Stochastic Games with lim sup Payoff; A. Maitra, W. Sudderth.24. Stochastic games with borel payoffs; A. Maitra, W. Sudderth.25. Stochastic games with incomplete information; S. Sorin.26. Stochastic games and nonexpansive maps; A. Neyman.27. The operator approach to zero-sum stochastic games; S. Sorin.28. Games with a recursive structure; J.-M. Coulomb.29. Stochastic games in economics: The lattice-theoretic approach; R. Amir.30. Stochastic games in economics and related fields: an overview; R. Amir.
Content:
Front Matter....Pages i-ix
Stochastic Games....Pages 1-7
From Markov Chains to Stochastic Games....Pages 9-25
Classification and Basic Tools....Pages 27-36
Stochastic Games and Stationary Strategies....Pages 37-50
Discounted Stochastic Games: The Finite Case....Pages 51-55
Real Algebraic Tools in Stochastic Games....Pages 57-75
Zero-Sum Stochastic Games with Borel State Spaces....Pages 77-91
N—Person Stochastic Games: Extensions of the Finite State Space Case and Correlation....Pages 93-106
A Measurable “Measurable Choice” Theorem....Pages 107-130
Equilibria for Discounted Stochastic Games....Pages 131-172
Stochastic Games: Existence of the Minmax....Pages 173-193
The Big Match and the Paris Match....Pages 195-204
Repeated Games with Absorbing States....Pages 205-213
Stochastic Games, Practical Motivation and the Orderfield Property for Special Classes....Pages 215-225
Finite-Step Algorithms for Single-Controller and Perfect Information Stochastic Games....Pages 227-251
Recursive Games....Pages 253-264
Perturbations of Markov Chains with Applications to Stochastic Games....Pages 265-280
Two-Player Non-Zero-Sum Games: A Reduction....Pages 281-292
On a Class of Recursive Games....Pages 293-307
Uniform Equilibrium: More than Two Players....Pages 309-321
Symmetric Incomplete Information Games as Stochastic Games....Pages 323-334
Absorbing Games with a Signalling Structure....Pages 335-355
Stochastic Games with Lim Sup Payoff....Pages 357-366
Stochastic Games with Borel Payoffs....Pages 367-373
Stochastic Games with Incomplete Information....Pages 375-395
Stochastic Games and Nonexpansive Maps....Pages 397-415
The Operator Approach to Zero-Sum Stochastic Games....Pages 417-426
Games with a Recursive Structure....Pages 427-442
Stochastic Games in Economics: The Lattice-Theoretic Approach....Pages 443-453
Stochastic Games in Economics and Related Fields: An Overview....Pages 455-470
Back Matter....Pages 471-473
....