The Scheduled Edge

In network creation games, agents buy edges to minimize their communication costs — balancing the price of connections against the penalty of being far from others. Temporal network creation adds a constraint: edges exist at specific time steps, and reachability requires not just a path but a temporally consistent one — each edge must be active at a later time than the previous edge in the path.

Standard models fix the time labels: edges appear at predetermined steps, and agents choose which to buy. Flexible labels give agents control over when their purchased edges appear. This is a richer strategy space — you choose not just which connections to make but when to activate them.

The equilibrium structure changes fundamentally. The paper establishes Nash equilibria, lower bounds on the Price of Anarchy, and upper bounds on the Price of Stability under flexible labeling. The strategic timing dimension creates equilibria that don’t exist under fixed labels — agents can coordinate their temporal choices to create efficient temporally-connected networks that fixed scheduling cannot achieve, or conversely, create temporal bottlenecks that selfishly benefit individuals.

The through-claim: when is an edge active is as strategic a choice as whether the edge exists. In static networks, the only decision is topology — which connections to form. In temporal networks with flexible labels, the same topology can have radically different properties depending on when each edge operates. Two networks with identical structure and identical edges but different activation times can have completely different reachability, and therefore completely different equilibrium properties. Timing transforms a topological game into a scheduling game.