An FPTAS for Computing Nash Equilibrium in Resource Graph Games

1 Introduction

There has been increasing interest in using game theory to model real-world multi-agent systems, and in the computation of game-theoretic solution concepts given such a model. For games with large numbers of agents and actions, the standard normal form game representation requires exponential space and is thus not a practical option as a basis for computation. In particular, in many domains [Daskalakis et al., 2006a; Rabinovich et al., 2009; Immorlica et al., 2011; Korzhyk et al., 2010], each player needs to make a decision that consists of multiple sub-decisions (e.g., assigning a set of workers to tasks, ranking a set of options, or finding a path in a network), and hence can have an exponential number of pure strategies. Nevertheless, this space of pure strategies is often structured, meaning that it can be represented compactly.

Recently, [Jiang et al., 2017] proposed resource graph games (RGGs), a general compact representation for games with structured strategy spaces that unifies and generalizes many of the existing classes of structured games studied in literature. In an RGG, there are n players and a set A of resources. A pure strategy of a player is a subset of the resources, represented by an |A|-dimensional 0-1 vector. Each player's set of pure strategies is represented compactly as a polytopal strategy space: the set of integer points in a convex polytope, specified by a set of linear inequality constraints. There is a resource graph, a directed graph whose vertices are the resources A, and the graph depicts the utility structure of the game. RGGs are able to compactly encode a wide variety of games studied in literature, including security games [Korzhyk et al., 2010; Tambe, 2011], network congestion games [Daskalakis et al., 2006a], simultaneous auctions [Rabinovich et al., 2009], dueling algorithms [Immorlica et al., 2011], and Blotto games [Ahmadinejad et al., 2016].

In this paper, we consider the problem of computing a mixed-strategy Nash equilbrium (MSNE) in RGGs. RGGs can represent arbitrary games, as a result the PPAD-hardness of finding an MSNE in normal form games [Chen and Deng, 2006; Daskalakis et al., 2006b] implies the PPAD-hardness for finding MSNE in RGGs. A natural question arises: are there subclasses of RGGs for which MSNE can be computed (or approximated) in polynomial time? In this paper we provide one answer to this question by identifying a subclass of RGGs that admits a fully polynomial time approximation scheme (FPTAs) for finding MSNE. In particular, we focus on symmetric RGGs that satisfy a multilinearity condition (the utility functions are linear in each player's strategy vector while keeping others' strategies fixed). We define constraint moralized resource graph as an undirected graph constructed by starting from the moralized graph (also known as the primal graph) of the resource graph, then adding nodes corresponding to the linear strategy constraints, and edges connecting each constraint with the resources that are involved in the constraint. Our main result is that there is a FPTAS for computing MSNE for a symmetric multilinear RGG whose constraint moralized resource graph has bounded treewidth. Treewidth is a well-studied graph property that has been applied to many graph-related problems, including Bayesian network inference and constraint satisfaction. In particular a tree has treewidth of 1. Our FPTAS can be extended to find specific MSNE, such as MSNE with the greatest (or lowest) social welfare. We also generalize our FPTAS to a constant number of player types. We then applied our FPTAS to classes of RGGs that correspond to games studied in literature, and obtained new results for these games.

In particular, (i) we provide FPTAS for computing MSNE in generalizations of security games [Korzhyk et al., 2011b; 2011a], in particular for cases when the defender and attacker have complex strategy sets not covered by existing results. (ii) [Chan and Jiang, 2016] provided a FPTAS for MSNE in a class of congestion games [Rosenthal, 1973] where the players' strategy constraints are totally unimodular, and the constraint graph has bounded treewidth and bounded degree. Our FPTAS applied to congestion games only requires bounded treewidth, without restriction on degree, and as a result is applicable to a boarder range of congestion games. (iii) Bilinear games [Garg et al., 2011] are two-player games whose utilities are characterized by payoff matrices A and B. When A and B are sparse matrices, the RGG representations have nontrivial graph structure. Furthermore, due to the special structure of bilinear game utilities, we can avoid the moralization step, resulting in further reduced treewidth.

Our algorithm makes use of a compact, primal-dual formulation of the MSNE condition. We then use a treedecomposition based dynamic programming approach to solve the resulting feasibility problem, passing partial assignments of primal and dual variables and partial sums of constraints across subgraphs. We omit all proofs in this version. A longer version of the paper with proofs and more discussion is available on the authors' websites.

