CanaDAM 2021
On-line, May 25 - 28, 2021

Game Theory

ALEXANDER CLOW, St. Francis Xavier University
From Poset Games to Partially Ordered Games  [PDF]

Combinatorial games are 2 player games of no chance and perfect information. Under the normal play condition the player to have no move on their turn loses and a game is impartial if for every position both players have the same set of moves. In their paper Advances in Finding Ideal Play on Poset Games Clow and Finbow showed that poset games (a class of impartial combinatorial games) under normal play can be reduced to much simpler poset games in such a way that the score of the game (nimber) and optimal moves are preserved. This talk generalizes these results to all normal play games. In doing so both the notions of ordinal sums (whose partial order is a total order of cardinality $2$) and disjoint sums of games are generalized. Furthermore the Colon Principle, which deals with ordinal sums of games is generalized.

MOZHGAN FARAHANI, Memorial University of Newfoundland
The deduction game to capture robbers  [PDF]

We study a variation of the game of cops and robbers on graphs in which the cops must capture an invisible robber in one move. Cops know each others' initial locations, but they can only communicate if they are on the same vertex. Thus, the challenge for the cops is to deduce the other cops' movement and move accordingly in order to capture the robbers and guarantee a win. We call this game the deduction game to capture robbers. In this talk, we introduce the deduction number as the minimum number of cops needed to capture all robbers and discuss the deduction number for some classes of graphs.

RYAN HAYWARD, University of Alberta
Let's Play Hex: Some Open Problems  [PDF]

For the regular nxn Hex board, what are some winning first moves? What about for the misere version of this game, Reverse Hex? Is the world's strongest Hexbot stronger than the world's strongest Hex human? What happens when a deterministic Hex player plays a random Hex player on a board whose shape (more rows than columns) favours the random player? What's a best strategy for Dark Hex (also known as Kriegspiel Hex, where you don't see your opponent's moves) on the 4x4 board? I will discuss these open problems.

MASOOD MASJOODY, Simon Fraser University
Confining the Robber on Cographs  [PDF]

In this talk, the notions of trapping and confining the robber on a graph, and the corresponding cop numbers are introduced. The latter two are easily seen to be lower bounds for the (regular) cop number of a graph. We present some structurally necessary conditions for graphs $G$ not containing the path on $k$ vertices ($P_k$-free graphs) so that $k-3$ cops do not have a strategy to capture or confine the robber on $G$. We show that for planar cographs and planar $P_5$-free graphs the confining cop number is at most one and two, respectively, and that the number of vertices of connected cographs having a confining cop number $\ge2$ has a tight lower-bound of eight. We conclude by posing two conjectures concerning the confining cop number of $P_5$-free graphs and the smallest planar graph of confining cop number of three.

Finding the smallest 4-cop-win graph(s)  [PDF]

We study extremal graphs for the game of Cops and Robbers. It is well known that the smallest connected graph on which 3 cops are needed to capture the robber is the Petersen graph. Using both formal and computational methods, we determine the minimum order of connected 4-cop-win graphs, which confirms a conjecture of Andreae (1986), and later of Baird et al. (2014), and work towards the uniqueness of such graphs. Joint work with Samuel Yvon.