Timing Matters: Online Dynamics in Broadcast Games

Abstract

This paper studies the equilibrium states that can be reached in a network design game via natural game dynamics. First, we show that an arbitrarily interleaved sequence of arrivals and departures of players can lead to a polynomially inefficient solution at equilibrium. This implies that the central controller must have some control over the timing of agent arrivals and departures in order to ensure efficiency of the system at equilibrium. Indeed, we give a complementary result showing that if the central controller is allowed to restore equilibrium after every set of arrivals/departures via improving moves, the eventual equilibrium states reached have exponentially better efficiency.

Part of this work was done when all the authors were visiting Microsoft Research - Redmond. Partial support for this work was provided by the following grants: S. Chawla from NSF grants CCF-1101429 and CCF-1320854; S. Naor from ISF grant 1585/15 and BSF grant 2014414; D. Panigrahi from NSF grants CCF-1527084 and CCF-1535972, an NSF CAREER Award CCF-1750140, and faculty research awards from Google and Yahoo; M. Singh from NSF grant CCF-1717947; S. Umboh from ERC consolidator grant 617951 and NSF grant CCF-1320854.

1 Introduction

In multi-agent systems where different agents have competing objectives, it is well-known that selfish behavior leads to suboptimal system performance at equilibrium. The Price of Anarchy (PoA) and the Price of Stability (PoS), which respectively correspond to the worst and best equilibrium states, are widely used in the literature to quantify this suboptimality relative to an optimal solution designed by a central authority. If these two measures are close to each other, they provide a satisfactory understanding of the quality of stable states the system is expected to reach. However when these measures differ significantly, the system can exhibit multiple equilibria with highly varying performance. But, which of these equilibria can be achieved in actual game dynamics? More generally, what is the minimal guidance by a central authority that can guarantee near-optimal system performance in equilibrium?

In this paper, we study these questions in the context of a game that exhibits a particularly rich set of equilibria, namely the broadcast game. A broadcast game is defined on a rooted undirected graph with costs on edges. Every vertex in the graph has an agent whose goal is to select a routing path to the root that minimizes her own cost. The cost of every edge is shared equally among all agents using it, and the cost of an agent is the sum of her cost shares along the edges in her path to the root. The system is in Nash equilibrium (or NE) if no agent can lower her own cost by unilaterally changing her routing path. The cost of an equilibrium is the total cost of all edges used by at least one agent. The quality of equilibria is measured with respect to the social optimum, which for broadcast games is the minimum spanning tree (mst) of the graph.

Broadcast games are a kind of potential games and the existence of NE in any instance can be proved through a potential function argument, originally given by Rosenthal [34] (see also Monderer and Shapley [30]). Anshelevich et al. [4] observed that different NE in broadcast games can exhibit vastly different performance: the PoA can be as large as $\varOmega (n)$ whereas the PoS (a concept they introduced to show this gap) is bounded by $O(\log n)$; here n denotes the number of vertices in the graph.¹ A long line of work (e.g., [10, 19, 27, 28]) subsequently improved the PoS bound to O(1).

Given this divergence of bounds, Chekuri et al. [13] posed the question of analyzing the quality of equilibria that are actually reachable via natural dynamics—a sequence of single agent moves where the moving agent always chooses a new path that strictly decreases her cost relative to her current path. We call such moves “improving moves” or “best response moves”, depending on whether they merely lower the agent’s cost or are optimal for the agent given the current state of the system. It follows from the potential function argument of Rosenthal [34] that any such sequence of moves will eventually converge to NE.

Chekuri et al. [13] considered the following restricted two-stage process: in the first stage, starting with an empty graph, agents arrive sequentially in arbitrary order and choose their respective best response paths upon arrival; in the second stage, agents make improving moves² in arbitrary order until they reach equilibrium. They showed that the equilibria reachable through this process have a cost of $O(\sqrt{n}\log ^2 n)$ times the mst, a significant improvement over the PoA bound. This bound was subsequently improved to $O(\log ^3 n)$ for the same two-stage process by Charikar et al. [11].

