Computer Science/Discrete Mathematics Seminar I

A network creation game abstracts a network construction by selfish agent who build a network by buying links to each other. Each player pays a fixed cost per link, and suffers an additional communication cost (which is the sum of distances to the it is interested in communicating with players). The uniform model (where a player is interested to the distances to all other players) was first proposed in Fabricant et al 2003, and we will also consider a non-uniform version of the game. The talk will focus on understanding the equilibrium structure in a network creation games. First, we will show that a pure Nash Equilibrium exists (and for the uniform model, even a strong equilibrium exists). Our main focus would be on the quality of the resulting Nash equilibrium, as modeled by the Price of Anarchy. We will bound worse case ratio of the cost of some Nash equilibrium to that of the social optimum.