On the min-entropy of equilibrium graphs in network creation games

This paper investigates the Equilibrium Graph Min-Entropy (EGME) of network creation games, aiming to quantify the underlying structural complexity of equilibrium graphs formed by strategic agents. Building upon classical network creation models, we define EGME based on the probability distribution derived from each agent’s social cost relative to the total social cost. Our analysis provides exact characterizations of EGME for various edge establishment cost regimes, including explicit results for small edge-cost values (α <2) and general bounds for larger edge-cost values (α ≥ 2). Comprehensive simulation experiments demonstrate that EGME effectively distinguishes structural variations induced by changes in network size and edge-cost parameters, exhibiting strong correlations with established global network metrics such as graph density, diameter, and betweenness centrality. These results highlight the utility of EGME as a robust measure for assessing structural complexity and network stability in strategic network formation scenarios.