×

Partizan subtraction games. (English) Zbl 1490.91032

Summary: 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 \in S_{\mathcal{L}}\) (resp. \(n \in S_{\mathcal{R}}\)) when it is Left’s (resp. Right’s) turn. The first player unable to move loses. These games were introduced by A. S. Fraenkel and A. Kotzig [Int. J. Game Theory 16, 145–154 (1987; Zbl 0662.90095)], 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_\mathcal{L}\) and \(S_\mathcal{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_\mathcal{L}\) and \(S_\mathcal{R}\) have size at most 2.

MSC:

91A46 Combinatorial games
91A05 2-person games

Citations:

Zbl 0662.90095

References:

[1] E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Vol. 1, A K Peters, Ltd., New York, 2001. · Zbl 1005.00004
[2] A.S. Fraenkel and A. Kotzig, Partizan octal games: partizan subtraction games, Internat. J. Game Theory 16(2) (1987), 145-154. · Zbl 0662.90095
[3] U. Larsson, N. A. McKay, R. J. Nowakowski and A. A. Siegel, Wythoff partizan subtraction, Internat. J Game Theory 47(2) (2018), 613-652. · Zbl 1457.91115
[4] G. A. Mesdal III, Partizan Splittles, Games of No Chance 3, MSRI Publications 56, 2003.
[5] T. Plambeck, Notes on Partizan Subtraction Games, working notes.
[6] J. Ramírez Alfonsín, Complexity of the Frobenius problem, Combinatorica 16 (1996), 143-147. · Zbl 0847.68036
[7] A. N. Siegel, Combinatorial Game Theory, American Mathematical Society, San Francisco, CA, 2013. · Zbl 1288.91003
[8] J. J. Sylvester, Mathematical questions, with their solutions. Educational Times 41 (1884), p 21.
[9] G.S. Lueker, Two NP-Complete Problems in Nonnegative Integer Programming, Report No. 178, Computer Science Laboratory, Princeton University, (1975).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.