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

Why sharing the load in networks matters

From online social media to power grids and shipping routes, many of today’s networks are built not by a central planner but by many individual players following their own interests. This paper asks a subtle but important question: when people or companies choose their own connections, how evenly is the burden of maintaining the network shared, and how can we measure hidden structural imbalances that might affect fairness, efficiency, or resilience? The authors introduce a new lens, called Equilibrium Graph Min-Entropy (EGME), to capture how lopsided or balanced a stable, self-organized network really is beneath the surface.

How selfish choices create stable networks

The work builds on the “network creation game,” a framework where each participant decides which links to pay for. Every link has a fixed building cost, and every extra step needed to reach others in the network adds to a player’s distance cost. A network is considered stable (a pure Nash equilibrium) when no single player can lower their own total cost by adding or removing a connection. Classic research on this model has focused on how inefficient such equilibria can be compared with a perfectly coordinated network, summarised by the so‑called price of anarchy. However, two different equilibria can have the same overall shape—say, everyone is connected to everyone else—while the expenses of building those connections fall very unevenly on a few “suckers,” or are shared more fairly. Traditional measures overlook this internal cost pattern.

A new measure that listens to who pays what

EGME tackles this blind spot by turning each player’s social cost into a probability: the higher your cost relative to the total, the larger your probability weight. The key number, the min‑entropy, zooms in on the largest of these weights. If one or a few players shoulder most of the cost, this maximum weight is large and EGME is small, flagging strong imbalance. If costs are spread evenly, the maximum weight is smaller and EGME is larger, reflecting a more balanced structure. Crucially, this measure is “equilibrium aware”: it depends not just on who is connected to whom, but also on who actually pays for which links. That means two networks with identical wiring but different cost ownership patterns can have very different EGME values, allowing the measure to distinguish formations that pure topology treats as identical.

What theory reveals at low and high link prices

The authors first analyze EGME using exact mathematics for regimes where the link cost is relatively low. When link costs are very small, every player has a strong incentive to connect to everyone else, so the only stable outcome is a fully connected network. In this setting, EGME can be written in closed form and reflects how costs might still concentrate on certain “over‑eager” connectors. When link costs are moderate, stable networks include star‑shaped trees in which one central player connects to all others, as well as denser structures. The authors show how EGME separates these cases: star‑like equilibria, where the center bears more of the burden, lead to noticeably lower EGME than more balanced arrangements with similar overall efficiency. For larger link costs, where stable networks tend to be sparse trees, they derive general bounds on EGME that depend on simple features such as the network’s diameter (longest shortest path) and size, tying the new measure to well‑known structural limits.

What computer experiments show in practice

To see how EGME behaves beyond tidy formulas, the authors simulate equilibrium networks of different sizes and link costs. They generate representative examples consistent with known theory: dense, highly connected networks when links are cheap; stars and tree‑like shapes when links are costly. Across these experiments, EGME rises with network size and responds sharply when structures shift from dense and regular to sparse and varied. It remains very stable for simple, predictable graphs, but shows larger variation when equilibria take random tree forms, revealing its sensitivity to structural randomness. Comparing EGME with familiar metrics such as density, diameter, average path length, clustering, and betweenness centrality, they find strong relationships with global properties like sparsity and path length, but little dependence on purely local clustering. EGME also outperforms more traditional entropy‑style measures when it comes to detecting who is disproportionately paying: in networks with the same wiring but different edge ownership, EGME shifts strongly, while degree‑based entropy does not move at all and Shannon‑type entropy barely changes.

What this means for real-world networks

Seen through EGME, a network is not just a tangle of connections but a pattern of who carries the costs of keeping everyone linked. The study shows that this min‑entropy view can highlight when self‑organized networks are quietly relying on a few heavy contributors, even if the overall layout looks ordinary and standard metrics give similar readings. By linking EGME to both exact theory and simulations, the authors argue that it is a robust tool for assessing structural complexity and stability in systems where individual incentives matter—from communication backbones to collaboration platforms. In simple terms, EGME helps reveal whether a network’s apparent harmony rests on a fair sharing of effort or on a hidden imbalance that might threaten its long‑term health.

Citation: Lin, CC., Hung, CC. On the min-entropy of equilibrium graphs in network creation games. Sci Rep 16, 14369 (2026). https://doi.org/10.1038/s41598-026-43792-2

Keywords: network creation game, graph entropy, complex networks, Nash equilibrium, network stability