Monoid associated to $>2$-player Hackenbush

Question

There is some literature on multiplayer combinatorial game theory, but as far as I can tell none of it follows the line of attack below. I'd love a pointer to a similar approach taken in the literature, though!

---

The assignment of (certain) numbers to (finite) Red/Blue Hackenbush boards can be thought of as developing along the following lines:

• We start with the "naive" monoid $N$ of Red/Blue Hackenbush boards with the operation being disjoint union.

• We then assign to each Hackenbush board a "basic type" from $\{$"Red win," "Blue win," or "Second player win"$\}$. The corresponding equivalence relation $\sim$ (= "has the same basic type as") is not a congruence on $M$, ...

• ... But it does give rise to one, namely $$A\approx B\quad \iff\quad \forall C(A+C\sim B+C),$$ and the resulting quotient $N/\approx$ is (isomorphic to) the dyadic rationals $\mathbb{Z}[{1\over 2}]$.

Since the "$\sim$-to-$\approx$" trick always works (I was originally only aware of this for cancellative monoids, but Keith Kearnes pointed me to Mal'cev's congruence generation theorem here), an analogous version of this can be whipped up for $n$-player Hackenbush for any fixed finite $n$ to get a monoid $\mathsf{Hack}_n$. For readability I've put the precise definition of $\mathsf{Hack}_n$ below, but note that as expected we would get $\mathsf{Hack}_2\cong \mathbb{Z}[{1\over 2}]$.

My question is:

Question: What is a more concrete description of $\mathsf{Hack}_n$ in general (or even $\mathsf{Hack}_3$ in particular)?

For example, it seems that $\mathsf{Hack}_n$ is never a group for $n>2$, but I haven't been able to prove that.

(There are a few choices I've made in the definition of the $\mathsf{Hack}_n$s which are not obviously correct; this includes the choice at the outset to focus on Hackenbush specifically as opposed to some other combinatorial game. I would be interested in answers addressing any variation of the construction here, although the specific $\mathsf{Hack}_n$s defined here are what I'm interested in primarily.)

---

Definition of $\mathsf{Hack}_n$

For $2\le n<\omega$, define an $n$-Hackenbush-board (or "$n$-board" for short) is a tuple $(V,E,S,l)$ where

• $(V,E)$ is a graph with $V\not=\emptyset$,

• $S$ is a nonempty subset of $V$ (the set of "ground vertices") such that every vertex in $V$ is in the same connected component as at least one element of $S$, and

• $l:E\rightarrow[n]$ (where $[n]=\{1,...,n\}$).

Analogously to Red/Blue Hackenbush, a given $n$-board $B$ has $n$-many possible games associated to it, one for each choice of first player; after the first move, we follow the obvious pattern $$...\rightarrow n\rightarrow 1\rightarrow 2\rightarrow ...\rightarrow n-1\rightarrow n\rightarrow 1\rightarrow ...$$ A move by player $k$ consists of erasing a single $k$-labelled edge, and then erasing all of the (current state of the) board apart from the (new) connected components of the vertices in $S$.

Given such a board $B$, let the basic type of $B$ be the set $bt_n(B)$ of pairs $(x,A)$ such that

• $x\in[n]$ is a choice of starting player,

• $A$ is a nonempty proper subset of $[n]$ (intuitively a set of players forming a coalition), and

• there are strategies $\pi_a$ for each $a\in A$ such that, in any legal play of $B$ with starting player $x$ in which each $a\in A$ plays according to $\pi_a$, the first player to be unable to move is in $[n]\setminus A$.

(Intuitively, $(x,A)\in bt(B)$ means "the $A$-coalition can avoid losing if player $x$ starts.")

We take as our "same basic type" relation $$B_1\sim_n B_2:\equiv bt_n(B_1)=bt_n(B_2),$$

and extract from this the more nuanced equivalence relation

$B_1\approx_n B_2$ iff for every board $B$ we have $$B_1+B\sim_nB_2+B.$$

Here $+$ denotes the obvious notion of "adding" boards by taking disjoint unions appropriately. Following the above-linked MSE post (either the argument in my question or Keith Kearnes' much more general argument) we can show that $\approx_n$ is a congruence on the "naive monoid" $N_n$ of $n$-boards under addition, and so - finally! - we can define the resulting quotient $\mathsf{Hack}_n:=N_n/\approx_n.$

Answer 1

This answer is more an extended comment since it doesn't address $\mathsf{Hack}_n$, which I haven't thought much about yet.

Since the basic type is a very complex object, we can define (for all finite games $G$, not just Hackenbush), the (singleton-coalition) outcome $o_n(G)$ to be the subset of $bt_n$ where each $A$ is a singleton. This naturally gives rise to a relation on finite games (Hackenbush or not) analogous to $\sim_n$, given by $o_n(G_1)=o_n(G_2)$. This relation is (a priori in general) coarser than $\sim_n$, since coalitions may be able to accomplish different things even if each player working alone cannot. However, for $n=2,3$, it's not coarser.

Note that $o_2(G)$ is the same as $bt_2(G)$. More interestingly, when $n=3$, $(i,\{j\}^\complement)\in bt_3(B)$ means that the players other than player $j$ can force player $j$ to be first unable to move (when player $i$ opens/moves first). This means precisely that $(i,\{j\})\notin bt_3(B)$. This means that $o_3(G)$ determines $bt_3(G)$, and that $o_3(G_1)=o_3(G_2)$ precisely when $G_1\sim_3G_2$ (extending $\sim_3$ to all finite games, say).

We can form an (a priori) finer relation than $\approx_3$ by replacing $B$ with an arbitrary finite game: $G_1\approxeq_3G_2$ iff $G_1+G\sim_3G_2+G$ for all finite games $G$, not just Hackenbush games (where $+$ is extended to all finite games in the natural way).

Relatedly, for $n>3$, this splits into $\approxeq^o_n$ and $\approxeq^{bt}_n$, depending on whether $o_n(G_1+G)=o_n(G_2+G)$ or $bt_n(G_1+G)=bt_n(G_2+G)$ (i.e. $\sim_n$) is used. $\approxeq^{bt}_n$ is (a priori) finer than $\approx_n$ since $G$ can be any game. But $\approxeq^o_n$ has a mixture of the two factors: the equivalence kernel of $o_n$ being coarser than that for $bt_n$, but $G$ being arbitrary making for a finer relation.

---

In my paper, "An Extension of the Normal Play Convention to $N$-player Combinatorial Games" (INTEGERS Vol. 20A, arXiv), "Corollary 4.26" essentially states that (for $n>2$) if $G\approxeq^o_n0$ then $G\cong0$ (where $0$ is the empty game with no available moves). In particular, if $G\approxeq_30$ then $G\cong0$.

Translating into the notation of the question and comment, here is most of the proof: Let $G$ be a finite game where some player other than player $1$ (let's say player $2$) has a move in $G$. Define $H$ to be a game where player $2$ can only move to $0$ and player $3$ can only move to many copies of $\langle2\rangle+\langle3\rangle+\cdots+\langle n\rangle$ (where "many" means more than the number of possible moves in $G$, say). Then $(2,\{1\})\in bt_n(H)$, but $(2,\{1\})\notin bt_n(G+H)$ since player $2$ can "burn" their first move in $G$, allowing player $3$ to doom player $1$ by playing in $H$. This works identically if player $2$ is replaced with another non-$1$ player other than $n$; and it only requires minor modification to replace player $2$ with player $n$. As a result, if $G\approxeq^o_n0$, then (initially) $G$ must only have moves available for player $1$. But by symmetry, this must be true for the other players as well, so that $G$ must have no moves at all.

To emphasize, since the relationship between $\approxeq^o_n$ and $\approx_n$ is murky, the above result doesn't really say anything about $\mathsf{Hack}_n$ directly. But since $\approxeq^o_n$ is coarser than $\approxeq^{bt}_n$, it does say something about "the corresponding construction for arbitrary finite games".