| |
|
| |
|
Eyal Even-Dar
Machine Learning Reading Group - Lunch
On Nash Equilibria for a Network Creation Game
April 7, 2006 12:00pm
Abstract:
We study a network creation game recently proposed by Fabrikant,
Luthra, Maneva, Papadimitriou and Shenker. In this game, each
player (vertex) can create links (edges) to other players at a
cost of $\alpha$ per edge. The goal of every player is to minimize the sum
consisting of (a)~the cost of the links he has created and
(b)~the sum of the distances to all other players.
Fabrikant et al.\ conjectured that there exists a constant $A$ such
that, for any $\alpha > A$, all non-transient Nash equilibria
graphs are trees. They showed that if a Nash equilibrium is a tree,
the price of anarchy is constant. In this paper we disprove the tree
conjecture. More precisely, we show that for any positive integer
$n_0$, there exists a graph built by $n\geq n_0$ players which
contains cycles and forms a non-transient Nash equilibrium, for any
$\alpha$ with $1< \alpha \leq \sqrt{n/2}$. Our construction makes
use of some interesting results on finite affine planes. On the
other hand we show that, for $\alpha \geq 12n\log{n}$, every Nash
equilibrium forms a tree.
Without relying on the tree conjecture, Fabrikant et al.\ proved
an upper bound on the price of anarchy of $O(\sqrt{\alpha})$, where $\alpha
\in [2,n^2]$. We improve this bound.
Specifically, we derive a constant upper bound for $\alpha \in
O(\sqrt{n})$ and
for $\alpha \geq 12n\log{n}$. For the intermediate
values we derive an improved bound of $O(1+ (\min\{{\alpha^2\over
n}, {n^2\over \alpha}\})^{1/3})$.
Additionally, we develop characterizations of Nash equilibria and
extend our results to a weighted network creation game as well as
to scenarios with cost sharing.
Joint work with Susanne Albers, Stefan Eilts, Yishay Mansour and Liam
Roditty
If you have questions, or would like to meet the speaker, please contact Ponda at 4-1994 or pondabarnes@tti-c.org. For information on future TTI-C talks or events, please go to the TTI-C Events page.