Originator(s): Moshe Rosenfeld (presented by Hong Liu - REGS 2010)
Definition: Assign to each vertex in a tree a nonnegative integer representing the amount of gold there; the result is a weighted tree Two players take turns deleting a leaf of the remaining tree and grabbing its gold. The game ends when all vertices have been taken; the player who has grabbed more gold wins.
Background: This game can be classified as a kind of graph-sharing game (see [MW]). Micek & Walczak [MW] proved that Player 1 can secure at least 1/4 of the weight when playing on any weighted tree with an even number of vertices.
Comments: Player 1 has a winning strategy on a path with even order when the total gold on the odd vertices does not equal the total gold on the even vertices. Player 2 has a winning strategy on a path with odd order when the total gold on the odd vertices is less than the total gold on the even vertices. On a star with even order, Player 1 can win by always taking the most valuable vertex currently available.
Conjecture ([MW]): Player 1 can secure at least half of the gold in any weighted tree with an even number of vertices.
Problem 1: Find other weighted trees in which a winning strategy can be determined? (consider caterpillars or subdivisions of stars)
Question 2: When weights are equal, the winner is determined by the parity of the number of vertices. For a given graph, how unbalanced do the weights need to be to change the winner?
Problem 3: Instead of trees, consider playing on chordal graphs (or other class of graphs). On chordal graphs, one could require that players take only simplicial vertices. In general graphs, one could require that played vertices have maximum distance from the center, avoid cut-vertices, etc.
References:
[MW] Piotr Micek and Bartosz Walczak, Parity in graph sharing
games, section 5, tcs.uj.edu.pl/~walczak/graph-sharing.pdf.