Graphs and Games Workshop, Day 2 Talks

Day 2 of the Graphs and Games Workshop continued a wonderful conference with more great talks!


Rebecca Milley's tutorial: "Progress and Problems in Misère Play"

Rebecca's excellent talk finally convinced me that I could understand this backwards world.  Although there isn't all the nice group structure, she showed how to use dicot and dead-end universes to reclaim some nice operations (e.g. invertibility, comparisons, and reductions).  It was especially helpful when she explained that Domineering, Hackenbush, NoGo, Snort, and Col are all dead-ending.

More recently, she's applied Absolute Game Theory to get even deeper with dicots and dead ends, including a version of comparisons ("subordinate") and reversibility through ends.


Fionn McInerney: "Spy Games on Graphs"

Fionn showed a cops and robbers variant knows as the spy game.  In this game, first a spy is placed on a vertex, then the guards are placed.  The spy then moves up to their speed, s.  After, the guards can each move up to one space.  (It's okay for the guards and spy to co-locate a vertex.)  The spy wins if they can escape from the guards on any turn by being at least d+1 distance from all guards.  The guards win if they can always prevent this.

Cool complexity connection: It's NP-hard to determine the minimum number of guards needed for their team to win.


Tomoaki Abuku: "Ryuo Nim: a Variant of Wythoff's Nim"

Tomoaki presented a nice variant of Wythoff's Nom, motivated by Shogi.  If we consider the piece to move as Shogi's Ryuo, instead of a Chess Queen, then we get a new game.  (Ryuo can move as a Rook (Hisya) or as a King.)

Tomoaki found a bunch of Grundy values for game positions and considered many variants.


Gabrielle Paris: "Pre-Grundy Games"

Gabrielle showed an extension to Grundy's Game: given a heap of n tokens, a move consists of splitting it into two different-sized heaps.  Gabrielle's Pre-Grundy games allow multiple cuts on one turn: any number in a given set L.  Her team has focused on lots of results here, including:

• If L does not contain 1, then the Grundy values are arithmetic-periodic, and
• If 1 is in L, L has at least two elements, and everything in L is odd, then the Grundy values are periodic!

Lior Goldberg: "Rulesets for Beatty Games"

Lior investigated a problem from 2010 where rulesets were discovered for any Beatty game given by (alpha, beta) where 1 < alpha < 2 and 1/alpha + 1/beta = 1.  The problem is that the rulesets were also very complicated.  Lior has found a nice ruleset for Beatty games where alpha < 1.5 and alpha >= 1.5.  Unfortunately, there are some examples where the ruleset must explicitly reference alpha.  He also showed how to get some specific rulesets that look like t-Wythoff generalizations.

Valentin Gledel: "Maker-Breaker Domination Game"

Valentin introduced a new Maker-Breaker version of a dominating set game.  Each player choose an unchosen vertex.  The Dominator (player) adds them to a potential dominating set (a set of vertices that contains and are neighbors to all vertices).  The Staller (player) chooses nodes to remove as options of the Dominator.  The Dominator wins if the final set dominates the entire graph.  Valentin and his team showed that there are only three outcome classes (N - Fuzzy, D - Dominator wins, S - Staller wins) and showed what happens for all disjoint unions and joins.  He showed that it's easy to decide on cographs and trees, but PSPACE-complete in general.

Clement Charpentier: "Nordhaus-Gaddum Inequalities for Coloring Games"

Clement and team investigated the Maker-Breaker Graph Coloring Game: Alice (Maker) and Bob (Breaker) take turns coloring vertices from one of k colors, following the regular graph coloring rules.  If, in the end, all vertices are colored, then Alice wins.  Otherwise, Bob wins.  

The Nordhaus-Gaddum inequality is about the chromatic number of a graph.  Clement applied these to help determine strategies for Alice.  Clement used this to create new inequalities describing when Alice can win!

Stephan Dominique Andres: "Characterizations of Game-perfect Graphs and Digraphs"

Dominique found a bunch of variants of the Graph-Coloring game by varying:

• Who goes first (Alice or Bob)
• Whether Alice or Bob (not both) can pass, and
• Whether missing a turn is allowed.

Then, for any variant, he and his team define a nice property: a graph is "game-perfect" for one variant exactly if the game-chromatic number equals the size of the largest clique.  They have lots of results for the different variants!  This talk was the first I've seen that used the word "perfectness". :)