8
$\begingroup$

Consider a finite graph $\Gamma$ with a positive number $n_v\geq 0$ of chips stacked at each vertex $v$ of $\Gamma$. Two players play in turn with moves consisting either of removing two chips from a unique vertex $v$ such that $n_v\geq 2$ or of removing one chip from both endpoints $v,w$ of an edge $\{v,w\}$ such that $n_v,n_w\geq 1$. The first player with no move left loses (or wins when using the misere convention).

The game is trivial on complete graphs. Winning positions have a nice (not completely trivial) description on the graph $P_3$ (Dynkin graph of type $A_3$) with vertices $1,2,3$ and edges $\{1,2\},\{2,3\}$: Given a position with $(a,b,c)$ chips on vertices $1,2,3$, the existence of a winning strategy for the first player and $a+b+c$ even (the case $a+b+c$ odd is trivial) depends on parities of $a,b,c$ and "coarsened" inequalities (coarsened in order to deal with two numbers of different parities) along edges after taking care of "fattened" boundaries.

A similar phenomenon seems to hold for the $P_4$ graph and perhaps for all trees.

Has somebody a reference/name for this game?

$\endgroup$
3
  • 3
    $\begingroup$ More generally, we can allow $\Gamma$ to have loops (edges from a vertex to itself), regarded as having two endpoints. Now the only rule is that we can remove one chip from both endpoints of an edge if the number of chips remains nonnegative at each vertex. $\endgroup$ Oct 17, 2021 at 14:16
  • $\begingroup$ @RichardStanley I have a slight preference for a formulation without loops : It has a straightforward generalization to simplicial complexes having simplices of dimension at most $d$ : Chose a simplex of dimension $k$ and remove from its $k+1$ vertices $(d+1)!/(k+1)$ chips (if possible). I guess the one-dimensional case of graphs is already quite complicated. $\endgroup$ Oct 17, 2021 at 20:00
  • 3
    $\begingroup$ The case of a path with each $n_v=1$ is equivalent to Dawson's Kayles. I believe this game was first analyzed by Guy and Smith, The $G$-values for various games, Proc. Cambridge Phil. Soc. 52 (1956), 514-526. $\endgroup$ Oct 17, 2021 at 23:32

1 Answer 1

4
$\begingroup$

In their paper A generalization of Arc-Kayles (Intl. J. Game Theory 48 (2019), 491–511), Antoine Dailly, Valentin Gledel, and Marc Heinrich define Weighted Arc Kayles to be a game played on graphs with counters on the vertices. The two players alternate choosing an edge and removing one counter on both endpoints. An edge can no longer be selected if any of its endpoints has no counter left.

In light of Richard Stanley's remark that removing two counters from a vertex $v$ may be thought of as removing a counter from both endpoints of a loop at $v$, your game seems to be equivalent to Weighted Arc Kayles.

$\endgroup$
1
  • $\begingroup$ Thanks for this comment. Their game is slightly different in the sense that they consider an arc to have only one end and they allow thus in this case removal of a unique chip from a vertex (they claim that the game obtained by removing two chips from a vertex is similar without going into details: this seems indeed to be the case). $\endgroup$ Oct 22, 2021 at 17:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.