Combinatorics Seminar
When: Sunday, December 22, 10am
Where: Schreiber 309
Speaker: Po-Shen Loh, Carnegie Mellon University
Title: Anarchy is free in network creation
Abstract:
The Internet has emerged as the most important network in modern
computing, but miraculously, it was created through the individual
actions of a multitude of agents rather than by a central
authority. This motivates the game theoretic study of network
formation, and we consider one of the best-studied models, due to
Fabrikant et al. In it, each of n agents is a vertex, which creates
edges to other vertices at a cost of \alpha each. Every edge can
be freely used by every agent, 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 of its (graph
theoretic) distances to all other vertices.
Previous research proved that in many regimes of the (\alpha,n)
parameter space, every Nash equilibrium has total social cost (sum
of all agents' costs) within a constant factor of the optimal
social
cost. In algorithmic game theory, this approximation ratio is
called
the price of anarchy. We significantly sharpen some of those
results,
proving that for all constant non-integral \alpha>2, the price of
anarchy is not only bounded by a constant, but tends to 1 as n
tends
to infinity. For constant integral \alpha>=2, we show that
the price of anarchy is bounded away from 1.
Joint work with Ronald Graham, Linus Hamilton, and Ariel Levavi.