TY - GEN
T1 - Asymmetric Swap-Equilibrium: A Unifying Equilibrium Concept for Network Creation Games
AU - Mihalák, Matús
AU - Schlegel, Jan Christoph
PY - 2012
Y1 - 2012
N2 - We introduce and study the concept of an asymmetric swap-equilibrium for network creation games. A graph where every edge is owned by one of its endpoints is called to be in asymmetric swap-equilibrium, if no vertex v can delete its own edge {v,w} and add a new edge {v,w'} and thereby decrease the sum of distances from v to all other vertices. This equilibrium concept generalizes and unifies some of the previous equilibrium concepts for network creation games. While the structure and the quality of equilibrium networks is still not fully understood, we provide further (partial) insights for this open problem. As the two main results, we show that (1) every asymmetric swap-equilibrium has at most one (non-trivial) 2-edge-connected component, and (2) we show a logarithmic upper bound on the diameter of an asymmetric swap-equilibrium for the case that the minimum degree of the unique 2-edge-connected component is at least n e , for \(\varepsilon>\frac{4\lg 3}{\lg n}\). Due to the generalizing property of asymmetric swap equilibria, these results hold for several equilibrium concepts that were previously studied. Along the way, we introduce a node-weighted version of the network creation games, which is of independent interest for further studies of network creation games.
AB - We introduce and study the concept of an asymmetric swap-equilibrium for network creation games. A graph where every edge is owned by one of its endpoints is called to be in asymmetric swap-equilibrium, if no vertex v can delete its own edge {v,w} and add a new edge {v,w'} and thereby decrease the sum of distances from v to all other vertices. This equilibrium concept generalizes and unifies some of the previous equilibrium concepts for network creation games. While the structure and the quality of equilibrium networks is still not fully understood, we provide further (partial) insights for this open problem. As the two main results, we show that (1) every asymmetric swap-equilibrium has at most one (non-trivial) 2-edge-connected component, and (2) we show a logarithmic upper bound on the diameter of an asymmetric swap-equilibrium for the case that the minimum degree of the unique 2-edge-connected component is at least n e , for \(\varepsilon>\frac{4\lg 3}{\lg n}\). Due to the generalizing property of asymmetric swap equilibria, these results hold for several equilibrium concepts that were previously studied. Along the way, we introduce a node-weighted version of the network creation games, which is of independent interest for further studies of network creation games.
U2 - 10.1007/978-3-642-32589-2_60
DO - 10.1007/978-3-642-32589-2_60
M3 - Conference article in proceeding
T3 - Lecture Notes in Computer Science
SP - 693
EP - 704
BT - Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS)
PB - Springer Verlag
ER -