Anarchy Is Free in Network Creation

摘要

The Internet has emerged as perhaps the most important network in modern computing, but rather miraculously, it was created through the individual actions of a multitude of agents rather than by a central planning authority. This motivates the game-theoretic study of network formation, and our article considers one of the most well-studied models, originally proposed by Fabrikant et al. In the model, each of n agents corresponds to a vertex, which can create edges to other vertices at a cost of a each, for some parameter a. Every edge can be freely used by every vertex, regardless of who paid the creation cost. To reflect the desire to be close to other vertices, each agent's cost function is further augmented by the sum total of all (graph-theoretic) distances to all other vertices.