Sprague-Grundy function of matroids and related hypergraphs

We consider a generalization of the classical game of Nim called hypergraph Nim. Given a hypergraph H on the ground set V={1,…,n} of n piles of stones, two players alternate in choosing a hyperedge H∈H and strictly decreasing all piles i∈H. The player who makes the last move is the winner. In this p...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2019-12, Vol.799, p.40-58
Main Authors: Boros, Endre, Gurvich, Vladimir, Ho, Nhan Bao, Makino, Kazuhisa, Mursic, Peter
Format: Article
Language:English
Subjects:
Hypergraph Nim
Impartial game
JM hypergraph
Matroid
Nim
Self-dual matroid
Sprague-Grundy function
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider a generalization of the classical game of Nim called hypergraph Nim. Given a hypergraph H on the ground set V={1,…,n} of n piles of stones, two players alternate in choosing a hyperedge H∈H and strictly decreasing all piles i∈H. The player who makes the last move is the winner. In this paper we give an explicit formula that describes the Sprague-Grundy function of hypergraph Nim for several classes of hypergraphs. In particular we characterize all 2-uniform hypergraphs (that is graphs) and all matroids for which the formula works. We show that all self-dual matroids are included in this class.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.09.041