Sequential network design

We examine dynamic network formation from a centralized perspective, where a forward-looking social planner constructs one new link between previously unconnected nodes in each period. The planner derives utility from the discounted sum of benefits generated throughout the formation process. Assuming the planner’s instantaneous utility depends monotonically on the aggregate number of walks of various lengths within the network, we derive several key results. First, it is always optimal to form a nested split graph at each stage, regardless of the discount function. Second, when the planner is sufficiently myopic, the optimal strategy uniquely generates a quasi-complete graph in each period. This finding provides a micro-foundation for quasi-complete graphs as natural outcomes of greedy network formation processes. Finally, we extend our analysis to weighted networks, demonstrating the robustness of our results.