Talk:Determinacy

Rationale for this page

I can easily imagine someone stumbling across this page and thinking it's an unnecessary duplication of Axiom of determinacy, an article of long standing, and ask why I don't simply try to improve that page.

Well, that was my thought originally, but I was running into all sorts of difficulties figuring out where things should go. Axiom of determinacy didn't have a good definition of "game", "strategy", or "winning strategy", and it wasn't clear where to put them. There's a winning strategy article, but it wants to be useful to game theorists as well, which was too much of a constraint.

Moreover, lots of times one wants to talk about determinacy but is not, in context, particularly interested in the axiom of determinacy. In particular, several pages had links that looked like [[Axiom of determinacy|determinacy]], when AD was perhaps not the main point of interest.

So it occurred to me that there should be a central article about determinacy in general. This is it, or rather the start of it. My vision is that this article will give the basic notions and say something about how they stand in relation to each other. Then there will be links out to more detailed articles on particular topics, such as axiom of determinacy, axiom of real determinacy, projective determinacy, long games, Blackwell games, axiom of quasideterminacy.

This article should be the central reference point for the new Category:Determinacy. If a major aspect of determinacy theory has been left out, then ideally in addition to writing an article on that particular topic, a new section or subsection should be added to this article, describing the topic briefly and saying how it relates to the other determinacy topics. --Trovatore 05:46, 2 September 2005 (UTC)

Too technical

This page needs some help to make it more accessible. I have a semi-math background (CS + statistics) and I have no idea what is going on. This needs a bit of a gentler intro (like the one for NP vs. P article which is very good ) novacatz 13:17, 13 January 2006 (UTC)

Well, that's what I had in mind for the Determinacy#Basic notions section. That strikes me as being of roughly the same level of technicality as the lead section of Complexity classes P and NP. Would you look over the "Basic notions" section again and see if you agree, and if not, let me know where it is you get lost? (As for the rest of the article, I wouldn't really expect it to be accessible to anyone without a set theory background; it's an inherently technical subject.) Thanks, Trovatore 00:13, 14 January 2006 (UTC)

