The Price of Universal Temporal Reachability
Binh-Minh Bui-Xuan, Nhat-Minh Nguyen, Sébastien Tixeuil, Yukiko Yamauchi · 2026
Read The Price of Universal Temporal Reachability by Binh-Minh Bui-Xuan, Nhat-Minh Nguyen, Sébastien Tixeuil, Yukiko Yamauchi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-15176.txt.
Introduction
Bui-Xuan and co-authors study a network creation game where edges exist only at set time instants. Players add or drop time-labeled edges to cut their own costs. Costs mix edge upkeep with the sum of temporal distances to all other players. For strict temporal shortest paths, the price of anarchy stays constant when the upkeep factor is below two. At high upkeep, some equilibria cost far more than the optimum. The authors also exhibit a best-response cycle, so play may never settle at an equilibrium.
Catalog record
| CREATOR | Binh-Minh Bui-Xuan, Nhat-Minh Nguyen, Sébastien Tixeuil, Yukiko Yamauchi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 33134 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.15176
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The Price of Universal Temporal Reachability Binh-Minh Bui-Xuan, Nhat-Minh Nguyen, Sébastien Tixeuil, Yukiko Yamauchi Abstract Dynamic networks are graphs in which edges are available only at specific time instants, modeling connections that change over time. The dynamic network creation game studies this setting as a strategic interaction where each vertex represents a player. Players can add or remove time-labeled edges in order to minimize their personal cost. This cost has two components: a construction cost, calculated as the number of time instants during which a player maintains edges multiplied by a constant α \alpha , and a communication cost, defined as the average distance to all other vertices in the network. Communication occurs through temporal paths, which are sequences of adjacent edges with strictly increasing time labels and no repeated vertices. We show for the shortest distance (minimizing the number of edges) that the price of anarchy can be proportional to the number of vertices, contrasting the constant price conjectured for static networks. LIP6, CNRS, Sorbonne Université, [email protected] LIP6, CNRS, Sorbonne Université, [email protected] LIP6, CNRS, Sorbonne Université, [email protected] Department of Informatics, Kyushu University, [email protected] ccs Theory of computation Network formation ccs Mathematics of computing Paths and connectivity problems keywords dynamic network, game theory, Nash equilibrium † † runningauthor: Binh-Minh Bui-Xuan, Nhat-Minh Nguyen, Sébastien Tixeuil, and Yukiko Yamauchi † † copyright: Binh-Minh Bui-Xuan, Nhat-Minh Nguyen, Sébastien Tixeuil, and Yukiko Yamauchi † † editors: John Q. Open and Joan R. Access † † event-title: 42nd Conference on Very Important Topics (CVIT 2016) † † event-shorttitle: CVIT 2016 † † event-acronym: CVIT † † year: 2016 † † event-date: December 24–27, 2016 † † event-location: Little Whinging, United Kingdom † † series-volume: 42 † † articleno: 23 1 Introduction The Network creation game (NCG) was first introduced by Fabrikant et al. [ 13 ] and has been extensively investigated as a game-theoretic model to understand networks formed by selfish agents. An NCG is defined by the strategy and cost at agents in the typical non-cooperative strategic game fashion. The strategy space of an agent is the subset of agents, that means the agent constructs a communication edge at a cost of \alpha to each agent in its strategy. A strategy profile (i. e., the tuple of strategies) of all agents defines a communication network, where each communication link can be used by other agents in both directions. The cost of an agent is the sum of the construction cost, which is the size of its strategy multiplied by \alpha , and the communication cost, which is the sum of distance to all the other agents on the communication network formed by the current strategy profile. Each agent can change its strategy so that its cost is minimized, but selfish behavior of agents may result in an Nash equilibrium , where no agent can strictly reduce it cost by changing its own strategy. The social cost of an NCG is the sum of the cost of all agents, and the quality of a communication network formed by NCG is evaluated by the Price of Anarchy (PoA) , which is the ratio between the maximum social cost of a Nash equilibrium and optimal social cost. Fabrikant et al. pointed out that if every Nash equilibrium is a tree, then the PoA of an NCG is smaller than five [ 13 ] . Then, the topology of a Nash equilibrium has been extensively investigated to prove this “Tree Conjecture,” while there are non-tree Nash equilibria for n<\alpha . Recently, Dippel and Vetta showed that the conjecture is true for \alpha>3n-3 , thus the PoA is constant [ 12 ] . However, Fabrikant et al. pointed out that computing a best response of NCG is NP-hard in their seminal paper [ 13 ] , and Kawald and Lenzner showed that an NCG may admit a best response cycle [ 14 ] . That is, selfish players cannot always form an efficient communication network by rational strategy changes. Alon et al. introduced a restricted version of the NCG, called the basic network creation game (BNCG), where an agent can only remove one incident edge and add another incident edge at one time [ 2 ] . The BNCG removes the construction cost since any strategy change cannot change the size of a strategy profile, and it focuses on the structure of a communication network. Additionally, a best response of a swap game can be computed in a polynomial time. The authors showed that the diameter of any tree Nash equilibrium of the BNCG is two (i.e., a star), while that of a general graph is 2^{O(\sqrt{\lg n})} . Lenzner showed that BNCG starting in a tree communication graph is a potential game , i.e., there exists a potential function on the strategy profile that monotonically decreases by selfish strategy changes. They showed that BNCG converges to an equilibrium in O(n^{3}) strategy changes, while it admits a best response cycle on a general graph. Inspired by large computer networks, where users and computers are subject to hardware limitations, locality, and asynchrony, NCGs under different constraints have been introduced. Bilò et al. introduced an NCG with local information, where each player knows strategies of other players in its k -neighborhood and considers the worst case for the other players in the outside of its visibility [ 5 ] . Cord-Landwehr and Lenzner introduced an NCG where the strategy space of a player is other players within distance k but the communication cost of a player depends on the entire communication network [ 10 ] . Bilò et al. introduced the NCG on a host graph, where agents cannot construct a communication edge not included in the host graph [ 6 ] . In recent years, temporal graphs have attracted attention as a fundamental mathematical framework for modeling the dynamic behavior of computer networks. A temporal graph is an edge-labeled graph, where a label of an edge shows when the edge is available. Bilò et al. introduced the temporal reachability network creation game , where the players buy the edges of a host temporal graph [ 3 ] . Specifically, the authors consider a single-labeled temporal graph, where each edge is available only at a particular time instance. The strategy space of a player is a subset of players, which corresponds to a set of temporal edges, i.e., a tuple of an edge and time instance. The construction cost of a player is the size of its strategy, and the communication cost is the number of unreachable players multiplied by a constant K , where two players are reachable when there exists a monotonically increasing temporal path. They showed that PoA is in \Omega(\log n) for n players by showing that a \log n -dimensional hypercube is a Nash equilibrium while a spanning tree is a social optimum. This result matches the optimum and minimal network design for temporal graphs by Akrida et al. [ 1 ] . The authors showed that given any graph G , the minimum number of time labels required for reachability between any pair of vertices is achieved by assigning time labels along a spanning tree of G and it is 2n-3 , while there exists