On Bipartite Sum Basic Equilibria

A connected and undirected graph G of size \(n\ge 1\) is said to be a sum basic equilibrium iff for every edge uv from G and any node \(v'\) from G, when performing the swap of the edge uv for the edge \(uv'\) the sum of the distances from u to all the other nodes is not strictly reduced. This concept comes from the so called Network Creation Games, a wide subject inside Algorithmic Game Theory that tries to better understand how Internet-like networks behave. It has been shown that the diameter of sum basic equilibria is \(2^{O(\sqrt{\log n})}\) in general and at most 2 for trees. In this paper we see that the upper bound of 2 not only holds for trees but for bipartite graphs, too. Specifically, we show that the only bipartite sum basic equilibrium networks are the complete bipartite graphs \(K_{r,s}\) with \(r,s \ge 1 \).