Skip to main content
Notice removed Draw attention by CommunityBot
Bounty Ended with no winning answer by CommunityBot
Notice added Draw attention by Noah Schweber
Bounty Started worth 250 reputation by Noah Schweber
added 91 characters in body
Source Link
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

This question is an outgrowth of a couple previous questions of mine. In order: 1,2,3. This should be fully self-contained, but those questions may help motivate this one.

To keep things readable, I'll start with the question and add the relevant definitions below:

General question: Is it the case that, for every $n\in\mathbb{N}_{>2}$ and every pair of $n$-player finite combinatorial games $\alpha,\beta$, the sequence $$bt(\alpha), bt(\alpha+\beta), bt(\alpha+\beta+\beta), bt(\alpha+\beta+\beta+\beta),...$$ eventually stabilizes?

Special case: What if we restrict attention to the case where $\beta$ is the "one-unrelated-move-for-each-player" game, ${\bf z}_n$? (Basically, an $n$-player Hackenbush board consisting of a single edge of each color with no edges touching each other.)

Even the special case when $n=4$ and $\alpha$ is required to be a "stalks-only $n$-player Hackenbush" game is unclear to me.

Mike Earnest showed that the answer to the special case is positive for $n=3$; however, his argument does not seem to generalize easily (the basic point is that there aren't many possibilities for a coalition from amongst three players, but already with four players the coalitioning $\{1,3\}$ vs. $\{2, 4\}$ causes issues), and a more general claimed argument is unclear to me although it may be correct and even further generalizable after all.

There are a few reasons I'm interested in this question, but the main one is the potential for algebraic "smoothing-over" - the algebraic structures naively gotten pretty directly from $bt$ a la the first above-linked question seem rather nasty, and their "appropriately-stabilized" versions might be nicer (e.g. have inverses, which seems to almost never happen without such modification).


The class of $n$-player finite combinatorial games is defined similarly to the two-player version. Formally, the class $\mathsf{CG}_n$ of $n$-player combinatorial games is the smallest class with the property that every triple $\theta=\langle A_1,A_2,...,A_n\rangle$ with each $A_i$ a finite subset of $\mathsf{CG}_n$ is an element of $\mathsf{CG}_n$; intuitively, $\theta$ represents the game in which player $1$ can move to a game in $A_1$, player $2$ can move to a game in $A_2$, etc. Addition of games is defined recursively by setting $\langle A_1,...,A_n\rangle+\langle B_1,...,B_n\rangle=\langle C_1,...,C_n\rangle$ where $$C_k=\{ \alpha+\langle B_1,..., B_n\rangle: \alpha\in A_k\}\cup\{\langle A_1,...,A_n\rangle+\beta:\beta\in B_k\}.$$

The basic type of a game $\xi\in\mathsf{CG}_n$ keeps track of which coalitions of players can avoid losing depending on who goes first. Formally, $bt(\xi)$ is the set of ordered pairs $\langle u,T\rangle$ with $u\in\{1,...,n\}$ and $T\subseteq \{1,...,n\}$ such that there are strategies $\pi_t$ for each $t\in T$ such that any play of $\xi$ in which

  • $u$ goes first and move order proceeds cyclically $$...\rightarrow 1\rightarrow 2\rightarrow ...\rightarrow n\rightarrow 1\rightarrow ...$$ and

  • each player $t\in T$ follows $\pi_t$

the first player to be unable to move is $\not\in T$.

Finally, for $1\le k\le n$ let ${\bf 1}_n$ be the game with $i$th coordinate $\emptyset$ if $i\not=k$ and $\{\langle\emptyset,...,\emptyset\rangle\}$ if $i=k$, and we let ${\bf z}_n={\bf 1}_1+{\bf 1}_2+...+{\bf 1}_n$.

This question is an outgrowth of a couple previous questions of mine. In order: 1,2,3. This should be fully self-contained, but those questions may help motivate this one.

To keep things readable, I'll start with the question and add the relevant definitions below:

General question: Is it the case that, for every $n\in\mathbb{N}_{>2}$ and every pair of $n$-player finite combinatorial games $\alpha,\beta$, the sequence $$bt(\alpha), bt(\alpha+\beta), bt(\alpha+\beta+\beta), bt(\alpha+\beta+\beta+\beta),...$$ eventually stabilizes?

Special case: What if we restrict attention to the case where $\beta$ is the "one-unrelated-move-for-each-player" game, ${\bf z}_n$? (Basically, an $n$-player Hackenbush board consisting of a single edge of each color with no edges touching each other.)

Even the special case when $n=4$ and $\alpha$ is required to be a "stalks-only $n$-player Hackenbush" game is unclear to me.

Mike Earnest showed that the answer to the special case is positive for $n=3$; however, his argument does not seem to generalize easily (the basic point is that there aren't many possibilities for a coalition from amongst three players, but already with four players the coalitioning $\{1,3\}$ vs. $\{2, 4\}$ causes issues), and a more general claimed argument is unclear to me although it may be correct and even further generalizable after all.

There are a few reasons I'm interested in this question, but the main one is the potential for algebraic "smoothing-over" - the algebraic structures naively gotten from $bt$ a la the first above-linked question seem rather nasty, and their "appropriately-stabilized" versions might be nicer.


The class of $n$-player finite combinatorial games is defined similarly to the two-player version. Formally, the class $\mathsf{CG}_n$ of $n$-player combinatorial games is the smallest class with the property that every triple $\theta=\langle A_1,A_2,...,A_n\rangle$ with each $A_i$ a finite subset of $\mathsf{CG}_n$ is an element of $\mathsf{CG}_n$; intuitively, $\theta$ represents the game in which player $1$ can move to a game in $A_1$, player $2$ can move to a game in $A_2$, etc. Addition of games is defined recursively by setting $\langle A_1,...,A_n\rangle+\langle B_1,...,B_n\rangle=\langle C_1,...,C_n\rangle$ where $$C_k=\{ \alpha+\langle B_1,..., B_n\rangle: \alpha\in A_k\}\cup\{\langle A_1,...,A_n\rangle+\beta:\beta\in B_k\}.$$

The basic type of a game $\xi\in\mathsf{CG}_n$ keeps track of which coalitions of players can avoid losing depending on who goes first. Formally, $bt(\xi)$ is the set of ordered pairs $\langle u,T\rangle$ with $u\in\{1,...,n\}$ and $T\subseteq \{1,...,n\}$ such that there are strategies $\pi_t$ for each $t\in T$ such that any play of $\xi$ in which

  • $u$ goes first and move order proceeds cyclically $$...\rightarrow 1\rightarrow 2\rightarrow ...\rightarrow n\rightarrow 1\rightarrow ...$$ and

  • each player $t\in T$ follows $\pi_t$

the first player to be unable to move is $\not\in T$.

Finally, for $1\le k\le n$ let ${\bf 1}_n$ be the game with $i$th coordinate $\emptyset$ if $i\not=k$ and $\{\langle\emptyset,...,\emptyset\rangle\}$ if $i=k$, and we let ${\bf z}_n={\bf 1}_1+{\bf 1}_2+...+{\bf 1}_n$.

This question is an outgrowth of a couple previous questions of mine. In order: 1,2,3. This should be fully self-contained, but those questions may help motivate this one.

To keep things readable, I'll start with the question and add the relevant definitions below:

General question: Is it the case that, for every $n\in\mathbb{N}_{>2}$ and every pair of $n$-player finite combinatorial games $\alpha,\beta$, the sequence $$bt(\alpha), bt(\alpha+\beta), bt(\alpha+\beta+\beta), bt(\alpha+\beta+\beta+\beta),...$$ eventually stabilizes?

Special case: What if we restrict attention to the case where $\beta$ is the "one-unrelated-move-for-each-player" game, ${\bf z}_n$? (Basically, an $n$-player Hackenbush board consisting of a single edge of each color with no edges touching each other.)

Even the special case when $n=4$ and $\alpha$ is required to be a "stalks-only $n$-player Hackenbush" game is unclear to me.

Mike Earnest showed that the answer to the special case is positive for $n=3$; however, his argument does not seem to generalize easily (the basic point is that there aren't many possibilities for a coalition from amongst three players, but already with four players the coalitioning $\{1,3\}$ vs. $\{2, 4\}$ causes issues), and a more general claimed argument is unclear to me although it may be correct and even further generalizable after all.

There are a few reasons I'm interested in this question, but the main one is the potential for algebraic "smoothing-over" - the algebraic structures gotten pretty directly from $bt$ a la the first above-linked question seem rather nasty, and their "appropriately-stabilized" versions might be nicer (e.g. have inverses, which seems to almost never happen without such modification).


The class of $n$-player finite combinatorial games is defined similarly to the two-player version. Formally, the class $\mathsf{CG}_n$ of $n$-player combinatorial games is the smallest class with the property that every triple $\theta=\langle A_1,A_2,...,A_n\rangle$ with each $A_i$ a finite subset of $\mathsf{CG}_n$ is an element of $\mathsf{CG}_n$; intuitively, $\theta$ represents the game in which player $1$ can move to a game in $A_1$, player $2$ can move to a game in $A_2$, etc. Addition of games is defined recursively by setting $\langle A_1,...,A_n\rangle+\langle B_1,...,B_n\rangle=\langle C_1,...,C_n\rangle$ where $$C_k=\{ \alpha+\langle B_1,..., B_n\rangle: \alpha\in A_k\}\cup\{\langle A_1,...,A_n\rangle+\beta:\beta\in B_k\}.$$

The basic type of a game $\xi\in\mathsf{CG}_n$ keeps track of which coalitions of players can avoid losing depending on who goes first. Formally, $bt(\xi)$ is the set of ordered pairs $\langle u,T\rangle$ with $u\in\{1,...,n\}$ and $T\subseteq \{1,...,n\}$ such that there are strategies $\pi_t$ for each $t\in T$ such that any play of $\xi$ in which

  • $u$ goes first and move order proceeds cyclically $$...\rightarrow 1\rightarrow 2\rightarrow ...\rightarrow n\rightarrow 1\rightarrow ...$$ and

  • each player $t\in T$ follows $\pi_t$

the first player to be unable to move is $\not\in T$.

Finally, for $1\le k\le n$ let ${\bf 1}_n$ be the game with $i$th coordinate $\emptyset$ if $i\not=k$ and $\{\langle\emptyset,...,\emptyset\rangle\}$ if $i=k$, and we let ${\bf z}_n={\bf 1}_1+{\bf 1}_2+...+{\bf 1}_n$.

Source Link
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

Eventual stabilization for repeatedly adding multiplayer games

This question is an outgrowth of a couple previous questions of mine. In order: 1,2,3. This should be fully self-contained, but those questions may help motivate this one.

To keep things readable, I'll start with the question and add the relevant definitions below:

General question: Is it the case that, for every $n\in\mathbb{N}_{>2}$ and every pair of $n$-player finite combinatorial games $\alpha,\beta$, the sequence $$bt(\alpha), bt(\alpha+\beta), bt(\alpha+\beta+\beta), bt(\alpha+\beta+\beta+\beta),...$$ eventually stabilizes?

Special case: What if we restrict attention to the case where $\beta$ is the "one-unrelated-move-for-each-player" game, ${\bf z}_n$? (Basically, an $n$-player Hackenbush board consisting of a single edge of each color with no edges touching each other.)

Even the special case when $n=4$ and $\alpha$ is required to be a "stalks-only $n$-player Hackenbush" game is unclear to me.

Mike Earnest showed that the answer to the special case is positive for $n=3$; however, his argument does not seem to generalize easily (the basic point is that there aren't many possibilities for a coalition from amongst three players, but already with four players the coalitioning $\{1,3\}$ vs. $\{2, 4\}$ causes issues), and a more general claimed argument is unclear to me although it may be correct and even further generalizable after all.

There are a few reasons I'm interested in this question, but the main one is the potential for algebraic "smoothing-over" - the algebraic structures naively gotten from $bt$ a la the first above-linked question seem rather nasty, and their "appropriately-stabilized" versions might be nicer.


The class of $n$-player finite combinatorial games is defined similarly to the two-player version. Formally, the class $\mathsf{CG}_n$ of $n$-player combinatorial games is the smallest class with the property that every triple $\theta=\langle A_1,A_2,...,A_n\rangle$ with each $A_i$ a finite subset of $\mathsf{CG}_n$ is an element of $\mathsf{CG}_n$; intuitively, $\theta$ represents the game in which player $1$ can move to a game in $A_1$, player $2$ can move to a game in $A_2$, etc. Addition of games is defined recursively by setting $\langle A_1,...,A_n\rangle+\langle B_1,...,B_n\rangle=\langle C_1,...,C_n\rangle$ where $$C_k=\{ \alpha+\langle B_1,..., B_n\rangle: \alpha\in A_k\}\cup\{\langle A_1,...,A_n\rangle+\beta:\beta\in B_k\}.$$

The basic type of a game $\xi\in\mathsf{CG}_n$ keeps track of which coalitions of players can avoid losing depending on who goes first. Formally, $bt(\xi)$ is the set of ordered pairs $\langle u,T\rangle$ with $u\in\{1,...,n\}$ and $T\subseteq \{1,...,n\}$ such that there are strategies $\pi_t$ for each $t\in T$ such that any play of $\xi$ in which

  • $u$ goes first and move order proceeds cyclically $$...\rightarrow 1\rightarrow 2\rightarrow ...\rightarrow n\rightarrow 1\rightarrow ...$$ and

  • each player $t\in T$ follows $\pi_t$

the first player to be unable to move is $\not\in T$.

Finally, for $1\le k\le n$ let ${\bf 1}_n$ be the game with $i$th coordinate $\emptyset$ if $i\not=k$ and $\{\langle\emptyset,...,\emptyset\rangle\}$ if $i=k$, and we let ${\bf z}_n={\bf 1}_1+{\bf 1}_2+...+{\bf 1}_n$.