Econ Papers Daily / 期刊论文
有向图放置博弈
Digraph placement games
摘要
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$$ .
中文摘要
本文研究了一种在有向图上进行党派组合博弈的自然规则集，我们称之为有向图放置（Digraph placement）。给定一个有向图G，其顶点集V(G)具有一个不一定正常的2-着色，由玩家Left和Right交替进行的Digraph放置博弈定义如下：轮到Left时，她选择一个蓝色顶点，该顶点连同其所有出邻点一起被删除；轮到Right时，他选择一个红色顶点，该顶点连同其所有出邻点一起被删除。若某玩家在其回合无法行动，则该玩家输掉游戏。我们构造性地证明，Digraph放置是一个通用的党派规则集；对于所有党派组合博弈X，存在一个Digraph放置博弈G，使得$$G = X$$。Digraph放置以及包括Nim、偏序集博弈、Col、Node Kayles、Domineering和Arc Kayles在内的许多其他博弈，都是我们称为冲突放置博弈的一类放置博弈的实例。我们证明，X是冲突放置博弈当且仅当它与某个Digraph放置博弈具有相同的字面形式。由此推论，判定Digraph放置博弈的胜者问题是PSPACE-hard的。接下来，对于博弈值X，我们证明了使得$$G = X$$的最小Digraph放置博弈G的阶数的界。