Jonas Sjöstrand: Pomax games are PSPACE-complete

A pomax game is played on a poset whose elements are colored black or white. The players Black and White take turns removing any maximal element of their own color. If there is no such element, the player loses.

Pomax games have the following two properties which make them unique among games in the literature.

• Being integer-valued, they play a simple role in the algebraic framework of combinatorial games.
• Being PSPACE-complete, they are computationally hard to analyze.

I will give a very short introduction to combinatorial game theory — a beautiful piece of combinatorics — but most of the talk will be focusing on the PSPACE-completeness of pomax games.

This is joint work with Erik Järleberg.