# A different equivalence relation on partizan combinatorial games

The following definitions are fairly standard, but reworded in a way that will be more appropriate for my question (so what follows is fairly long, but should be easy to read for the experts and might even serve as an introduction to the subject):

• A partizan combinatorial game is a set $G$ (of positions or states), together with an element $x_0 \in G$ (the starting position or initial state) and two relations, $L, R \subseteq G^2$ which we call the blue and red edges of the graph $(G, L\cup R)$ (an edge which is both blue and red can be called green), such that the graph in question is well-founded (=progressively finite, =there is no infinite sequence $z_0,z_1,z_2,\ldots$ of elements of $G$ with $(z_i,z_{i+1}) \in (L\cup R)$ for each $i$). The game is played as follows: starting with $x = x_0$, each player (called Left and Right) selects an edge $(x,y)$ in his respective set ($L$ for Left and $R$ for Right), replacing the position $x$ by its out-neighbor $y$; the player who cannot play loses (something which always happens in finite time by the well-foundedness assumption).

• Define the extensional collapse of a game $G$ as follows: first, remove all vertices unreachable from the starting position; then, repeatedly (transfinitely) identify two vertices $x,x'$ which have the same sets of blue-neighbors and the same sets of red-neighbors (i.e., identify $x,x'$ if $\{y : (x,y) \in L\} = \{y : (x',y) \in L\}$ and the same is true for $R$). Call two games $G,G'$ extensionally equivalent when they have isomorphic extensional collapses and write $G \cong G'$. For example, any two games in which no player has any legal play ($L=R=\varnothing$) are extensionally equivalent to the trivial game $0$ with only one position. Essentially everything will be studied up to extensional equivalence.

• The sum $G'' := G \oplus G'$ of two games $G,G'$ is the Cartesian product $G\times G'$ with starting position $x''_0 := (x_0,x'_0)$ and edge relations $L'' := (L\times\Delta_{G'}) \cup (\Delta_G\times L')$ and similarly for $R''$, where $\Delta$ stands for the diagonal: i.e., playing a move in $G\oplus G'$ consists of playing a move in $G$ xor playing one in $G'$. Clearly this is well-founded, and clearly this operation is compatible with extensional equivalence, and it is commutative and associative (up to extensional equivalence, in fact, even isomorphism). The opposite $-G$ of a game $G$ is the same set $G$ but with $L$ and $R$ exchanged; we write $G \ominus G'$ for $G \oplus (-G')$.

• A game $G$ is Conway-positive when Left has a winning strategy no matter who plays first, Conway-negative when Right has (i.e., $-G$ is positive), and Conway-zero when the second player has a winning strategy. Two games $G,G'$ are Conway-equal when $G-G'$ is Conway-zero. Let me write $G \doteq G'$ for this. It is not hard to see that $\doteq$ is an equivalence relation, which is weaker (=larger) than extensional equivalence.

• The product $G'' := G \otimes G'$ of two games $G,G'$ is defined informally as follows. Its positions will be finite combinations of "plus" and "minus" tokens on the vertices of $G \times G'$. The starting position has a single "plus" token on $(x_0,x'_0)$ (the starting positions of $G$ and $G'$). At each turn, each player chooses a single token ("plus" or "minus"), at $(x,x')$ say, and chooses edges $(x,y)$ from $G$ and $(x',y')$ from $G'$: for a "plus" token, Left must choose two blue edges or two red edges (i.e., $(x,y) \in L$ and $(x',y') \in L'$, or else $(x,y) \in R$ and $(x',y') \in R'$) and Right must choose a blue edge and a red edge; for a "minus" token, it's the reverse (Left chooses a blue edge and a red edge, and Right chooses two blue edges or two red edges); in either case, the token that was at $(x,x')$ is removed and three new tokens are created: two of the same sign as the original token at $(x,y')$ and $(y,x')$, and one of opposite sign at $(y,y')$. In brief, we move from $x\otimes x'$ to $(x\otimes y') \oplus (y\otimes x') \ominus (y\otimes y')$.

The product has some nice properties: it is commutative and associative (up to extensional equivalence), it is distributive over the sum (ditto), has $1$ (defined below) as unit element (again, up to extensional equivalence) and $-G \cong (-1) \otimes G$.

For impartial games (those with $L=R=:E$), Conway-equality is exactly the equality of the Grundy ordinals (the Grundy ordinal of an impartial game $(G,x)$ being recursively defined as the least ordinal not equal to the Grundy ordinal of $(G,y)$ for any out-neighbor $y$ of $x$, i.e., $(x,y) \in E$), and the sum and product operations are compatible with this equivalence, and define over the ordinals two operations called "nim sum" and "nim product" which have plenty of nice properties (e.g., each infinite cardinal is an algebraically closed field of characteristic $2$; Conway calls these "nimbers", a portmanteau of "nim" and "number").

