Price of anarchy grows with network size in max-distance games
The price of anarchy in the max-distance network creation game is not constant
Computer Science and Game TheoryDiscrete Mathematics
Summary
This work studies how inefficient networks can become when individuals create connections selfishly, focusing on a game where players try to minimize their longest distance to others. The authors found that, contrary to some hopes, the inefficiency can grow quite fast as the network gets larger when the cost to add an edge is exactly one. They built specific network examples to show this large inefficiency, and also showed that when edge costs shrink fast enough, the inefficiency remains bounded. This helps to better understand how selfish behavior influences network quality in such settings.
What this means in practice
- •For network architects: Know that selfish addition of network links can yield highly inefficient networks as size grows when link cost is fixed at one.
- •For network protocol designers: Design protocols that anticipate large inefficiencies in decentralized link formation under constant edge costs by adjusting incentives accordingly.
A theory result. No direct application yet.
Authors
Christoph Schlegel
Abstract
At edge price $α=1$, we construct an infinite family of pure Nash equilibria of the unilateral max-distance network creation game with $\PoA\ge2^{\sqrt{\log_2 n}-O(\log\log n)}$. Together with the known upper bound, this gives $2^{Θ(\sqrt{\log n})}$ along the constructed sequence of population sizes. We subdivide every edge of the bipartite double cover of a distance-uniform graph with large diameter constructed by Lavrov, Loh and Messegué, and let each subdivision vertex buy its two incident edges. A distance calculation rules out every profitable unilateral deviation. The equilibria are not strict. We also give a short proof that the price of anarchy is constant for every polynomially vanishing edge price.