1
$\begingroup$

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$.

$\endgroup$

0

You must log in to answer this question.