2
$\begingroup$

Generalized Sprague-Grundy theory has been used to analyze finite impartial loopy games with normal play. There is a nice short account by Mark S. in this answer. It was introduced by Cedric Smith in the 60s, and developed independently by Fraenkel and others.

The theory is usually described in the setting of finite directed graphs (see for example section IV.4 of Siegel's Combinatorial Game Theory).

I see that Fraenkl and Rahat (2001) looked at the case of infinite directed graphs which are locally path-bounded, i.e. where for any vertex $v$, the sup of the length of all paths starting at $v$ is finite.

I'm interested in the case of directed graphs which are allowed to contain infinite paths. Suppose we assume that every vertex has finite outdegree. It seems to me that much of the structure (e.g. all the results of Section IV.4 of Siegel) extends unchanged to this setting. In particular, every such game has a "loopy nim value" which is either a non-negative integer (in which case the game is equivalent to a finite nim heap) or of the form $\infty(\mathcal{A})$ for some subset $\mathcal{A}$ of $\mathbb{N}$ (see the answer by Mark S. linked above).

(Once we allow infinite paths, it's no longer important to allow cycles, since we can create multiple "copies" of each node. Without loss of generality one could consider "game trees", i.e. rooted trees directed away from the root, with all degrees finite.)

Can someone point me to a reference covering such games? Does the generalized Sprague-Grundy theory go through straightforwardly to that context as I imagine?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

I am not sure what you imagine, but once one makes the move to games with infinite play, then various set-theoretic issues come to light, and the subject becomes more set-theoretic and less like combinatorial game theory. The keyword is determinacy, and there is a very rich literature.

A Gale-Stewart game is a game allowing infinite play, where the winner is determined by a certain set $A$ of plays. So player I is trying to play into the payoff set and player II is trying to play out of the payoff set.

The Gale-Stewert theorem (1953) asserts that any game whose payoff set is open in the product topology is determined, meaning that one of the players has a winning strategy. This is generalized by Martin's theorem establishing Borel determinacy, generalizing from open sets to Borel sets.

The axiom of choice implies that there are non-determined sets, but meanwhile, if one drops the axiom of choice, then the assertion that every game has a winning strategy, known as the axiom of determinacy, has many extremely attractive consequences, such as the fact that all sets of reals are Lebesgue measurable and every set has the property of Baire, among others. The axiom of determinacy is equiconsistent over ZF+DC with the existence of infinitely many Woodin cardinals.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Thanks Joel. The theory is all fine for "loopy" games, defined on finite graphs but allowing cycles. There one already has infinite play. I am asking whether that theory (the "generalized Sprague-Grundy theory") extends to the case of infinite graphs with finite degrees. Very specifically, if you like, whether every such game has a "loopy nim value". See the answer by Mark S. that I linked to, or Chapter IV.4 of Siegel's book. I think the assumption of finite degrees gets around the need for any difficult set theory here. $\endgroup$
    – James Martin
    Commented Aug 13, 2018 at 21:04
  • 1
    $\begingroup$ Yes, my answer is that in the general context of infinite play, then for games on countable graphs, even with finite degree, the analysis becomes completely set-theoretic, and quickly things become totally unlike the case of combinatorial game theory. The simplest case of the new realm may be clopen games, which are games that all end in finitely many moves (but not necessarily uniformly bounded), and in this case, one still has determinacy, by the fundamental theorem of finite games, also known as Zermelo's theorem. $\endgroup$
    – Joel David Hamkins
    Commented Aug 13, 2018 at 21:20
  • 2
    $\begingroup$ Finite degree is a limitation on the number of moves for a player at each turn, but these set-theoretic issues even with games on $\{0,1\}$, where each player has only two moves. $\endgroup$
    – Joel David Hamkins
    Commented Aug 13, 2018 at 21:21
  • 2
    $\begingroup$ Those directions are fascinating, but I don't think relevant to my actual question. Maybe I should make clear that this is all about games with "normal play", i.e. the game terminates if a player has no move, and that player loses. There are three outcome-classes with optimal play: 1st-player win, 2nd-player win, draw. From the finite-degree assumption you get compactness: if a player has a winning strategy, then they can guarantee to win within some finite number of moves. I am pretty confident that the loopy Sprague-Grundy theory does extend, but I don't know if it's written anywhere. $\endgroup$
    – James Martin
    Commented Aug 13, 2018 at 21:42
  • 2
    $\begingroup$ It seems you are not interested in the larger possibilities offered by infinite play, which are extremely fascinating. Meanwhile, your context of normal play does allow for arbitrary clopen games, however, which never have draws, and I'm not sure the extent to which the Sprague Gundy analysis extends into that realm. Perhaps that would be the real answer to your question, which I encourage others to provide. $\endgroup$
    – Joel David Hamkins
    Commented Aug 13, 2018 at 21:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .