Combinatorial Game Theory Colloquium III

Fionn Mc Inerney, Université Côte D’Azur, France

(Joint work with Kyle Burke)

Beatty Games: Big and Small

Michael Fisher, West Chester University, United States of America

Octal games are impartial games that involve removing tokens from heaps of tokens.  These types of games are interesting in that they can be uniquely described using an octal code.  Historically, research efforts have focused almost exclusively on octal games with finite codes.  We consider octal games based on infinite octal codes where the heap sizes corresponding to elements of a Beatty α sequence are played according to some fixed removal rule and the heap sizes corresponding to elements of a Beatty β sequence are played according to some other fixed removal rule.  Interesting periodicity seems to occur in most cases.

The Index: a measure of equality

Melissa Huggan, Dalhousie University, Canada

Abstract: Playing combinatorial games with simultaneous moves naturally introduces a probabilistic element to game play. This small change to game play forces big changes when we consider the underlying theory of simultaneous play combinatorial games. In particular, understanding how to interpret equality of games has been very challenging. Throughout this talk, I will present a refinement on the expected value, called the Index, which captures the notion of equality for simultaneous play combinatorial games played under continued conjunctive sum with the extended normal play winning convention.
(Joint work with Richard J. Nowakowski and Paul Ottaway)

Svenja Huntemann, Carleton University, Canada

Abstract: We will demonstrate a quick technique for enumerating the number of DOMINEERING positions on a rectangular board. The method is then modified to count the number of maximal DOMINEERING positions.
(Joint work with Neil McKay)

Shotgun wedding:  ECGT + CGT

Thane Plambeck, Counterwave inc, United States of America

Abstract: Everyone knows that Combinatorial (CGT) theorists are the cool people, but Economic Game Theorists (EGT) get the Nobel Prizes and nearly all the money. Therefore, we aim to contrive and present for your consideration some games that require a knowledge of both Nash Equilibria and the CGT temperature theory to play correctly. Like all shotgun weddings, things may get a bit ugly, but it’s the thought that counts.

On NIM-like games played on graphs

Tomoaki Abuku, University of Tsukuba, Japan

Abstract: We study «NIM on graphs», an impartial game played on a finite undirected weighted graph. In the starting position, a piece is placed at a vertex of the graph. Each player alternately moves the piece from the vertex to one of its adjacent vertices and decreases the weight of the edge to any strictry smaller non-negative integer. The game terminates when one player has no moves and then this player loses. We give the winning strategy and the Grundy values for positions of the game.

Efficiency of cumulative subtraction games as extensive form games

Urban Larsson, Technion – Institute of Technology, Israel

Abstract: This is an extension of a talk on Cumulative Subtraction Games (CS). Zermelo’s backward induction provides a foundational theory for both combinatorial game theory and classical game theory zero-sum extensive form games, in that the optimal play can be computed, although the generic complexity provides little hope for the algorithmically inclined, since the number of terminals grow exponentially with the depth of the game tree. Some time ago, we displayed a beautifully short and efficient way to compute such optimal play outcomes, for the class of 2-player symmetric (impartial) CS games. Now, we answer the question, precisely how far does this approach generalize to general-sum extensive form games. The second part of the talk reveals that, in fact n-player Cumulative subtraction games are in bijective correspondence to classical extensive form games. We finish off by proving that, in the case of 2 player symmetric CS games, the self-interest optimal actions are identical to those of the analogous zero-sum variation, if the reward function is increasing.
(Joint work with Reshef Meir)

The Maker-Breaker domination number

Valentin Gledel, LIRIS, University of Lyon, France

Abstract: The Maker-Breaker domination game is played on a graph G by Dominator and Staller. The players alternatively select a vertex of G that was not yet chosen in the course of the game. Dominator wins if at some point the vertices he has chosen form a dominating set. Staller wins if Dominator cannot form a dominating set. In this paper we introduce the Maker-Breaker domination number of G as the minimum number of moves of Dominator to win the game provided that he has a winning strategy.  This parameter is compared with the domination number and residual graphs are introduced to determine the Maker-Breaker domination number of an arbitrary tree. The invariant is also obtained for cycles and bounded for union of graphs.

p-Saturations of Welter’s game and the irreducible representations of symmetric groups

Yuki Irie, Research Alliance Center for Mathematical Sciences, Tohoku University, Japan

Abstract: We establish a relation between the Sprague-Grundy function of p-saturations of Welter’s game and the degrees of the ordinary irreducible representations of symmetric groups. We present a theorem on these degrees, and using this theorem, we obtain an explicit formula for the Sprague-Grundy function of p-saturations of Welter’s game.