论文标题
影响力：图表上的党派得分游戏
INFLUENCE: a partizan scoring game on graphs
论文作者
论文摘要
我们介绍了游戏影响力，这是一个得分组合游戏，在有向图上播放，每个顶点颜色为黑色或白色。两位球员，黑白玩家，通过占据其颜色的顶点及其所有继任者（对于黑色）或所有前任（对于白色）而交替出现。每个球员的得分是他所采用的顶点。 我们证明了影响力是一款非Zugzwang游戏，这意味着没有玩家在游戏的任何步骤中通过，因此属于Milnor的宇宙。我们在黑色和白色交替的特定路径类别中研究该游戏。当有一条路径时，我们为两个球员提供了几乎紧密的策略。更确切地说，我们证明了第一个球员总是比第二个球员获得的分数要好得多，但是得分之间的差异为5。最后，我们展示了一些播放器颜色顶点的最初比例的图形，尽可能小，但是该玩家几乎可以得到所有顶点。
We introduce the game INFLUENCE, a scoring combinatorial game, played on a directed graph where each vertex is either colored black or white. The two players, Black and White play alternately by taking a vertex of their color and all its successors (for Black) or all its predecessors (for White). The score of each player is the number of vertices he has taken. We prove that INFLUENCE is a nonzugzwang game, meaning that no player has interest to pass at any step of the game, and thus belongs to Milnor's universe. We study this game in the particular class of paths where black and white are alternated. We give an almost tight strategy for both players when there is one path. More precisely, we prove that the first player always gets a strictly better score than the second one, but that the difference between the score is bounded by 5. Finally, we exhibit some graphs for which the initial proportion of vertices of the color of a player is as small as possible but where this player can get almost all the vertices.