Currently, the basic notions section reads like a math textbook (cf. 'firstly we shall consider...' and 'More formally, ... , recall that the latter consists of...'). If you look at the gentle introduction of NP vs. P article intro, you will see they spend a lot of time explaining what is the problem using layman English (cf. the 'time space tradeoff' has an explanation what 'time' mean and what 'space' means. You can see that the page has a lot of somewhat loose descriptions that are useful on helping people grasp why the area is interesting (eg. 'NP Complete problems can be loosely described as...'). For determinacy - the intro is a bit weak on why the field is important (some examples might help) and starts getting into the results without explaning why they are significant (eg. determinacy from ZFC). Someone with some elementary set theory knowledge (me) can appeciate this result a lot more if some explaination is provided on interepetations of the result. novacatz 04:58, 14 January 2006 (UTC)

Query

What does this phrase mean? (for example, if we say that Black wins draws at chess) Stephen B Streater 07:54, 1 April 2006 (UTC)

It means, if we modify the rules of chess, keeping everything the same except that if the play ends in a draw according to traditional chess, we'll say that Black has won. It hadn't occurred to me that this wasn't clear. Can you think of better, but still hopefully concise, language? --Trovatore 15:28, 1 April 2006 (UTC)

I misread "draws" as a verb like "wins". It makes sense as a noun. How about "wins all draws"? Stephen B Streater 16:37, 1 April 2006 (UTC)

Or "wins all drawn positions". Stephen B Streater 16:37, 1 April 2006 (UTC)

Go for it. You might also mention that Black should win if play continues forever (that's optional because it doesn't really matter; in any play that continues forever there are opportunities for Black to claim a draw, and therefore a win). --Trovatore 16:40, 1 April 2006 (UTC)

I've made the first change. Is your second point about play continuing for ever referring only to the modified chess (ie repeated positions leading to a draw)? Presumably there are games which can go on for ever without leading to a draw eg two sides take turns to write down numbers and the one with the biggest number written down wins. I'll have to think this game through to see if it counts as a game in this article, as the game may never finish but it never be obvious this is going to happen so never be a draw either. Stephen B Streater 18:37, 1 April 2006 (UTC)

Oh yes, that point was specific to chess. In most of the interesting cases studied, play can go on forever without any finite part of the play determining the winner. (However I don't really follow your "biggest number" example; why should the set of numbers written down have a greatest element?) --Trovatore 18:40, 1 April 2006 (UTC)

Thanks - I'll put something in, though the chess example is getting quite long, particularly as we can't necessarily assume that everyone understands the draw-by-repetition rule - I might put all the chess bits together and not in brackets. The game I described may not have a biggest element, but it may do. But if it did have a biggest element, I was thinking you wouldn't know in finite time, so couldn't end the game. But then perhaps you could find the maximum element in an infinite set. Stephen B Streater 19:20, 1 April 2006 (UTC)

An infinite set of naturals cannot have a maximal element. However, you could make rules like:

• If there is a greatest number played, then the player who played it, wins. If both players have played that number, then the first one to play it wins.
• If there is no greatest number played, then the second player wins.

This game is trivially a win for the second player, who can guarantee that no greatest number is played, just by playing ever-bigger numbers on subsequent plays. But it is an example of a game whose winning condition is not determined by any finite part of the play (after any finitely many moves, it is still possible for either player to win; while the second player can always force a win if he wants to, there's no guarantee that he will). --Trovatore 19:26, 1 April 2006 (UTC)

chess example

So I agree that the wording is now clearer, but I see a couple of problems:

• You assert that "Black can eventually force a win", which assumes that unmodified chess is not an outright win for White. Surely this is still unknown?

• Yes - it is unknown whether white can force a win in chess. I assumed that if play continued long enough then repetition would have occurred, so Black could claim a draw/win. Stephen B Streater 21:47, 1 April 2006 (UTC)

I think your wording makes this clear. Stephen B Streater 21:49, 1 April 2006 (UTC)

• You've lost the point about the connection with clopen sets. --Trovatore 19:39, 1 April 2006 (UTC)

Fixed the first point. I await your input on the second (your help here could be very useful in making this section accessible). --Trovatore 21:33, 1 April 2006 (UTC)

I didn't change the mention of clopen sets - it is now in the first paragraph general description. Would you prefer it to be referred to again in the particular example of modified chess? Stephen B Streater 21:47, 1 April 2006 (UTC)

Sorry, you're right; I looked at the diff too fast. --Trovatore 23:03, 1 April 2006 (UTC)

• The article mentions a revised form of chess (where a draw is changed to a win for black), but neglects to address the primary game of chess. I did start a little work in the article to remedy this.LithiumFlash (talk) 21:32, 26 March 2017 (UTC)

  I am not entirely convinced by your changes as they stand. Determinacy is a branch of set theory; it's not really about games played for entertainment. Those are just a convenient language to use to get across the ideas. From a set-theory standpoint, there is little gain in adding the possibility of a draw, and it is not usually done (except maybe in the context of Blackwell games).

  Will have to think about how the point could be addressed, but I don't think extending the notion of "determined" to games that have draws is the right way to go here. --Trovatore (talk) 22:04, 26 March 2017 (UTC)

The article already mentions chess (albeit a revision of the game). If this branch of mathematics can say nothing about the real game of chess, then it has a weakness in the sense it is of little value for games which can end in a draw. If correct, the article should say so in the introductory paragraph, so people who have an interest in real games know to look elsewhere.

fyi, one of the later sections in the article "Games of imperfect information" would lead one to believe that the first half of the article pertains to games of "perfect information", i.e. chess.LithiumFlash (talk) 02:07, 27 March 2017 (UTC)

Discussion from the AC page

Aleph4 pointed out at Talk:Axiom of choice that determinacy for games on arbitary sets implies the axiom of choice, and also implies that a countable union of countable sets is countable. The second result can be modified to show in AD that a countable union of countable sets of reals is countable. These facts are very interesting to me and ought to appear here. Also, Martin's later paper on Borel Determinacy would be good to reference; it is much easier to read than his first one from the Annals. I will get to this sometime, so you can view this message as a reminder to myself as much as a prod to everyone else. CMummert 12:09, 6 October 2006 (UTC)

Split out Gale-Stewart games?

I want to suggest making an article on Gale-Stewart games, which would be an expansion of the Games section here. Then this article could just have a summary of the topic with a link to the main article. The topics for the Gale-Stewart games article would be:

• The definition of a Gale-Stewart game on $X^{\omega }$ where X is any set (as in Martin's paper on Borel determinacy). The specific cases for Cantor and Baire space.
• The definition of a winning strategy.
• A statement of the theorem that closed games are determined.
• A link to Determinacy.

I am willing to do the writing; I want to see if there are objections before I do it. CMummert 17:37, 15 November 2006 (UTC)

Well, I guess my concern is, what exactly is a Gale–Stewart game? One with a clopen payoff set? Is this really standard terminology? Gale's and Stewart's result is key, of course, but I really don't recall coming across this nomenclature for the games. --Trovatore 19:48, 15 November 2006 (UTC)

A Gale-Stewart game is just a two-player game of perfect information of length ω. This is standard terminology in some parts of the world; a google search turned up quite a few papers such as [1] [2] that use the term without further citation. From JStor, I found that Jockusch uses the term (The Journal of Symbolic Logic Vol. 38, No. 2 (Jun., 1973), pp. 293-294) and so does Becker (The Journal of Symbolic Logic Vol. 50, No. 1 (Mar., 1985), pp. 110-122). So I think it is standard. CMummert 20:35, 15 November 2006 (UTC)

Hm, still not too excited about giving the concept a name I'd never really heard for it. This is the content I'd intended to treat in the "games played on trees" section of the article. --Trovatore 21:36, 15 November 2006 (UTC)

The idea I had in mind is to separate the material on games (which don't require strong axioms to define and are of interest in ZFC) from the material on determinacy beyond ZFC, which is more esoteric. Since Gale-Stewart game is a standard term describing these games, that was the title I suggested, but any other title is OK with me. The present article, if all the sections were filled in, would be quite long and intimidating. CMummert 22:02, 15 November 2006 (UTC)

The article might be a good idea. I think it would be unfortunate, though, if it presented ZFC as some sort of natural dividing line. I really don't think it is. --Trovatore 07:07, 9 December 2006 (UTC)

Angle brackets

I think the angle brackets should be written as "\langle" and "\rangle" instead of "<" and ">". --Trigamma 18:15, 8 December 2006 (UTC)

I don't like \langle and \rangle; never have. They are too tall, and the angle is too obtuse. It would be nice to have something a little bit in between. --Trovatore 18:46, 8 December 2006 (UTC)

My problem is that < and > are typeset the wrong way: they are not treated as delimiters but as binary relations. You can see that in the first formula, where the closing > is next to the \in. But by the way: Why do you use angle brackets at all and not round parentheses? --Trigamma 19:54, 8 December 2006 (UTC)

Um. In my experience, angle brackets are just more usual, in set theory, as a way to indicate tuples, than are round brackets. I don't really know why this should be so. Maybe they have fewer other meanings (for example, (αβ) could be the pair <α,β> or the open interval from α to β). --Trovatore 21:09, 8 December 2006 (UTC)

Determinacy from ZFC

Quote from the article:

"Martin's proof uses the powerset axiom in an essential way. There is a level-by-level result detailing what fragment of the powerset axiom is necessary to guarantee determinacy through what level of the Borel hierarchy."

I am curious about what "fragment of the powerset axiom" means more precisely. Does it mean that in this and that model, built not using the full power set operation but something that is possibly weaker (like when L is built compared to when V is built), then determinacy is guaranteed through a lower degree inte the model? YohanN7 (talk) 14:47, 14 September 2009 (UTC)

It means: how many iterations of the powerset axiom are required in order to guarantee the desired amount of determinacy. In other words, there is result giving the minimum necessary α for V_α to be a model of the desired amount of determinacy. Now the powerset axiom itself says nothing about iteration; it is really the axiom of replacement that is used to ensure that the ordinals in the model are long enough. — Carl (CBM · talk) 15:18, 14 September 2009 (UTC)

Ah, that explains it. Would you mind if I attempt a rewording of that passage in the article? YohanN7 (talk) 16:37, 14 September 2009 (UTC)

It appears to be done already. Things happen quickly here;) YohanN7 (talk) 16:49, 14 September 2009 (UTC)

Blackwell Games

Didn't Donald Martin prove that determinacy for a set implies Blackwell determinacy for that set? I don't think that's mentioned on the page (and I don't have access to the paper).Chimpionspeak (talk) 17:33, 12 March 2011 (UTC)

I don't believe he ever proved that, no, though I wouldn't swear to it. I think that's still open. Generally what has been proved is consistent with that (e.g. I think that the large cardinals you need to prove Π¹₁-determinacy are the same as you need to prove Π¹₁-Blackwell determinacy) but as far as I know the proof has not been uniformized. I could be completely wrong though. Get in touch with Benedikt Löwe if you really want to know. --Trovatore (talk) 21:21, 12 March 2011 (UTC)

Hi, I checked this, and it is as I remembered. Have made the necessary changes. Chimpionspeak (talk) 16:30, 14 March 2011 (UTC)

I just took a ten-second look at the paper, and I don't actually see that result. Could you point me to it? What it says in the opening is that if all (length-ω on the naturals) perfect-information games are determined, then so are all Blackwell games, which is not the same thing as saying that if an individual game is determined then it's determined as a Blackwell game. --Trovatore (talk) 18:23, 14 March 2011 (UTC)

I found Martin's 1998 paper. What he says is

[W]e associate with each Blackwell game a family of perfect information games, and we show that the (mixed strategy) determinacy of the former follows from the (pure strategy) determinacy of the latter. The complexity of the payoff function for the Blackwell game is approximately the same as the complexity of the payoff sets for the perfect information games. In particular, this means that the determinacy of Blackwell games with Borel measurable payoff function follows from the known determinacy of perfect information games with Borel payoff sets.

So this is close to the idea you were trying to get across, but does not appear to justify the precise text you added. --Trovatore (talk) 19:00, 14 March 2011 (UTC)

I think I have the outline of a refutation of the game-by-game claim. First, consider the trivial "matching game": The players play zeroes and ones and, at the end, II wins if his every move exactly matches I's immediately previous move. Clearly II has a winning strategy for this game, as a perfect-information game. On the other hand, as a Blackwell game, I simply plays each value with probability 0.5, and then any strategy for II has value 0 for II.

That by itself doesn't refute the claim — the game is determined in both senses; it just has a different winner.

But now take some non-Blackwell-determined game G (with a 0-1 payoff function). Now I and II play the matching game on even pairs of moves, and G on odd pairs of moves. For I to win, he has to win both games.

As a perfect-information game, this is a win for II. He just plays his winning strategy on the even pairs of moves, and doesn't care what happens on the odd.

But as a Blackwell game, presumably I plays his winning strategy on the even pairs, and then the game (more or less) reduces to G on the odd pairs, which is not determined.

There's some work to be done in the "(more or less)" part. You have to make sure that the even moves don't in some tricky way help one of the players win on the odd moves. But I'm confident it can be done (might require a careful choice of G). --Trovatore (talk) 20:28, 14 March 2011 (UTC)

Right, there is some subtlety that I had missed out on, sorry. I searched a little more, and theorems 7 and 12 here say that for boldface pointclasses, determinacy for omega-games in the pointclass implies Blackwell-determinacy for the same pointclass. Have made the necessary changes. Chimpionspeak (talk) 20:37, 14 March 2011 (UTC)

We were editing at the same time. I think your argument should work (again, modulo the "more or less"). I am a little embarrassed to admit that I do not know much about Blackwell games! But your argument does make sense. Chimpionspeak (talk) 20:48, 14 March 2011 (UTC)

Does an infinite game ever end?

Yes it does. At least in the sense that if both players actually have strategies as described in the article, then the recursion theorem guarantees that there is a sequence f:ω->ω whose values can be matched against the lookup table. This escaped me when I first read the article (quite some time ago). Perhaps the article could point out that (and why) the infinite games end? YohanN7 (talk) 19:57, 5 April 2011 (UTC)

Payoff sets

Hi!

Q: Does the payoff set (A in the article) by definition include finite sequences too?

If not, the subsection "Winning Strategies" need to be clarified. I.e. there is a sequence in A beginning with the old moves plus our new one.

/Johan — Preceding unsigned comment added by 90.225.13.43 (talk) 09:52, 5 April 2012 (UTC)

I'm not entirely clear what you're saying here. The sequence

$\langle \sigma (\langle \rangle ),a_{1},\sigma (\langle \sigma (\langle \rangle ),a_{1}\rangle ),a_{3},\ldots \rangle$

is infinite (that's what the dot dot dot means), so I don't see any issue raised by the fact that A consists of infinite sequences. Did you have some other piece of text in mind? --Trovatore (talk) 21:59, 5 April 2012 (UTC)

Inline LaTeX

Some of my edits adding inline LaTeX were reverted because of "sizing issues". However, there are still sections where inline LaTeX is used despite the objections to my edits with respect to "sizing issues".

While the issue is mainly aesthetic, I think that typesetting consistency would aid the readability of the article. 2601:8:AB80:7C0:573:A3AB:E740:805B (talk) 01:55, 20 May 2014 (UTC)

Yeah, I noticed that later. Those should be converted to HTML as well. I'll try to find some time and take care of it. --Trovatore (talk) 02:03, 20 May 2014 (UTC)

Done 2601:8:AB80:7C0:573:A3AB:E740:805B (talk) 02:09, 20 May 2014 (UTC)

Thanks! --Trovatore (talk) 02:42, 20 May 2014 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Determinacy. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Corrected formatting/usage for http://lara.epfl.ch/w/_media/sav08:rabin69s2s.pdf

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

Y An editor has reviewed this edit and fixed any errors that were found.

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—^{cyberbot II}_{Talk to my owner:Online} 09:50, 25 May 2016 (UTC)

What is definition of a "class" of games?

Can one game within a class be determined, and another not? If so, in "Determined games" we should revise:

A (class of) game(s) is determined if for all instances of the game there is a winning strategy for one player (not necessarily the same player for each instance), or a drawing strategy for both players.

to:

A game is determined if there is a winning strategy for one player, or a drawing strategy for both players.

The latter is simpler and correct. The former may be too broad and I think not always strictly true.LithiumFlash (talk) 01:44, 27 March 2017 (UTC)

"Class" here means pointclass. Specifically one closed downward under Wadge reducibility, and maybe with some other properties that aren't specified too carefully. --Trovatore (talk) 02:03, 27 March 2017 (UTC)

Understood. If that is the case, after clarifying and recasting the sentence, the article should say so. But I won't change anything yet at this point. Let's see if there is other commentary. Then we can decide if we should make this point in a way that is simple, general, and to the point. Or be more specific, carefully amending the sentence with the restricted definition as you mention. Thanks.LithiumFlash (talk) 02:18, 27 March 2017 (UTC)

Recent edits (Regarding Games with Draws)

I don't want to give the impression that I'm trying to prevent all change to this article. Not at all. I've done a lot of work on it, but I'll freely admit that it isn't really very good yet and could use a lot of work.

But I think the recent edits kind of miss the point. Determinacy is a subfield of set theory, not game theory. Game theory as developed by Nash et al is basically irrelevant, except maybe for the very most elementary cases. So we don't need to talk about "strictly determined games"; in the context of work done in this field, they are simply called "determined". We don't need to worry about games that have draws, because they don't add any extra power to the theory and therefore are not generally considered (maybe except in the context of Blackwell games).

One edit that I thought was sort of telling was the addition of text that said "some have suggested" that some infinite games of perfect information might not be determined. It's not just "suggested"; it's proven. (You do need the axiom of choice.) It would probably be a good thing to state this more prominently (right now, there's an allusion to it in the axiom of determinacy subsection, but you could easily miss it, and even if you see it it takes a step or two to figure out that that's what it's saying).

So I think it's a good thing that someone is looking at the article and trying to improve it. But I think the recent edits have not really been improvements withal. Let's discuss ideas here on the talk page. --Trovatore (talk) 02:18, 27 March 2017 (UTC)

That's fine. I do feel that if this branch of mathematics does not deal with games that can end in a draw, it should say so right in the first paragraph. Many people who play and study chess have asked if chess is a determined game or not. It seems every time someone tries to answer the question they change the definition of chess. And this article also does not satisfactorily answer the question either (despite chess being one of the most popular and mathematically studied of all games). We'll need to work on it, but I'll let it stand for now. Thanks, LithiumFlash (talk) 02:35, 27 March 2017 (UTC)

Oh, good point. You know, I may have overreacted on the game theory language. I think it's fine to connect the concepts with the corresponding ones from game theory. I just wouldn't want the game theory terminology to be taken as primary in this article.

I think determinacy theorists, asked if chess is a determined game, would say "yes" pretty uncritically, just adjusting in their heads for the possibility of draws and doing "the obvious thing". We can try to work that in somehow. Needs sources (so does a lot of the article, actually).

It's not so much that the branch of mathematics doesn't deal with games that can have draws as it is that the branch of mathematics really doesn't care about the individual games per se. The goal is to prove other things, using the games as a tool. Allowing draws doesn't seem to help you do that in most cases, so most formulations just don't include them. If you care about the games, then of course you want to deal with the question of draws, but if you don't, then it's just a distraction. --Trovatore (talk) 02:57, 27 March 2017 (UTC)

Please notice this reference^ which was with my contribution (but now deleted). It is a popular youtube video backed up by very good academic material. The video examines the game of chess, and infinite chess, saying both are determined games. But early in the video (0:55) the host says they are considering chess that "does not have draws". Many viewer comments seem to suggest this was overlooked, causing confusion. So in general, people (myself included) are still confused as to whether (real) chess is a determined game or not. This Wikipedia article currently provides no help in answering that. I think this article should either quickly inform readers that this branch of mathematics does not address such games. Or, it should provide a clear and concise answer. I'm inclined to add a statement in the introductory paragraphs that reads something such as "The study of Determinacy excludes games which can end in draws, and therefore contributes nothing for the study of games such as Tic-tac-toe, Chopsticks, Checkers, and Chess. Readers seeking mathematical analysis of such games should instead refer to 'such-and-such'".LithiumFlash (talk) 12:46, 27 March 2017 (UTC)

I have added a reference and two sentences to the lede. Essentially every set theory book that mentions determinacy will have the definition of what it means for a game to be determined, but in order to choose one I went with the book by Kechris. This article, in any case, is not about chess as a real-world game, it is about determinacy as studied in set theory. So I don't think we need to go into great depth about game with ties, which do not seem to be used in set theory in my experience. — Carl (CBM · talk) 13:02, 27 March 2017 (UTC)

Looks good. Although the article is not about chess, it talks about chess (in "Determinacy from elementary considerations"). It also talks about Tic-tac-Toe. (Both are real world games that can end in draws). I did add the reference (below) to the article to support a statement the article makes about the (modified) game of chess. If the article talks about Tic-Tac-Toe and chess, I would eventually like to see in the article how those games are classified (determined games or not). Thanks for your amendments and contributions to the article.LithiumFlash (talk) 13:55, 27 March 2017 (UTC)

References

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Determinacy. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20061109170500/http://seminariomatematico.dm.unito.it/rendiconti/61-4/393.pdf to http://seminariomatematico.dm.unito.it/rendiconti/61-4/393.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 18 January 2022).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 23:56, 11 January 2018 (UTC)