# A Refined Study of the Complexity of Binary Networked Public Goods Games

Yongjie Yang1 Jianxin Wang2

###### Abstract

We study the complexity of several combinatorial problems in the model of
binary networked public goods games. In this game, players are represented by
vertices in a network, and the action of each player can be either investing
or not investing in a public good. The payoff of each player is determined by
the number of neighbors who invest and her own action. We study the complexity
of computing action profiles that are Nash equilibrium, and those that provide
the maximum utilitarian or egalitarian social welfare. We show that these
problems are generally NP-hard but become polynomial-time solvable when the
given network is restricted to some special domains, including networks with a
constant bounded treewidth, and those whose critical clique graphs are
forests.

## Introduction

Binary networked public good games (BNPGs) model the scenario where players
reside in a network and decide whether they invest in a public good. The value
of the public good is determined by the total amount of investment and is
shared by players in some specific way. Particularly, the payoff of each
player is determined by the number of her neighbors who invest and her own
action. BNPGs are relevant to several real-world applications. One example
could be vaccination, where parents decide whether to vaccinate their
children, and the public good here is herd immunity.

In a recent paper, Yu et al. (2020) explored the complexity of determining the
existence of pure-strategy Nash equilibria (PSNE) in BNPGs. In particular,
they showed that this problem is NP-hard. On the positive side, they derived
polynomial-time algorithms for the case where the given network is a clique or
a tree. Following their work, we embark on a more refined complexity study of
BNPGs. Our main contributions are as follows.

  * •

We fix a flaw in an NP-hardness proof in (Yu et al. 2020).

  * •

Besides PSNE (action) profiles, we consider also profiles with the maximum
utilitarian or egalitarian social welfare which are not the main focus of (Yu
et al. 2020).

  * •

We show that the problem of computing profiles with the maximum
utilitarian/egalitarian social welfare is NP-hard, and this holds even when
the given network is bipartite and has a constant diameter.

  * •

For the problems studied, we derive polynomial-time algorithms restricted to
networks whose critical clique graphs are forests, or whose treewidths are
bounded by a constant. Note that the former class of graphs contains both
trees and cliques, and the latter class contains trees. Therefore, our results
widely extend the P results studied in (Yu et al. 2020).

Related Works. BNPGs are a special case of graphical games proposed by Kearns,
Littman, and Singh (2001), where the complexity of computing Nash equilibria
has been investigated in the literature (Kearns, Littman, and Singh 2001;
Elkind, Goldberg, and Goldberg 2006). Recall that graphical games are proposed
as a succinct representation of $n$-player $2$-action games whose action space
is $2^{n}$. In graphical games, players are mapped to vertices in a network
and the payoff of each player is entirely determined by her own action and
those of her neighbors. BNPGs are specified so that, in addition to one’s own
action, only the number of neighbors who invest matters for the payoff of this
player. In other words, in BNPGs, every player treats her neighbors equally.
An intuitive generalization of BNPGs where each player may take more than two
actions have been considered by Bramoullé and Kranton (2007). Additionally,
BNPGs are also related to supermodular network games (Manshadi and Johari
2009) and best-shot games (Harrison and Hirshleifer 1989; Carpenter 2002;
Levit et al. 2018). For more detailed discussions or comparisons we refer to
(Yu et al. 2020).

## Preliminaries

We assume that the reader is familiar with basic notions in graph theory and
computational complexity, and, if not, we refer to (West 2000; Tovey 2002).

Let $G=(V,E)$ be an undirected graph. The vertex set of $G$ is also denoted by
${\sf{V}}(G)$. The set of (open) neighbors of a vertex in $v\in V$ in $G$ is
denoted by $N_{G}(v)=\\{v^{\prime}\in V:(v,v^{\prime})\in E\\}$. The set of
closed neighbors of $v$ is $N_{G}[v]=N_{G}(v)\cup\\{v\\}$. We define
$n_{G}(v)$ (resp. $n_{G}[v]$) as the cardinality of $N_{G}(v)$ (resp.
$N_{G}[v]$). The notion $n_{G}(v)$ is often called the degree of $v$ in $G$ in
the literature. Given a subset $V^{\prime}\subseteq V$, we use
$n_{G}(v,V^{\prime})=\left|N_{G}(v)\cap V^{\prime}\right|$ (resp.
$n_{G}[v,V^{\prime}]=\left|N_{G}[v]\cap V^{\prime}\right|$) to denote the
number of open neighbors (resp. closed neighbors) of $v$ contained in the set
$V^{\prime}$. The subgraph induced by $V^{\prime}\subseteq V$ is denoted by
$G[V^{\prime}]$, and $G-V^{\prime}$ is the subgraph induced by $V\setminus
V^{\prime}$.

A BNPG $\mathcal{G}$ is a $4$-tuple $(V,E,g_{V},c)$. In the notion, $V$ is a
set of players, and $(V,E)$ is an undirected graph with $V$ being the vertex
set. In addition, $g_{V}$ is a set of functions, one for each player. In
particular, for every player $v\in V$ there is one function
$g_{v}:\mathbb{N}_{0}\rightarrow\mathbb{R}_{\geq 0}$ in $g_{V}$ such that
$g_{v}(i)$, where $i$ is a nonnegative integer not greater than $n_{G}[v]$,
measures the external benefits of the player $v$ when exactly $i$ of her
closed neighbors invest. Thus, the function $g_{v}$ is called the externality
function of $v$. Finally, $c:V\rightarrow\mathbb{R}_{\geq 0}$ is a cost
function where $c(v)$ is the investment cost of player $v\in V$.

For a function $f:A\rightarrow B$ and $A^{\prime}\subseteq A$, we use
$f|_{A^{\prime}}$ to denote the function $f$ restricted to $A^{\prime}$, i.e.,
it holds that $f_{A^{\prime}}:A^{\prime}\rightarrow B$ such that
$f_{A^{\prime}}(v)=f(v)$ for all $v\in A^{\prime}$. Sometimes we also write
$f|_{\neg(A\setminus A^{\prime})}$ for $f|_{A^{\prime}}$. For
$V^{\prime}\subseteq V$, a subgame of $\mathcal{G}=(V,E,g_{V},c)$ induced by
$V^{\prime}$, denoted by $\mathcal{G}|_{V^{\prime}}$, is the game
$(V^{\prime},E^{\prime},g_{V^{\prime}},c|_{V^{\prime}})$ such that
$E^{\prime}=\\{(u,u^{\prime})\in E:u,u^{\prime}\in V^{\prime}\\}$ and
$g_{V^{\prime}}=\\{g_{v}:v\in V^{\prime}\\}$.

An (action) profile of a BNPG is represented by a subset consisting of the
players who invest. Given a profile $\mathbf{s}\subseteq V$, the payoff of
every player $v\in V$ is defined by

$\mu(v,{\bf{s}},\mathcal{G})=g_{v}(n_{G}[v,{\bf{s}}])-{\mathbf{1}}_{\bf{s}}(v)\cdot
c(v),$

where ${\mathbf{1}}_{\bf{s}}(\cdot)$ is the indicator function of ${\bf{s}}$,
i.e., ${\bf{1}}_{\bf{s}}(v)$ is $1$ if $v\in\bf{s}$ and is $0$ otherwise. If
it is clear which BNPG is discussed, we drop $\mathcal{G}$ from
$\mu(v,{\bf{s}},\mathcal{G})$ for brevity.

Nash equilibria. In the setting of noncooperative game, it is assumed that
players are all self-interested. In this case, profiles that are stable in
some sense is of particular importance. For a profile ${\bf{s}}$ and a player
$v\in V$, let ${\bf{s}}(\neg v)$ be the profile obtained from ${\bf{s}}$ by
altering the action of $v$, i.e., $v\in{\bf{s}}(\neg v)$ if and only if
$v\not\in{\bf{s}}$, and for every $v^{\prime}\in V\setminus\\{v\\}$ it holds
that $v^{\prime}\in{\bf{s}}(\neg v)$ if and only if $v^{\prime}\in{\bf{s}}$.
We say that a player $v\in V$ has an incentive to deviate under ${\bf{s}}$ if
it holds that $\mu({\bf{s}},v,\mathcal{G})<\mu({\bf{s}}(\neg
v),v,\mathcal{G})$. A profile ${\bf{s}}$ is a PSNE if none of the players has
an incentive to deviate under ${\bf{s}}$.

Social welfare. In some other settings, there is an organizer, a leader, or an
authority (e.g., in the game of vaccination the authority might be the
government) who is able to coordinate the actions of the players in order to
yield the maximum possible welfare for the whole society. We consider two
types of social welfare as follows. Let $\mathcal{G}=(V,E,g_{V},c)$ be a BNPG
and ${\bf{s}}$ a profile of $\mathcal{G}$.

Utilitarian social welfare (USW)

The USW of $\bf{s}$, denoted by ${\textsf{USW}}({\bf{s}},\mathcal{G})$, is the
sum of all utilities of all players:

${\textsf{USW}}({\bf{s}},\mathcal{G})=\sum_{v\in
V}\mu({\bf{s}},v,\mathcal{G}).$

Egalitarian social welfare (ESW)

Under profiles with the maximum USW, it can be the case where some player
receives extremely large utility while others obtain only little utility,
which is considered unfair in some circumstances. Unlike USW, ESW cares about
the player with the least payoff. Particularly, the ESW of ${\bf{s}}$ is

${\textsf{ESW}({\bf{s}},\mathcal{G})}=\min_{v\in
V}\mu({\bf{s}},v,\mathcal{G}).$

Problem formulation. We study the following problems which have the same input
$\mathcal{G}=(V,E,g_{V},c)$. The notations of the problems and their tasks are
as follows.

PSNE Computation (PSNEC): Compute a PSNE profile of $\mathcal{G}$ if there are
any, and output “No” otherwise.

USW/ESW Computation (USWC/ESWC): Compute a profile of $\mathcal{G}$ with the
maximum USW/ESW.

Some hard problems. Our hardness results are established based on the
following problems.

For a positive integer $d$, a $d$-regular graph is a graph where every vertex
has degree exactly $d$.

$3$-Regular Induced Subgraph ($3$-RIS)
---
Given: |  A graph $G$.
Question: |  Does $G$ admit a $3$-regular induced subgraph?

The $3$-RIS problem is NP-hard (Broersma, Golovach, and Patel 2013; Cheah and
Corneil 1990).

A clique of a graph is a subset of vertices such that between every pair of
vertices there is an edge.

$\kappa$-Clique
---
Given: |  A graph $G$ and a positive integer $\kappa$.
Question: |  Is there a clique of size $\kappa$ in $G$?

$\kappa$-Clique is a well-known NP-hard problem (Karp 1972). A vertex $v$
dominates another vertex $v^{\prime}$ in a graph $G$ if there is an edge
between $v$ in $v^{\prime}$ in $G$. In addition, a subset $A$ of vertices
dominate another subset $B$ of vertices if every vertex in $B$ is dominated by
at least one vertex in $A$.

Red-Blue Dominating Set (RBDS)
---
Given: |  A bipartite graph $G=(B\uplus R,E)$ and a positive integer $\kappa$.
Question: |  Is there a subset $B^{\prime}\subseteq B$ such that $\left|B^{\prime}\right|\leq\kappa$ and $B^{\prime}$ dominates $R$?

The RBDS problem is NP-hard (Garey and Johnson 1979).

We assume that in instances of $\kappa$-Clique and RBDS, the graph $G$ does
not contain any isolated vertices (vertices of degree one).

## BNPG Solutions in General

In this section, we settle the complexity of the PSNEC/USWC/ESWC problems. We
first point out a flaw in the proof of Theorem 10 in (Yu et al. 2020), where
an NP-hardness reduction for PSNEC restricted to fully-homogeneous BNPGs is
established. 111Due to space limitation they omitted the proof in (Yu et al.
2020) but the proof is included in a full version posted online
(https://arxiv.org/pdf/1911.05788.pdf). [19.11.2020] Recall that a BNPG is
fully-homogenous if both the externality functions and the investment costs of
all players are the same. A profile is trivial if either all players invest or
none of the players invests. Checking whether a trivial profile is PSNE is
clearly easy. Yu et. al. provide a reduction to show that determining whether
a fully-homogenous BNPG admits a nontrivial PSNE is NP-hard. However, this
reduction is flawed. Let us briefly reiterate the reduction, which is from the
$\kappa$-Clique problem. The instance of BNPG is obtained from an instance
$(G=(V,E),\kappa)$ of $\kappa$-Clique by first considering vertices in $V$ as
players and then adding a large set $T$ of $M$ players who form a clique and
are adjacent to all players in $V$. The externality functions and costs of
players are set so that every player is indifferent between investing and not
investing if exactly $\kappa-1+M$ of her open neighbors invest, otherwise, the
player prefers to not investing. If there is a clique of size $\kappa$, then
there is a PSNE. However, the other direction does not work. In fact, a
nontrivial PSNE needs only the existence of a $(\kappa-1)$-regular induced
subgraph of $G$ (in this case, all players in $M$ and the players in the
regular subgraph invest). A more concrete counterexample is demonstrated in
Figure 1. Our amendment is as follows.

Figure 1: A counterexample to the reduction in the proof of Theorem 10 in (Yu
et al. 2020). The graph part $G$ in the $\kappa$-Clique instance is a
$3$-regular graph without cliques of size $3$, as shown in the gray area.
Additionally, $\kappa=3$. The clique $T$ contains more than $12$ vertices. The
profile consisting of the black-filled players in $G$ and all those in $T$ is
a nontrivial PSNE.

######  Theorem 1.

Determining if a fully-homogeneous BNPG admits a nontrivial PSNE is NP-hard.

###### Proof.

We prove the theorem via a reduction from the $3$-RIS problem. Let
$(G,\kappa)$ be a $3$-RIS instance. The network is exactly $G$. We set the
externality functions and the costs of the players so that everyone is
indifferent between investing and not investing if exactly three of her open
neighbors invest, and prefers to not investing otherwise. This can be achieved
by setting, for every $v\in V$, $c(v)=2$ and

$g_{v}(x)=\begin{cases}x&x\leq 3\\\ x+1&4\leq x\leq n_{G}[v]\\\ \end{cases}$

The correctness is easy to see. If the graph $G$ admits a $3$-regular subgraph
induced by a subset $H\subseteq V$, then $H$ is a nontrivial PSNE. On the
other hand, if there is a nontrivial PSNE $\emptyset\neq H\subseteq V$, due to
the above construction, every vertex in $H$ must have exactly $3$ open
neighbors in $H$, and so $G[H]$ is $3$-regular. ∎

Now we start the exploration on profiles providing the maximum social welfare.
We show that the corresponding problems are all hard to solve, and this holds
even when the given network is a bipartite graph with a constant bounded
diameter. Recall that the diameter of a graph is the maximum possible distance
between vertices, where the distance between two vertices is defined as the
length of a shortest path between them.

######  Theorem 2.

USWC is NP-hard. This holds even when the given network is bipartite and has
diameter at most $4$.

###### Proof.

We prove the theorem via a reduction from the $\kappa$-Clique problem to the
decision version of USWC which consists in determining whether there is a
profile of utilitarian social welfare at least a threshold value.

Let $(H,\kappa)$ be a $\kappa$-Clique instance, where $H=(U,E)$ is a graph,
$n=\left|U\right|$, and $m=\left|E\right|$. We assume that $\kappa$ is
considerably smaller than $m$, say $(k+1)^{10}<m$. As $\kappa$-Clique is
W[1]-hard with respect to $\kappa$, this assumption does not change the
hardness of the problem. We construct the following instance. For each vertex
$u\in U$, we create a player denoted by $v(u)$. The externality function of
$v(u)$ is defined so that $g_{v(u)}(0)=1$ and $g_{v(u)}(x)=0$ for positive
integers $x\leq n_{H}[u]$, and the investment cost of $v(u)$ is $c(v(u))=1$.
Let $V(U)=\\{v(u):u\in U\\}$ be the set of the vertex-players. In addition,
for each edge $e\in E$, where $e=(u,u^{\prime})$, we create a player $v(e)$.
We define $g_{v(e)}(0)=1$ and $g_{v(e)}(x)=0$ for all $x\in[4]$. Moreover,
$c(v(e))=0$. Let $V(E)=\\{v(e):e\in E\\}$ be the set of edge-players. Finally,
we create a player $v^{*}$ such that
$g_{v^{*}}(\frac{\kappa\cdot(\kappa-1)}{2})=m$ and $g_{v^{*}}(x)=0$ for all
other possible values of $x$. The investment cost of $v^{*}$ is $c(v^{*})=m$.
The player network is a bipartite graph with the vertex partition
$(V(U)\cup\\{v^{*}\\},V(E))$. In particular, the edges in the network are as
follows: for every edge $e=(u,u^{\prime})\in E$, the player $v(e)$ is adjacent
to exactly $v(u)$, $v(u^{\prime})$, and $v^{*}$, and thus has degree $3$ in
the network. It is clear that the network has exactly $3m$ edges and has
diameter at most $4$.

The construction clearly can be done in polynomial time. We claim that there
is a clique of size $\kappa$ in the graph $H$ if and only if there is a
profile of USW at least

$q=(n-\kappa)+\left(m-\frac{\kappa\cdot(\kappa-1)}{2}\right)+m.$

$(\Rightarrow)$ Assume that there is a clique $K\subseteq U$ of size $\kappa$
in the graph $H$. Let $E(K)=\\{(u,u^{\prime})\in E:u,u^{\prime}\in K\\}$ be
the set of edges in the subgraph induced by $K$. Clearly, $E(K)$ consists of
exactly $\frac{\kappa\cdot(\kappa-1)}{2}$ edges. Let ${\bf{s}}=\\{v(e):e\in
E(K)\\}$ be the set of the $\frac{\kappa\cdot(\kappa-1)}{2}$ players
corresponding to the edges in $E(K)$. We claim that ${\bf{s}}$ has USW at
least $q$. From the above construction, the utility of each player $v(u)$,
where $u\in U$, is $1$ if $u\not\in K$ and is $0$ otherwise. Hence, the total
utility of the vertex-players is exactly $n-\kappa$. In addition, the utility
of a player $v(e)$, $e\in E$, is $1$ if $e\not\in E(K)$ and is $0$ otherwise.
Therefore, the total utility of edge-players is
$m-\frac{\kappa\cdot(\kappa-1)}{2}$. Finally, the utility of the player
$v^{*}$ is exactly $m$. The sum of the above utility is exactly $q$.

$(\Leftarrow)$ Assume that there is a profile with USW at least $q$. Due to
the large investment cost of the player $v^{*}$, to maximize the USW, $v^{*}$
must not invest and, moreover, by the externality functions, exactly
$\frac{\kappa\cdot(\kappa-1)}{2}$ edge-players must invest. Additionally, by
the specific setting of the externality functions and the costs of the vertex-
players, none of the vertex-players invests in any profile with the maximum
USW. It follows that in a profile with the maximum USW, exactly
$\frac{\kappa\cdot(\kappa-1)}{2}$ edge-players invest. Then, due to the
setting of the externality functions, the smaller the number of vertex-players
dominated by the investing edge-players, the larger is the USW. It is then
easy to check that a profile achieves a USW at least $q$ if and only if at
most $\kappa$ vertex-players are dominated by the investing edge-players. This
implies that the edges whose corresponding players invest in a profile with
USW at least $q$ induce a clique in $H$. ∎

For the computation of profiles with the maximum egalitarian social welfare,
we have the same result.

######  Theorem 3.

ESWC is NP-hard. This holds even when the given network is bipartite with
diameter at most $4$ and all players have the same investment cost.

###### Proof.

Our proof is based on a reduction from the RBDS problem. Let $(G,\kappa)$ be
an RBDS instance, where $G$ is a bipartite graph with the vertex partition
$(R\uplus B)$. We construct an instance of the decision version of ESWC, which
takes as input a BNPG and a number $q$, and determines if the give BNPG admits
a profile of ESW at least $q$. For each vertex $v\in B\uplus R$, we create one
player denoted still by the same symbol $v$ for simplicity. In addition, we
create a player $v^{*}$. The network of the players is obtained from $G$ by
first adding $v^{*}$ and then creating edges between $v^{*}$ and all blue-
players in $B$, which is clearly a bipartite graph with the vertex partition
$(R\cup\\{v^{*}\\},B)$. Furthermore, the diameter of the network is at most
$4$. The externality and the cost functions are defined as follows.

  * •

For every red-player $v\in R$, we define $g_{v}(0)=0$ and $g_{v}(x)=1$ for all
other possible integers $x$.

  * •

For every blue-player $v\in B$, we define $g_{v}(0)=1$, $g_{v}(1)=2$, and
$g_{v}(x)=0$ for all other possible integers $x\geq 2$.

  * •

For the player $v^{*}$, we define $g_{v^{*}}(x)=1$ for every nonnegative
integer $x\leq\kappa$ and $g_{v^{*}}(x)=0$ for all other possible integers
$x>\kappa$.

  * •

All players have the same investment cost $1$, i.e., $c(v)=1$ for every player
$v$ constructed above.

The reduction is completed by setting $q=1$. The above instance can be
constructed in polynomial time. It remains to show the correctness of the
reduction.

$(\Rightarrow)$ Assume that there is a subset $B^{\prime}\subseteq B$ such
that $\left|B^{\prime}\right|\leq\kappa$ and every red-player has at least one
neighbor in $B^{\prime}$. One can check that profile $B^{\prime}$ has ESW at
least one. Particularly, as $B^{\prime}$ is the set of the investing neighbors
of $v^{*}$, due to the definitions of the externality and cost functions given
above, the utility of the player $v^{*}$ is
$g_{v^{*}}(\left|B^{\prime}\right|)=1$. Let $v$ be a player other than
$v^{*}$. If $v\in R$, then as $v$ has at least one neighbor in $B^{\prime}$,
the utility of $v$ is exactly one. If $v\in B^{\prime}$, then the utility of
$v$ is $g_{v}(2)-c(v)=1$. Finally, if $v\in B\setminus B^{\prime}$, the
utility of $v$ is $g_{v}(0)=1$.

$(\Leftarrow)$ Assume that there is a profile ${\bf{s}}$ where every player
obtains utility at least one. Observe first that none of $R\cup\\{v^{*}\\}$
can be contained in ${\bf{s}}$, since for every player in $R\cup\\{v^{*}\\}$,
the investment cost is exactly one and the externality benefit is at most one.
It follows that ${\bf{s}}\subseteq B$. Then, it must hold that
$\left|\bf{s}\right|\leq\kappa$, since otherwise the utility of the player
$v^{*}$ can be at most $g_{v^{*}}(\left|\bf{s}\right|)=0$. Finally, as every
player $v\in R$ obtains utility at least one under $\bf{s}$, at least one of
$v$’s neighbors must be contained in ${\bf{s}}$. This implies that $\bf{s}$
dominates $R$. ∎

A close look at the reduction in the proof of Theorem 3 reveals that if the
RBDS instance is a No-instance, the best achievable ESW in the constructed
BNPG is zero. The following corollary follows.

######  Corollary 1.

ESWC is not polynomial-time approximable within factor $\beta(p)$ unless
${\textsf{P}}={\textsf{NP}}$, where $p$ is the input size and $\beta$ can be
any computable function in $p$. Moreover, this holds even when the given
network is bipartite with diameter at most $4$ and all players have the same
investment cost.

## Games with Critical Clique Forests

In the previous section, we showed that all problems studied in the paper are
NP-hard. This motivates us to study the problems when the give network is
subject to some restrictions. Yu et. al. (2020) considered the cases where the
given networks are cliques or trees, and showed separately that PSNEC in both
cases becomes polynomial-time solvable. To significantly extend their results,
we derive a polynomial-time algorithm which applies to a much larger class of
networks containing both cliques and trees. Generally speaking, we consider
the networks whose vertices can be divided into disjoint cliques and,
moreover, contracting these cliques results in a forest. For formal
expositions, we need the following notions.

A critical clique in a graph $G=(V,E)$ is a clique $K\subseteq V$ whose
members share exactly the same neighbors and is maximal under this property,
i.e., for every $v\in V\setminus K$ either $v$ is adjacent to all vertices in
the clique $K$ or is adjacent to none of them, and there does not exist any
other clique $K^{\prime}$ satisfying the same condition and $K\subset
K^{\prime}$. The concept of critical cliques was coined by Lin, Jiang, and
Kearney (2000), and since then has been used to derive many efficient
algorithms (see, e.g., (Guo 2009; Dom et al. 2006, 2008)). It is well-known
any two different critical cliques do not intersect. In addition, for two
critical cliques, either they are completely adjacent (i.e., there is an edge
between every two vertices from the two cliques respectively), or they are not
adjacent at all (i.e., there are no edges between these two cliques). For
brevity, when we say two critical cliques are adjacent we mean that they are
completely adjacent. For a graph $G$, its critical clique graph, denoted by
$\mathcal{K}(G)$, is the graph whose vertices are critical cliques of $G$ and,
moreover, there is an edge between two vertices if and only if the
corresponding critical cliques are adjacent in $G$. See Figure 2 for an
illustration. Every graph has a unique critical clique graph and, importantly,
it can be constructed in polynomial time (Lin, Jiang, and Kearney 2000; Dom et
al. 2006).

Figure 2: A graph $G$ and its critical clique graph $\mathcal{K}(G)$.

We are ready to show the first main result in this section.

######  Theorem 4.

PSNEC is polynomial-time solvable when the critical clique graph of the given
network is a forest.

###### Proof.

To prove the theorem, we derive a dynamic programming algorithm to solve PSNEC
in the case where the given network has a critical clique graph being a
forest. Let $\mathcal{G}=(V,E,g_{V},c)$ be a BNPG, where $G=(V,E)$ is a
network of players. We first create the critical clique graph of $G$ in
polynomial time. Let $T$ denote the critical clique graph of $G$. For clarity,
we call vertices in $T$ nodes. For notational simplicity, we directly use the
critical clique to denote its corresponding node in $T$. If $G$ is
disconnected, we run the following algorithm for each connected component.
Then, we return the union of the profiles computed for all connected
components if all subgames restricted to these connected components admit
PSNEs; otherwise, we return “No”. Therefore, let us assume now that $G$ is
connected, and hence $T$ is a tree. We choose any arbitrary node in $T$ and
make it as the root of the tree. For each nonroot node $K$ in $T$, let
$K^{\text{P}}$ denote the parent node of $K$ in $T$. If $K$ is the root, we
define $K^{\text{P}}=\emptyset$. In addition, let $\textsf{chd}(K)$ be the set
of the children of $K$ in $T$ for every nonleaf node $K$. If $K$ is a leaf, we
define ${\textsf{chd}}(K)=\\{\emptyset\\}$. We use $T_{K}$ to denote the
subtree of $T$ rooted at $K$, and use $\textsf{Ver}(T_{K})$ to denote the set
of vertices in $G$ that are contained in the nodes of $T_{K}$, i.e.,

$\textsf{Ver}(T_{K})=\bigcup_{K~{}\text{is a node in}~{}T_{K}}K.$

For each node $K$ in $T$, we maintain a binary dynamic table
${\textsf{DT}}_{K}(x,y,z)$, where $x$, $y$, and $z$ are integers such that

  * •

$0\leq x\leq\left|K\right|$,

  * •

$0\leq y\leq\left|K^{\text{P}}\right|$, and

  * •

$0\leq z\leq\left|\bigcup_{K^{\prime}\in\textsf{chd}(K)}K^{\prime}\right|$.

Particularly, $\textsf{DT}_{K}(x,y,z)$ is supposed to be $1$ if and only if
the subgame $\mathcal{G}|_{{\textsf{Ver}}(T_{K^{\text{P}}})}$ admits a profile
${\bf{s}}$ under which (regard $T_{K^{\text{P}}}$ as $T$ if $K$ is the root of
$T$)

  * •

everyone in $K$ has exactly $x$ closed neighbors in $K$ who invest, i.e.,
$\left|{\bf{s}}\cap K\right|=x$,

  * •

everyone in $K$ has exactly $y$ neighbors in $K^{\text{P}}$ who invest, i.e.,
$\left|{\bf{s}}\cap K^{\text{P}}\right|=y$,

  * •

everyone in $K$ has exactly $z$ neighbors in their children nodes who invest,
i.e., $\sum_{K^{\prime}\in{\textsf{chd}}(K)}\left|{\bf{s}}\cap
K^{\prime}\right|=z$ and,

  * •

none of players in ${\textsf{Ver}}(T_{K})$ has an incentive to deviate.

Clearly, after computing all entries of the table ${\textsf{DT}}_{\hat{K}}$
associated to the root node $\hat{K}$ in $T$, we could conclude that the given
BNPG admits a PSNE if and only if there if there is a $1$-valued entry
${\textsf{DT}}_{\hat{K}}(x,0,z)=1$.

The tables associated to the nodes in $T$ are computed in a bottom-up manner,
from those associated to leaf nodes up to that associated to the root node.
Let ${\textsf{DT}}_{K}(x,y,z)$ be an entry considered at the moment. For each
player $v$, we define

$\triangle(v,0)=g_{v}(x+y+z)-c(v)-g_{v}(x+y+z-1),$
$\triangle(v,1)=g_{v}(x+y+z)-(g_{v}(x+y+z+1)-c(v)).$

Note that if $\triangle(v,0)<0$, $v$ does not invest in any PSNE, and if
$\triangle(v,1)<0$, $v$ must invest in every PSNE. Therefore, if there is a
player $v\in K$ such that $\triangle(v,0)<0$ and $\triangle(v,1)<0$, we
immediately set $\textsf{DT}_{K}(x,y,z)=0$. Otherwise, we divide the players
from $K$ into

  * •

$K_{{-}}=\\{v\in K:\triangle(v,0)<0\\}$;

  * •

$K_{{+}}=\\{v\in K:\triangle(v,1)<0\\}$; and

  * •

$K_{*}=K\setminus(K_{{+}}\cup K_{-})$.

We have the following observations.

  * •

None of $K_{{-}}$ invests in any PSNE;

  * •

All players in $K_{{+}}$ must invest in all PSNEs;

  * •

Each player in $K_{*}$ can be in both the set of investing players and the set
of noninvesting players under all PSNEs.

Given the above observations, if $\left|K_{{+}}\right|>x$ or
$\left|K_{{+}}\cup K_{*}\right|<x$, we directly set
${\textsf{DT}}_{K}(x,y,z)=0$. Let us assume now that $\left|K_{{+}}\right|\leq
x$ and $\left|K_{{+}}\cup K_{*}\right|\geq x$. We determine the value of
${\textsf{DT}}_{K}(x,y,z)$ as follows. If $K$ is a leaf node, we set
${\textsf{DT}}_{K}(x,y,z)=1$ if and only if $z=0$. Otherwise, let
($K_{1},K_{2},\dots,K_{t})$ be an arbitrary but fixed order of the children of
$K$ in $T$, where $t$ is the number of children of $K$ in $T$. Then, we set
${\textsf{DT}}_{K}(x,y,z)=1$ if and only if the following condition holds:
there are entries $\textsf{DT}_{K_{1}}(x_{1},y_{1},z_{1})=1$,
$\textsf{DT}_{K_{2}}(x_{2},y_{2},z_{2})=1$, $\dots$,
$\textsf{DT}_{K_{t}}(x_{t},y_{t},z_{t})=1$ such that $y_{j}=x$ for all
$j\in[t]$ and $\sum_{j=1}^{t}x_{t}=z$. In fact, in this case we let all
players in $K_{{+}}$ and arbitrarily $x-\left|K_{{+}}\right|$ players in
$K_{*}$ invest; and let all the other players in $K$ not invest. Importantly,
the above condition can be checked in polynomial time by a dynamic programming
algorithm. To this end, we maintain a binary dynamic table
${\textsf{DT}^{\prime}}(i,x_{i}(1),x_{i}(2))$ where $i\in[t]$, and $x_{i}(1)$
and $x_{i}(2)$ are two integers such that $0\leq
x_{i}(1)\leq\left|K_{i}\right|$ and $0\leq
x_{i}(2)\leq\left|\bigcup_{j\in[i-1]}K_{j}\right|$ if $i>1$ and $x_{i}(2)=0$
if $i=1$. In particular, ${\textsf{DT}^{\prime}}(i,x_{i}(1),x_{i}(2))$ is
supposed to be $1$ if and only if there are entries
$\textsf{DT}_{K_{1}}(x_{1},y_{1},z_{1})=1$,
$\textsf{DT}_{K_{2}}(x_{2},y_{2},z_{2})=1$, $\dots$,
$\textsf{DT}_{K_{i}}(x_{i},y_{i},z_{i})=1$ such that $y_{j}=x$ for all
$j\in[i]$, $\sum_{j=1}^{i-1}x_{j}=x_{i}(2)$, and $x_{i}=x_{i}(1)$. The table
is computed as follows. First, every base entry
$\textsf{DT}^{\prime}(1,x_{1}(1),x_{1}(2))$ has value $1$ if and only if
$x_{1}(2)=0$ and ${\textsf{DT}}_{K_{1}}(x_{1}(1),x,z^{\prime})=1$ for some
integer $z^{\prime}$. Then, the value of every entry
${\textsf{DT}^{\prime}}(i,x_{1}(1),x_{1}(2))$ such that $i\geq 2$ is $1$ if
and only if there exists an entry
${\textsf{DT}}^{\prime}(i-1,x_{i-1}(1),x_{i-2}(2))=1$ such that
$x_{i-1}(1)\leq x_{i}(2)$, $x_{i-2}(2)=x_{i}(2)-x_{i-1}(1)$, and
${\textsf{DT}}_{K_{i}}(x_{i}(1),x,z^{\prime})=1$ for some integer
$z^{\prime}$. The above condition is satisfied if and only if
$\textsf{DT}^{\prime}(t,x_{t}(1),x_{t}(2))=1$ for some valid values of
$x_{t}(1)$ and $x_{t}(2)$ such that $x_{t}(1)+x_{t}(2)=z$.

The algorithm can be implemented in polynomial time since for each node $K$,
the corresponding table has at most $n^{3}$ entries, where $n$ is the number
of total players. So, we have in total at most $n^{4}$ entries each of which
can be computed in polynomial time. ∎

For USWC and ESWC we have similar results.

######  Theorem 5 (*).

USWC is polynomial-time solvable if the critical clique graph of the given
network is a forest.

###### Proof.

To prove the theorem, we derive a dynamic programming algorithm to solve USWC
in the case where the given network has a critical clique graph being a
forest. Let $\mathcal{G}=(V,E,g_{V},c)$ be a BNPG, where $G=(V,E)$ is a
network of players. We first create the critical clique graph of $G$ in
polynomial time. Let $T$ denote the critical clique graph of $G$. For clarity,
we call vertices in $T$ nodes. For notational simplicity, we directly use the
critical clique to denote its corresponding node in $T$. If $G$ is
disconnected, we run the following algorithm for each connected component.
Then, we sum up all the values returned by the algorithms running on the
connected components. Therefore, let us assume now that $G$ is connected, and
hence $T$ is a tree. We choose any arbitrary node in $T$ and make it as the
root of the tree. For each nonroot node $K$ in $T$, let $K^{\text{P}}$ denote
the parent node of $K$ in $T$. If $K$ is the root, we define
$K^{\text{P}}=\emptyset$. In addition, let $\textsf{chd}(K)$ be the set of the
children of $K$ in $T$ for every nonleaf node $K$. If $K$ is a leaf, we define
${\textsf{chd}}(K)=\\{\emptyset\\}$. We use $T_{K}$ to denote the subtree of
$T$ rooted at $K$, and use $\textsf{Ver}(T_{K})$ to denote the set of vertices
in $G$ that are contained in the nodes in the subtree $T_{K}$. For each node
$K$ in $T$, we maintain a dynamic table ${\textsf{DT}}_{K}(x,y,z)$, where $x$,
$y$, and $z$ are integers such that

  * •

$0\leq x\leq\left|K\right|$,

  * •

$0\leq y\leq\left|K^{\text{P}}\right|$, and

  * •

$0\leq z\leq\left|\bigcup_{K^{\prime}\in\textsf{chd}(K)}K^{\prime}\right|$.

We say that a profile of the subgame
$\mathcal{G}|_{\textsf{Ver}(T_{K^{\text{P}}})}$ (regard $T_{K^{\text{P}}}$ as
$T$ if $K$ is the root of $T$) is a $\textsf{DT}_{K}(x,y,z)$-compatible
profile of the subgame if in this profile the following three conditions are
satisfied:

  1. 1.

exactly $x$ players in $K$ invest,

  2. 2.

exactly $y$ players in $K^{\text{P}}$ invest, and

  3. 3.

exactly $z$ players in $\bigcup_{K^{\prime}\in\textsf{chd}(K)}K^{\prime}$
invest.

The value of the entry ${\textsf{DT}}_{K}(x,y,z)$ is supposed to be the
maximum possible USW of players in ${\textsf{Ver}}(T_{K})$ under
$\textsf{DT}_{K}(x,y,z)$-compatible profiles of the subgame
$\mathcal{G}|_{\textsf{Ver}(T_{K^{\text{P}}})}$.

The values of the entries in the table can be computed recursively, beginning
from the leaf nodes up to the root node. In particular, if
${\textsf{DT}}_{K}(x,y,z)$ is a leaf node in $T$ (note that in this case
$z=0$), we compute ${\textsf{DT}}_{K}(x,y,0)$ as follows. For every player
$v\in K$, the number of closed neighbors who invest is exactly $x+y$ in every
${\textsf{DT}}_{K}(x,y,0)$-compatible profile. Then, the utility of every
player $v\in K$ to investing and not to investing are respectively
$g_{v}(x+y)-c(v)$ and $g_{v}(x+y)$. We order players in $K$ according to a
nondecreasing order of the investment costs $c(v)$ of players $v\in K$. Then,
it is easy to see that a ${\textsf{DT}}_{K}(x,y,0)$-compatible profile which
consists of the first $x$ players in the order achieves the maximum possible
USW of players in $K$, among all ${\textsf{DT}}_{K}(x,y,0)$-compatible
profiles of the game restricted to $\textsf{Ver}(T_{K^{\text{P}}})$. Let $H$
be the set of the first $x$ players in the order. In light of the above
discussion, we define

$\displaystyle{\textsf{DT}}_{K}(x,y,0)$ $\displaystyle=\sum_{v\in
H}(g_{v}(x+y)-c(v))+\sum_{v\in K\setminus H}g_{v}(x+y)$
$\displaystyle=\sum_{v\in K}g_{v}(x+y)-\sum_{v\in H}c(v).$

For a nonleaf node $K$, we compute ${\textsf{DT}}_{K}(x,y,z)$ as follows,
assuming that the values of all tables associated to the descendants of $K$
are already computed. First, similar to the above case, we first order players
in $K$ according to a nondecreasing order of $c(v)$, $v\in K$, and let $H$
denote the first $x$ players in the order. Then, we define

$s=\sum_{v\in H}\left(g_{v}(x+y+z)-c(v)\right)+\sum_{v\in K\setminus
H}g_{v}(x+y+z),$

which is the maximum possible USW of players in $K$ under
${\textsf{DT}}_{K}(x,y,z)$-compatible profiles. However, we need also to take
into account the USW of the descendents of $K$. We solve this by a dynamic
programming. Let $(K_{1},K_{2},\dots,K_{t})$ be an arbitrary but fixed order
of children of $K$, where $t$ is the number of children of $K$. As $K$ is the
parent of each $K_{i}$, only the entries
${\textsf{DT}}_{K_{i}}(x_{i},y_{i},z_{i})$ such that $y_{i}=x$ are relevant to
our computation. For each $i\in[t]$, we maintain a dynamic table
${\textsf{DT}^{\prime}}(i,x_{i}(1),x_{i}(2))$ where $x_{i}(1)$ and $x_{i}(2)$
are two integers such that $0\leq x_{i}(1)\leq\left|K_{i}\right|$ and $0\leq
x_{i}(2)\leq\bigcup_{j\in[i-1]}K_{j}$ if $i>1$ and $x_{i}(2)=0$ if $i=1$. The
integer $x_{i}(1)$ and $x_{i}(2)$ respectively indicate the number of players
in $K_{i}$ who invest and the number of players in $\bigcup_{j\in[i-1]}K_{j}$
who invest, and the value of the entry is the maximum possible USW of players
in $\bigcup_{j\in[i]}K_{j}$ and their descendants, i.e., the USW of players in
$\bigcup_{j\in[i]}{\textsf{Ver}}(T_{K_{j}})$, under the above restrictions.
The table is computed as follows. First, we let

${\textsf{DT}^{\prime}}(1,x_{1}(1),0)=\max_{z^{\prime}}{\textsf{DT}}_{K_{1}}(x_{1}(1),x,z^{\prime}),$

where $z^{\prime}$ runs over all possible values. Then, for each $i$ from $2$
to $t$ (this applies only when $t\geq 2$), the entry
${\textsf{DT}}^{\prime}(i,x_{i}(1),x_{i}(2))$ is computed by the following
recursive:

$\displaystyle\textsf{DT}^{\prime}(i,x_{i}(1),x_{i}(2))=\max_{z^{\prime}}{\textsf{DT}}_{K_{i}}(x_{i}(1),x,z^{\prime})+$
$\displaystyle\max_{\begin{subarray}{c}0\leq
x_{i-1}(1)\leq\left|K_{i-1}\right|\\\ x_{i}(2)-x_{i-1}(1)\geq
0\end{subarray}}\\{\textsf{DT}^{\prime}(i-1,x_{i-1}(1),x_{i}(2)-x_{i-1}(1))\\},$

where $z^{\prime}$ runs all possible values. After all the entries are
updated, we define

$s^{\prime}=\max_{\begin{subarray}{c}0\leq x_{t}(1)\leq\left|K_{t}\right|\\\
x_{t}(1)+x_{t}(2)=z\end{subarray}}\\{\textsf{DT}^{\prime}(t,x_{t}(1),x_{t}(2))\\}.$

Now we are ready to update the entry for $K$. In particular, we define

$\textsf{DT}_{K}(x,y,z)=s+s^{\prime}.$

After the entries of the table DT are computed, we return

$\max_{x^{\prime},z^{\prime}}\\{\textsf{DT}_{K}(x^{\prime},0,z^{\prime})\\},$

where $K$ is the root node and $x^{\prime}$ and $z^{\prime}$ run over all
possible values.

The algorithm can be implemented in polynomial time since for each node $K$,
the corresponding table has at most $n^{3}$ entries, where $n$ is the number
of total players. So, we have in total at most $n^{4}$ entries each of which
can be computed in polynomial time. ∎

######  Theorem 6 (*).

ESWC is polynomial-time solvable if the critical clique graph of the given
network is a forest.

###### Proof.

The algorithm is similar to the one in the proof of Theorem 5. In particular,
we guess the ESW of the desired profile. There can be polynomially many
guesses. For each guessed value $q$, we determine if there is a profile of ESW
at least $q$, i.e., every player receives utility at least $q$ under this
profile. This can be solved using a dynamic programming algorithm. We adopt
the same notations in the proof of Theorem 5. However, in the current
algorithm, each entry $\textsf{DT}_{K}(x,y,z)$ in the dynamic tables takes
only binary values. Precisely, $\textsf{DT}_{K}(x,y,z)$ is supposed to be $1$
if and only if the subgame $\mathcal{G}|_{{\textsf{Ver}}(T_{K}^{\text{P}})}$
admits a profile ${\bf{s}}$ under which (regard $T_{K^{\text{P}}}$ as $T$ if
$K$ is the root of $T$)

  1. 1.

exactly $x$ players in $K$ invest, i.e., $\left|{\bf{s}}\cap K\right|=x$,

  2. 2.

exactly $y$ players in $K^{\text{P}}$ invest, i.e., $\left|{\bf{s}}\cap
K^{\text{P}}\right|=y$,

  3. 3.

exactly $z$ players in $\bigcup_{K^{\prime}\in\textsf{chd}(K)}K^{\prime}$
invest, i.e., $\sum_{K^{\prime}\in\textsf{chd}(K)}\left|{\bf{s}}\cap
K^{\prime}\right|=z$ and, more importantly,

  4. 4.

every player $v\in{\textsf{Ver}}(T_{K})$ obtains utility at least $q$ under
this profile, i.e.,
$\mu(v,{\bf{s}},\mathcal{G}|_{{\textsf{Ver}}(T_{K^{\text{P}}})})\geq q$.

The values of entries in the tables associated to leaf nodes can be computed
trivially based on the above definition. We describe how to update the
remaining tables. Let ${\textsf{DT}}_{K}(x,y,z)$ be the currently considered
entry in a table associated to a node $K$ in $T$. Let
$K_{1},K_{2},\dots,K_{t}$ be the children of $K$ in $T$. We set
${\textsf{DT}}_{K}(x,y,z)$ to be $1$ if and only if the following conditions
hold simultaneously.

  1. 1.

There is a subset $K^{\prime}\subseteq K$ of cardinality $x$ such that

     * •

for every $v\in K^{\prime}$ it holds that $g_{v}(x+y+z)-c(v)\geq q$; and

     * •

for every $v\in K\setminus K^{\prime}$ it holds that $g(x+y+z)\geq q$.

  2. 2.

There are ${\textsf{DT}}_{K_{1}}(x_{1},x,z_{1})=1$,
${\textsf{DT}}_{K_{2}}(x_{2},x,z_{2})=1$, $\dots$,
${\textsf{DT}}_{K_{t}}(x_{t},x,z_{t})=1$ such that $\sum_{j=1}^{t}x_{j}=z$.

We point out that both of the above two conditions can be checked in
polynomial time. Precisely, to check the first condition, we define $A=\\{v\in
K:g_{v}(x+y+z)<q\\}$ and $B=\\{v\in K:g_{v}(x+y+z)\geq
q,g_{v}(x+y+z)-c(v)<q\\}$, both of which can be computed in polynomial time.
Clearly, if $A\neq\emptyset$, Condition 1 does not hold. Otherwise, if
$\left|B\right|>\left|K\right|-x$, we also conclude that Condition 1 does not
hold, because due to the definition of $B$, none of them should invest in
order to obtain utility at least $q$. If none of the above two cases occurs,
we conclude that Condition 1 holds. As a matter of fact, in this case, we can
let $K^{\prime}$ be any subset of $K\setminus B$ of cardinality $x$. To check
Condition 2, we use a similar dynamic programming algorithm with the
associated table ${\textsf{DT}^{\prime}}(i,x_{i}(1),x_{i}(2))$ in the proof of
Theorem 5.

The algorithm runs in polynomial time since there are polynomially many
entries and computing the value for each entry can be done in polynomial time.
∎

## Networks with Bounded Treewidth

In this section, we study another prevalent class of tree-like networks,
namely, the networks with a constant bounded treewidth. We show that the
problems studied in the paper are polynomial-time solvable in this special
case. Notice that as every clique of size $k$ has treewidth $k-1$, the results
established in the previous section do not cover the polynomial-time
solvability in this case. The other direction does not hold too because every
cycle has treewidth three but the critical clique graph of every cycle is
itself.

The following notion is due to (Robertson and Seymour 1986).

A tree decomposition of a graph $G=(V,E)$ is a tuple $(T=(L,F),\mathcal{B})$,
where $T$ is a rooted tree with vertex set $L$ and edge set $F$, and
$\mathcal{B}=\\{B_{x}\subseteq V\mid x\in L\\}$ is a collection of subsets of
vertices of $G$ such that the following three conditions are satisfied:

  * •

every $v\in V$ is contained in at least one element of $\mathcal{B}$;

  * •

for each edge $(v,v^{\prime})\in E$, there exists at least one
$B_{x}\in\mathcal{B}$ such that $v,v^{\prime}\in B_{x}$; and

  * •

for every $v\in V$, if $v$ is in two distinct $B_{x},B_{y}\in\mathcal{B}$,
then $v$ is in every $B_{z}\in\mathcal{B}$ where $z$ is on the unique path
between $x$ and $y$ in $T$.

The width of the tree decomposition is $\max_{B\in\mathcal{B}}{|B|-1}$. The
treewidth of a graph $G$, denoted by $\omega(G)$, is the width of a tree
decomposition of $G$ with the minimum width. The subsets in $\mathcal{B}$ are
often called bags. The root bag in the decomposition is the bag associated to
the root of $T$. To avoid confusion, in the following we refer to the vertices
of $T$ as nodes. The parent bag of a bag $B_{i}\in\mathcal{B}$ means the bag
associated to the parent of $i$.

A more refined notion is the so-called nice tree decomposition. Particular, a
nice tree decomposition $(T,\mathcal{B})$ of a graph $G$ is a specific tree
decomposition of $G$ satisfying the following conditions:

  * •

every bag associated to the root or a leaf of $T$ is empty;

  * •

inner nodes of $T$ are categorized into introduce nodes, forget nodes, and
join nodes such that

    * –

each introduce node $x$ has exactly one child $y$ such that $B_{y}\subset
B_{x}$ and $|B_{x}\setminus B_{y}|=1$;

    * –

each forget node $x$ has exactly one child $y$ such that $B_{x}\subset B_{y}$
and $|B_{y}\setminus B_{x}|=1$; and

    * –

each join node $x$ has exactly two children $y$ and $z$ such that
$B_{x}=B_{y}=B_{z}$.

For ease of exposition, we sometimes call a bag associated to a join (resp.
forget, introduce) node a join (resp. forget, introduce) bag. It can be known
from the definition that in a nice tree decomposition of a graph $G$, every
vertex in $G$ can be introduced several times but can be only forgotten once.
Nice tree decomposition was introduced by Bodlaender and Kloks (1991), and has
been used in tacking many problems. At first glance, nice tree decomposition
seems very restrictive. However, it is proved that given a tree decomposition
of width $\omega$, one can calculate a nice tree decomposition with the same
width in polynomial-time (Kloks 1994).

It is known that calculating the treewidth of a graph $G$ is NP-hard
(Bodlaender 1993). However, determining whether a graph has a constant bounded
treewidth can be solved in polynomial time and, moreover, powerful heuristic
algorithms, approximation algorithms, and fixed-parameter algorithms to
calculating treewidth have been reported (Bodlaender 2012; Bodlaender et al.
2016; van der Zanden and Bodlaender 2017). Hence, in the following results we
assume that a nice tree-decomposition of the given network is given.

######  Theorem 7 (*).

PSNEC is polynomial-time solvable if the treewidth of the given network is a
constant.

###### Proof.

Let $\mathcal{G}=(V,E,g_{V},c)$ be a BNPG, where $(V,E)$ is a network of
players, $g_{V}$ is a set of externality functions of players in $V$, one for
each player, and $c:V\rightarrow\mathbb{R}_{\geq 0}$ is the investment cost
function. For every player $v\in V$, let
$g_{v}:\mathbb{N}_{0}\rightarrow\mathbb{R}_{\geq 0}$ denote its externality
function in $g_{V}$. Let $G$ denote the network $(V,E)$, and let
$n=\left|V\right|$ be the number of players. In addition, let
$(T,\mathcal{B})$ be a nice-tree decomposition of $G$ which is of polynomial
size in $n$ and of width at most $p$ for some constant $p$. For a node $i$ in
$T$, let $B_{i}\in\mathcal{B}$ denote its associated bag in the nice tree
decomposition. Moreover, let $T_{i}$ denote the subtree of $T$ rooted at $i$,
let $G_{i}=G[\bigcup_{j\in{\sf{V}}(T_{i})}B_{j}]$ denote the subgraph of $G$
induced by all vertices contained in bags associated to nodes in $T_{i}$, and
let $V_{i}$ denote the vertex set of $G_{i}$. For each nonroot bag
$B_{i}\in\mathcal{B}$, we define $B_{i}^{\text{P}}$ as the parent bag of
$B_{i}$. If $B_{i}$ is the root bag, we define $B_{i}^{\text{P}}=\emptyset$.
For each bag $B_{i}$ associated to a node $i$ and each vertex $v\in B_{i}$, we
use $n_{i}(v)$ to denote the number of neighbors of $v$ in the subgraph
$G_{i}-B_{i}$. In the following, we derive a dynamic programming algorithm to
determine if the BNPG game $\mathcal{G}$ has a PSNE profile, and if so, the
algorithm returns a PSNE profile.

For each bag $B_{i}\in\mathcal{B}$, we maintain a binary dynamic table
${\textsf{DT}}_{i}(U,f)$ where $U$ runs over all subsets of $B_{i}$ and $f$
runs over all functions $f:B_{i}\rightarrow\mathbb{N}_{0}$ such that $f(u)\leq
n_{i}(u)$ for every $u\in B_{i}$. The entry ${\textsf{DT}}_{i}(U,f)$ is
supposed to be $1$ if the subgame $\mathcal{G}|_{V_{i}}$ admits a profile
${\bf{s}}$ such that

  1. 1.

${\bf{s}}\cap B_{i}=U$;

  2. 2.

no player in $V(G_{i})\setminus B_{t^{\prime}}$ has an incentive to deviate
under ${\bf{s}}$; and

  3. 3.

every player $v\in B_{i}$ has exactly $f(v)$ investing neighbors contained in
$G_{i}-B_{i}$ under ${\bf{s}}$.

We compute the tables for the bags in a bottom-up manner, beginning from those
associated to leaf nodes to the table associated to the root. Assume that
${\textsf{DT}}_{i}(U,f)$ is the currently considered entry. To compute the
value of this entry, we distinguish the following cases.

Case 1: $B_{i}^{\text{P}}$ is a join or an introduce bag, or $i$ is the root
of $T$

We further distinguish between the following subcases.

Case 1.1: $B_{i}$ is a join bag

Let $x$ and $y$ be the two children of $i$. Therefore, it holds that
$B_{x}=B_{y}=B_{i}$. In this case, we set ${\textsf{DT}}_{i}(U,f)=1$ if and
only if ${\textsf{DT}}_{x}(U,f)=1$ and ${\textsf{DT}}_{y}(U,f)=1$.

Case 1.2: $B_{i}$ is an introduce bag

Let $x$ be the child of $i$, and let $B_{i}\setminus B_{x}=\\{v\\}$. (In this
case, $i$ cannot the root of $T$) Notice that in this case, $v$ does not have
any neighbor in $G_{i}-B_{i}$. Then, we set ${\textsf{DT}}_{i}(U,f)=1$ if and
only if $f(v)=0$ and ${\textsf{DT}}_{x}(U\setminus\\{v\\},f|_{\neg v})=1$.

Case 1.3: $B_{i}$ is a forget node

Let $x$ be the child of $i$, and let $B_{x}\setminus B_{i}=\\{v\\}$. Then, we
set ${\textsf{DT}}_{i}(U,f)=1$ if and only if there exists an entry
${\textsf{DT}}_{x}(U^{\prime},f^{\prime})=1$ such that
$U^{\prime}\setminus\\{v\\}=U$ and $f^{\prime}|_{\neg v}=f$.

Case 2: $B_{i}^{\text{P}}$ is a forget node

Let $B_{i}\setminus B_{i}^{\text{P}}=\\{v\\}$. We further divided into three
subcases.

Case 2.1 $B_{i}$ is a join bag

Let $x$ and $y$ denote the two children of $i$ in $T$. Then, we set
${\textsf{DT}}_{i}(U,f)=1$ if and only if
${\textsf{DT}}_{x}(U,f)={\textsf{DT}}_{y}(U,f)=1$ and, moreover,
$g_{v}(n_{G}[v,U]+f(v))-c(v)\geq g_{v}(n_{G}(v,U))$ when $v\in U$ and
$g_{v}(n_{G}(v,U)+f(v))\geq g_{v}(n_{G}(v,U)+f(v))-c(v)$ when $v\in
B_{i}\setminus U$.

Case 2.2 $B_{i}$ is an introduce bag

Let $x$ denote the child of $i$ in $T$. Let $B_{i}\setminus B_{x}=\\{u\\}$.
Obviously, $u$ does not have any neighbor in $G_{i}-B_{i}$. Therefore, if
$f(u)>0$, we directly set ${\textsf{DT}}_{i}(U,f)=0$. Let us assume now that
$f(u)=0$. Then, we set ${\textsf{DT}}_{i}(U,f)=1$ if and only if
${\textsf{DT}}_{x}(U\setminus\\{u\\},f|_{\neg u})=1$ and, moreover, it holds
that $g_{v}(n_{G}[v,U]+f(v))-c(v)\geq g_{v}(n_{G}(v,U))$ when $v\in U$ and
$g_{v}(n_{G}(v,U))\geq g_{v}(n_{G}[v,U]+f(v))-c(v)$ when $v\in B_{i}\setminus
U$.

Case 2.3, $B_{i}$ is a forget bag

Let $x$ denote the child of $i$ in $T$, and let $B_{i}\setminus
B_{x}=\\{u\\}$. In this case, we set ${\textsf{DT}}_{i}(U,f)=1$ if and only if
the following two conditions holds:

  * •

there exists an entry ${\textsf{DT}}_{x}(U^{\prime},f^{\prime})=1$ such that
$U^{\prime}\setminus\\{u\\}=U$, $f^{\prime}|_{\neg u}=f$ and

  * •

$g_{v}(n_{G}[v,U]+f(v))-c(v)\geq g_{v}(n_{G}(v,U))$ when $v\in U$ and
$g_{v}(n_{G}(v,U))\geq g_{v}(n_{G}[v,U]+f(v))-c(v)$ when $v\in B_{i}\setminus
U$.

Recall that the root bag is empty. Therefore, there is only one entry in the
table associated to the root. The game $\mathcal{G}$ admits a PSNE profile if
the only entry in the table of the root takes the value $1$. A PSNE can be
constructed using standard backtracking technique of dynamic programming
algorithms if such a profile exists.

Finally, we analysis the running time of the algorithm. First, there are in
total $O(n)$ bags where $n$ denotes the number of all players in the given
game. Let $k$ be the treewidth of the given nice tree decomposition of the
given network. For each bag $B$, the set associated to $B$ is of cardinality
$2^{|B|}\cdot n^{|B|}=O^{*}(2n^{k})$, which can be constructed in
$O^{*}(2n^{k})$ time. Therefore, the running time of the algorithm is bounded
by $O^{*}(2n^{k})$, which is polynomial if $k$ is a constant. ∎

######  Theorem 8 (*).

USWC is polynomial-time solvable if the treewidth of the given network is a
constant.

###### Proof.

Let $\mathcal{G}=(V,E,g_{V},c)$ be a BNPG, where $(V,E)$ is a network of
players, $g_{V}$ is a set of externality functions of players in $V$, one for
each player, and $c:V\rightarrow\mathbb{R}_{\geq 0}$ is the cost function. For
every player $v\in V$, let $g_{v}:\mathbb{N}_{0}\rightarrow\mathbb{R}_{\geq
0}$ denote its externality function in $g_{V}$. Let $G$ denote the network
$(V,E)$, and let $n=\left|V\right|$ be the number of players. In addition, let
$(T,\mathcal{B})$ be a nice-tree decomposition of $G$ which is of polynomial
size in $n$ and of width at most $p$ for some constant $p$. For a node $i$ in
$T$, let $B_{i}\in\mathcal{B}$ denote its associated bag. Moreover, let
$T_{i}$ denote the subtree of $T$ rooted at $i$, let
$G_{i}=G[\bigcup_{j\in{\sf{V}}(T_{i})}B_{j}]$ denote the subgraph of $G$
induced by all vertices contained in bags associated to nodes in $T_{i}$, and
let $V_{i}$ denote the vertex set of $G_{i}$. For each nonroot bag
$B_{i}\in\mathcal{B}$, we define $B_{i}^{\text{P}}$ as the parent bag of
$B_{i}$. If $B_{i}$ is the root bag, we define $B_{i}^{\text{P}}=\emptyset$.
For each bag $B_{i}$ associated to a node $i$ and each vertex $v\in B_{i}$, we
use $n_{i}(v)$ to denote the number of neighbors of $v$ in the subgraph
$G_{i}-B_{i}$. In the following, we derive a dynamic programming algorithm to
compute a profile of $\mathcal{G}$ with the maximum possible USW.

For each bag $B_{i}\in\mathcal{B}$, we maintain a dynamic table
${\textsf{DT}}_{i}(U,f)$ where $U$ runs over all subsets of $B_{i}$ and $f$
runs over all functions $f:B_{i}\rightarrow\mathbb{N}_{0}$ such that $f(u)\leq
n_{i}(u)$ for every $u\in B_{i}$. A profile ${\bf{s}}$ of a the subgame
$\mathcal{G}|_{V_{i}}$ is consistent with the tuple $(U,f)$ if among the
players in $B_{i}$ exactly those in $U$ invest and, moreover, each $v\in
B_{i}$ has exactly $f(v)$ neighbors in $G_{i}-B_{i}$ who invest, i.e.,
${\bf{s}}\cap B_{i}=U$ and $n_{G}(v,{\bf{s}}\setminus U)=f(v)$. The entry
${\textsf{DT}}_{i}(U,f)$ is defined as

$\max_{{\bf{s}}}\left(\sum_{v\in V_{i}\setminus
B_{i}^{\text{P}}}\mu(v,\mathcal{G}|_{V_{i}},{\bf{s}})\right),$

where ${\bf{s}}$ runs over all profiles of the subgame $\mathcal{G}|_{V_{i}}$
that are consistent with $(U,f)$. If the subgame does not admit a profile
which is consistent with $(U,f)$, ${\textsf{DT}}_{i}(U,f)=-\infty$.

To compute the values of the entries, we distinguish the following cases. Let
${\textsf{DT}}_{i}(U,f)$ denote the currently considered entry.

Case 1: $B_{i}^{\text{P}}$ is a join or an introduce bag, or $i$ is the root
of $T$

We consider the following subcases.

Case 1.1: $B_{i}$ is a join bag

Let $x$ and $y$ denote the two children of $i$ in the tree $T$. Then, we
define

${\textsf{DT}}_{i}(U,f)={\textsf{DT}}_{x}(U,f)+{\textsf{DT}}_{y}(U,f).$

Case 1.2 $B_{i}$ is an introduce bag

Let $x$ be the child of $i$ in $T$, and let $B_{i}\setminus B_{x}=\\{v\\}$.
(In this case, $i$ cannot be the root of $T$.) Observe that in this case $v$
does not have any neighbors in $G_{i}-B_{i}$. Hence, if $f(v)>0$, we let
${\textsf{DT}}_{i}(U,f)=-\infty$. Otherwise, it must be that $f(v)=0$, and we
let

${\textsf{DT}}_{i}(U,f)={\textsf{DT}}_{x}(U\setminus\\{v\\},f|_{\neg v}).$

Case 1.3: $B_{i}$ is a forget bag

Let $x$ be the child of $i$ in $T$ and let $B_{x}\setminus B_{i}=\\{v\\}$.
Then, we define

${\textsf{DT}}_{x}(U,f)=\max_{\begin{subarray}{c}U^{\prime}\subseteq
B_{x}~{}\text{s.t.}~{}U^{\prime}\setminus\\{v\\}=U,\\\
f^{\prime}:B_{x}\rightarrow\mathbb{N}_{0}~{}\text{s.t.}~{}f^{\prime}|_{\neg
v}=f\end{subarray}}\\{{\textsf{DT}}_{x}(U^{\prime},f^{\prime})\\}.$

Case 2: $B_{i}^{\text{P}}$ is a forget bag

Let $B_{i}\setminus B_{i}^{\text{P}}=\\{v\\}$. We consider the following
subcases.

Case 2.1: $B_{i}$ is a join bag

Let $x$ and $y$ denote the two children of $i$ in $T$. We define

${\textsf{DT}}_{i}(U,f)={\textsf{DT}}_{x}(U,f)+{\textsf{DT}}_{y}(U,f)+\pi(v),$

where

$\pi(v)=\begin{cases}g_{v}(f(v)+n_{G}[v,U])-c(v)&v\in U\\\
g_{v}(f(v)+n_{G}(v,U))&v\in B_{i}\setminus U\\\ \end{cases}$

Case 2.2: $B_{i}$ is an introduce bag

Let $x$ denote the child of $i$ in $T$. In addition, let $B_{i}\setminus
B_{x}=\\{u\\}$. In this case, $u$ does not have any neighbor in $G_{i}-B_{i}$,
and hence if $f(u)>0$ the game restricted to $V_{i}$ does not have a profile
which is consistent with $(U,f)$. Therefore, if $f(u)>0$ we directly set
${\textsf{DT}}_{i}(U,f)=-\infty$. Let us assume that $f(u)=0$. Then, we define

${\textsf{DT}}_{x}(U,f)={\textsf{DT}}_{x}(U\setminus\\{u\\},f|_{\neg
u})+\pi(v),$

where $\pi(v)$ is as defined in Case 2.1.

Case 2.3: $B_{i}$ is a forget bag

Let $x$ denote the child of $i$ in $T$. In addition, let $B_{x}\setminus
B_{i}=\\{u\\}$. Let $\pi(v)$ be as defined in Case 2.1. Then, we define

${\textsf{DT}}_{x}(U,f)=\pi(v)+\max_{\begin{subarray}{c}U^{\prime}\subseteq
B_{x}~{}\text{s.t.}~{}U^{\prime}\setminus\\{u\\}=U\\\
f^{\prime}:B_{i}\rightarrow\mathbb{N}_{0}~{}\text{s.t.}~{}f^{\prime}|_{\neg
u}=f\end{subarray}}\\{{\textsf{DT}}_{x}(U^{\prime},f^{\prime})\\}.$

The algorithm returns ${\textsf{DT}}_{r}(\emptyset,\emptyset)$, where $r$ is
the root. The dynamic programming algorithm runs in polynomial time as there
are in total polynomially many entries and computing the value of each entry
takes polynomial time. ∎

######  Theorem 9.

ESWC is polynomial-time solvable if the treewidth of the given network is a
constant.

###### Proof.

Let $\mathcal{G}=(V,E,g_{V},c)$ be a BNPG, where $(V,E)$ is a network of
players, $g_{V}$ is a set of externality functions of players in $V$, one for
each player, and $c:V\rightarrow\mathbb{R}_{\geq 0}$ is the cost function. For
every player $v\in V$, let $g_{v}:\mathbb{N}_{0}\rightarrow\mathbb{R}_{\geq
0}$ denote its externality function in $g_{V}$. Let $G$ denote the network
$(V,E)$, and let $n=\left|V\right|$ be the number of players. In addition, let
$(T,\mathcal{B})$ be a nice-tree decomposition of $G$ which is of polynomial
size in $n$ and of width at most $p$ for some constant $p$. For a node $i$ in
$T$, let $B_{i}\in\mathcal{B}$ denote its associated bag. Moreover, let
$T_{i}$ denote the subtree of $T$ rooted at $i$, and let
$G_{i}=G[\bigcup_{j\in{\sf{V}}(T_{i})}B_{j}]$ denote the subgraph of $G$
induced by all vertices contained in bags associated to nodes in $T_{i}$. For
each nonroot bag $B_{i}\in\mathcal{B}$, we define $B_{i}^{\text{P}}$ as the
parent bag of $B_{i}$. If $B_{i}$ is the root bag, we define
$B_{i}^{\text{P}}=\emptyset$.

For each bag $B_{i}\in\mathcal{B}$, where $i\in{\sf{V}}(T)$, and each vertex
$v\in B_{i}$, we use $n_{i}(v)$ to denote the number of neighbors of $v$ in
the subgraph $G_{i}-B_{i}$. We derive an algorithm as follows. The algorithm
first guesses the ESW of the desired profile. Note that we need only to
consider at most $2n\cdot(n+1)$ possible values (the utility of every player
has at most $2(n+1)$ possible values and there are $n$ players). For each
guessed value $q$ of the ESW, we solve the problem of determining if
$\mathcal{G}$ admits a profile of ESW at least $q$. This problem can be solved
by the following dynamic programming algorithm running in polynomial time.

For each bag $B_{i}\in\mathcal{B}$, we maintain a binary dynamic table
$\textsf{DT}_{i}(U,f)$, where $U$ runs over all subsets of $B_{i}$ and $f$
runs over all functions $f:B_{i}\rightarrow\mathbb{N}_{0}$ such that $f(u)\leq
n_{i}(u)$ for every $u\in B_{i}$. Each entry ${\textsf{DT}}_{i}(U,f)$ is
supposed to be $1$ if and only if $\mathcal{G}$ admits a profile such that

  1. (1)

among the players in $B_{i}$, exactly those in $U$ invest;

  2. (2)

every $v\in B_{i}$ has exactly $f(v)$ neighbors in $G_{i}-B_{i}$ who invest;
and

  3. (3)

everyone in $B_{i}$ but not in $B_{i}^{\text{P}}$ obtains utility at least
$q$, i.e.,

    1. (3.1)

for every $v\in U\setminus B_{i}^{\text{P}}$, it holds that
$g_{v}(n_{G}[v,U]+f(v))-c(v)\geq q$; and

    2. (3.2)

for every $v\in(B_{i}\setminus U)\setminus B_{i}^{\text{P}}$, it holds that
$g_{v}(n_{G}(v,U)+f(v))\geq q$.

We do not request players in $B_{i}$ who also appear $B_{i}^{\text{P}}$ to
obtain the threshold utility $q$ at the moment because we do not have the
complete information over the number of their neighbors who invest at the
moment. These players will be treated when they leave their corresponding
forget bags. The tables are computed in a bottom-up manner, from those
maintained for the leaf nodes up to that for the root node in $T$. Assume that
$i$ is the currently considered node. We show how to compute
$\textsf{DT}_{i}(U,f)$ as follows. Recall that every leaf bag is empty. So, if
$i$ is a leaf node, the table for $i$ contains only one entry with the two
parameters being an empty set and an empty function. We let this entry contain
the value $1$. Let us assume now that $i$ is not a leaf node. We distinguish
the following cases.

Case: $B_{i}$ is a join bag

Let $x$ and $y$ denote the two children of $i$ in the tree $T$. If $i$ is the
root, or $B_{i}^{\text{P}}$ is a join bag or an introduce bag, we set
${\textsf{DT}}_{i}(U,f)=1$ if and only if
${\textsf{DT}}_{x}(U,f)={\textsf{DT}}_{y}(U,f)=1$. If $B_{i}^{\text{P}}$ is a
forget bag, let $B_{i}\setminus B_{i}^{\text{P}}=\\{v\\}$. Then, we set
${\textsf{DT}}_{i}(U,f)=1$ if and only if
${\textsf{DT}}_{x}(U,f)={\textsf{DT}}_{y}(U,f)=1$ and one of the following
holds:

  * •

$v\in U$ and $g_{v}(n_{G}[v,U]+f(v))-c(v)\geq q$; or

  * •

$v\in B_{i}\setminus U$ and $g_{v}(n_{G}(v,U)+f(v))\geq q$.

Case: $B_{i}$ is an introduce bag

Let $x$ be the child of $i$ in $T$. Let $B_{i}\setminus B_{x}=\\{v\\}$. Note
that $v$ does not have any neighbor in $G_{i}-B_{i}$. Thus, if $f(v)>0$, we
directly set ${\textsf{DT}}_{i}(U,f)$=0. We assume now that $f(v)=0$. We
consider the following cases. First, if $B_{i}^{\text{P}}$ is a join bag or an
introduce bag, then ${\textsf{DT}}_{i}(U,f)=1$ if and only if
${\textsf{DT}}_{x}(U\setminus\\{v\\},f|_{\neg\\{v\\}})=1$. If
$B_{i}^{\text{P}}$ is a forget bag, let $B_{i}\setminus
B_{i}^{\text{P}}=\\{u\\}$. Then, we set ${\textsf{DT}}_{i}(U,f)=1$ if and only
if ${\textsf{DT}}_{x}(U\setminus\\{v\\},f|_{\neg\\{v\\}})=1$ and one of the
following holds (notice that when $u=v$ we have $f(u)=0$):

  * •

$u\in U$ and $g_{u}(n_{G}[u,U]+f(u))-c(u)\geq q$;

  * •

$u\in B_{i}\setminus U$ and $g_{u}(n_{G}(u,U)+f(u))\geq q$.

Case: $B_{i}$ is a forget bag

Let $x$ be the child of $i$ in $T$. Let $B_{x}\setminus B_{i}=\\{v\\}$. If $i$
is the root, or $B_{i}^{\text{P}}$ is a join or an introduce bag, then
${\textsf{DT}}_{i}(U,f)=1$ if and only if there is a
${\textsf{DT}}_{x}(U^{\prime},f^{\prime})=1$ such that $U^{\prime}\cap
B_{i}=U$ and $f^{\prime}|_{\neg\\{v\\}}=f$. If $B_{i}^{\text{P}}$ is a forget
bag, let $B_{i}\setminus B_{i}^{\text{P}}=\\{u\\}$. Then, we set
${\textsf{DT}}_{i}(U,f)=1$ if and only if there is a
${\textsf{DT}}_{x}(U^{\prime},f^{\prime})=1$ such that $U^{\prime}\cap
B_{i}=U$, $f^{\prime}|_{\neg\\{v\\}}=f$ and one of the following conditions
holds:

  * •

$u\in U$ and $g_{u}(n_{G}[u,U]+f(u))-c(u)\geq q$;

  * •

$u\in B_{i}\setminus U$ and $g_{u}(n_{G}(u,U)+f(u))\geq q$.

After computing the values of all tables, we conclude that the game
$\mathcal{G}$ admits a profile with ESW at least $q$ if and only if
${\textsf{DT}}_{r}(\emptyset,\emptyset)=1$ where $r$ is the root of $T$.

To see that the algorithm runs in polynomial time, recall first that, as
described above, the value of each entry in all tables can be computed in
polynomial time. Moreover, there are polynomially many nodes in the tree $T$,
and for each node $i$, the associated table ${\textsf{DT}}_{i}$ contains at
most $2^{\left|B_{i}\right|}\cdot(\max_{u\in
B_{i}}n_{i}(u))^{\left|B_{i}\right|}\leq 2^{p}\cdot n^{p}$ entries. The
running time follows then from the fact that $p$ is a constant.

For the whole algorithm, we first find the maximum possible value $q$ such
that $\mathcal{G}$ admits a profile of ESW at least $q$, then using standard
backtracking technique, a profile with ESW $q$ can be computed in polynomial
time based on the above dynamic programming algorithm. ∎

## References

  * Bodlaender (1993) Bodlaender, H. L. 1993.  A Tourist Guide Through Treewidth.  _Acta Cybern._ 11(1-2): 1–21.
  * Bodlaender (2012) Bodlaender, H. L. 2012.  Fixed-Parameter Tractability of Treewidth and Pathwidth.  _The Multivariate Algorithmic Revolution and Beyond_ , 196–227.
  * Bodlaender et al. (2016) Bodlaender, H. L.; Drange, P. G.; Dregi, M. S.; Fomin, F. V.; Lokshtanov, D.; and Pilipczuk, M. 2016.  A $c^{k}n$ 5-Approximation Algorithm for Treewidth.  _SIAM J. Comput._ 45(2): 317–378.
  * Bodlaender and Kloks (1991) Bodlaender, H. L.; and Kloks, T. 1991.  Better Algorithms for the Pathwidth and Treewidth of Graphs.  _ICALP_ , 544–555.
  * Bramoullé and Kranton (2007) Bramoullé, Y.; and Kranton, R. 2007.  Public Goods in Networks.  _J. Econ. Theory_ 135(1): 478–494.
  * Broersma, Golovach, and Patel (2013) Broersma, H.; Golovach, P. A.; and Patel, V. 2013.  Tight Complexity Bounds for FPT Subgraph Problems Parameterized by the Clique-Width.  _Theor. Comput. Sci._ 485: 69–84.
  * Carpenter (2002) Carpenter, J. P. 2002.  Information, Fairness, and Reciprocity in the Best Shot Game.  _Econom. Lett._ 75(2): 243–248.
  * Cheah and Corneil (1990) Cheah, F.; and Corneil, D. G. 1990.  The Complexity of Regular Subgraph Recognition.  _Discret. Appl. Math._ 27(1-2): 59–68.
  * Dom et al. (2006) Dom, M.; Guo, J.; Hüffner, F.; and Niedermeier, R. 2006.  Error Compensation in Leaf Power Problems.  _Algorithmica_ 44(4): 363–381.
  * Dom et al. (2008) Dom, M.; Guo, J.; Hüffner, F.; and Niedermeier, R. 2008.  Closest 4-Leaf Power is Fixed-Parameter Tractable.  _Discret. Appl. Math._ 156(18): 3345–3361.
  * Elkind, Goldberg, and Goldberg (2006) Elkind, E.; Goldberg, L. A.; and Goldberg, P. W. 2006.  Nash Equilibria in Graphical Games on Trees Revisited.  _ACM-EC_ , 100–109.
  * Garey and Johnson (1979) Garey, M.; and Johnson, D. 1979.  _Computers and Intractability: A Guide to the Theory of NP-Completeness_.  New York: W. H. Freeman.
  * Guo (2009) Guo, J. 2009.  A More Effective Linear Kernelization for Cluster Editing.  _Theor. Comput. Sci._ 410(8-10): 718–726.
  * Harrison and Hirshleifer (1989) Harrison, G. W.; and Hirshleifer, J. 1989.  An Experimental Evaluation of Weakest Link/Best Shot Models of Public Goods.  _J. Polit. Econ._ 97(1): 201–225.
  * Hudry (2004) Hudry, O. 2004.  A Note on “Banks Winners in Tournaments are Difficult to Recognize” by G. J. Woeginger.  _Soc. Choice Welfare_ 23(1): 113–114.
  * Karp (1972) Karp, R. M. 1972.  Reducibility Among Combinatorial Problems.  _Complexity of Computer Computations_ , 85–103.
  * Kearns, Littman, and Singh (2001) Kearns, M. J.; Littman, M. L.; and Singh, S. P. 2001.  Graphical Models for Game Theory.  253–260.
  * Kloks (1994) Kloks, T. 1994.  _Treewidth, Computations and Approximations_ , volume 842 of _Lecture Notes in Computer Science_.  Springer.
  * Levit et al. (2018) Levit, V.; Komarovsky, Z.; Grinshpoun, T.; and Meisels, A. 2018.  Incentive-based Search for Efficient Equilibria of the Public Goods Game.  _Artif. Intell._ 262: 142–162.
  * Lin, Jiang, and Kearney (2000) Lin, G.; Jiang, T.; and Kearney, P. E. 2000.  Phylogenetic _k_ -Root and Steiner _k_ -Root.  _ISAAC_ , 539–551.
  * Manshadi and Johari (2009) Manshadi, V. H.; and Johari, R. 2009.  Supermodular Network Games.  _ALLERTON_ , 1369–1376.
  * Robertson and Seymour (1986) Robertson, N.; and Seymour, P. D. 1986.  Graph Minors. II. Algorithmic Aspects of Tree-Width.  _J. Algorithms_ 7(3): 309–322.
  * Tovey (2002) Tovey, C. A. 2002.  Tutorial on Computational Complexity.  _Interfaces_ 32(3): 30–61.
  * van der Zanden and Bodlaender (2017) van der Zanden, T. C.; and Bodlaender, H. L. 2017.  Computing Treewidth on the GPU.  _IPEC_ , 29:1–29:13.
  * West (2000) West, D. B. 2000.  _Introduction to Graph Theory_.  Prentice-Hall.
  * Yu et al. (2020) Yu, S.; Zhou, K.; Brantingham, P. J.; and Vorobeychik, Y. 2020.  Computing Equilibria in Binary Networked Public Goods Games.  _AAAI_ , 2310–2317.