Product Rule Wins a Competitive Game

‘We consider a two player game that guides the evolution of a random graph on $n$ vertices. During each turn a pair of random edges is generated and one of the players chooses one of these edges to be an edge in the graph. One player controls the even rounds with the goal of creating a so-called giant component as quickly as possible. The other player controls the odd rounds and has the goal of keeping the giant from forming for as long as possible. We show that the product rule is an asymptotically optimal strategy for both players.’