Wythoff partizan subtraction

Urban Larsson (), Neil A. McKay (), Richard J. Nowakowski () and Angela A. Siegel ()
Additional contact information
Urban Larsson: Dalhousie University
Neil A. McKay: Dalhousie University
Richard J. Nowakowski: Dalhousie University
Angela A. Siegel: Robert Gordon University

International Journal of Game Theory, 2018, vol. 47, issue 2, No 12, 613-652

Abstract: Abstract We introduce a class of normal-play partizan games, called Complementary Subtraction. These games are instances of Partizan Subtraction where we take any set A of positive integers to be Left’s subtraction set and let its complement be Right’s subtraction set. In wythoff partizan subtraction we take the set A and its complement B from wythoff nim, as the two subtraction sets. As a function of the heap size, the maximum size of the canonical forms grows quickly. However, the value of the heap is either a number or, in reduced canonical form, a switch. We find the switches by using properties of the Fibonacci word and standard Fibonacci representations of integers. Moreover, these switches are invariant under shifts by certain Fibonacci numbers. The values that are numbers, however, are distinct, and we can find their binary representation in polynomial time using a representation of integers as sums of Fibonacci numbers, known as the ternary (or “the even”) Fibonacci representation.

Keywords: Combinatorial game theory; Complementary subtraction; Fibonacci sequence; Partizan subtraction game; Reduced canonical form; Sturmian word; Wythoff’s sequences; 91A46; 11B39 (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-018-0613-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jogath:v:47:y:2018:i:2:d:10.1007_s00182-018-0613-2

Ordering information: This journal article can be ordered from
http://www.springer. ... eory/journal/182/PS2

DOI: 10.1007/s00182-018-0613-2

Access Statistics for this article

International Journal of Game Theory is currently edited by Shmuel Zamir, Vijay Krishna and Bernhard von Stengel

More articles in International Journal of Game Theory from Springer, Game Theory Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().