The Dynamic Price of Stability. These previous works motivate extending the notion of the price of stability to online dynamics. In the static (or “one shot”) version of our problem, in which players are initially in an empty configuration, the central planner can force the players into any configuration, in particular the one realizing the price of stability. In the dynamic case, however, the central planner cannot do so since some players have already chosen a route. Thus, the central planner has to offer existing players a better strategy, so as to incentivize changes. Informally, the dynamic price of stability is the cost of a solution in equilibrium resulting from online dynamics, while allowing for algorithmic intervention by the central planner. The notion of dynamic price of stability can be applied to any game in which one needs to characterize which equilibria can be reached via online dynamics, while minimizing the power of intervention of the central planner. It would be very interesting to find further applications of this new notion.

One way to restate Charikar et al.’s result is that the dynamic PoS is polylogarithmic when all arrivals happen before any improving moves. But, what if some agents make improving moves before all of the other agents have arrived, i.e., the sequence of improving moves is interleaved with arrivals? Unfortunately, the analyses presented in [13] and [11] strongly build on the fact that all agents arrive upfront and remain in the system thereafter, and agents must wait for everyone to arrive before making any changes to their strategies. Charikar et al. posed the question of analyzing dynamics in which arrivals and improving moves are interleaved as a “tantalizing and difficult” open problem. In the decade following their work, in spite of tremendous progress in PoS bounds for broadcast games, no progress has been made on understanding more general game dynamics.³

More General Dynamics. Since the work of Chekuri et al., our work is the first to study more general dynamics of the broadcast game. We consider two kinds of extensions to the two-stage process. First, we consider systems with churn where agents arrive as well as depart over time. Second, we allow multiple interleaved stages of arrivals, departures, and improving moves. Our first result shows that if we make a minimal change to the two-stage dynamics studied above, namely adding departures to the first stage, then it is possible to reach an equilibrium that is polynomial (in n) worse than the social optimum, placing it in the same regime as the PoA bound. To the best of our knowledge, this is the first polynomial lower bound for any game dynamics for broadcast games.

Theorem 1

For any large enough integer n, there exists an instance of the broadcast game with n vertices and a sequence of arrivals and departures that terminates in an NE of cost $\varOmega (n^{1/3})$ times that of the minimum spanning tree on all the vertices.

It is important to observe that since we allow departures, not all vertices have agents at the end of the game. This creates two candidates for opt: the optimal Steiner tree on the remaining agents, or the mst on all vertices.⁴ The former leads to trivial and uninteresting lower bounds (see the full version); so, we use the mst as opt in this paper. This choice of a weaker optimum makes for a stronger lower bound.

The Power of Intervention. Given the above lower bound, a natural question is whether some limited intervention from a central planner can lead to a better outcome for the game. At one extreme, if the central planner is allowed to suggest a strategy to every player simultaneously, then any NE, in particular the best one corresponding to the PoS of O(1), can be achieved. This level of control is unrealistic. A more reasonable level of control is for the central planner to suggest improving moves to players one by one; importantly, any such move should lower the corresponding agent’s current cost share, otherwise the player has no incentive to follow the planner’s suggestion.

What about the timing of such interventions? As our lower bound demonstrates, if the timing of interventions is completely adversarial, in particular if no interventions are allowed during the initial arrival/departure phase, the system can end up in a poor NE. To get around this lower bound, we consider dynamics where the central planner is allowed to make a series of improving moves after every adversarial arrival/departure. Observe that the sequence of arrivals and departures can still be ordered adversarially, and indeed can depend on the previous algorithmic interventions. We call such dynamics equilibrium-preserving (eq-p) dynamics because the central planner restores the system to a good equilibrium after every adversarial arrival/departure.

Specifically, the eq-p dynamics starts from an empty configuration and continues in epochs. At the beginning of each epoch the system is at equilibrium. The epoch begins with an arrival or departure, followed by a series of improving moves to restore equilibrium. Once equilibrium is restored, the epoch ends. Our analysis, in fact, allows for multiple simultaneous arrivals⁵ at the beginning of an epoch, and multiple departures at any point of time during the epoch. Formally, we define three different kinds of moves within an epoch:

• 1. (Arrivals.) A set of new players arrive and each picks a best response path with respect to the configuration reached at the end of the previous epoch. (The choice of the set of arrivals is adversarial.)

• 2. (Departures.) A set of players departs the system. (Choice of departing players is adversarial.)

