International Journal of Game Theory Social Sciences (miscellaneous)

Digraph placement games

Clow, Alexander, McKay, Neil Anderson
Springer Nature · 2026-08-25 · DOI 10.1007/s00182-026-01010-3

Abstract

This paper considers a natural ruleset for playing a partisan combinatorial game on a directed graph, which we call Digraph placement . Given a digraph G with a not necessarily proper 2-coloring of V ( G ), the Digraph placement game played on G by the players Left and Right, who play alternately, is defined as follows. On her turn, Left chooses a blue vertex which is deleted along with all of its out-neighbours. On his turn Right chooses a red vertex, which is deleted along with all of its out-neighbours. A player loses if on their turn they cannot move. We show constructively that Digraph placement is a universal partisan ruleset; for all partisan combinatorial games X there exists a Digraph placement game, G , such that $$G = X$$ . Digraph placement and many other games including Nim , Poset Games , Col , Node Kayles , Domineering , and Arc Kayles are instances of a class of placement games that we call conflict placement games. We prove that X is a conflict placement game if and only if it has the same literal form as a Digraph placement game. A corollary of this is that deciding the winner of a Digraph placement game is PSPACE-hard. Next, for a game value X we prove bounds on the order of a smallest Digraph placement game G such that $$G = X$$ .

Read at publisher →