Sadly, whereas the sum is always compatible with Conway equality (if $G_1 \doteq G_2$ then $G_1 \oplus G' \doteq G_2 \oplus G'$), product is not in general. For a counterexample, leg $1$ be the game with two positions $0,1$ and a blue edge between $1$ and $0$, let $2$ be the game with three positions $0,1,2$ and blue edges $L = \{(1,0),(2,0),(2,1)\}$, and let $1\oplus 1$ be the same game as $2$ but without the $(2,0)$ edge (this is, indeed, extensionally equivalent to the sum $1\oplus 1$ as defined above): then $1\oplus 1 \doteq 2$ yet $(1\oplus 1)\otimes * \cong * \oplus * \doteq 0$ is not Conway-equal to $2 \otimes * =: * 2$, where here $*$ and $* 2$ are the same games as $1$ and $2$ but with green (=both blue and red) edges instead of just blue (multiplying by $*$ is extensionally the same as making the game impartial by making all edges green): the Grundy ordinals of $*$ and $*2$ are $1$ and $2$ respectively, so they are not Conway-equal.

So there are two obvious ways to try to solve this problem:

• Restrict the definition of the product $G \otimes N$ for certain games $N$ for which $G \doteq G'$ implies $(G\otimes N) \doteq (G'\otimes N)$. This is Conway's approach in On Numbers and Games, the games $N$ in question being called "numbers" (I'm not sure whether all the games for which $G \doteq G'$ implies $(G\otimes N) \doteq (G'\otimes N)$ are numbers, but numbers satisfy this property). This gives a nice theory where the numbers are a field and the games a partially ordered group, and we can multiply games and numbers, but we can't multiply two games.

• But the other would be to change the equivalence relation $\doteq$, and define a stronger (=smaller, =finer) equivalence relation, say $\triangleq$, by $G\triangleq G'$ iff $(G\otimes H) \doteq (G'\otimes H)$ for all games $H$ (i.e. not only does the second player win $G' \ominus G$, but in fact $(G'\ominus G) \otimes H$ for all games $H$; in particular, this is required for $H = *$, which demands that the impartial games $G \otimes *$ and $G' \otimes *$ have the same Grundy ordinals). It seems that this should still give the games (up to a certain size…) a ring structure, of which the nimbers are a factor or something like that.

My question (at last) is whether this second approach has been studied, and whether it leads to an interesting theory or whether on the contrary there is something obviously wrong with it.

• This is an interesting question, and I don't know if your proposal has been considered in any depth before. That said, I found the way you worded your question to be a bit of a hindrance, as you set things up in preparation for loopy games which it seems you are not interested in. It seems that in more conventional notation, you could simply say something like: "Note that $(1+1)\times *=*+*=0$, but $2\times *=\{1,0|\}\times*=*2\ne0$, where $\times$ is the Conway product. Has anyone examined the equivalence relation: $G \triangleq G'$ iff $G\times H=G'\times H$ for all $H$?" – Mark S. Mar 26 '16 at 21:51
• @MarkS. I grant you that defining games as graphs may have been more distracting than useful (I did that to make it completely clear what extensional equivalence means rather than take it as granted). However, using $=$ for Conway-equality when I'm trying to discuss a finer equivalence relation would probably have been a bad idea, since equality is always supposed to be "the finest equivalence relation that will ever need to be considered in any given domain". – Gro-Tsen Mar 27 '16 at 0:09

As soon as we have 0, 1 , 1/2 (assumed to satisfy the usual properties) and distributivity, we cannot have an element of additive order 2. Since if * has order 2, then

$$* = 1 \otimes * = (1/2 + 1/2) \otimes * = 1/2 \otimes * + 1/2 \otimes * = 1/2 \otimes (* + *) = 1/2 \otimes 0 = 0$$.

[EDIT: The next sentence goes the other way wrt the question: in the question $$\triangleq$$ is finer than $$\doteq$$; here on the contrary $$\triangleq$$ is assumed to be coarser than $$\doteq$$] Hence it seems that $$\triangleq$$ collapses all first-winner games (which have order 2). So I guess that when we take the quotient modulo $$\triangleq$$ we get a Ring isomorphic to the Surreals.

Hence we should renounce to something. I guess everyone wants to keep 0 and 1, at least. Hence we can

(A) Do as Conway, restrict ourselves to numbers.

(B) Renounce to 1/2. I do not know whether this could work and how could be done exactly. We have to consider some class of games in which there are no "fractions". This should be given a precise meaning, surely we cannot have "divisors of 1", but probably many other games should be taken out.

(C) As above, but discarding only "dyadic" fractions. In this case some identifications are necessary, for example, arguing as above, $$1/3 \cdot *$$ should be identified with $$*$$. Again, I do not know whether this could work

(D) Renounce to distributivity. This does not change a lot with the present situation, but leaves open the problem of giving a good definition of the product which does not depend on the representatives.

(E) Consider instead a coarser [EDIT: I meant finer] equivalence relation (classes are smaller) than Conway's. Then we can find a way to make * have infinite order. Alas, in this case it is probably hard to mantain the group structure, that is, to have inverses.

EDIT Not exactly, it seems that we can actually have inverses even with an equivalence relation finer than $$\doteq$$. Let $$\mathbf{PG}$$ be the class of all (extensional equivalence classes of) partizan combinatorial games. Set-theoretical complications can be dealt with in the usual way.

$$\mathbf{PG}$$ is a commutative Monoid wrt $$\oplus$$ and $$0$$. Moreover, the operation $$-$$ satisfies $$-(G \oplus H) =( -G )\oplus (-H)$$.

It is then obvious that if we define $$\sim$$ by
$$G \sim H$$ if and only if there are games $$X$$ and $$Y$$ such that $$G \oplus X \ominus X \cong H \oplus Y \ominus Y$$, then $$\sim$$ is an equivalence relation on $$\mathbf{PG}$$ and $$(\mathbf{PG}/ {\sim}, \oplus/{\sim})$$ becomes a Group with $$(-G)/{\sim}$$ the additive inverse of $$G/{\sim}$$.

I do not know whether $$\sim$$ and $$\triangleq$$ are the same relation. However, it is interesting to notice that one arrives at $$\sim$$ just by group theoretical considerations, with no need of considering products. The relation $$\sim$$ is the finest relation which makes the quotient of $$\mathbf{PG}$$ a Group, at least if $$-$$ is supposed to be the inverse. Were actually $$\sim$$ equal to $$\triangleq$$, this would give additional arguments to the supposition that $$\triangleq$$ is an interesting relation.

Now for the product. We need not have $$(G\oplus H) \otimes K \cong (G\otimes K) \oplus (H\otimes K)$$ in $$\mathbf{PG}$$, for example as a consequence of the counterexample presented in the question. However, the classical (and standard) proof that $$(G\oplus H) \otimes K \doteq (G\otimes K) \oplus (H\otimes K)$$ actually shows that $$(G\oplus H) \otimes K \sim (G\otimes K) \oplus (H\otimes K)$$, since in the proof two opposite games annihilate, hence we do not actually need the full strength of $$\doteq$$. Given distributivity, there is no problem in proving associativity (modulo $$\sim$$).

By the definition of $$\sim$$ and the above formula, we easily get that $$G \sim L$$ implies
$$G \otimes K \sim L \otimes K$$, for every game $$K$$. Just use $$(-X) \otimes K = - (X \otimes K )$$. Thus $$\otimes$$ passes to the quotient with respect to $$\sim$$. Hence $$(\mathbf{PG}/ {\sim}, \oplus/{\sim}, \otimes/{\sim})$$ is a Ring. This implies that $$\sim$$ is finer than $$\triangleq$$.

Arguing in the same way, we get that $$(\mathbf{PG}/ {\triangleq}, \oplus/{\triangleq}, \otimes/{\triangleq})$$ is a Ring. Otherwise, just check that the $$\triangleq$$-class of $$0$$ is an ideal of $$\mathbf{PG}/ {\triangleq}$$. Strictly formally, we should work with the $$(\triangleq/{\sim})$$-class of $$0 /{\sim}$$.

To check whether $$\sim$$ is the same as $$\triangleq$$ means to check if the following is true. Given any game $$G$$, if
$$G \otimes H \sim 0$$, for every game $$H$$, then $$G \sim 0$$.

All the above structure definitely deserves further study, so your question is a really great question!

• Of course, there is a game $x$ that corresponds to (say) the Hackenbush realization of Conway's $½$, which satisfies $x+x≐1$, but it will not satisfy $x+x≜1$. So my question is about renouncing $½$ if you want, but not renouncing it in the sense that it ceases to be a game, but that it does not have a representative satisfying $x+x≜1$. – Gro-Tsen Sep 16 '18 at 11:03
• I have understood your question in the sense that $\triangleq$ should be such that if $G \doteq H$, then $G \triangleq H$. So if $1/2 + 1/2 \doteq 1$, then $1/2 + 1/2 \triangleq 1$. Of course, we can consider instead a relation coarser than $\doteq$, as I mentioned in (E), but then it is hard to get a group, that is, to have additive inverses. – Paolo Lipparini Sep 17 '18 at 20:28
• I want $≜$ to imply $≐$ (i.e., the sought-after equivalence relation $≜$ is stronger, i.e., has smaller classes, and I call this "finer", than Conway's $≐$). So in fact I want (E) but apparently what you call "coarser" is what I (and Wikipedia) call "finer". Sorry about the confusion. I believe additive inverses should still work if I define $G≜G'$ as something like "$G⊗H≐G'⊗H$ for all $H$", which is what I proposed. – Gro-Tsen Sep 17 '18 at 22:01
• You're right, I have taken things the other way round (it sometimes happens ;). Yes, additive inverses do work, and the whole stuff becomes a Ring, I have edited the answer. I suggest you to write a paper about the subject! – Paolo Lipparini Sep 22 '18 at 13:02