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

Endre Boros, Vladimir Gurvich, Nhan Bao Ho, Kazuhisa Makino, Peter Mursic

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
JournalInternational Journal of Game Theory
StateAccepted/In press - 2023

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Mathematics (miscellaneous)
  • Social Sciences (miscellaneous)
  • Economics and Econometrics
  • Statistics, Probability and Uncertainty


  • Hypergraph NIM
  • Impartial game
  • NIM
  • SG-decreasing hypergraph
  • Sprague-Grundy function


Dive into the research topics of 'Impartial games with decreasing Sprague–Grundy function and their hypergraph compound'. Together they form a unique fingerprint.

Cite this