Xref: utzoo sci.math:11868 comp.theory:912
Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!mit-eddie!uw-beaver!ubc-cs!fornax!mahajan
From: mahajan@fornax.UUCP (Sanjeev Mahajan)
Newsgroups: sci.math,comp.theory
Subject: Infinite games
Keywords: Determinacy, Borel games.
Message-ID: <1033@fornax.UUCP>
Date: 1 Aug 90 22:35:43 GMT
Organization: School of Computing Science, SFU, Burnaby, B.C. Canada
Lines: 30

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