Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello,

Intro about standard two player games

Gale-Stewart games are the well-known games played by two Players $I$ and $II$, which in turn play natural numbers for infinitely many ($\omega$) steps. The "outcome" of a play is an element is in $\omega^{\omega}$. Given an objective $A\subseteq \omega^{\omega}$, Player $I$ wins a play, if the outcome in $A$. He loses (and Player $II$ wins) otherwise. A strategy for a player is a function $\sigma : \omega^{ * }\rightarrow \omega$ which, given a history of previously played moves (an element in $\omega^{*}$) tells the player how to choose the following natural number. A game with objective $A$ is determined if one of the two player has a winning strategy. The notion of determinacy, for a given (class of) set(s) $A$, is of course very important in set theory.

Imperfect information two player games

Games recently are also becoming more and more important in theoretical computer science. And partial information games are being studied as well. Let us define, here, a partial information Gale Stewart game, as a standard G.S. game, with the difference that the set of strategies available to the players is a (proper) subset $\Sigma\subseteq \omega^{ * }\rightarrow \omega$.

As an example, we might model that Players do not have memory of the past moves, by restricting the set of strategies to the set

$\Sigma=\{ \sigma : \sigma( s ) = \sigma (t)$ if $last(s)=last(t) \}$,

where $last: \omega^{ * } \rightarrow \omega$ returns the last natural number in the input sequence. These strategies are usually called positional or memoryless strategies.

It is an interesting question to see what classes of sets are determined under positional strategies. But in general I suspect it is interesting to study determinacy under many other sets $\Sigma$ of strategies, in other words, it should be interesting enough to study partial information games.

The case of Blackwell's games

A famous class of imperfect information G.S. games is the class of Blackwell's games. It can be described as follows: the game is played by two players, $I$ and $II$, which at each turn, play independently and at the same time two naturals $a$ and $b$ chosen from a finite set $ K=\{0,\dots,k\}$ for some $k\in\mathbb{N}$. A play takes $\omega$ steps. The result of a play is an element in $(K\times K)^{\omega}$. Given an objective $W\subseteq (K\times K)^{\omega}$, Player $I$ wins if the produced play is in $W$. The set of strategies for the two players in a Blackwell game, is given by the functions $\sigma: (K\times K)^{*} \rightarrow K$. One is often interested in mixed strategies, i.e. randomized strategies; one can model randomized strategies, abstractly, as probability measures over the Borel-sigma algebra on the space of the strategies).

Note that Blackwell's games can be defined as imperfect information G.S. games (in the sense defined above), if desired.

Blackwell's games have been studied by set theorists. For instance D. Martin proved that (in ZFC) all Blackwell's game (with Borel objectives) are determined under mixed strategies. (here determinacy has a slightly different meaning than usual).

Questions

So after this discussion, my questions are:

Q1: Do imperfect informations G.S. games play an important (or any) role in Set theory? I'm not aware of particular use of them. For instance in Jach's Set theory, I think there is no mention at all about Blackwell's games. Could you point to some relevant literature if your answer is positive? Or even any "feeling" about their potential use?

Q2: In particular, do Blackwell's game play any important (or any) role in Set theory? Just the fact that Martin's worked on this, suggests (to me) that they actually might have some role.

An application, of Blackwell's games (or anyway similar concepts) i'm aware of is in Logic, and it can be found in Hintikka's works on Independence friendly logics, where Blackwell's games are used to give "game semantics" to this/these logic(s).

Thank you in advance for any answer!

Matteo Mio

share|improve this question
    
