Impartial games with decreasing Sprague–Grundy function and their hypergraph compound

Endre Boros (), Vladimir Gurvich (), Nhan Bao Ho (), Kazuhisa Makino () and Peter Mursic ()
Additional contact information
Endre Boros: Rutgers University
Vladimir Gurvich: National Research University Higher School of Economics
Nhan Bao Ho: La Trobe University
Kazuhisa Makino: Kyoto University
Peter Mursic: Rutgers University

International Journal of Game Theory, 2024, vol. 53, issue 4, No 3, 1119-1144

Abstract: Abstract The Sprague–Grundy (SG) theory reduces the disjunctive compound of impartial games to the classical game of NIM. We generalize this concept by introducing hypergraph compounds of impartial games. An impartial game is called SG-decreasing if its SG value is decreased by every move. Extending the SG theory, we reduce hypergraph compounds of SG-decreasing games to hypergraph compounds of single-pile NIM games. We show that this reduction works only if all games involved in the compound are SG-decreasing. A hypergraph is called SG-decreasing if the corresponding hypergraph compound of single-pile NIM games is an SG-decreasing game. We provide some necessary and some sufficient conditions for a hypergraph to be SG-decreasing. In particular, for hypergraphs with hyperedges of size at most 3 we obtain a necessary and sufficient condition verifiable in polynomial time.

Keywords: Impartial game; Sprague-Grundy function; NIM; Hypergraph NIM; SG-decreasing hypergraph (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s00182-023-00850-7 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:53:y:2024:i:4:d:10.1007_s00182-023-00850-7

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

DOI: 10.1007/s00182-023-00850-7

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 ().