• 3. (Equilibrium Restoration.) The central authority offers players strategies that can improve their (shared) connection costs. This step continues till equilibrium is restored to the system.

Our second result shows that this limited level of central intervention is sufficient to guarantee a NE with exponentially better performance:

Theorem 2

Every instance of the broadcast game using eq-p dynamics converges to an NE of cost $O(\log n)$ times that of the minimum spanning tree on all the vertices.

Observe that, as for our lower bound result, we compare the performance of eq-p dynamics to the mst on all vertices⁶ and not the optimal Steiner tree on the vertices that remain in the system. The two benchmarks are identical when there are no departures but the mst benchmark can potentially be much weaker when there are many departures. However, as mentioned earlier, the Steiner tree benchmark is not interesting because it leads to trivial polynomial lower bounds (see the full version [12]). Furthermore that the guarantee provided by the above theorem holds at the end of every epoch as compared against the mst over vertices that have arrived up to the end of that epoch, not including future arrivals. A natural open question is whether a polylogarithmic dynamic PoS can be achieved through less algorithmic intervention relative to eq-p dynamics, for example, by allowing players to make best response moves instead of improving moves.

Technical Challenges. The broadcast game exhibits a rich set of equilibria and a far richer set of intermediate states of the system. For example, whereas the set of agent strategies (paths) in any equilibrium of the game always forms a tree,⁷ intermediate states, even those reached by a series of best response moves, can contain a complex structure of interconnected cycles. A major impediment to analyzing dynamics is that it is extremely challenging to maintain any structural invariant on intermediate states. Our work overcomes this challenge by algorithmically maintaining such a structural invariant. Whenever the structural invariant is broken by arrivals or departures, we restore it algorithmically. Importantly, we show that this can always be achieved through a sequence of improving moves.

Our structural invariant is a charging of the cost of a state (i.e. collection of paths) against a family of partitions of the underlying graph. Each partition corresponds to a solution to the dual of the standard mst linear program. As such, our charging scheme can be interpreted as a dual fitting approach. One challenge in carrying out this approach is that as agents arrive and leave, our analysis must allow for the dual to become grossly infeasible at intermediate states, which in turn results in very expensive intermediate (non-equilibrium) states. At the crux of our argument is a careful construction of improving moves that ensures that the system cycles between a small set of states of which the stable ones correspond to feasible duals.

Related Work. We have already mentioned the long line of work on improving PoS bounds for broadcast games [4, 10, 19, 27], and the game dynamics studied by Chekuri et al. [13] and Charikar et al. [11]. A different approach was taken by Balcan et al. [6], who considered the problem of influencing the dynamics of broadcast games so as to achieve socially efficient equilibria. In their model, players use expert learning, choosing between a best response expert and a central authority expert suggesting (near-)optimal global behavior. Broadcast games belong to a broader class called network design games (see, e.g., [2, 4, 9, 10, 14, 15, 18, 20, 26, 28]), which in turn, are a special case of the widely studied congestion and potential games (see, e.g., [1, 7, 17, 24, 29, 30, 33,34,35]).

The analysis of game dynamics in this paper crucially relies on the construction of a hierarchial family of multiple dual solutions. This method of analysis has been highly influential in designing online algorithms for network design problems. Implicit use of this method dates back to the work of Imase and Waxman [25] on online Steiner trees and a subsequent line of work of Awerbuch et al. [5], Berman and Coulston [8], Naor et al. [31]. More recently, this method has been explicitly employed in solving a range of node and edge-weighted Steiner network design problems in the online setting [3, 16, 21,22,23, 32]. In terms of the exact techniques, perhaps the closest to our work is that of Umboh [36], who uses hierarchical tree embeddings to analyze greedy-like online algorithms for network design problems. In contrast to these applications in competitive analysis where decisions are irrevocable, game dynamics allows temporary overcharging of dual solutions, which we crucially use in this paper.

Organization of the Paper. We present a proof of our lower bound (Theorem 1) in Sect. 2, and a proof of our upper bound (Theorem 2) in Sect. 3. Due to lack of space, we defer most of the proofs to the full version [12].

2 Lower Bound

In this section, we will show that if arrivals and departures are allowed at non equilibrium states, then no dynamics can lead to a good equilibrium (Theorem 1).

Fig. 1.