In computer science (I'm not sure about game theory) imperfect information games are those in which you don't know everything that your opponent has done, and imperfect recall games are those in which you don't remember everything that you (or maybe your team) has done. –  Peter Shor Dec 19 '10 at 17:19
    
Hello Peter. Yes both these two notion can be "encoded", in the general definition of Imperfect Inf. games I proposed in my question, as particular sets $\Sigma$. –  Matteo Mio Dec 19 '10 at 17:26
    
Perhaps I should explain myself better. Since the two Players $I$ and $II$ takes turns (and $I$ starts the game), an imperfect recall strategy for Player $I$, say, is a function $\sigma:\omega^{*}\rightarrow \omega$, with some constraints on the choices that $\sigma$ can make on even histories (which corresponds to the positions where $I$ play: $0, 2, 4, \dots$. So an imperfect recall game is just an imperfect information G.S. game (in the sense defined in the question) where the available strategies are constrainted appropriately. –  Matteo Mio Dec 19 '10 at 17:31

2 Answers 2

Thank you for your posting and question. > Matteo

Thank you very much for your detailed explanation and positive comments on my work. > Andres

I also do not know about applications of Blackwell determinacy to set theory. One question would be whether Bl-AD_{omega_1} is consistent or not, where Bl-AD_{omega_1} means that every subset of omega_1^{omega} is Blackwell determined. As is known, the counter axiom (AD_{omega_1}) in Gale-Stewart games is inconsistent with ZF. If Bl-AD_{omega_1} (or some weaker version of it) is consistent, then one might be able to hope to use it to analyze the theory of H_{omega_3}, e.g., ideals on omega_2. For example, one might wonder if one could use such strong axioms to force the existence of saturated ideals on omega_2 in the analogy of Steel-Van Wesep forcing of P_max forcing.

Nowadays, many set theorists are working on the theory of H_{omega_2} while we do not know almost anything about H_{omega_3} and recently there is a development of descriptive set theory in P(omega_1) by Sy Friedman, Tapani Hyttinen, Vadim Kulikov, Philipp Schilicht et al. I am kind of hoping that if there is any connection between such strong axioms of Blackwell determinacy and descriptive set theory in P(omega_1) and am wondering whether one could attack many problems about H_{omega_3} by developing and using such generalized descriptive set theory.

But these are all my imagination and nothing has been seriously done yet.

Any comments and questions to this answer are welcome.

share|improve this answer
    
MO e youkoso, Daisuke, welcome to MO! –  Joel David Hamkins Dec 20 '10 at 0:17
    
Daisuke! Nice to see you here. –  Andres Caicedo Dec 20 '10 at 1:27
    
I second (third?) the last two comments. –  Stefan Geschke Dec 20 '10 at 2:20
    
Thanks Daisuke! great answer! –  Matteo Mio Dec 20 '10 at 12:58

Hi Matteo,

I am not aware of any specific applications of Blackwell's games within set theory that cannot be obtained from traditional games. I think the main reason for this and for why they do not appear in Jech's book has nothing to do with importance and is simply due to the fact that their (set theoretic) theory is much more recent and still being developed. I actually think that from the set theoretic point of view they are very interesting, and certainly worth studying as these are games that outside of set theory are more widely used than their perfect information counterparts, but we will need more time to see whether we can actually (genuinely) apply them.

For now, there has been significant work on them, and it has concentrated on studying the consistency strength of the assumption that they are determined, and whether this determinacy directly implies/is implied by determinacy in the usual sense. Besides the original work of Martin, there are some recent additional results, most notably

  • Donald A. Martin, Marco Vervoort, and Itay Neeman, "The strength of Blackwell determinacy". J. of Symb. Logic, vol. 68 (2003), pp. 615–636,

and the recent graduate thesis of Daisuke Ikegami, Games in Set Theory and Logic, together with his recent co-authored preprints,

  • David de Kloet, Benedikt Löwe and Daisuke Ikegami, "The Axiom of Real Blackwell Determinacy",
  • W. Hugh Woodin and Daisuke Ikegami, "Real Determinacy and Real Blackwell Determinacy",

available from his page. I've followed the work of Daisuke for the last year of so, and I think you will find the mathematics in these papers to be not just significant but also quite elegant.

share|improve this answer
    
Thanks Andreas! –  Matteo Mio Dec 19 '10 at 17:34
    
But Matteo, Andrés's name is Andrés, not Andreas, although that is also a very excellent name for logic here on MO. –  Joel David Hamkins Dec 20 '10 at 4:50
    
ops!! I apologize! :-) –  Matteo Mio Dec 20 '10 at 9:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.