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 -log₂(n) ≤ bAg(G) ≤ n/2 if n is even and 0 ≤ bAg(G) ≤ n/2 + log₂(n) if n is odd. Moreover we show that bAg(G) + bIg(Ḡ) = n/2.