2 Preliminaries

Denote by Z+ the set of nonnegative integers. A rational polytope is defined by a set of inequalities with integer coefficients; P = {x ∈ Rm|Dx ≤ f} is a rational polytope if D and f consist of integers.

2.1 Games, Strategies and Equilibrium

A game is specified by (N, S, u), where N = {1, . . . , n} is the set of players. Each player i ∈ N chooses from a finite set of pure strategies Si. Denote by si ∈ Si a pure strategy of i. Then S = ∏i Si is the set of pure-strategy profiles. Moreover, u = (u1, . . . , un) are the utility functions of the players, where the utility function of player i is ui : S →R. A mixed strategy σi of player i is a probability distribution over her pure strategies. Denote by σ = (σ1, . . . , σn) a mixed strategy profile. Denote by σ-i the mixed strategy profile of players other than i. Denote by ui(σ) the expected utility of player i under σ.

For ϵ ≥ 0, player i's mixed strategy σi is an ϵ-best response to σ-i if ui(σi, σ-i) ≥ ui(s′i , σ-i) - ϵ ∀s′i ∈ Si. A mixed strategy profile σ is an ϵ-MSNE if for each player i ∈ N, σi is an ϵ-best response to σ-i. A best response is a 0-best response and an MSNE is a 0-MSNE.

2.2 Resource Graph Games

A resource graph game (RGG) is specified by the tuple Γ = (N, A, {Si}i=1,...,n, G, {uα}α∈A), where N = {1, 2, ..., n} is the set of n players; A = {1, ...,m} is the set of m resources. Each si ∈ Si is an |A|-dimensional 0-1 vector. Si is represented as a polytopal strategy space where Si = Pi ∩ {0, 1}|A| , Pi = {x ∈ [0, 1]|A| |Dix ≤ fi}, Di ∈ Zli×|A| , and fi ∈ Zli . In other words, Pi is a rational polytope defined by li linear constraints. We let siα denote the component corresponds to α ∈ A. Given a pure-strategy profile s = (s1, ..., sn), the configuration c = ∑i∈N si is an integer vector that counts the number of players who have selected each resource. The resource graph G = (A,E) is a directed graph that could contain self-loops. The neighborhood of α ∈ A, denoted by ν(α), is the set of resources with edges going into α. Let C (α) ⊂ Zν(α) + be the set of local configurations over ν(α), and c(α) ∈ C (α) a local configuration. The local utility function uα : C (α) → R represents the utility contribution of using α given the configuration over its neighborhood ν(α). Given the pure-strategy profile s = (s1, ..., sn), the utility of player i is defined to be ui(s) = ∑α:siα=1 uα(c(α) ) = ∑α∈A siαuα(c(α) ).

[Jiang et al., 2017] showed that the representation size is polynomial in m, nI , and ∑i li, where I is the maximum in-degree of the resource graph.

We define symmetric RGGs to be those in which the players have the same polytopal strategy space.

Definition 1. An RGG, Γ = (N,A, {Si}ni=1 ,G, {uα}α∈A), is symmetric if and only if for all player i, Di = D, fi = f, Si = S, and Pi = P for some D ∈ Zli×|A| and f ∈ Zli .

More generally, we call an RGG k-symmetric if there are k equivalence classes of players, and within each equivalence class the players have the same polytopal strategy space.

Definition 2. An RGG, Γ = (N,A, {Si}ni=1 ,G, {uα}α∈A), is k-symmetric if and only if the players are partitioned into k classes, and for any player i in class j ∈ {1, ..., k}, Di = Dj , fi = f j for some Dj ∈ Zlj i ×|A| and f j ∈ Zlj i (and therefore Si = Sj , and Pi = P j ).

Every (k-)symmetric game has a (k-)symmetric MSNE in which every player in the same equivalence class plays the same (possibly mixed) strategies [Nash, 1951].

2.3 Multilinearity andMarginal Vectors

When |Si| is exponential, representing a mixed strategy σi explicitly would take exponential space. Given player i's mixed strategy σi, the marginal vector πi that corresponds to σi is πi = Eσi [si] = ∑si∈Si σi(si)si. In other words, πiα is the marginal probability that resource α is chosen under the mixed-strategy σi. Thus if we represent a mixed strategy using its marginal vector, this would only require O(m) space. However, for this representation to work, we need to be able to express the expected utilities of the game in terms of marginal vectors. [Chan et al., 2016] showed that this can be done if the game has the multilinear property: for all i, j ∈ N, given a fixed s-j, ui is a linear function of sj.

