Séminaire Algorithmique : Paul Dorbec (GREYC) « How can the balance game be so unfair? »

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, coloring them with their own color. The discrepancy in the balance game is defined as the difference of the number of well colored edges minus the number of monochromatic edges. The two players have opposite goals: Admirable attempts to minimize the discrepancy while Impish attempts to maximize d.

During this talk, we will show bounds on the discrepancy of graphs, showing that the game is strongly biased in favor of Impish.