Saturday, January 6, 2018

Graphs and Games Workshop, Day 3 Talks

Games and Graphs Workshop in Lyon had three days of great talks.  Here are my short summaries of the third day.

Richard Nowakowski's Tutorial: "Introduction to the Theory of Scoring Games"

Richard gave a great tutorial introduction to to scoring games.  There are a lot of issues here I wasn't aware of, including really painful Zugzwangs. ("Anti-Switches"?)  E.g: {Final Score: -1 | Final Score: +1}  How does this happen?

Consider an Independent Set game played on a cube added to another already-finished game with a score of -3.  In the IS game, players choose independent vertices and Left scores a point for the total size of the set.  Now, if Left is forced to go first on the cube, Right can choose the opposite vertex, ending the game with a score of 2 (and a total score of -1).  If Right goes first, Left can choose another vertex that shares a face with the first.  This will force the score to be 4, for a total of +1.

Richard went on to describe many other properties that scoring games can have.  He also polled us about whether we should even allow some types of outcomes and games.

Koki Suetsugu: "Normal and Misere play of Multiplayer Games with Preference

Koki looked at what happens in more-than-two-player games when the players have a preference on who they would like to win.  He described a result using generalized Nim Sums that I was not aware of.  Koki has extended this to misere play by shifting the preference lists any number of spaces to mimic a misere situation.  With this, he uses the generalized Nim Sum to solve the game.

Paul Dorbec: "Quantum Nim"

Paul looked at what happens when instead of making a single move in Nim, you make a superposition of two different moves.  He points out that it's important to specify the number of sticks you're taking--not the number you're leaving--in each of the submoves.  Since some moves may be no longer legal on some parts of the superposition, there are five different versions of the ruleset concerning the allowance of classical moves.  (E.g. unsupervised moves are allowed only if they're valid in all of the parts of the current superposition, etc.)

Melissa Huggan: "What Happens When Players Move Simultaneously in a Combinatorial Game?"

Melissa is really pushing at the border of CGT and Classical (Economic) Game Theory (EGT?).  She wants to let both players take their turn simultaneously and wrap new theory around it.  For her examples, she used Hackenbush where the resulting move is the intersection of the two chosen options  She then defines the outcome classes of terminal positions based on which player has moves left:

  • Draw: no moves for either player
  • Positive: Left still has a move
  • Negative: Right still has a move
Perhaps unsurprisingly, many of the ideas from Classical GT arise as a result of Melissa's ideas, including matrices, expected values, and the benefits of mixed strategies.

Adam Atkinson: "Medieval French Poetry"

This is the only talk that had multiple people climbing to the front of the room to get a better look at all the poems that Adam brought with him.  Adam claimed to have brought some old poems that had been rediscovered in 1950, but that was a bit of a ruse.  I don't want to fully explain what happened here because I don't want to blow his cover on the chance he's giving a similar talk in any other venue.  Nevertheless, maybe we could write some poetry about combinatorial games... but not in English.

Wai Lim (William) Fong: "The Edge-Coloring Game on Trees Played with One More Color"

As I learned at this workshop, there are some really weird and interesting results in the world of Maker-Breaker games.  For example, in the edge-coloring game, adding more colors doesn't necessarily help Alice win on graphs.  Specifically, exactly one more than the minimum needed to ensure Alice has a winning strategy can actually cause her to lose!  William worked on the tree case and showed that if the max degree of the tree is 4, and Alice can win with 4 colors, then she can also win with 5.  (6+ colors is already known to be a win for her.)  William shows this by constructing Alice's winning strategy!

Urban Larsson: "Playful Game Comparison and Absolute CGT"

Urban and team are looking at other extensions using Absolute CGT.  Here he uses an abelian group, called "adorns", of values to assign to terminal positions.  This really opens the doors to many rulesets outside of the Winning Ways spectrum.  He explains that universes of games are absolute if they are dense and parental.  "Normal play is more absolute," he explained.  In any absolute universe, comparisons work exactly as you'd want.

Khaled Mama: "Computing the Shapely Values of Graph Games with Restricted Coalitions"

The Shapely value of a coalition describes how much each actor contributes to the coalition.  Khaled & team looked at this in an interesting way: what if some coalitions are impossible due to communication barriers?  Given some constraints, Khaled can compute these new values using chains across the lattice of coalition chains.  To get working games for this, he's focused on some cool graph games. 

I learned a ton as a result of these talks!  I met a lot of new people that I hope I get to see again.  I'm also very interested in everything I learned about Maker-Breaker games.  I did not realize there was so much being done on this.  Which Maker-Breaker games should I add first to the ruleset table-page?

1 comment: