An exploration of the balance game

The balance game is played on a graph G by two players, Admirable (A) and Impish (I), who take turns selecting unlabeled vertices of G. Admirable labels the selected vertices by 0 and Impish by 1, and the resulting label on any edge is the sum modulo 2 of the labels of the vertices incident to that edge. Let e₀ and e₁ denote the number of edges labeled by 0 and 1 after all the vertices are labeled. The discrepancy in the balance game is defined as d = e₁ - e₀. The two players have opposite goals: Admirable attempts to minimize the discrepancy d while Impish attempts to maximize d. When (A) makes the first move in the game, the (A) -start game balance number, bAg (G), is the value of d when both players play optimally, and when (I) makes the first move in the game, the (I) -start game balance number, bIg (G), is the value of d when both players play optimally. Among other results, we show that if G has order n, then -₂ (n) bAg (G) n2 if n is even and 0 bAg (G) n2 + ₂ (n) if n is odd. Moreover we show that bAg (G) + bIg (G) = n/2.