We investigate the computational complexity of several decision problems in a simple strategic game of network formation.We find that deciding if a player has a strategy that guarantees him a certain payoff against a given strategy profile of the other players is an NP-complete problem. Deciding if...