Congestion Games with Polytopal Strategy Spaces

1 Introduction

There has been increasing interest in using game theory to model real-world multiagent systems, with the goal of predicting the behavior of the agents in these settings. This will often require the computation of game-theoretic solution concepts given a description of the model. Nash equilibrium is the most well-known solution concept, and the computational problem of finding Nash equilibria has received extensive study in recent years. While perhaps the most famous theoretical results [Chen et al., 2009; Daskalakis and Papadimitriou, 2005] established the (PPAD-) hardness of the problem given a game in normal form, this does not necessarily mean efficient computation is impossible in practice. In fact, most large games of practical interest are highly structured, and this structure can potentially be exploited for efficient computation.

One of the more well-known class of structured games is congestion games, first introduced in [Rosenthal, 1973]. Congestion games model the situation in which there is a set of resources and each agent selects a subset of resources. The cost of using a resource depends on the total number of agents using it. As such, the agent's goal is to select a subset of resources that minimizes the total cost. An important subclass is network congestion games, which have been used to model agents' decisions when dealing with (potential) traffic congestion on roads, as well as when sending data through a computer network. More concretely, consider a road network (represented by a graph) and each agent wants to travel from a source to a destination. Since the congestion/delay of each road depends on the number of people driving on them, the goal of each agent is to select a route, from its source to its destination, that minimizes the total delay which is the sum of the delay the agent experience on each road of the route.

A key challenge. Notice that in network congestion games each player's set of pure strategies (i.e. paths) can be exponential in the size of the graph. This is not unique to network congestion games: since a pure strategy is a subset of resources, in many congestion games of interest, the set of pure strategy is exponential in the number of resources. This presents a significant obstacle to efficient computation, as most existing algorithmic approaches for gametheoretic computation assume that the game has polynomial type [Daskalakis et al., 2006; Papadimitriou and Roughgarden, 2008], i.e., a polynomial number of players and strategies, because they rely on being able to enumerate the set of pure strategies for each player. As a result, such algorithms would take exponential time on these congestion games.

In this paper, we study congestion games in which each player's strategy space is defined by a polytope, specified as set of linear inequalities. This captures a wide range of congestion games; for instance, in the case of network congestion games, we can capture the set of pure strategies of each player using a set of flow constraints [Daskalakis et al., 2006].

In particular, our main contributions are: (i) we show that we can represent players' mixed strategies compactly using marginals. As a result, we can compute the expected utilities and best responses in polynomial time using the marginals as opposed to the exponential time and space required when using the mixed strategies directly. (ii) We reduce the problem of computing a best (or worst) social welfare symmetric approximate Nash equilibrium in symmetric congestion games to a constraint optimization problem on a graph formed by the resources and strategy constraints. (iii) We provide a fully polynomial approximation scheme (FPTAS) when the graph has bounded treewidth. As a corollary, our algorithm can be used to solve network congestion games efficiently when the network has bounded degree and bounded treewidth.

1.1 RelatedWork

As mentioned earlier, congestion games are first introduced and studied in [Rosenthal, 1973]. It has been shown that every congestion game has a pure-strategy Nash equilibrium (PSNE) via a reduction to its potential game. Despite of this, finding a PSNE is PLS-complete even in network congestion games [Fabrikant et al., 2004]. In the case of symmetric network congestion games, Fabrikant et al provided a polynomial time algorithm to find a PSNE. Independent of our work, a recent work [Pia et al., 2015] also studied totally unimodular symmetric congestion games and showed that there is a polynomial time algorithm to compute a PSNE. Furthermore, they also show that it is PLS-complete to find a PSNE in the asymmetric case. In contrast, we focus on finding symmetric approximate mixed-strategy Nash equilibria, which required us to develop novel techniques on compactly representing mixed strategies that is different from the existing literature on congestion games. Furthermore, our algorithm is able to compute extremal equilibria, such as those with the best/worst social welfare, which provide more information about the entire set of equilibria. The only other result for optimal equilibria in congestion games is Ieong et als' algorithm for optimal PSNE in singleton congestion games, in which each pure strategy consists of one resource and thus there are only a polynomial number of pure strategies per player [Ieong et al., 2005]. Our algorithm is applicable to a much wider range of congestion games, including those with exponential number of pure strategies.