Not all RGGs are multilinear; the following proposition gives a sufficient condition for an RGG to be multilinear.

Proposition 1 (Proposition 7 of [Jiang et al., 2017]). An RGG, Γ = (N, A, {Si}i=1,...,n, G, {uα}α∈A), is multilinear if, for each player i, for each α ∈ A, and for each si ∈ Si, ∑α′∈ν(α)∪{α} siα′ ≤ 1. Moreover, given an RGG, we can verify the above condition in polynomial time.

In practice, it is often desirable to be able to recover a mixed strategy from a marginal vector representation. Since the explicit representation of mixed strategies has exponential size, we would instead like to have the mixed strategy specified in some manner that requires less space. [Chan et al., 2016] provides one sufficient condition for the efficient recovery of mixed strategies frommarginals: If the constraint matrix Di is totally unimodular, then given a marginal vector πi, we can efficiently generate a mixed strategy σi, represented as a sparse vector with polynomial number of nonzero entries, such that πi = ∑si∈Si σi(si)si.

3 Statements of Results

Assumptions. In summary, to ensure the compact representation of mixed strategies as marginal vectors, we make the following assumptions:

Assumption 1. ∀i ∈ N, the matrix Di is totally unimodular. Assumption 2. For each i ∈ N, for each α ∈ A, and for each si ∈ Si, ∑α′∈ν(α)∪{α} siα′ ≤ 1.

Without either one of these assumptions, even single agent versions of RGG can represent NP-hard optimization problems, i.e., we end up with problems whose hardness has nothing to do with game theory.

A fully-polynomial time approximation scheme (FPTAS) for MSNE is an algorithm that given an RGG, computes an ϵ-MSNE in time poly(nI , m, l, 1ϵ ). While Nash equilibria are preserved under affine transformations of the utility functions ui, ϵ-Nash equilibria are not. E.g. multiplying all ui by a constant κ would turn a ϵ-MSNE into a κϵ-MSNE in the new game. A standard practice is to normalize the utility functions ui into the range [0, 1], by the affine mapping ui ↦→ (ui - umin)/(umax - umin), where umax = maxi,s ui(s) and umin = mini,s ui(s) are the maximum and minimum achievable utilities of the game, respectively. Then use the normalized game to measure the quality of approximation, i.e., ϵ. An ϵ-MSNE in the original game would correspond to an ϵ (umax-umin) -MSNE in the normalized game. While Assumption 3 implies ui(s) ∈ [0,m] for all i and s, these are in general not tight bounds on umax and umin, and indeed umax and umin may be hard to compute given an RGG. We note that this is a common issue with compact game representations whose utility functions are sums of other functions, e.g., polymatrix games [Barman et al., 2015]. For our purposes, in order to ensure that our FPTAS remains an FPTAS for the normalized game, it is sufficient to assume that (umax - umin) is lower-bounded by an inverse polynomial of the size of the game.

This is a reasonable assumption for natural classes of games, as we would normally expect umax -umin to not decrease as the size of the game grows. Indeed it can be easily verified that this holds for all games discussed in this paper.

Constraint Moralized Resource Graph. Let C = {1, ..., l} be the set of constraints, corresponding to rows of the constraint matrix D of a symmetric RGG.

Definition 3. Given a resource graph G = (A,E), its moralized resource graph is an undirected graph MG = (A,E ∪ E′ ) where E is an undirected edge set of E, and E′ = {{α, α′ } ∈ A×A | ∃¯α ∈ A s.t. (α, ¯α), (α′ , ¯α) ∈ E} is a set of undirected edges connecting the parents of their children. The constraint moralized resource graph is an undirected graph CMG = (A ∪ C, E ∪ E′ ∪ E′′ ) where E′′ = {{c, α} ∈ C ×A | Dcα ̸= 0} is a set of undirected edges connecting resources and constraints. In other words, there is an edge from the constraint to all of the resources involved in the constraint.

Our main result is stated as follows.

Theorem 1. There is an FPTAS for computing a k-symmetric MSNE in k-symmetric RGGs that satisfy Assumptions (1-4) and have constraint moralized resource graphs with bounded treewidth, when k is a constant. In particular, the algorithm finds an ϵ-MSNE in time poly(n,m, l, 1ϵ ). The algorithm can be extended to compute ϵ-MSNE with the highest (or lowest) social welfare.

Applications to Security Games. In a typical security game [Tambe, 2011] between a defender (d) and an attacker (a), there is a set T of targets, the defender can only protect m of the targets and attacker can attack one target. Defender and attacker's utilities depend on whether the attacked target is covered. [Jiang et al., 2017] showed that security games can be compactly encoded as RGGs. Figure 1(a) illustrates the resource graph. For each target t ∈ T , we have a resource node at for the attacker, representing the utility of attacker for attacking target t, and two resource nodes b0t and b1t for the defender, representing the defender's utility for not protecting and protecting t, respectively. The constraint matrices of the attacker and the defender are totally unimodular, and the strategies of the players satisfy Proposition 1. This can be generalized to the model of [Korzhyk et al., 2011a] where the attacker can attack K targets.

Given the RGG representation of the security game, we can proceed to construct its moralized constraint resource graph, as shown in Figure 1(b). We provide a constant-width tree decomposition of the moralized constraint resource graph in Figure 1(c). Since we have only two classes of players (an attacker and a defender) and constant treewidth, our algorithm yields an FPTAS for Nash equilibrium in these games.

Our result holds for general classes of security games with arbitrary strategy constraints for the players as long as their constraint matrices are totally unimodular and the treewidth of the moralized constraint resource graph is bounded.

Proposition 2. Given a security game, if the strategy constraint matrices for the attacker and defender are totally unimodular, and treewidth of the moralized constraint resource graph is bounded, there is an FPTAS for computing MSNE.

Example 1. Consider a security game as defined above, but with a more complex attacker strategy space. In particular the targets correspond to edges in a network with a source and a destination, and the attacker can choose a path from source to destination, thereby attacking all edges on the path chosen. It is known that the set of valid paths can be encoded compactly as linear constraints with a totally unimodular constraint matrix. If the network has constant treewidth, the constraint moralized resource graph also has constant treewidth, and Proposition 2 applies.

Applications to Congestion Games. Congestion games model the situation in which there is a set of resources, and each player 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.

Each resource in the congestion game corresponds to a resource node in the RGG representation. The resource graph contains only self-edges. When the constraint matrix of each player is totally unimodular, then we have totally unimodular congestion games [Chan and Jiang, 2016; Del Pia et al., 2017]. Our result generalizes the results of [Chan and Jiang, 2016]. In particular, their FPTAS for totally unimodular congestion games requires each resource to only be involved in a constant number of constraints and each constraint can only involve a constant number of resources, in addition to having bounded treewidth. Our result lifts these restrictions and applies as long as the treewidth of the constraint moralized resource graph is bounded.

Proposition 3. Given a totally unimodular congestion game with k player types, if the treewidth of the moralized constraint resource graph is bounded, there is an FPTAS for computing k-symmetric MSNE for constant k.

Example 2 (Network Congestion). Consider network congestion games [Fabrikant et al., 2004], where resources correspond to edges in a network, and each player chooses a path from a source to a destination in the network. [Chan and Jiang, 2016] provided an FPTAS when the network has constant treewidth and constant degree. Our result provides an FPTAS when the network has constant treewidth, without restriction on the degree.

Example 3 (Security Game with Multiple Attackers). Consider the following generalization to security games, now with na attackers. Each attacker can attack K targets. Payoffs for defender and attackers are sums of contributions from each target, which depend on (a) the number of attackers choosing to attack that target, and (b) whether defender protects that target. The attackers are interchangeable so this is a 2-symmetric game. This game combines the utility structure of congestion games (among the attackers) and security games (between defender and attackers). The RGG representation has resource graph similar to Figure 1(a), except now there are self-loops on each attacker node at for each target. It can be verified that Assumption 2 remains satisfied, and Figure 1(c) remains a tree decomposition for the new constraint moralized resource graph. Thus our result applies to yield an FPTAS.