Example for $m = 4$. Auxiliary vertices are in red, end vertices are in blue. Ovals represent clusters. Intra-cluster edges are shown as dashed edges. The two bold paths starting from the same cluster successively diverge into different clusters and converge into the same cluster on their way to the root.

We construct a family of lower bound instances parameterized by an integer $m\ge 1$. The $m\hbox {th}$ instance uses the metric induced by weighted graph $G_m$ (see Fig. 1). The vertex set of this graph consists of a root r and $m+1$ layers $V^0, \ldots , V^m$. For $1 \le i \le m$, layer $V^i$ consists of m clusters $C^i_1, \ldots , C^i_m$, each of which is a clique over m vertices. We use $v^i_{j,k}$ to denote the k-th vertex of $C^i_j$; recall that each of i, j, and k take on integral values in [m]. Layer $V^0$ also consists of $m^2$ vertices, which are labeled $v^0_{j,k}$ for $j,k \in [m]$, but there are no edges between these vertices. The vertices of $V^m$ are called end vertices, and those of $V^0$ are called auxiliary vertices. Observe that the graph $G_m$ has $n = m^2(m+1) + 1$ vertices in all.

Next, we describe the edges. Each pair of vertices within the same cluster $C^i_j$ is connected by an edge of length 1/m for all layers except $V^0$. The remaining edges in the graph connect vertices in neighboring layers and are all of length 1. Each auxiliary vertex $v^0_{j,k}$ in $V_0$ is connected to the root and to its corresponding vertex $v^1_{j,k}$ in layer 1. For $1 \le i \le m-1$, we have an edge $(v^i_{j,k}, v^{i+1}_{k,j})$ for each $j,k \in [m]$. In other words, the vertices of the j-th cluster in layer i are connected to the k-th vertices of the clusters in layer $i+1$; in particular, the k-th vertex of the j-th cluster in layer i is connected to the j-th vertex of the k-th cluster in layer $i+1$. For example, see the edges leaving the first (top) cluster of $V_1$ in Fig. 1. Observe that there are exactly $m^2(m+1)$ inter-layer edges, and exactly $m^3(m-1)/2$ intra-cluster edges.

Observe that each end vertex $v^m_{j,k}$ has a unique path $P_{j,k}$ to the root that consists of only inter-layer edges (see Fig. 1). We call these paths canonical paths. Note that each inter-layer edge belongs to exactly one canonical path. In other words, the set of inter-layer edges is a disjoint union of all the canonical paths $P_{j,k}$.

The Cost of the Final Equilibrium. Before describing the sequence of arrivals and departures of terminals, let us analyze the final equilibrium state and its cost relative to the optimal cost. Let $\mathop {{\text {OPT}}}$ denote the cost of the minimum spanning tree over all vertices in $G_m$. Observe that this is an upper bound on the cost of any optimal solution at the end. The final state following our sequence of arrivals and departures, denoted ${\mathscr {F}}$, consists of m players situated at every end vertex $v^m_{j,k}$ in layer m; each player uses the canonical path $P_{j,k}$ to route to the root. The following lemma shows that this is an equilibrium state with a polynomially larger cost relative to $\mathop {{\text {OPT}}}$.

Lemma 1

State ${\mathscr {F}}$ is an equilibrium and the cost of ${\mathscr {F}}$ is $\varOmega (m)\mathop {{\text {OPT}}}$.

Sequence of Arrivals and Departures. The sequence is constructed in m phases, each phase consisting of $m^2$ rounds, one per end vertex $v^m_{j,k}$, and indexed by (j, k). Informally, the objective of each phase is to add one more terminal at each of the end vertices $v^m_{j,k}$. Within round (j, k) in a phase, we use a set of “temporary” terminals whose sole aim is to force the terminal at $v^m_{j,k}$ that arrives at the end of the round to choose the canonical path as its best response. The temporary terminals are introduced at intermediate vertices along the canonical path during the round, and removed at the end of the round.

Formally, let $\prec$ be an arbitrary total order on the pairs (j, k). The sequence $\sigma$ is constructed to maintain the following invariant: at the end of round (j, k) of phase $\ell$, there will be $\ell$ players on $v^m_{j',k'}$ for $(j', k') \prec (j, k)$, and $\ell -1$ players on the remaining end vertices. Furthermore, each player on $v^m_{j,k}$ uses the path $P_{j,k}$.

We now specify the subsequence for each round. Consider round (j, k) of phase $\ell$. For simplicity of notation, we use $v^i$ to denote the vertex of $V^i$ on $P_{j,k}$. We also use $P^i$ to denote the segment of $P_{j,k}$ starting at $v^i$ and ending at the root. The round consists of $m+1$ iterations. In iteration $0 \le i\le m-1$, $m^2$ players arrive at $v^i$. In iteration $i = m$, one player arrives at $v^m$. Finally, the players on $v^0, \ldots , v^{m-1}$ depart. We can now show using induction over the terminal arrivals, that for every terminal the best-response path on arrival is the segment of the canonical path connecting it to the root.

Lemma 2

Consider a terminal arriving at vertex $v^i$ in iteration i of round (j, k) in phase $\ell$. The best-response path of the terminal to the root is the segment of its canonical path $P^i$.

Lemma 2 shows that the sequence of arrivals and departures above terminates in the final state ${\mathscr {F}}$, which costs $\varOmega (m)\mathop {{\text {OPT}}}$ by Lemma 1. Since m is polynomial in the number of vertices, Theorem 1 follows.

3 eq-p Dynamics

In this section and the next, we describe and analyze eq-p dynamics for the broadcast game. We first set up our notation and terminology, and prove some basic structural properties that are used in the rest of the paper. Let $G=(V,E)$ be a complete graph, $|V|=n$, with metric costs $c:V\times V\rightarrow \mathbb {R}_+$ defined on the edges. We assume without loss of generality that every vertex has a unique agent (a.k.a. terminal) residing at it. Agents arrive and depart over time. Since edge costs satisfy the triangle inequality, before an agent arrives, no other agents route their paths via the vertex corresponding to this agent. Indeed, we assume that our intervention algorithm has no knowledge of vertices corresponding to agents that are yet to arrive. However, if an agent already in the system departs, other agents may continue to route their paths via its vertex, and the vertex remains in the graph. At any point of time during the process, our algorithm only considers the subgraph induced over vertices whose agents have arrived prior to that time. We call a vertex active if the agent at that vertex is still in the system.

The graph G is revealed via an online process that is divided into epochs (indexed by time t). At the start of epoch t, the set of vertices in G that have already appeared is denoted by $V_t$. We denote the set of active terminals among them by $A_t \subseteq V_t$. Each terminal $v\in A_t$ has a current routing path $p_v$ connecting it to the common root r. The cost share of v along this path is the sum of v’s cost share over the edges in the path, where the cost of an edge is equally shared between all terminals currently using it. In the eq-p scenario, we further enforce the invariant that the set of paths $p_v$ are in NE, i.e., no terminal has an incentive to unilaterally deviate to a different routing path.

The routing at any time t is defined to be the set of routing paths $(p_v)_{v\in A_t}$. A best response path of a terminal v with respect to a routing, denoted $p^*_v$, is a path from v to r with the minimum shared cost if v were to move to this path. If there are multiple such paths, we break ties in favor of paths having fewer edges with no terminal other than v using them. Note that this may not break all ties, in which case, any of these paths can be designated as the best response path. A terminal $v\in A$ is said to have an improving move with respect to a routing if by moving from its current path $p_v$ to a new path $q_v$ strictly decreases v’s cost share. Given a routing, its potential [34] is defined to be $\varPhi = \sum _{e \in E} \sum _{i=1}^{N_e} c_e/i$, where $N_e$ is the number of agents using e. A standard argument shows that any improving move decreases the potential by a value which is uniformly bounded away from zero, resulting in a finite convergence of our dynamics. The following well-known lemma states that in equilibrium, the routing paths form a tree.

Lemma 3

In equilibrium, the routing paths of a broadcast game form a tree.

Each epoch t is divided into several phases. The first phase consists of an arrival or departure event. In the former case, a new set of terminals $U_t\subseteq V\setminus V_t$ arrive, and the cost of all edges incident on terminals in $U_t$ is revealed. Each new terminal $u\in U_t$ chooses a best response routing path $p_u$. In the latter case, a set of terminals leave, thereby removing the corresponding vertices from the set of terminals $A_t$. (Note that the corresponding vertices remain in $V_t$.) Lemma 6 establishes that the structure of the set of routing paths after arrivals or departures remains a tree.

