Yishay Mansour

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.

Monday, October 29, 2007 4:15 PM 5130 Upson Hall		Theory Seminar Fall 2007 CS 789
	Yishay Mansour Google Tel Aviv Univ
	On a Network Creation Game
	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.