Bilinear Games. A bilinear game [Garg et al., 2011] is played between two players 1 and 2. The strategy spaces of the players are described using polytopes X and Y . Player 1 and player 2 have payoff matrices A ∈ RM×N and B ∈ RM×N , respectively. In particular, given (pure) strategies x ∈ X and y ∈ Y , u1(x, y) = xT Ay and u2(y, x) = xT By.

Given a bilinear game with (possibly sparse) A and B, the resource graph is a bipartite graph where one side has M resources corresponding to rows and the other side has N resources corresponding to columns. There is an edge from column c to row r iff Ac,r ̸= 0, and an edge from row r to column c iff Br,c ̸= 0. We can further exploit the linearity of the utility functions, and as a result we do not need to moralize the resource graph.

Theorem 2. Given a bilinear game, if the strategy constraint matrices for both players are totally unimodular, and treewidth of the constraint resource graph (without moralization) is bounded, there is an FPTAS for computing MSNE.

4 Sketch of Derivation of Our FPTAS

4.1 A Primal-Dual Definition of MSNE

We can express the expected utility as ui(πi, π-i) = πT i ∇i(π-i) where ∇i(π-i) is the utility gradient of i and ∇i(π-i)α denotes the expected utility contribution of i from using the resource α and πT i is the transpose of πi. [Jiang et al., 2017] showed that given an RGG and π-i, the utility gradient ∇i(π-i) can be computed in polynomial time. Moreover, to compute ∇i(π-i)α we only need to know (πjα′)j̸=i,α′∈ν(α), i.e., other players' marginals projected to α's neighborhood.

In the standard definition of MSNE, we need to enumerate all pure strategies to verify whether a mixed-strategy profile is a MSNE. This is not feasible for games (RGGs) with exponential number of pure strategies. We need a more efficient way to check whether a mixed-strategy profile is an MSNE.

Given the marginal vectors of others π-i, the best response for i is the solution to the following primal and dual LPs.

Here we assume that the constraint πiα ≤ 1 is embedded into the constraints Diπi ≤ fi. Given that the primal LP has a solution, the primal and dual LPs solutions have the same optimal objective value. As a result, πi is i's best response when there exists a feasible dual vector λi such that πT i ∇i(π-i) = f T i λi. Thus, a feasible marginal vector ¯π is an MSNE if for each player i, there exists λi ≥ 0 such that DT i λi ≥ ∇i(¯π-i) and ¯πT i ∇i(¯π-i) = f T i λi. This primaldual formulation of best responses do not tell us how to find an MSNE; in particular we cannot simply solve the LPs to find an MSNE because these are LPs only for fixed π-i.

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 an ϵ-MSNE in this discretized space.

Lemma 1. For any δ > 0, there is a (symmetric) marginal vector ∀i qi = q = (qα)α∈A in which qα ∈ {0, 1K , 2K , . . . , 1} and K = O( logm δ2 ), such that u(qi, q-i) = qT ∇(q-i) ≥ q′T ∇(q-i)-O(δdnm) for q′ ∈ [0, 1]m that satisfies Dq′ ≤ f and d is the maximum in-degree of the resource graph G.

The above lemma implies that if every player plays according to q, then we have an O(δdnm)-MSNE. Our next step is to present an efficient algorithm to find such q.

4.2 An Efficient Algorithm to Compute ϵ-MSNE

From Lemma 1, there is a marginal vector q that lies in the m-dimensional uniform discretized grid with discretization size 1 O(δdnm) . Thus, a brute-force approach does not yield an efficient algorithm. We instead use the definition of NE in terms of linear programming of Section 4.1 and introduce a message-passing algorithm that runs on a tree decomposition of the constraint moralized resource graph.

