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?

Improve this question
$\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$
    – Richard Stanley
    Commented 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$
    – Roland Bacher
    Commented 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$
    – Richard Stanley
    Commented Oct 17, 2021 at 23:32

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Roland Bacher
    Commented Oct 22, 2021 at 17:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .