Appendix A. Martin’s Theorem for Stochastic Games In this section I formulate Martin’s Theorem about the determinacy of stochastic games. The stochastic game used in this paper has complete information, while Martin studied a more general setup in which the players play simultaneously. Note, however, that Martin’s older theorem about the determinacy of Gale-Stewart games [8] is not sufficient for my purposes because of the presence of Chance. A stochastic game with perfect information is given by (( S$_{n}$, B$_{n}$ )$_{n}$$_{∈}$ N , z, V ), where B$_{0}$, B$_{1}$, . . . are finite sets of actions , S$_{0}$, S$_{1}$, . . . are finite sets of states or Chance’s actions , z = { z$_{n}$ : S$_{0}$ × B$_{0}$ × · · · × S$_{n}$$_{−}$$_{1}$ × B$_{n}$$_{−}$$_{1}$ → Δ( S$_{n}$ ) } is Chance’s strategy , and V ⊆ S$_{0}$ × B$_{0}$ × S$_{1}$ × B$_{1}$ × . . . is the winning set of Player 1. The game is played as follows: Player 1 plays at even stages and player 2 at odd stages. At every stage n , Chance announces a state s$_{n}$ in S$_{n}$ , and then the player that plays at that stage announces an action b$_{n}$ in B$_{n}$ . Chance chooses the state s$_{n}$ of stage n from the distribution z ( s$_{0}$, b$_{0}$, . . . , s$_{n}$$_{−}$$_{1}$, b$_{n}$$_{−}$$_{1}$ ). Player 1 wins the game if ( s$_{0}$, b$_{0}$, s$_{1}$, b$_{1}$, . . . ) ∈ V . I call a triple S = (( S$_{n}$, B$_{n}$ )$_{n}$$_{∈}$ N , z, ) of action sets, states sets, and Chance’s strategy a stochastic setup . So the stochastic games that I use in this paper are given by a stochastic setup S = (( S$_{n}$, B$_{n}$ )$_{n}$$_{∈}$ N , z } ) and a winning set V ⊆ S$_{0}$ × B$_{0}$ × S$_{1}$ × B$_{1}$ × . . . . The definitions of strategies of the players, and of determinacy and value of the game, are omitted. The following proposition was proved by Martin [9]. For the stochastic extension, see Maitra and Sudderth’s paper [7]. The fact that the lower value of the game can be ap- proximated by the value on some compact subset was proved earlier by Maitra, Purves and Sudderth [6]. A.1. Proposition. Let S = (( S$_{n}$, B$_{n}$ )$_{n}$$_{∈}$ N , z } ) be a stochastic setup, and let V be a Borel subset of S$_{0}$ × B$_{0}$ × S$_{1}$ × B$_{1}$ × . . . . Then: 20 (1) The game ( S , V ) is determined.