Discretization of Variables. To search for the marginal representation, we provide discretization bounds for the existence of an ϵ-MSNE in the marginal and utility spaces. Here, we provide other discretization spaces that are necessary for our algorithm. We use the notation DC,A to denote the subcomponent of D consisting of the rows in C ⊆ C and columns in A ⊆ A. If |C| = 1 and |A| = 1, then DC,A is the value corresponds to the row and column. To begin, recall that we want to find a marginal vector q = (qα)α∈A where qα ∈ Q (as in Lemma 1) such that Dq ≤ f, DT λ∗q ≥ proj(∇(q-i)), and qT proj(∇(q-i)) ≥ f T λ∗q - ϵ2 - O(δdnm) for λ = (λc)c∈C where λc ∈ Λ. Clearly, we are not going to try all the possible q ∈ Q|m| directly. Instead, our approach is to find feasible (qα)α∈A′ and (λc)c∈C′ for some ordering of A′ ⊆ A and C ′ ⊆ C induced by the tree decomposition incrementally. Thus, we need to keep track of the partial sums of (1) Dc,Aq for each constraint c, (2) DTα,C λq for each resource α, (3) qT proj(∇(q-i)), and (4) f T λq for a given q and λq. Because D is totally unimodular, its entries can only have values of 0, 1, or -1. Thus, the possible values of the partial sums are finite. For (1), given a constraint c, we let ∂Sc be partial sum of the constraint c from Sc. For (2), given a resource node α, we let ∂λα be the partial sum of a resource constraint α (i.e., DTα,C ) from SA. For (3), we let ∂t to be the partial utility sum from T. For (4), we let ∂f to be the partial dual objective sum from F. Finally, to ensure we have a marginal vector of ϵ-Nash equilibrium, we let δ = O ( ϵ dmn ). For the sake of space, we leave the details of the discretization of set in full version1 .

Message Passing Algorithm. Given the tree decomposition of the constraint moralized graph and the discretization spaces, we provide a two-pass message passing algorithm that is an FPTAS when the tree decomposition has a bounded tree width and there is a polynomial number of constraints.

To begin, let T = (B,E) be the decomposed tree. It is clear that, for each X ∈ B, the node X consists of a set of resources and a set of constraints, denoted by AX and CX, respectively. From the moralization and the tree decomposition, for each α ∈ A, there is an X ∈ B such that ν(α) ⊆ AX. This allows us to compute the partial sum of the expected utility qα · proj(∇(qν(α))α). Because of that, we preprocess the tree and designate a node of X to compute the partial sum of the expected utility for each resource α exactly once. Of course, the designated node X should contain the ν(α). We let A∗X ⊆ AX to denote the set of resources where we compute the expected utility at X ∈ B. Such preprocessing can be done using depth-first search or breath-first search.

We first present the algorithm when the tree T is a line. Then, we show how we can generalize the algorithm to a tree. We assume all of the graphs are connected, otherwise we can just form a new tree by joining the connected components.

The Line Case. Suppose that the resulted tree decomposition is a line, say L = (B,E). We relabel the nodes of L so that B = {1, 2, ..., n} where 1 is the leftmost node and n is the right most node. Thus, the edge set E = {{i, i + 1}, i = 1, ..., n - 1} is the adjacent neighbors.

At a high level, the message passing algorithm has an upstream pass and a downstream pass. The upstream pass starts passing messages/tables sequentially from 1 to 2, 2 to 3, ..., n-1 to n. After n has received the messages, the downstream pass begins and starts with n passing message to n-1, n-1 to n-2, so on and so forth until 1 received the message/table from 2, sequentially. The idea of the upstream pass is to keep track of the potential ϵ-MSNE, and the goal of downstream pass is to construct a feasible ϵ-MSNE.

Upstream pass. For each node i ∈ B, we construct a set fi containing tuples of Q|Ai| ×S|Ci| C ×Λ|Ci| ×S|Ai| A ×T ×F based on Mi-1→i which is the message i-1 sends to i. More specifically,

where & denotes the regular "and" condition and 1[exp] is the indicator function for the expression (1 if the exp is true, 0 otherwise).

The (1) condition keeps track of the partial sums of the expected utilities of the resources in A∗j , j = 1 to i-1, and add the expected utilities of resources in A∗i . The (2) and (3) conditions accumulate the partial sum of the constraints in Ci (i.e., we are keeping track of the Ci constraints of D to ensure DCi,Ai qAi ≤ fCi ). This boils down to two cases given a c ∈ Ci, either c appears in Ci+1 (condition (2)) or c does not appear in Ci+1 (condition (3)). If c appears in Ci+1 (condition (2)), then we keep track of the partial sum of the resources together with c that will not appear in Ci+1, otherwise we will just include all of the resources in Ci if c doesn't appear in Ci+1 (condition (3)) since c will not appear again in the later nodes (due to the property of the tree decomposition). In either case, we need to the include the (possible) existing partial sum ∂Sc for c that appears in the previous j = i - 1, ... nodes.