2 Preliminaries

A congestion game is specified by the tuple (N↪ R↪ ¶Si♦i2N ↪ ¶cr♦r2R↪ ¶ui♦i2N ) where

• ÷ N = ¶1↪ ▷▷▷↪ n♦ is the set of players.
• ÷ R = ¶1↪ ▷▷▷↪m♦ is the set of resources.
• ÷ Each pure strategy si 2 Si of player i corresponds to a subset of resources, represented by a ♣R♣-dimensional 0-1 vector. Let sir be the corresponding component of a resource r 2 R.
• ÷ Let S = S1 ⇥ ▷▷▷ ⇥Sn and s 2 S be a joint pure strategy of the players.
• ÷ # : R⇥S ! N is a function that counts the numbers of times the resources are used given joint pure-strategies. In other words, #(r↪ s) = Pi2N sir.
• ÷ cr : N!R is a cost function for resource r 2 R.
• ÷ Given a joint pure-strategy s = (si↪ s-i) 2 S, the utility of player i is defined to be ui(si↪ s-i) = - Pr2R:sir=1 cr(#(r↪ s)) = - Pr2R sircr(#(r↪ s))▷

Before we move on, we make the following assumption.

A congestion game with polytopal strategy space (CG+) is a congestion game (N↪ R↪ ¶Si♦i2N↪ ¶cr♦r2R↪ ¶ui♦i2N) in which Si is represented as a polytopal strategy space: Si = Pi \ ¶0↪ 1♦m where Pi = ¶x 2 Rm ♣ Dix  fi♦, Di 2 Zli⇥m, and fi 2 Zli . In other words, Pi is a rational polytope defined by li linear constraints. Since Si should be nonempty for the game to be well-defined, we require that Pi \ ¶0↪ 1♦m 6= ; for each i 2 N.

Assumption 1. For each player i, the constraint matrix Di is totally unimodular. 1

As a result of this assumption, all extreme points of the polytope Pi are integral (and therefore pure strategies of i). In other words, Pi = conv(Si).

Network Congestion Games. For instance, network congestion games are an important class of CC + that has the totally unimdoular property. A network congestion game of n players is defined on a directed graph G = (V↪E) with vertex set V and edge set E. Each player i's goal is to select a path from its source si 2 V to its destination di 2 V that minimizes the sum of delay on each edge, which depends on the number of players selects the edge. The set of resources is the set E, and the strategy set of each player i is the possible number of paths from si to di in G. For each player i, its constraint matrix Di is the ♣V ♣ by ♣E♣ incidence matrix of G and Di is totally unimodular [Pia et al., 2015].

Notation and Definition. The set of mixed strategies of player i is defined to be the set of probability distributions over i's pure-strategy set Si. We let Xi = ∆(Si) to denote such set and let X = Xi⇥▷▷▷⇥Xn be the joint mixed-strategy set. Moreover, for any xi 2 Xi, xi(si) denote the probability of playing pure-strategy si 2 Si and Psi2Si xi(si) = 1. Let x(s) = Qi2N xi(si). Given a joint mixed strategy x 2 X, the expected utility of player i is defined to be Es⇠x[ui(si↪ s-i)] = Ps2S x(s)ui(si↪ s-i). With a slight abuse of notation, we let ui(xi↪ x-i) = Es⇠x[ui(si↪ s-i)]. For the rest of the paper, we assume the utility values ui(s) are all between zero and one.

For ease of reference, we provide the following standard definition of Nash Equilibrium in terms of best-response.

Definition 1. Given a CG+ and a joint mixed strategy x-i 2 X-i of other players except i, the mixed strategy xi is an ✏-best-response of player i if and only if ui(xi↪ x-i) ≥ ui(¯xi↪ x-i) - ✏ for each ¯xi 2 ∆(Si) and some 1 ≥ ✏ ≥ 0.

Definition 2. Given a CG+, a joint mixed strategy x 2 X is an ✏-mixed-strategy Nash equilibrium (✏-MSNE) if and only if for each player i 2 N, playing xi is an ✏-best-response to x-i. We have an exact MSNE when ✏ = 0.

It is not hard to see that computing best responses is a key computational step in finding an MSNE, and computing expected utilities is an important part of finding best responses.

1 Amatrix is totally unimodular if each of its square sub-matrices has determinant of 1, 0, and -1. [Hoffman and Kruskal, 1956]

However, there are two key issues in using the traditional approach to compute expected utilities. The first is that we need to specify the probability of playing each pure strategy, and, in order to this, we need to know the set Si for each player i. While finding a solution that is in the polytope takes polynomial time, finding and enumerating all of the feasible solutions would take exponential time. Second, computing expected utilities of a given joint mixed strategy by directly summing over the joint pure strategies could take time exponential in the number of players.

In the next section we describe a way to compactly represent each mixed strategy (without enumerating all of the pure strategies), which then allows us to compute the expected utilities more efficiently.

3 Representation of Mixed-Strategies

It turns out that we can use marginal vectors to compactly represent mixed strategies. In particular, given a mixed strategy xi 2 Xi of player i, we define the marginal vector pxi i = (pir)r2R to be an m-dimensional vector such that pxi ir = Psi2Si sirxi(si). In other words, pxi ir specifies the probability that i plays resource r given the mixed strategy xi. When the context is clear, we will drop the superscript xi. As a result, we can show that we can compute the expected utility of each player using the marginal mixed-strategies.

Claim 1. Given a joint mixed-strategy x-i 2 X-i of other players except i and a pure-strategy si 2 Si, the expected

Claim 2. Given a joint mixed strategy x-i 2 X-i of other players except i and a pure strategy si 2 Si, let pj = (pjr)r2R be the marginal vectors of the player j 2 N ∩ ¶i♦ such that pjr = Psj2Sj sjrxj(sj). Let ⌦jr = ¶0↪ 1♦ to be the outcome of whether player j will play a pure strategy that contains the resource r. The expected utility of i of playing si can be written as

Lemma 1. Given a joint mixed-strategy x 2 X, the expected utility of player i can be computed via the following

where ⌦r = Qj2N∩¶i♦ ⌦jr is the Cartesian product of the sets (⌦jr)j2N∩¶i♦.

The above shows that we can compute the expected utilities of the players by using marginal vectors. Directly computing the above sum requires m♣⌦r♣ = m2n-1 summands. Nevertheless, expected utilities can be computed in polynomial time, using a dynamic programming approach analogous to [Papadimitriou and Roughgarden, 2008; Jiang et al., 2011].

FromMarginal Probabilities to Mixed-Strategies Let us now consider the issue of constructing a mixed strategy given a marginal vector. First of all, since we have assumed that the extreme points of the polytope Pi are integer points, and thus Pi = conv(Si), this becomes the problem of describing a point in a polytope by a convex combination of extreme points of the polytope. By Caratheodory's theorem, given ⇡i 2 Rmi there exists a mixed strategy of support size at most mi + 1 that matches the marginals. There has been existing work that provides efficient constructions for different types of polytopes, including the Birkhoff-von Neumann theorem and its generalizations [Budish et al., 2013]. The most general result in [Gr¨otschel et al., 1981] reduces the problem to the task of optimizing an arbitrary linear objective over Pi. This can be solved via linear programming in time polynomial in m and li (the number of constraints in Pi).

Thus, instead of specifying the probabilities of the mixedstrategies, which can be exponential, now we only need to specify the marginal probabilities of playing the resources.

3.1 Linear Programming Formulation of Best Responses

As part of our algorithmic approach for finding MSNE, we would like to formulate the best response condition as a set of constraints on the player's marginal vectors. One formulation is that the expected utility of playing the best response should be greater or equal to the expected utilities of playing all other pure strategies. However, even though we can compute expected utilities efficiently, stating the above will require an exponential number of inequality constraints. Instead, we will reformulate the best-response condition of each player using linear programing.

Let pi = (pir)r2R be a marginal vector of player i. Let ri(p-i) = (Ur(p-i))r2R be the (resource-utility) vector that specifies the contributions to i's utility from each resource given that the other players play the strategy p-i. Then the expected utility of i (the expression in Lemma 1) can be written as pTi ri(p-i). Therefore, given the marginal vectors of other players, the best-response for player i is the solution to the following linear program.

We can formulate the dual linear program as the following.

Since the primal LP is feasible, by LP duality the primal and dual LPs obtain the same optimal objective value. Therefore, pi is Player i's best response when there exists a feasible dual vector λi such that pTi ri(p-i) = f T i λi. Thus, a feasible marginal vector ¯ p is an MSNE if for each player i, there exists λi ≥ 0 such that DT i λi ≥ri(¯ p-i) and ¯ pTi ri(¯ p-i) = f T i λi.

Therefore, to check whether a particular marginal vector is a best-response, we can check to see whether the expected utility is equal to the optimal solution of the dual program.

This will involve only a polynomial number of constraints and variables, in contrast to the exponential number of constraints in the direct formulation. Our goal now is to find a set of marginal probabilities that will correspond to an MSNE.

Notice that the players' linear programming formulation of best responses do not tell us how to find an equilibrium, thus we provide an algorithm to find one next.

4 Optimal Approximate Symmetric MSNE

Most algorithmic results for congestion games focus on finding a PSNE, including polynomial algorithms for symmetric network congestion games [Fabrikant et al., 2004] and symmetric CG+ [Pia et al., 2015]. Nevertheless, finding one equilibrium would have limited usefulness since there can be an exponential number of equilibria in a game. We instead focus on finding extremal equilibria, which tell us more information about the entire set of equilibria. In particular, we consider the problem of computing a best/worst social welfare symmetric ✏-MSNE efficiently for symmetric CG+. Our results and algorithm can be extended to k-symmetric CG+ with constant number of player types k.

Definition 3. Consider a CG+ with (N↪R↪ ¶Si♦i2N↪ ¶cr♦r2R↪ ¶ui♦i2N). The game is symmetric if and only if Di = Dj = D, fi = fj = f for all i↪ j 2 N 2 .

Below, we state a known useful result [Nash, 1951].

Proposition 1. For every symmetric CG+, there is a symmetric MSNE in which every player plays the same strategies.

Since the same mixed strategies can be represented using the same marginal vectors, the above implies the existence of symmetric MSNE in terms of marginal vectors.

While there can be multiple symmetric MSNE in a symmetric CG+, we are interested in those with maximal (or minial) social welfare, where social welfare is defined to be the sum of all players' expected utilities. Since in a symmetric MSNE of a symmetric game, all players have the same expected utility, this is equivalent to finding symmetric MSNE with maximal/minimal utility for one player.

Next, we show the existence of a symmetric ✏-MSNE in which the marginal vector lies in a discretized grid in Pi. This allows us to search for ✏-MSNE in this discretized space.

Lemma 2. For any δ > 0, there is a (symmetric) marginal vector q = (qr)r2R in which qr 2 ¶0↪ 1K ↪ 2K ↪ ▷ ▷ ▷ ↪ 1♦ and K = O( logm δ2 ), such that u(q↪ q-i) = qT r(q-i) ≥ q0T r(q-i)-O(δnm) for q0 2 [0↪ 1]m that satisfies Dq0  f.

Proof. Recall that there is at least one s 2 S⇤ such that Ds  f. It follows from Proposition 1, there is a symmetric MSNE x⇤ 2 X in any symmetric CG+. Let p = (pr)r2R be the marginal vector of the MSNE. From the approximated version of the Caratheodory's theorem (Theorem 3 of [Barman, 2015]), for every δ > 0 and for every p 2 conv(S), there is a multi-set Q ⇢ S⇤ of size O( logm δ2 ) and q = 1 ♣Q♣ P¯ q2Q ¯ q and q 2 conv(S⇤ ) such that ♣♣p - q♣♣1  δ. Thus, there is a marginal mixed-strategies q such that ♣pr - qr♣  δ for all r 2 R. Next, we provide the following useful claims.

2 This implies Si = Sj = S⇤ , Pi = Pj = P ⇤ for all i↪ j 2 N.

Proof. (Sketch) From Lemma 1, the difference of the expected utility from a resource r can be written as ♣r(q-i)r - r(p-i)r♣  P!r2⌦r ∣∣∣Qn-1 j=1 q!rj r (1- qr)1-!rj - Qn-1 j=1 q!rj r (1- qr)1-!rj ∣∣∣,

because the utility/cost functions are between 0 and 1. It can be shown that the total variation distance of the above distribution is O(δn) [Daskalakis et al., 2009].

Claim 4. For any marginal mixed-strategy p, ♣pT r(p-i) - pT r(q-i)♣  O(δnm).

Claim 5. The marginal symmetric MSNE p is an O(δnm)- best-response to the marginal mixed-strategy q when all other players play according to q.

Proof. By the definition of the symmetric MSNE, for any p0 2 conv(S), pT r(p-i) ≥ p0T r(p-i). Moreover, pT r(q-i) + O(δnm) ≥ pT r(p-i) ≥ p0T r(p-i) ≥ p0T r(q-i) - O(δnm)↪ where the first inequality is by Claim 4, the second inequality is by the definition of MSNE, and the last inequality is by Claim 4. It follows that pT r(q-i) ≥ p0T r(q-i)-O(δnm)▷ Our result follows since p is no less than the expected utility of other marginal mixedstrategies minus O(δnm).

To finish the proof, notice that, by our construction/existence of q, for all r 2 R, ♣pr - qr♣  δ. Thus,

and the last inequality is by Claim 5. Therefore, q is an O(δnm)-best-response to all others using the marginal mixed-strategies q. If every player plays according to q, then we have an O(δnm)-MSNE.

4.1 Conditions for Symmetric ✏-MSNE

From the proof of Lemma 2, we know the possible (discretized) values of q. However, the crucial part is checking whether each marginal mixed-strategy (of the discretized space) can be used to form an ✏-MSNE.

While we could use the standard ✏-MSNE conditions for a given marginal mixed-strategy, it would take exponential time. Instead of using the conditions, we will use the solution of the dual linear program (as discussed in Section 3.1) to check for equilibrium. We will derive such condition below.

For tractability, we also discretize the resource-utility space and project the resource-utility to some discretization of the space. Let V = ¶vi↪ i = 0↪ 1↪ 2↪ ▷▷▷↪ d 4m ✏ e ♣ vi = i✏ 4m ♦ to be the discretization of the utility space for some epsilon 1 ≥ ✏ > 0.

Claim 6. Given a symmetric marginal mixed-strategy q, and let proj(u) = v be the projection of some value u to a value v 2 V such that u 2 (v - ✏ 4m ↪ v + ✏ 4m ). We have Pr2R qrproj(r(q-i)r) ≥ Pr2R q0r proj(r(q-i)r) - ✏2 - O(δnm), for any q0 2 [0↪ 1]m that satisfies Dq0  f.

Proof. To verify the above claim, notice that, for each r 2 R, ♣r(q-i)r - proj(r(q-i)r)♣  ✏ 4m ↪ and, for any marginal mixed-strategy ¯ q, ∣∣Pr2R ¯ qrr(q-i)r - Pr2R ¯ qrproj(r(q-i)r)∣∣  ✏4 ▷ Thus, our bound follows from the above inequality.

Using the above claim, we provide the following lemma.

Lemma 3. Given a symmetric marginal vector q, and let proj(u) = v be the projection of some value u to a value v 2 V such that u 2 (v- ✏ 4m ↪ v+ ✏ 4m ). Let q⇤ be a best response to q. We have Pr2R q⇤ r proj(r(q-i)r) = f T λ⇤ - ✏2 -O(δnm)↪ where f T λ⇤ is the optimal solution of the dual problem that corresponds to the primal program given the discretized utility values under proj(·) 3 .

The above lemma allows us to verify whether a marginal vector can be used to form an ✏-MSNE. It is not clear how we can find the λ⇤ as claimed in the above lemma. Below, we provide a lemma to specify the potential values of λ⇤ .

Lemma 4. The value of λ⇤ = (λ⇤i )i=1↪2↪▷▷▷↪l is such that λ⇤i = civi for some integer constant 0  ci  m and v 2 V .

Proof. Since the solution for the primal program (i.e., existence of an ✏-MSNE) exists, there is a solution for its dual. Since the transpose DT is totally unimodular by Assumption 1, each λ⇤i is some linear combination of the value of proj(r(q-i)). Moreover, V is a uniform discretization and λ⇤i ≥ 0. Thus, λ⇤i is some combination of values in V .

4.2 An Algorithm to Find Symmetric ✏-MSNE

In this subsection, our goal is to develop an efficient algorithm to find marginal vectors that satisfy the ✏-MSNE conditions as discussed in the previous subsection.

Table 1 lists the variables and their uniform discretization that we used in the following discussion. To get an ✏-MSNE, we set δ = ✏ O(nm) . Notice that the marginal qr of each r 2 R has finitely many values (from Lemma 2) in Q. Since the marginals have finitely many values and the resource-utility values are discretized and projected as specified in the previous subsection, the expected utility has finitely many values in T. In addition, because the constraint matrix consists of only 0, 1, and -1, for any constraint c, the possible values of c · q of any q 2 Qm is in @D. Finally, each dual variable λi is positive and is some linear combination of values in Q. As a result, λc 2 ⇤ for some constraint c.

A natural question is how can we use these discretized values to compute ✏-MSNE efficiently? Before answering this question, we define and introduce the following notation.

Definition 4. Given a symmetric CG+ with (N↪ R↪ ¶S♦i2N↪ ¶cr♦r2R↪ ¶u♦i2N). Let C be the set of indices of constraints in P ⇤ and c 2 C corresponds to row c of D. The game's constraint graph is a directed graph G = (R [ C↪ E) where E = ¶(c↪ r) 2 C⇥R ♣ Dcr 6= 0♦. The game's induced graph is an undirected graph IG = (R↪ E) where E = ¶(r1↪ r2) 2 R2 ♣ 9j 2 C↪Dj↪r1 6= 0↪Dj↪r2 6= 0♦.

We now state our main result.

3 To get the primal/dual programs, take the programs in Section 3.1 and replace ri(p-i) by proj(ri(p-i)).

Theorem 1. Given a symmetric CG+ whose constraint graph's in-degree is bounded by a constant d and whose induced graph has treewidth bounded by a constant w. There is a fully polynomial time approximate scheme (FPTAS) to compute a best/worst social welfare symmetric ✏-MSNE in poly(n↪m↪ 1✏ ) time.

As a corollary, we can state the sufficient condition for FPTAS as a single graphical property of the game. Given a directed graph (R↪E), its primal graph (also known as moral graph) is the undirected graph (R↪E [ ¶(r↪w)♣9t 2 R↪ (r↪ t) 2 E↪ (w↪ t) 2 E♦), i.e., adding edges between each pair of in-neighbors of each node.

Corollary 1. Given a symmetric CG+ such that the treewidth of the primal graph of the constraint graph is bounded by a constant W. There is a fully polynomial time approximate scheme (FPTAS) for compute a best/worst social welfare symmetric ✏-MSNE in poly(n↪m↪ 1✏ ) time.

For simplicity of exposition, we describe our algorithm for the case when the in-degrees of the constraint graph are bounded by d and when its IG is a tree. The algorithm can be generalized to IG with a bounded tree-width W.

Without loss of generality, we orient the tree in "levelorder" so that the first level consists of the root, the second level consists of its children and so on. For convenience, we relabel the nodes/resources so that the nodes are ordered such that root is n, and its children, Ch(n), are (from right to left) n - ♣Ch(n)♣, ..., n - 1, and subsequently for their respective children in the respective level. We let D(r) = ¶j 2 C ♣ Djr 6= 0♦ to be the set of constraints such that their column corresponding to resource r is nonzero. Since r(q-i)r for r 2 R only depends on qr, we write r(qr)r instead.

Our message passing algorithm will be run on the induced graph. Each resource will pass the appropriate messages to its neighbors as specified below, first in an upstream pass from the leaves to the root, then in a downstream pass from root to the leaves. Since each resource, say a r 2 R, can be involved in more than one constraints (each of which corresponds to a dual variable), we need to keep track of possible values of (λj)j2D(r) and the possible (sum of) values of D:↪rqr. Indeed, since D is totally unimodular and we have a discretization on qr, we have discretization on the possible sums of the constraints. It is clear that we have a finite discretization for the possible value of λ as well. As a result, this reduces to a constraint optimization problem on discrete values.

To begin, we first describe the message from a leave l 2

R of the tree to its parent. Notice that along each message passing, we will keep track of the best possible value of λ⇤ = (λ⇤j )j2C. We begin by discussing the upstream pass.

Upstream Pass. For each leave l 2 R, l computes a table fl : Q ⇥ T ⇥ @D♣D(l)♣ ⇥ ⇤♣D(l)♣ ! ¶0↪ 1♦ such that

specifies the feasible ✏-MSNE region. Moreover, the size of this table is poly(n↪m↪ 1✏ ) (for bounded in-degrees). Let k = Pa(l) denote the parent of l and let D(l↪ k) = D(l) \ D(k). The message of l ! k is

is the set of feasible tuples of size at most poly(n↪m↪ 1✏ ). In addition, for j 2 D(l) ∩ D(l↪ k), λ⇤j 2 argmin(·)2Mi!k:f(·↪λj)=1 fjλj▷ For each non-leaf node r 2 R, r computes a table fr : Q⇥T ⇥@D♣D(r)♣ ⇥⇤♣D(r)♣ ! ¶0↪ 1♦ given the messages from its children. Let Ch(r) be the children of r and and we order the children by their index such that r1 < r2 < ▷▷▷ < r♣Ch(r)♣. Notice that r will have ♣Ch(r)♣ messages and the goal is to combine these messages efficiently and construct fr.

Below, we describe an efficient way of combining the messages. For k = r1, we construct

and for k = r2↪ ▷▷▷↪ r♣Ch(r)♣, we construct the following successively, in that order,

Finally,

Similarly, the message r will send to its parent k is

is the set of feasible tuples. In addition, for j 2 D(r) ∩ D(r↪ k), λ⇤j 2 argmin(·)2Mr!k:f(·↪λj)=1fjλj▷

Note that computing the fr↪k requires us to deal with at most two tables of poly(n↪m↪ 1✏ ) size. Thus, computing the final table fr doesn't blow up the computation exponentially.

DownstreamPass. After root n has received the messages from its children, it is going to compute a partial ✏-MSNE and pass it to its children. Given fn, we construct

For j 2 D(n), let λ⇤j 2 argmin(·↪λj)2Rn fjλj. Next, find 4

Indeed, n will send such a message to each of its children. Given the message from the parent, say i, k = r♣Ch(i)♣↪ ▷▷▷r2, in that reverse order, will compute

where k will select (an arbitrary tuple of) message in Ri↪k and send it to its children and the k - 1 node. In particular, k will send the Mk!i tuple to its children and send the fi↪k-1 to k - 1 so that k - 1 will use that tuple to compute Ri↪k-1. When k = r1, we have

Standard techniques that generalize algorithms for tree to those of bounded treewidth yield Theorem 1.

Computing ✏-MSNE in Symmetric network congestion games. As discussed in Section 2, the constraint matrix of the players in network congestion games is totally unimdoular. It turns out that the induced graph of the constraint matrix is the line graph 5 of G. Applying a bounded-treewidth result in [Atserias, 2008; Bienstock, 1990; C˘alinescu et al., 2003], if the graph of a congestion game has constant treewidth and degree, the treewidth of its line graph is bounded.

Corollary 2. There is an FPTAS to compute a best/worst symmetric ✏-MSNE for congestion games where their graphs have constant treewidth and constant degree.

4 For the worst ✏-MSNE, replace argmax by argmin.

5 Given a graph G = (V↪ E), a line graph of G is a graph on E where two edges in E are connected if they are incident in G.