February 4, 2008
Yishay Mansour
Google and Tel Aviv University
Title: On a network creation game
Abstract: A network creation game abstracts a network construction by selfish agents who build a network by buying links to each other. Each player pays a fixed cost per link, and suffers an additional communication cost. 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.