Partizan subtraction games

Authors E. Duchêne, Marc Heinrich, Aline Parreau, R. J. Nowakowski

Publication date 25 March 2022

Full work available at URL https://arxiv.org/abs/2101.01595, http://math.colgate.edu/~integers/vb8/vb8.pdf

2-person games (91A05) Combinatorial games (91A46)

Abstract: Partizan subtraction games are combinatorial games where two players, say Left and Right, alternately remove a number n of tokens from a heap of tokens, with

n i n S_{L}

(resp.

n i n S_{R}

) when it is Left's (resp. Right's) turn. The first player unable to move loses. These games were introduced by Fraenkel and Kotzig in 1987, where they introduced the notion of dominance, i.e. an asymptotic behavior of the outcome sequence where Left always wins if the heap is sufficiently large. In the current paper, we investigate the other kinds of behaviors for the outcome sequence. In addition to dominance, three other disjoint behaviors are defined, namely weak dominance, fairness and ultimate impartiality. We consider the problem of computing this behavior with respect to

S_{L}

and

S_{R}

, which is connected to the well-known Frobenius coin problem. General results are given, together with arithmetic and geometric characterizations when the sets

S_{L}

and

S_{R}

have size at most 2.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Partizan subtraction games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3390720)