摘要 Abstract
在位置博弈的回避者-强制者约定中,两名玩家——回避者和强制者轮流从超图H中选择顶点。如果在H的所有顶点都被选完时,回避者在其所选顶点中完全填满了一条边,则强制者获胜;否则,回避者获胜。本文首先给出了一些通用结果,特别是关于博弈结果和超图的不交并的结果。然后我们确定了对于所有秩为2的超图以及当回避者最后移动时的线性秩为3的超图,哪位玩家有必胜策略。我们获得的结构特征使得算法可以在多项式时间内运行。
In the Avoider-Enforcer convention of positional games, two players, Avoider and Enforcer, take turns selecting vertices from a hypergraph H. Enforcer wins if, by the time all vertices of H have been selected, Avoider has completely filled an edge of H with her vertices; otherwise, Avoider wins. In this paper, we first give some general results, in particular regarding the outcome of the game and disjoint unions of hypergraphs. We then determine which player has a winning strategy for all hypergraphs of rank 2, and for linear hypergraphs of rank 3 when Avoider plays the last move. The structural characterisations we obtain yield polynomial-time algorithms.