Both arrival and departure events lead to changes in the cost shares of edges. In the eq-p scenario, this might lead to a violation of the equilibrium state that was being previously maintained. In this case, the system performs a sequence of improving moves, in each of which a terminal changes its routing path in order to reduce its cost share.

Improving moves may temporarily create cycles in the collection of routing paths $\{p_v\}_{v\in A_t}$. We order and group improving moves into contiguous blocks or phases such that every phase ends with the routing paths forming a tree. Furthermore, the trees at the beginning and end of the phase differ in a single pair of edges. The collection of moves in each such phase is called a tree-follow move.

Definition 1

(Tree-follow move). A tree-follow move from u to v in T is a sequence of improving moves that start with routing tree T and end with routing tree $T'=T\setminus (u,\text {parent}(u))\cup (u,v)$, where $\text {parent}(u)$ is the parent vertex of u in T. Observe that each terminal in the subtree rooted at u in T reroutes its path to the root according to $T'$.

Because of departure events, the routing tree may contain non-terminal vertices as Steiner vertices. It is convenient to extend the notion of an improving move to vertices that are not terminals. Let $w\notin A$ be a non-terminal vertex. We say that w has an improving move if the following properties hold: (1) There exists a terminal v whose routing path $p_v$ includes w; let $p_w$ denote the segment of $p_v$ between w and r; (2) There exists a path $q_w$ between w and r such that if v were to retain its current routing path from v to w but move from $p_w$ to $q_w$, then the cost share of v would strictly decrease.

A priori, it is not clear whether improving moves can always be grouped into tree-follow moves. In Lemma 7, we show that in every routing tree T which is not in equilibrium, there exists a sequence of improving moves that collectively form the tree-follow move from u to v for some vertices u and v. When there are multiple such moves, we use a careful charging scheme to identify the order in which tree-follow moves should be implemented. (See Algorithm select tree move defined at the end of this section.)

Since every vertex in a tree has a unique path to the root, it suffices to specify the tree itself in lieu of all of the routing paths. Henceforth, we will use $T_t$ to denote the tree induced by $\{p_v\}_{v\in A_t}$ without explicitly specifying the paths themselves.

Charging Scheme. In proving the upper bound for eq-p dynamics, we use a dual charging scheme to bound the cost of the routing tree. We define the dual and the corresponding lower bound on the optimal cost next. We call a partition $P = (S_1,\cdots , S_m)$ of the vertex set V a level-j dual for an integer j if it satisfies the following:

• P is a partition: $\cup _{S\in P} S = V$, and for any $S_a, S_b\in P$, $S_a\cap S_b=\emptyset$.

• The components have bounded diameter: for any $S\in P$, and any vertices $x,y\in S$, $c(x,y)< 2^j$.

• The components are far from each other: there exists a “center” $s_i$ in each component $S_i$, such that for all $S_a, S_b\in P$, $c(s_a,s_b)\ge 2^{j-1}$.

We use the term cuts to denote the components S of the partition. The lemma below follows immediately from the observation that any spanning tree over V must connect the centers of all cuts in a level-j dual P.

Lemma 4

For any level-j dual P, the cost of the minimum spanning tree opt is at least $2^{j-1}(|P|-1)$.

In order to bound the cost of an equilibrium resulting from eq-p, we relate the cost of the edges used in the solution to a family of duals. Let $\varPi = \{P_j\}_{j\in {\mathbb {Z}}}$ denote a family of partitions, where $P_j$ is a level-j dual.

Our charging scheme for routing solutions that form a tree proceeds as follows. Every vertex in the routing tree is responsible for the cost of its parent edge. Consider an edge $e=(v,\text {parent}(v))$ with length in $[2^{j+2},2^{j+3})$ for some $j\in {\mathbb {Z}}$. We charge the cost of this edge to the cut in the level-j dual that contains v: $S\in P_j$ such that $v\in S$. Our goal is to show that every cut gets charged a small number of times, and use the following well-known property (see the full version for a proof).

Lemma 5

Suppose that our charging scheme charges each cut in the family $\varPi$ at most once. Then the cost of the solution is at most $O(\log n)$ opt.

