Discrete Gambling and Stochastic Games

ISBN-13: 9781461284673 / Angielski / Miękka / 2011 / 244 str.

Ashok P. Maitra; William D. Sudderth

Opis

The theory of probability began in the seventeenth century with attempts to calculate the odds of winning in certain games of chance. However, it was not until the middle of the twentieth century that mathematicians de- veloped general techniques for maximizing the chances of beating a casino or winning against an intelligent opponent. These methods of finding op- timal strategies for a player are at the heart of the modern theories of stochastic control and stochastic games. There are numerous applications to engineering and the social sciences, but the liveliest intuition still comes from gambling. The now classic work How to Gamble If You Must: Inequalities for Stochastic Processes by Dubins and Savage (1965) uses gambling termi- nology and examples to develop an elegant, deep, and quite general theory of discrete-time stochastic control. A gambler "controls" the stochastic pro- cess of his or her successive fortunes by choosing which games to play and what bets to make.

Spis treści

1 Introduction.- 1.1 Preview.- 1.2 Prerequisites.- 1.3 Numbering.- 2 Gambling Houses and the Conservation of Fairness.- 2.1 Introduction.- 2.2 Gambles, Gambling Houses, and Strategies.- 2.3 Stopping Times and Stop Rules.- 2.4 An Optional Sampling Theorem.- 2.5 Martingale Convergence Theorems.- 2.6 The Ordinals and Transfinite Induction.- 2.7 Uncountable State Spaces and Continuous-Time.- 2.8 Problems for Chapter 2.- 3 Leavable Gambling Problems.- 3.1 The Fundamental Theorem.- 3.2 The One-Day Operator and the Optimality Equation.- 3.3 The Utility of a Strategy.- 3.4 Some Examples.- 3.5 Optimal Strategies.- 3.6 Backward Induction: An Algorithm for U.- 3.7 Problems for Chapter 3.- 4 Nonleavable Gambling Problems.- 4.1 Introduction.- 4.2 Understanding u(?).- 4.3 A Characterization of V.- 4.4 The Optimality Equation for V.- 4.5 Proving Optimality.- 4.6 Some Examples.- 4.7 Optimal Strategies.- 4.8 Another Characterization of V.- 4.9 An Algorithm for V.- 4.10 Problems for Chapter 4.- 5 Stationary Families of Strategies.- 5.1 Introduction.- 5.2 Comparing Strategies.- 5.3 Finite Gambling Problems.- 5.4 Nonnegative Stop-or-Go Problems.- 5.5 Leavable Houses.- 5.6 An Example of Blackwell and Ramakrishnan.- 5.7 Markov Families of Strategies.- 5.8 Stationary Plans in Dynamic Programming.- 5.9 Problems for Chapter 5.- 6 Approximation Theorems.- 6.1 Introduction.- 6.2 Analytic Sets.- 6.3 Optimality Equations.- 6.4 Special Cases of Theorem 1.2.- 6.5 The Going-Up Property of $$ \overline M $$.- 6.6 Dynamic Capacities and the Proof of Theorem 1.2.- 6.7 Approximating Functions.- 6.8 Composition Closure and Saturated House.- 6.9 Problems for Chapter 6.- 7 Stochastic Games.- 7.1 Introduction.- 7.2 Two-Person, Zero-Sum Games.- 7.3 The Dynamics of Stochastic Games.- 7.4 Stochastic Games with lim sup Payoff.- 7.5 Other Payoff Functions.- 7.6 The One-Day Operator.- 7.7 Leavable Games.- 7.8 Families of Optimal Strategies for Leavable Games.- 7.9 Examples of Leavable Games.- 7.10 A Modification of Leavable Games and the Operator T.- 7.11 An Algorithm for the Value of a Nonleavable Game.- 7.12 The Optimality Equation for V.- 7.13 Good Strategies in Nonleavable Games.- 7.14 Win, Lose, or Draw.- 7.15 Recursive Matrix Games.- 7.16 Games of Survival.- 7.17 The Big Match.- 7.18 Problems for Chapter 7.- References.- Symbol Index.