On a network creation game


  Yishay Mansour


    Google & Tel Aviv Univ


    Monday, October 15th at 2:30 in AKW 200


  / ABSTRACT    ------------------------------------------------------------------------
  /

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.

      _______________________________________________
Dmtcs mailing list
Dmtcs@cs.yale.edu
http://mailman.cs.yale.edu/mailman/listinfo/dmtcs