For conditions (4), (5), (6), and (7), they are similar to conditions (2) and (3) but instead, we want to keep track of partial sums of the dual constraints (i.e., DTAi,Ci λCi ≥ proj(∇(qν(Ai))Ai )). Clearly, we can only compute the projected expected utility for the resources in A∗i . Therefore, we have cases (6) and (7) for which we can compute the expected utilities and cases (4) and (5) for which we cannot. For (4) and (5), we just want to keep track of the partial constraints of Dα,Ci λCi ; either we include all of the constraints in Ci in the partial sum (condition (5)) or the constraints that do not appear in Ci+1. For (6) and (7), this is similar except that we subtract from the projected expected utilities for α in A∗i . The reason we are doing this is because we will not able to compute the projected expected utilities after this, therefore we subtract from the partial sum. In all of these cases, we need to include the existing partial sum of α.

For condition (8), we keep track of the partial sum of f T Ci λCi . We only need to add the partial sum for those constraints that will not appear again in the tree. Finally (9) ensures that our tuples are consistent with the messages that i-1 send to i. We observe that the resulting set fi has cardinality bounded by poly(n, m, l, 1/ϵ), if the width of the tree decomposition is bounded by a constant.

Message Table. Given the set of tuples fi, we discuss the message Mi→i+1 i sends to i + 1. We define and construct an auxiliary set Mfi that will facilitate the constructing of the message and also make the downstream pass more clear.

=⇒ ∂t ≥ ∂f - ϵ]}, and the message from i to i + 1 is

When i = 0, C0 = A0 = Cn+1 = An+1 = ∅ and M0→1 = {∅, ∅, ∅, ∅, 0, 0}. When i = n, Cn+1 = An+1 = ∅ and n does not send message to n + 1 but still construct table Mfn .

Downstream Pass. Now that we have completed the upstream pass, we have enough information to construct an ϵMSNE. We will do this by starting selecting partial ϵ-MSNE for n, n-1, ..., 1, sequentially. In particular, given the selected partial ϵ-MSNE at node i, i will send node i-1, Ri→i-1, the feasible strategies that i -1 should select to ensure ϵ-MSNE. The details are in full version1 .

Generalization to Trees. Our message-passing algorithm can be generalized easily to trees. It has been shown that given a tree decomposition, we can modify it in polynomial time to a nice tree decomposition with the same treewidth and a polynomial increase in the number of nodes, where each node of the nice tree has at most two children (say left and right). Thus, we can construct the sets fi, Mfi , Mi→parent, Ri, Ri→left, and Ri→right based on the messages from the two children, with only polynomial increase in the computation and space requirements. For the upstream pass, a node i with a left child and a right child will construct fi based on the messages from its left child and right child. The equations (1)-(8) will include partial sums from the left and right children (as opposed to just based on i - 1) and i + 1 will be replaced by the parent of i. The tables Mfi and Mi→parent will be constructed the same way as before by replacing the index i+1 with the parent of i. For the downstream pass, the Ri can be constructed similarly using the message from the parent of i. The messages Ri→left and Ri→right can be constructed the same way but based on the messages Mleft→i andMright→i that satisfy the conditions (1)-(8).

Computing Optimal MSNE. For example, to find the social welfare maximizing symmetric ϵ-MSNE, in the downstream pass, at the root we select a tuple with the highest ∂t, i.e., utility, among the feasible tuples. Continuing the downstream pass as before yields a symmetric ϵ-MSNE with maximum social welfare.

RGGs with Constant Number of Player Types. We can generalize our message passing algorithms to cases where RGGs have a constant number of types. It can be verified our results and tools (constrained moralized resource graph and message-passing algorithm) for computing symmetric approximate MSNE in symmetric multilinear RGGs can be used to compute k-symmetric approximate MSNE in k-symmetric multilinear RGGs by considering k different symmetric strategies for the k classes of players.

More specifically, we construct the constrained moralized resource graph from the resources and the constraints from the polytopes of the k-classes and perform a tree decomposition (with bounded treewidth) on the resulting graph. In the construction of tables/sets for each node i in the tree decomposition, we need to keep track of (qjα)α∈Ai , (∂Sc)c∈Cj i , (λc)c∈Cj i , (∂λjα)α∈Ai , ∂tj , and ∂f j for each class j = 1, ..., k. This results in running time and table size exponential in k and the treewidth.