For much of our analysis, we will assume that the dual family $\varPi$ is provided to us. In the full version, we discuss how to construct this family algorithmically as terminals arrive online.

Classification of a Tree Routing. We classify the tree routings reachable via eq-p dynamics into one of four states depending on the charging structure defined by the solution. We remark that not all tree routings are reachable via eq-p dynamics, indeed even the set of equilibria obtained is smaller than the set of all equilibria. Let T be a routing tree for some set of active terminals A. We say a vertex u is a leaf (non-leaf) if it is a leaf (non-leaf) in T. Note that all leaves must be terminals, but a non-leaf vertex may or may not be a terminal.

• 1. balanced-equilibrium: In this state, no terminal (and therefore, no non-terminal vertex in T) has an improving move. Furthermore, every cut is charged at most once. (Note that not every NE is a balanced-equilibrium state.)

• 2. balanced: In this state, some terminals (and potentially non-terminals) may have improving moves, but every cut is charged at most once.

• 3. leaf-unbalanced: In this state, every cut is charged by at most one non-leaf vertex (and any number of leaf terminals). (Recall that leaf vertices in the routing tree are necessarily terminals.)

• 4. non-leaf-unbalanced: In this state, all but one of the cuts are charged by at most one non-leaf vertex (and any number of leaf terminals). The exceptional cut, that we denote by $S^*$, is charged by at most two non-leaf vertices, say u and v (and any number of leaf terminals). One of these, u or v, must be the last vertex to have made a (tree-follow) move.

Note: balanced-equilibrium $\subseteq$ balanced $\subseteq$ leaf-unbalanced $\subseteq$ non-leaf-unbalanced, where $A\subseteq B$ implies that a routing tree in state A is also in state B.

Selecting a Tree-Follow Move. To define the tree-follow move performed in a non-equilibrium tree state T, we establish a system of priorities among the improving tree moves based on the current state of the routing tree. A tree follow move of u to v is said to be a leaf move if v is a leaf in T, and a non-leaf move otherwise.

The validity of the algorithm depends on two claims. The first shows that whenever a cut is being charged by a leaf and a non-leaf, at least one of these two vertices has an improving move to the other. In this case, we can find a valid tree-move for Step (3c) of select tree move. The second shows that in a non-leaf-unbalanced state, whenever a cut is being charged by two non-leaves, at least one of these two vertices has an improving move to the other; we can then find a valid tree-move for Step (4) of select tree move.

3.1 Analysis of eq-p Dynamics

We now given an outline of the proof of Theorem 2. Our argument hinges on a closure property: the epoch starts with the routing tree being in the balanced-equilibrium state; Lemma 7 argues that whenever the current routing tree is not in equilibrium, at least one improving move exists, and we can use algorithm select tree move to make a move; Lemma 8 then shows that for the moves made by algorithm select tree move, the routing tree remains in one of the four states defined above, in particular, it is always in a non-leaf-unbalanced state. The epoch ends when the routing tree re-enters a balanced-equilibrium state. At this point, by definition, each dual cut is charged at most once, and therefore, by Lemma 5 the cost of the routing tree is bounded, and Theorem 2 follows. We must also argue termination of the sequence of moves, but this follows directly from a standard potential argument based on the fact that all our moves are improving moves. The following lemmas capture the essence of our argument.

Observation 1

In eq-p dynamics the routing paths at the end of every phase form a tree.

Lemma 6

After the arrival or departure of a set of terminals in an balanced-equilibrium state, the routing tree T remains in a leaf-unbalanced state.

Lemma 7

If the routing tree is not in equilibrium, then at least one improving tree-follow move exists.

Lemma 8

Let T be the routing tree for which we make an improving tree-move in Step (3) of algorithm eq-p.

• (i) If T is in a balanced state but not in a balanced-equilibrium state, then after the move selected in Step (2) of select tree move, the resulting tree is in a non-leaf-unbalanced state.

• (ii) If T is in a leaf-unbalanced state, then after the move selected in Step (3) of select tree move, the resulting tree is in a non-leaf-unbalanced state.

• (iii) If T is in a non-leaf-unbalanced state, then after the move selected in Step (4) of select tree move, the resulting tree is in a non-leaf-unbalanced state.