Games and Graphs Workshop, Day 1 Talks

The Games and Graphs Workshop in Lyon was outstanding!  There were so many talks, but I think I understood at least the basics of most of them.  The first talks were on Monday.


Aviezri Fraenkel: "Problems and Results in Combinatorial Games and Combinatorics"

Aviezri presented a talk about games with some elements of (Economic) Game Theory (EGT).  For example, he considered playing Geography on a binary tree where all terminal nodes are after Alice's turn, except for a great many on the lowest level.  At each level, Alice has one instantly-winning move, but what if there are many other moves and Alice can't differentiate between them? Now she is essentially choosing at random because of some hidden information.  With enough of these extra edges, she is not going to be able to win the game, despite having a winning option each turn.

Aviezri showed many other connections to EGT and called for future work on infinite games in the partizan, scoring, and misere realms.


Craig Tennenhouse: "Three Graph Games"

Craig presented three new games: Tumbleweeds, Deletion/Contraction, and Total Conversion.  Tumbleweeds is a cool variant of Hackenbush without a static root.  Instead, whenever a player chooses an edge that breaks the graph up into multiple connected components, that player chooses either of the components to completely discard!

The partizan game Deletion/Contraction is played on a multigraph (but no loops).  The Left player moves by deleting an edge on their turn, while the Right player chooses an edge to contract (removing any loops that are created).

In Total Conversion, the position is a graph with a non-zero game embedded into each edge and each vertex colored either Red or Blue.  To take a turn, the player must make a move on each game where the edge has ends colored in opposing colors.  Edges with exactly 0 are then removed and both vertices are subsequently repainted with that player's color.

Craig already drew attention with these games and, as always, I suspect he has about three new projects as a result of the conference.


Loic Cellier: "The Game of Hex"

It always seems like there are new things to learn about Hex.  Loic presented just about everything I knew and lots that I didn't.  He covered the history---I did not know that Einstein was a supporter of the game!---the connection to Y, and even presented a variant of the Pie Rule, the Swap Rule:  Here, instead of swapping the identity of the players (if Player 2 wants), instead just swap the color of the piece on the board.  This is, of course, not always equivalent; it prevents the first player from playing in a position that would be too good for their opponent as well.

I also (finally) learned why a Y game must end, by the self-reduction of each vertex into a hex on a slightly-smaller board.  This is surprisingly elegant and easy to explain, but with that little twist that makes it amazing.  It may be more likely to be in The Book than the Hex Theorem (that no Hex game can end in a tie.


Milos Stojakovic: "Maker-Breaker Games Played on Random Graphs"

Milos talked about Positional Games: maker-breaker games on a finite set of elements, X, where F, the winning set, is a subset of the power set of X.  The players alternate turns claiming one element of X.  Maker then wins if they claim all the elements in some set in F; Breaker wins otherwise.  Milos paid special attention games where X is the set of edges in a complete graph.

Unfortunately, for many common sets F (e.g. set of Triangles) it is too easy for Maker to win.  To balance things out, he considers adding biases for each player to change the frequency of turns.  (E.g. Maker takes 3 turns, then Breaker takes 7.)  The idea he took off with was to begin the game by removing a number of random edges.  If each edge remains with probability p, how low does p have to be before Breaker can (usually) win?  He calls this the Threshold Probability, and looked in to determining this value.


Mirjana Mikalacki: "Fast Winning in Positional Games on Graphs"

Mirjana is also interested in positional games, but is looking for other ways to give Breaker a chance to win.  Instead of removing some edges, she considers a "fast" variant where Maker only gets to make a certain number of moves before the game ends in Breaker's favor.  (Breaker still gets to move as normal too.)

Mirjana also combined this with the biases mentioned above.  These "combination" fast games generalize positional games significantly.