On the Structure of Equilibria in Basic Network Formation
| Autor: | Panagiota N. Panagopoulou, Paul G. Spirakis, Christoforos L. Raptopoulos, Sotiris Nikoletseas |
|---|---|
| Rok vydání: | 2013 |
| Předmět: |
Discrete mathematics
FOS: Computer and information sciences Conjecture General Computer Science 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Network formation Vertex (geometry) Combinatorics Probabilistic method Swap (finance) 010201 computation theory & mathematics Computer Science - Computer Science and Game Theory Shortest path problem 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Potential game Time complexity Mathematics MathematicsofComputing_DISCRETEMATHEMATICS Computer Science and Game Theory (cs.GT) |
| DOI: | 10.48550/arxiv.1306.1677 |
| Popis: | We study network connection games where the nodes of a network perform edge swaps in order to improve their communication costs. For the model proposed by Alon et al. (2010), in which the selfish cost of a node is the sum of all shortest path distances to the other nodes, we use the probabilistic method to provide a new, structural characterization of equilibrium graphs. We show how to use this characterization in order to prove upper bounds on the diameter 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 \geq 1$ and in terms of the number of edges, thus settling positively a conjecture of Alon et al. in the cases of graphs of large $k$-vicinity size (including graphs of large maximum degree) and of graphs which are dense enough. Next, we present a new swap-based network creation game, in which selfish costs depend on the immediate 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 model, this network creation game admits an exact potential, and also that any equilibrium graph contains an induced star. The existence of the potential function is exploited in order to show that an equilibrium can be reached in expected polynomial time even in the case where nodes can only acquire limited knowledge concerning non-neighboring nodes. Comment: 11 pages, 4 figures |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|