Categories of impartial rulegraphs and gamegraphs

Bojan Bašić, Paul Ellis, Dana Ernst, Danijela Popović, Nándor Sieben

Research output: Contribution to journalArticlepeer-review

Abstract

The traditional mathematical model for an impartial combinatorial game is defined recursively as a set of the options of the game, where the options are games themselves. We propose a model called gamegraph, together with its generalization rulegraph, based on the natural description of a game as a digraph where the vertices are positions and the arrows represent possible moves. Such digraphs form a category where the morphisms are option preserving maps. We study several versions of this category. Our development includes congruence relations, quotients, and isomorphism theorems and is analogous to the corresponding notions in universal algebra. The quotient by the maximum congruence relation produces an object that is essentially equivalent to the traditional model. After the development of the general theory, we count the number of non-isomorphic gamegraphs and rulegraphs by formal birthday and the number of positions.

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

Keywords

  • 05C57
  • 08A30
  • 91A43
  • 91A46
  • Congruence relation
  • Minimum quotient
  • Option preserving map
  • Valuation

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Categories of impartial rulegraphs and gamegraphs'. Together they form a unique fingerprint.

Cite this