The median game

We introduce a game which is played by two players on a connected graph GG. The players II and IIII alternatively choose vertices of the graph until all vertices are taken. The set of vertices chosen by player II is denoted by ΠIΠI, and by IIII is denoted by ΠIIΠII. Let d(x,π)=∑y∈πd(x,y)d(x,π)=∑y∈πd(x,y) and let M(π)=min{d(x,π)∣x∈π}M(π)=min{d(x,π)∣x∈π} be the median value   of a profile π⊆V(G)π⊆V(G). The objective of player II is to maximize M(πII)−M(πI)M(πII)−M(πI) and the objective of player IIII is to minimize M(πII)−M(πI)M(πII)−M(πI). The winner of the game is the player with the smaller median value of her profile. We give a necessary condition for a tree so that player II (who begins the game) has a winning strategy for the game. We prove also that for hypercubes and some other symmetric graphs the player IIII has a strategy to draw the game. Complete bipartite graphs are considered as well.