Three-player perfect information games are usually undetermined

Recently, I gave the talk Undeterminacy and choice (Indeterminación y elección), at the XVII Colombian Mathematical Congress, in Cali. Slides can be found at my talks page.

The talk addressed the results of my recent paper on with Richard Ketchersid, mentioned in my previous entry, and some extensions, about which I expect to be posting soon. Afterwards, somebody asked me how much of the theory of determinacy can be extended to three-player (or more) perfect information games. Not much.

The following easy example was suggested by Richard Ketchersid: There is an undetermined one-move game where players I, II, III play 0 or 1, with I playing first, then II, and finally III. To see this, say that and are the numbers played, and that:

Player I wins iff

Player II wins iff and

Player III wins if

(One may think of this game as a perfect information version of paper-rock-scissors.) I imagine this observation is ancient, and would be grateful for a reference.

This entry was posted on Monday, September 7th, 2009 at 4:20 pm and is filed under Conferences. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

2 Responses to Three-player perfect information games are usually undetermined

Marginalia to a theorem of Silver (see also this link) by Keith I. Devlin and R. B. Jensen, 1975. A humble title and yet, undoubtedly, one of the most important papers of all time in set theory.

Given a positive integer $a$, the Ramsey number $R(a)$ is the least $n$ such that whenever the edges of the complete graph $K_n$ are colored using only two colors, we necessarily have a copy of $K_a$ with all its edges of the same color. For example, $R(3)= 6$, which is usually stated by saying that in a party of 6 people, necessarily there are 3 that know e […]

No, this is not consistent. Todorčević has shown in ZF that, in fact, there is no function $F\!:\mathcal W(S)\to S$ with the property you require. Here, $\mathcal W(S)$ is the collection of subsets of $S$ that are well-orderable. This is corollary 6 in MR0793235 (87d:03126). Todorčević, Stevo. Partition relations for partially ordered sets. Acta Math. 155 (1 […]

As suggested by Gerald, the notion was first introduced for groups. Given a directed system of groups, their direct limit was defined as a quotient of their direct product (which was referred to as their "weak product"). The general notion is a clear generalization, although the original reference only deals with groups. As mentioned by Cameron Zwa […]

A database of number fields, by Jürgen Klüners and Gunter Malle. (Note this is not the same as the one mentioned in this answer.) The site also provides links to similar databases.

You do not need much to recover the full ultrapower. In fact, the $\Sigma_1$-weak Skolem hull should suffice, where the latter is defined by using not all Skolem functions but only those for $\Sigma_1$-formulas, and not even that, but only those functions defined as follows: given a $\Sigma_1$ formula $\varphi(t,y_1,\dots,y_n)$, let $f_\varphi:{}^nN\to N$ be […]

I posted this originally as a comment to Alex's answer but, at his suggestion, I am expanding it into a proper answer. This situation actually occurs in practice in infinitary combinatorics: we use the axiom of choice to establish the existence of an object, but its uniqueness then follows without further appeals to choice. I point this out to emphasize […]

I think you may find interesting to browse the webpage of Jon Borwein, which I would call the standard reference for your question. In particular, take a look at the latest version of his talk on "The life of pi" (and its references!), which includes many of the fast converging algorithms and series used in practice for high precision computations […]

The reference you want is MR2768702. Koellner, Peter; Woodin, W. Hugh. Large cardinals from determinacy. Handbook of set theory. Vols. 1, 2, 3, 1951–2119, Springer, Dordrecht, 2010. Other sources (such as the final chapter of Kanamori's book) briefly discuss the result, but this is the only place where the details are given. More recent papers deal with […]

All I know about it is a paper by Benedikt on infinite games with more than two players:

It will be appear in Journal of Applied Logic. But I suspect that this is not the oldest reference for the undeterminacy.

Thanks! The paper looks interesting, and I didn’t know anything about this area.