research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:chita
TitleOn the Structure of Equilibria in Basic Network Formation
Bibtex cite IDRACTI-RU1-2013-20
Booktitle FCT 2013
Series Springer LNCS Proceedings
Year published 2013
Pages 259-270
Location Liverpool, UK
We study network connection games where the nodes of a networ k perform edge swaps in order to improve their communication costs. For the model proposed by [2], in which the selfish cost of a node is the sum of all shortest path distances to the o ther nodes, we use the probabilistic method to provide a new, structural characterization of equ ilibrium graphs. We show how to use this characterization in order to prove upper bounds on the diame ter of equilibrium graphs in terms of the size of the largest k -vicinity (defined as the the set of vertices within distance k from a vertex), for any k ≥ 1 and in terms of the number of edges, thus settling positivel y a conjecture of [2] in the cases of graphs of large k -vicinity size (including graphs of large maximum degree) a nd of graphs which are dense enough. Next, we present a new swap-based network creation game, in w hich selfish costs depend on the imme- diate neighborhood of each node; in particular, the profit of a node is defined as the sum of the degrees of its neighbors. We prove that, in contrast to the previous m odel, this network creation game admits an exact potential, and also that any equilibrium graph cont ains an induced star. The existence of the potential function is exploited in order to show that an equi librium can be reached in expected polyno- mial time even in the case where nodes can only acquire limite d knowledge concerning non-neighboring nodes.
Nikoletseas, Sotiris
Panagopoulou, Panagiota
Raptopoulos, Christoforos
Spirakis, Paul
1306.1677v1.pdf (main file)
Publication ID1001