Nim variants

ICGA Journal, vol. 44, pp. 2–17

Abstract

Combinatorial game theory provides results for the class of two-player, deterministic games with perfect information. With the aim of generalizing this theory to the class of non-perfect information games in mind, we introduce and analyze three variants of the game of Nim. In these variants, the opponent only receives partial information on the move executed by the opponent. We model the variants as games in extensive form and compute Nash equilibria for different starting configurations. For one variant, this provides a full characterization of the game. For the other variants, we prove some partial and structural results, but a full characterization remains elusive.

Authors 3

1. Mark van den Bergh corresponding Aachen Mathematisch Instituut

   Leiden University

   Affiliation as printed

   Mathematisch instituut, Universiteit Leiden, Netherlands

2. Walter A. Kosters Aachen Leiden Institute of Advanced Computer Science

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science, Universiteit Leiden, Netherlands

3. F. M. Spieksma Aachen Mathematisch Instituut

   Leiden University

   Affiliation as printed

   Mathematisch instituut, Universiteit Leiden, Netherlands