mahajan@fornax.UUCP (Sanjeev Mahajan) (08/02/90)
It is known (I forget the reference) that all Borel games are determinate, (that is either their is a winning strategy for player I or there is a winning strategu for the player II) if measurable cardinals exist. In particular it is known than all SIGMA-k games are determinate (this is true indpendent of whether measurable cardinals exist or not). My question is this: Let us, for simplicity, consider only closed games. Then the proof of the theorem runs roughly as follows: Let us assume that for all stratgies for player II there is a strategy for player I, such that the player II doesn't win. Then there is a first move for player I, such that for any strategy of player II after this move there is a strategy of player I such that player II does not win (because if this wasn't so, there would be a winning strategy for player II). One can continue this argument at finite level, and hence prove by induction that there is strategy of player I such that (s)he always has a winning path at a finite level, and as the game is closed this is also a winning strategy for player I. OK, now finally the question :-). Observe that the argument that 'there is a first move ...' is in some vague sense non-constructive. So my question is, is there a constructive version of this theorem, or does the question even make sense. One way of formulating the constructive version would be as follows: if for all computable strategies s of player II, one can uniformly compute, in a recursive index of s, a computable strategy s' of player I such that player II does not win then one can construct (uniformly in an index of the algorithm that computes s' from s) a computable strategy for player I such that for all computable strategies of player II, player I wins. If this statement is not true, can it be modified in some non-trivial way, so that it is true. Sanjeev
spector@sumax.UUCP (Mitchell Spector) (08/03/90)
In article <1033@fornax.UUCP> mahajan@fornax.UUCP (Sanjeev Mahajan) writes: >It is known (I forget the reference) that all Borel games are determinate, >(that is either their is a winning strategy for player I or there is >a winning strategu for the player II) if measurable cardinals exist. Martin proved without any large cardinal assumption that all Borel games are determined. The proof does require a substantial amount of ZF and cannot be carried out, for example, by discussing just reals and sets of reals (as H. Friedman showed, actually before Martin's proof). The existence of a measurable cardinal implies that all analytic games are determined; in fact, by work of Martin and Harrington, the determinacy of analytic games is equivalent to the existence of r# for all reals r (which follows from the existence of a measurable cardinal). >Sanjeev -- Mitchell Spector Dept. of Computer Science and Software Engineering Seattle University E-mail: spector%sumax.uucp@beaver.cs.washington.edu
rld@function.mps.ohio-state.edu (Randall L Dougherty) (08/04/90)
In article <1033@fornax.UUCP> mahajan@fornax.UUCP (Sanjeev Mahajan) writes: >It is known (I forget the reference) that all Borel games are determinate, ... >My question is this: Let us, for simplicity, consider only closed games. ... >the argument that 'there is a first move ...' is in some vague sense >non-constructive. So my question is, is there a constructive version >of this theorem, or does the question even make sense. One way >of formulating the constructive version would be as follows: if >for all computable strategies s of player II, one can uniformly compute, >in a recursive index of s, a computable strategy s' of player I such that >player II does not win then one can construct (uniformly in an index of >the algorithm that computes s' from s) a computable strategy for player I >such that for all computable strategies of player II, player I wins. >If this statement is not true, can it be modified in some non-trivial way, >so that it is true. A more standard way of stating this question would be: do computable closed games have computable winning strategies? A closed set is considered to be computable if there is an algorithm for generating a list (probably infinite) of basic open sets whose union is the complement of the given closed set. It turns out that the answer to this is negative. There are computable clopen games (both the winning set and its complement are computable closed sets) such that neither player has a computable winning strategy. In fact, to find winning strategies for all computable clopen games, one has to go arbitrarily high up in the hyperarithmetic hierarchy (the computable analogue of the Borel hierarchy; level 0 is the recursive sets, level 1 is the recursively enumerable sets and their complements, etc.). This result appears as 6E.8 from "Descriptive Set Theory" by Y. Moschovakis. This also gives a negative answer to the original formulation above. If we are given a computable clopen game such that player I has a winning strategy but no computable winning strategy, then any given strategy for player II must fail, and in fact must fail after finitely many steps, since the game is clopen. To find a strategy for player I which beats this strategy for II, just search through all finite sequences of moves until one is found for which II's strategy has already failed; this is clearly a computable process. On the other hand, since no computable strategy for I is a winning strategy, the same argument shows that, given a computable strategy for I, II can find a computable strategy which beats it (just search for a suitable finite sequence of moves and then always play 0). Given these results, it is unlikely that any nontrivial reformulation of the original question (without drastic restrictions) will have a positive answer. Randall Dougherty [Disclaimer out of order] Internet: rld@function.mps.ohio-state.edu UUCP: ...!{att,pyramid}!osu-cis!function.mps.ohio-state.edu!rld "I have yet to see any problem, however complicated, that when looked at in the right way didn't become still more complicated." Poul Anderson, "Call Me Joe"