论文标题
发病率，图表上的得分位置游戏
Incidence, a Scoring Positional Game on Graphs
论文作者
论文摘要
Hales and Jewett于1963年引入了位置游戏，此后对文献进行了广泛的调查。这些游戏是在HyperGraph上进行的，其中两个玩家交替选择了一个无人认领的顶点。在“制造商”大会中，如果制造商设法完全取得了超越的态度，那么她将获胜，否则，Breaker将是赢家。在制造商大会上，第一个获得超越胜利的球员。在这两种情况下，游戏制造商都采取了超越的状态，游戏就会停止。根据定义，这个游戏家族无法处理分数，也不能代表玩家想要最大化数量的游戏。 在这项工作中，我们介绍了得分位置游戏，这些游戏包括在超图上玩耍，直到要求所有顶点，并将分数定义为玩家已经完全采用的Hyperedge的数量。我们在这里专注于发病率，这是一款在2均匀的超图上玩的得分位置游戏，即无向图。在这个游戏中，两个玩家交替声称图形的顶点并为拥有两个末端顶点的边数评分。在制造商版本中，制造商旨在最大化她拥有的边缘数量，而Breaker则旨在最大程度地减少它。在制造商版本中，两位玩家都试图比对手更多的边缘。 我们首先在得分位置游戏上给出了一些一般结果，以使他们在米尔诺的宇宙中的成员资格以及得分的一般界限。我们证明，令人惊讶的是，计算在制造商破坏者版本中的得分是PSPACE完全完整的，而在制造商制造商约定中，可以在多项式时间内获得相对分数。此外，对于制造商公约，我们通过使用Milnor的宇宙来提供一些等价的路径分数的公式。该结果意味着也可以在多项式时间内计算周期的分数。
Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity. In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on Incidence, a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent. We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of Incidence is PSPACE-complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time.
