Graph sharing games: Complexity and connectivity
Graph sharing games: Complexity and connectivity
复制标题
图共享游戏：复杂性和连通性
DOI：
10.1016/j.tcs.2012.12.029
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
P. Valtr
中科院分区：
文献类型：
--
作者：
Josef Cibulka;J. Kynčl;Viola Mészáros;R. Stolar;P. Valtr
我们研究了Alice和Bob这两个参与人的组合博弈，它推广了Brown，Winkler等人所考虑的比萨饼博弈。给定一个连通图G，其顶点被赋予非负权重，参与者在每一轮轮流取G的一个顶点。第一轮是爱丽丝的。根据以下两个规则中的一个（或两个）来获取顶点：（T）由所获取的顶点导出的G的子图在整个博弈期间是连通的，（R）由剩余顶点导出的G的子图在整个博弈期间是连通的。我们证明了，如果规则（T）和/或（R）是必需的，则对每个ε>0和每个k≥1，存在一个k-连通图G，其中Bob有一个策略来获得顶点总重量的（1-ε）。这与最初的比萨饼游戏形成鲜明对比，在循环中，爱丽丝知道有一个策略来获得总重量的九分之四。我们证明了决定爱丽丝是否有获胜策略的问题（即，获得超过总重量一半的策略）是PSPACE完备的，如果需要条件（R）或条件（T）和（R）两者。我们还考虑了一个在连通图（没有权）上进行的博弈，其中第一个违反条件（T）或（R）的玩家输掉了比赛。我们表明，决定谁有获胜的策略是PSPACE完全的。
We study the following combinatorial game played by two players, Alice and Bob, which generalizes the pizza game considered by Brown, Winkler and others. Given a connected graph G with non-negative weights assigned to its vertices, the players alternately take one vertex of G in each turn. The first turn is Alice’s. The vertices are to be taken according to one (or both) of the following two rules: (T) the subgraph of G induced by the taken vertices is connected during the whole game, (R) the subgraph of G induced by the remaining vertices is connected during the whole game. We show that if rules (T) and/or (R) are required then for every ε>0 and for every k≥1 there is a k-connected graph G for which Bob has a strategy to obtain (1−ε) of the total weight of the vertices. This contrasts with the original pizza game played on a cycle, where Alice is known to have a strategy to obtain four-ninths of the total weight. We show that the problem of deciding whether Alice has a winning strategy (i.e., a strategy to obtain more than half of the total weight) is PSPACE-complete if condition (R) or both conditions (T) and (R) are required. We also consider a game played on connected graphs (without weights) where the first player who violates condition (T) or (R) loses the game. We show that deciding who has the winning strategy is PSPACE-complete.