ifaamas doi 2020 2020 [AAMAS’20]Proc. of the 19th International Conference on
Autonomous Agents and Multiagent Systems (AAMAS 2020), B. An, N. Yorke-Smith,
A. El Fallah Seghrouchni, G. Sukthankar (eds.)May 2020Auckland, New Zealand
University of Southern California Washington University in St. Louis
Washington University in St. Louis

# Inducing Equilibria in Networked Public Goods Games through Network
Structure Modification

David Kempe<EMAIL_ADDRESS>,  Sixie Yu<EMAIL_ADDRESS>and
Yevgeniy Vorobeychik<EMAIL_ADDRESS>
###### Abstract.

Networked public goods games model scenarios in which self-interested agents
decide whether or how much to invest in an action that benefits not only
themselves, but also their network neighbors. Examples include vaccination,
security investment, and crime reporting. While every agent’s utility is
increasing in their neighbors’ joint investment, the specific form can vary
widely depending on the scenario. A principal, such as a policymaker, may wish
to induce large investment from the agents. Besides direct incentives, an
important lever here is the network structure itself: by adding and removing
edges, for example, through community meetings, the principal can change the
nature of the utility functions, resulting in different, and perhaps socially
preferable, equilibrium outcomes. We initiate an algorithmic study of targeted
network modifications with the goal of inducing equilibria of a particular
form. We study this question for a variety of equilibrium forms (induce all
agents to invest, at least a given set $S$, exactly a given set $S$, at least
$k$ agents), and for a variety of utility functions. While we show that the
problem is NP-complete for a number of these scenarios, we exhibit a broad
array of scenarios in which the problem can be solved in polynomial time by
non-trivial reductions to (minimum-cost) matching problems.

##  1\. Introduction

Groups of individuals often encounter the following type of scenario. Each
member of the group can decide whether or how much effort (or money) to invest
for the common good; everyone in the group (including the individual) profits
from all members’ efforts, but the individual incurs a cost for the
investment. Examples of such scenarios include decisions whether or not to
vaccinate, report crime in a neighborhood, invest in security, chip in on
department committee work, keep one’s yard representable or sidewalk shoveled,
or purchase a tool that one’s friends or neighbors can share.

These and many other scenarios are modeled by _public goods games_ Samuelson
(1954); Mas-Collel et al. (1995). In many applications, including most of the
ones listed above, the benefits of an individual’s effort are not reaped by
all group members, but only by those with whom the individual interacts. This
naturally motivates the definition of _networked public goods games_ Bramoullé
and Kranton (2007); Bramoullé et al. (2014); Feldman et al. (2013), in which a
(given, known) network captures which individuals will benefit from which
other individuals’ efforts.

In networked public goods games, an agent’s utility depends on (1) her111For
clarity, we will always refer to agents using female pronouns, and the
principal using male pronouns. own investment decision, which incurs some cost
(in terms of money, time, effort, or risk), and (2) the aggregate investment
by the agent and her neighbors in the network. (Precise definitions of all
concepts are given in Section 2.) While the agent’s utility is always non-
decreasing in the neighbors’ joint investment, the specific functional form
can vary widely. For example, it may suffice to have a single friend with a
useful tool, but lowering crime rates in a neighborhood may require broad
participation in crime reporting.

For practically all public goods scenarios, the equilibria involve significant
underinvestment. That is, significantly fewer agents expend effort than would
lead to a socially optimal outcome, a phenomenon closely related to the so-
called “Tragedy of the Commons” and the “Bystander Effect.” This kind of
underinvestment is not only predicted by theory, but typically observed in
practice as well. When the equilibrium outcomes are socially undesirable, a
principal, such as a policymaker, may be interested in changing the parameters
of the game so as to induce equilibrium outcomes that are better aligned with
the social interest. A natural and traditional approach is to change the cost
structure, by rewarding investment (decreasing investment costs) or punishing
failure to invest (increasing the cost of non-investment). For many of the
scenarios listed above, monetary fines, other types of penalties, or social
pressure implement such rewards or punishments. Generally, the design of cost
or reward structures and rules of encounter is at the heart of work in
mechanism and market design Nisan et al. (2007).

In graphical games, such as the networked public goods game, however, there is
an additional important parameter that may be subject to modification: the
network structure itself. For example, to facilitate crime prevention, the
principal may organize community meetings in particular neighborhoods,
increasing the density of the social network among the community members. The
principal may also add individual links, for example, by introducing
individuals to one another, or weaken relationships (remove links) by adding
hurdles to specific interactions (e.g., if the public goods game represents
strategic interactions in a criminal organization, and law enforcement chooses
which relationships to monitor).

We initiate an algorithmic study of targeted network structure modifications
in networked public goods games with binary actions, with the goal of inducing
pure strategy Nash equilibria (PSNE) with desirable properties. We will
consider a principal who is aiming for “high investment.” Each edge has a cost
for addition/removal, and to induce a desirable equilibrium of the game, the
principal can add/remove edges from the network, subject to an upper bound on
the total cost.

Naturally, there are different concrete ways of capturing the goal of “high
investment,” and we consider the following four natural candidate properties
which the target equilibrium should satisfy: (1) all agents invest, (2)
exactly a given subset $S$ of agents invest, (3) at least the agents in a
given subset $S$ invest, and (4) at least $r$ agents invest. We study each of
these objectives for games with a variety of utility functions, ranging from
general monotone functions to generalized sigmoid functions, as well as convex
and concave functions. While we show (in Section 3) that the problem is NP-
complete for several of these scenarios, we exhibit (in Section 4) a broad
array of settings in which it can be solved in polynomial time by non-trivial
reductions to minimum-cost matching problems. Both the hardness and
algorithmic results are established by showing equivalence between our problem
and the problem of modifying an input graph $G$ such that each node $i$ ends
up with its degree in a prescribed set $D_{i}$. Modifying graphs to achieve
prescribed node degrees is a problem with an extensive line of work (discussed
in detail below), and our results provide a significant generalization of
prior algorithmic results. The full summary of our main results is presented
in Table 1.

| all | $=S$ | $\supseteq S$ | $\geq r$
---|---|---|---|---
general | hard | hard | hard | hard
sigmoid | poly | poly | hard | hard
convex | poly | poly | hard | hard
concave | poly | poly | hard | hard
Table 1. An overview of our results.

For all entries of the table marked “poly,” our algorithms handle fully
general edge cost structures. On the other hand, all of the hardness proofs
apply already in very restrictive cases, allowing only one of addition and
removal, and either allowing unlimited changes of the allowed type, or simply
restricting the total _number_ of added/removed edges.

Related Work:  Our work is conceptually connected to three broad threads in
the literature: graphical games, mechanism and market design, and network
design. Graphical models of games capture various forms of structure in the
players’ utility functions which limit the scope of utility dependence on
other players’ actions Shoham and Leyton-Brown (2009). An important class of
these are _graphical games_ , where a player’s utility only depends on the
actions of her network neighbors Kearns et al. (2001). Networked public goods
games are one important example of graphical games, with utilities only
depending on the investment choices by a player’s network neighbors Bramoullé
and Kranton (2007); Galeotti et al. (2010); Levit et al. (2018). Bramoullé and
Kranton Bramoullé and Kranton (2007) studied the effects of network structure
modification on a public goods game. Our results, however, are novel in
several respects. First, they assumed that only a single edge is added to the
underlying network and studied how the addition affects welfare. In contrast,
we consider addition and deletion of sets of edges, and focus on the
algorithmic aspects of the problem. Moreover, Bramoullé and Kranton only
consider strictly concave utility functions, whereas we study convex, concave,
and general sigmoid utility functions. (Detailed definitions are in Section
2.) Galeotti et al. Galeotti et al. (2010) also considered the effects of
modifying the underlying network of a public goods game on equilibrium
behavior and welfare. However, their analysis is restricted to convex or
concave utilities which are degree symmetric (i.e., if two nodes have the same
degree, they must have the same utility function), involves incomplete
information of players about the network, and does not consider the associated
algorithmic problem. In contrast, we focus on algorithmic questions and allow
heterogeneous utilities. Yu et al. Yu et al. (2020) studied algorithmic
aspects of binary public goods games. They showed that in general, checking
the existence of a pure-strategy Nash equilibrim is NP-complete, and also
identified tractable cases based on restrictions of either the utility
functions or the underlying network structure. However, they did not consider
modifying the network structure to induce certain Nash equilibria. Grossklags
et al. Grossklags et al. (2008) studied how economic agents invest in security
through the lens of public goods games. The value of the public goods is the
overall protection level. Each agent has two options: investing in self-
protection, or investing in self-insurance. The former affects the overall
protection level, as well as the loss incurred by the agent, while the latter
only affects the agent’s own loss. They analyzed the Nash equilibria under
five economic settings, which characterize different threat models.

Mechanism and market design (e.g., Nisan et al. (2007)) also aim to change the
parameters of a game to induce equilibrium outcomes favored by a principal.
However, the specific ways in which the game’s parameters are changed are
vastly different; key approaches include the design of market structure, such
as matching market mechanisms Haeringer (2018), payments, as in traditional
mechanism design Nisan et al. (2007), or the structure of information
available to the players Dughmi (2017).

Another relevant line of research is network design. The idea of altering a
(social) network in order to induce certain outcomes is present in a number of
recent works, for a variety of different outcomes. Sheldon et al. Sheldon et
al. (2010) aim to modify the network so as to maximize the spread of cascades,
while Chen et al. (2016); Ghosh and Boyd (2006); Tong et al. (2012) aim to
alter the spectral gap of the network to make it more or less connected. Along
similar lines, Bredereck and Elkind Bredereck and Elkind (2017) considered the
converging state of simple information diffusion dynamics, with a specific
focus on how the removal of edges can be used to manipulate the majority
opinion in such outcomes. Similar ideas arise in a recent line of work (e.g.,
Sina et al. (2015); Matteo Castiglioni (2020) and the references therein)
studying how the outcome of an election can be manipulated by altering network
structures. In a sense, the converse problem is studied by Amelkin and Singh
Amelkin and Singh (2019), who aim to reduce opinion control by recommending
(i.e., adding) links to social network users. Similar ideas are present in the
work of Garimella et al. Garimella et al. (2018), who aim to decrease opinion
polarization by connecting pairs of individuals with differing opinions. Sless
et al. Sless et al. (2014) investigated the problem of coalition formation
through adding links to the underlying social network. All of these works
share the high-level goal of inducing (socially) preferable equilibrium
behavior, but the specific optimization goals, and with them the algorithmic
approaches, are vastly different.

An analysis of connections between equilibrium outcomes of games and network
structure was carried out by Bramoullé et al. Bramoullé et al. (2014). They
found that the smallest eigenvalue $\lambda_{\min}$ of the network’s adjacency
matrix is a key quantity for equilibria; recall that spectral properties also
play a role in several of the other related papers discussed above. Bramoullé
et al. also considered the effects of network structure modification; in
particular, they investigated how the addition of edges affects
$\lambda_{\min}$, which in turn provides a qualitative understanding of the
effects of edge additions on equilibria. However, they did not investigate the
algorithmic issues involved. Milchtaich Milchtaich (2015) studied equilibrium
existence as a function of network topology in weighted network congestion
games.

Most directly relevant is a line of work on editing graphs to satisfy degree
constraints; many variants of this problem have been extensively studied.
Perhaps the most basic question is whether a given graph $G$ has an
$r$-regular subgraph. This problem was proved NP-complete, even for $r=3$, by
Chvátal (see Page 198 of (Garey and Johnson, 1979)); Stewart (1994) extended
the NP-completeness result to the case when the input graph $G$ is planar.
Yannakakis (1978) proved a general NP-hardness result for node/edge deletion
problems; this result implies, as special cases, that minimizing the number of
deleted nodes such that the resulting graph has maximum degree at most $r$ is
NP-hard, and similarly, that minimizing the number of deleted edges such that
the resulting graph has maximum degree at most $r$ _and is connected_ is NP-
hard.

When the goal is to achieve $r$-regularity alone (with no connectivity
requirements) with edge deletions only, the problem has long been known to be
polynomial-time solvable. Specifically, the $r$-factor problem asks whether we
can delete edges from a graph such that each node in the resulting subgraph
has degree exactly $r$. This problem can be solved in polynomial time by a
reduction to the Perfect Matching problem Tutte (1954). In fact, the reduction
introduced in Tutte (1954) applies to the more general $f$-factor problem, in
which a target degree $f_{i}$ is specified for each node $i$.

Lovász (1970, 1972) generalizes the result further, defining the General
Factor problem, which is closely related to the problem we reduce to. In the
General Factor problem, for each node $i$, a set $D_{i}$ of target degrees is
given, and the question is whether the graph contains a subgraph in which each
node has degree in $D_{i}$.222Lovász (1970, 1972) also studies the smallest
total deviation of node degrees from the sets $D_{i}$ that can be achieved by
any subgraph, which is not directly relevant to our work. Lovász (1970)
characterized the positive instances when all of the $D_{i}$ are intervals; an
algorithm can be extracted from this characterization, as noted in (Lovász,
1972). A more explicitly algorithmic proof was given by Anstee (1985), who
gave a reduction to a matching problem, similar to our approach here. Lovász
(1972) generalizes the results from (Lovász, 1970), giving a characterization
when each $D_{i}$ has gaps of length at most 1; i.e., when $x,y\in D_{i}$, no
two consecutive numbers in $\\{x,x+1,\ldots,y\\}$ can be missing. However,
this generalized characterization is not algorithmic. An efficient algorithm
for this generalization was obtained by Cornuéjols (1988). When the $D_{i}$
can have gaps of length 2 or more, the problem is NP-complete in general; this
was outlined in (Lovász, 1972) with a reduction from 3-Colorability and made
more explicit by Cornuéjols (1988).

The tractable cases we present in Section 4 are closely related to the General
Factor problem when the $D_{i}$ are intervals. However, we allow not just for
the deletion, but also for the _addition_ of edges. For the General Factor
problem, it is natural to consider only deletions, because we are looking for
subgraphs with a certain property. For the problem of actively modifying a
network, however, the addition of edges is equally relevant, and the
combination of both adds more complexity, and requires a more complex
reduction than, e.g., the one in (Anstee, 1985).

Given the NP-hardness of editing graphs (in particular, through node
deletions), one possible approach is to show fixed-parameter tractability in
terms of some of the problem’s parameters. Indeed, the parameterized
complexity of editing graphs to satisfy certain degree constraints has been
studied in a somewhat more recent line of work; see Golovach and Mertzios
(2017); Mathieson and Szeider (2012) and the references therein. Most of this
line of work is based on the model in which both vertices and edges can be
deleted (and edges added). As we saw above, the ability to delete vertices
makes the problem NP-hard even when the degree constraints are singletons,
i.e., a target degree is given for each node; indeed, this is the setting
studied in these papers. The parameter of interest, called $k$, is the total
number of changes (deletions and additions) the algorithm is allowed to
perform, and the preceding papers obtain algorithms with running time
$f(k)\cdot\mbox{poly}(n)$.

##  2\. Model

###  2.1. Binary Networked Public Goods Game

A _binary networked public goods (BNPG)_ game is characterized by the
following:

  1. (1)

A simple, undirected and loop-free graph $G=(V,E)$ whose nodes
$V=\\{1,2,\ldots,n\\}$ are the agents/players, and whose edges $E=\\{(i,j)\mid
i,j\in V\\}$ represent the interdependencies among the players’ payoffs.

  2. (2)

A binary strategy space $\\{0,1\\}$ for each player $i$. Choosing strategy 1
corresponds to _investing_ in a public good, while choosing 0 captures non-
investment. We use $x_{i}$ to denote the action chosen by player $i$, and
$\bm{x}=(x_{1},x_{2},\ldots,x_{m})$ for the joint pure strategy profile of all
players.

  3. (3)

For each player $i$, a non-decreasing utility function $U_{i}(\bm{x})$.

As is standard in the literature on networked public goods Bramoullé and
Kranton (2007), we assume that each player’s utility depends only on (1) her
own investment (for which she incurs a cost), and (2) the joint investment of
herself and her neighbors in the network, which provides her with a positive
externality. Formally, we capture this as follows. Let
$\mathcal{N}_{i}^{(G)}=\\{j\mid(j,i)\in E\\}$ be the set of neighbors of $i$
in the graph $G$; then, we can define
$n_{i}^{(G,\bm{x})}=\sum_{j\in\mathcal{N}_{i}^{(G)}}x_{j}$ to be the number of
$i$’s neighbors who invest under $\bm{x}$. When $G,\bm{x}$ are clear from the
context, we will omit them from this notation. We assume that each player
$i$’s utility function is of the following form:

$\displaystyle U_{i}(\bm{x})$
$\displaystyle=U_{i}(x_{i},n_{i}^{(\bm{x})})\;=\;g_{i}(x_{i}+n_{i}^{(\bm{x})})-c_{i}x_{i}.$
(1)

The second term ($-c_{i}x_{i}$) simply captures the cost that $i$ incurs from
investing herself. Each $g_{i}$ is a non-negative and non-decreasing function
(a standard assumption in the public goods games literature), capturing the
positive externality that $i$ experiences from her neighbors’ (and her own)
investments. In many scenarios, $g_{i}$ will have additional properties, such
as being concave or convex, and we discuss such properties in Section 2.3.
Observe that each function $g_{i}$ can be represented using $O(n)$ values, so
the entire BNPG game (including the graph structure) can be represented using
$O(n^{2})$ values.

We are interested in inducing particular pure strategy Nash Equilibria of the
game by modifying the network structure. Pure strategy Nash Equilibria are
defined as follows:

######  Definition .

In a BNPG game, a _pure strategy Nash Equilibrium (PSNE)_ is an action profile
$\bm{x}\in\\{0,1\\}^{n}$ satisfying
$U_{i}(x_{i},n_{i}^{(\bm{x})})>U_{i}(1-x_{i},n_{i}^{(\bm{x})})$, or
$U_{i}(x_{i},n_{i}^{(\bm{x})})=U_{i}(1-x_{i},n_{i}^{(\bm{x})})$ and $x_{i}=1$,
for every player $i$. Thus, we are assuming that each player in equilibrium
always breaks ties in favor of investing.

A given BNPG game may have multiple equilibria. We will be interested in
modifying the graph $G$ to ensure that at least one element of a given set
$\mathcal{X}$ is a PSNE. For notational convenience, we interpret
$\mathcal{X}$ both as a set of strategy vectors $\bm{x}\in\\{0,1\\}^{n}$ and
as the subset of investing players $S(\bm{x}):=\\{i\mid x_{i}=1\\}$, whichever
is notationally more convenient. We are interested in the following classes of
PSNE:

all::

Every player invests, i.e., $\mathcal{X}=\\{\\{1,2,\ldots,n\\}\\}$.

$\bm{=S}$::

Exactly a given set $S$ of players invests (and the other players do not),
i.e., $\mathcal{X}=\\{S\\}$. All players investing is the special case
$S=\\{1,\ldots,n\\}$.

$\bm{\supseteq S}$::

_At least_ the set $S$ of players invests; other players may also invest.
Here, $\mathcal{X}=\\{T\mid T\supseteq S\\}$.

$\bm{\geq r}$::

At least $r$ players invest. Here, $\mathcal{X}=\\{T\mid|T|\geq r\\}$.

In general, even without the ability to modify $G$, deciding if a BNPG has an
equilibrium in $\mathcal{X}$ is NP-hard. This can be seen most directly with
the following example (see also Section 3.2 of Bramoullé and Kranton (2007)):
Each cost is $c_{i}=1$, and each $g_{i}(z)=2$ if $z\geq 1$, and $g_{i}(0)=0$.
Then, the PSNE are exactly the strategy profiles $\bm{x}$ in which independent
sets of $G$ invest. Therefore, if $\mathcal{X}$ is the set of all profiles in
which at least $r$ players invest (for given $r$), the problem of deciding if
the game has a PSNE in $\mathcal{X}$ is equivalent to the Independent Set
problem.

###  2.2. Network Modifications

The main modeling contribution of our work is to assume that a principal can
modify the network $G$ (subject to a budget) with the goal of inducing
equilibria from a class $\mathcal{X}$. Formally, an input graph
$G^{\prime}=(V,E^{\prime})$ on the agents is given. Each node pair $(i,j)$ has
an associated cost $\gamma_{(i,j)}=\gamma_{(j,i)}\geq 0$. When $(i,j)\in
E^{\prime}$, this is the cost for removing the edge $(i,j)$ from $G^{\prime}$,
while for $(i,j)\notin E^{\prime}$, it is the cost for adding the edge $(i,j)$
to $G^{\prime}$. When the principal produces a graph $G=(V,E)$, the cost of
doing so is $\sum_{e\in E\triangle E^{\prime}}\gamma_{e}=\sum_{e\in E\setminus
E^{\prime}}\gamma_{e}+\sum_{e\in E^{\prime}\setminus E}\gamma_{e}$. The
principal is given a budget $B$ not to be exceeded. The goal is to solve the
following problem:

######  Definition  (Network Design for BNPG).

Given a BNPG instance, edge costs $\gamma_{e}$, desired PSNE class
$\mathcal{X}$, and budget $B$, find an edge set $E$ with $\sum_{e\in
E\triangle E^{\prime}}\gamma_{e}\leq B$ such that the BNPG game on $(V,E)$ has
at least one PSNE in $\mathcal{X}$.

The general costs $\gamma_{(i,j)}$ admit many natural special cases: by
setting $\gamma_{(i,j)}=\infty$ for $(i,j)\in E^{\prime}$ (or for $(i,j)\notin
E^{\prime}$), we can prohibit the removal (or addition) of edges. By setting
$\gamma_{(i,j)}=0$, we can allow unlimited removal (or addition) of edges. And
by setting $\gamma_{(i,j)}=1$, we can simply restrict the number of edges
removed/added.

###  2.3. Utility Functions and Induced Degrees

In the fully general version of the model, the $g_{i}$ can be arbitrary non-
decreasing functions. We will show that at this level of generality, the
Network Design problem is NP-hard for all four classes of PSNE we consider
(Theorem 3). In most scenarios, $g_{i}$ will have additional properties. Among
the most common of these are:

Concavity:

When $g_{i}$ is concave, the returns for additional investments of neighbors
are diminishing. The incentive structures in binary _best-shot games_ Galeotti
et al. (2010) can be captured by concave $g_{i}$.

Convexity:

When $g_{i}$ is convex, the returns for additional investments of neighbors
are increasing.

Sigmoid:

For many natural scenarios, such as the adoption of innovations Zhang et al.
(2016), the $g_{i}$ are neither concave nor convex on their entire domain.
Instead, $g_{i}$ begins convex, with increasing returns to more investors, but
eventually reaches saturation and diminishing returns.

We call such a function $g_{i}$ a _(generalized) sigmoid function_ 333There
are several definitions for the term sigmoid function, requiring various
normalizations, smoothness properties, or even specific functional forms
(e.g., logistic). Here, we use the term in the very broad sense. if there
exists some $\hat{z}$ such that $g_{i}(z)$ is convex on $\\{z\mid
z\leq\hat{z}\\}$ and concave on $\\{z\mid z\geq\hat{z}\\}$. Note that sigmoid
functions subsume both concave functions (with $\hat{z}=-\infty$) and convex
functions (with $\hat{z}=\infty$).

The first useful observation is that we can capture all the relevant
information about an agent $i$’s utility function using the set of numbers of
investing neighbors that would make $i$ invest. We call such sets _investment
degree sets_ 444Lovász (1970, 1972) and subsequent work call these sets a
_prescription_. We deviate from this nomenclature since we consider the
addition of edges as well., and denote them by $D_{i}$. When $g_{i}$ is
convex/concave/sigmoid, the investment degree sets have particularly nice
forms, captured by the following lemma:

###### Lemma

For every non-decreasing function $g_{i}:[0,n-1]\rightarrow{}_{+}$ and cost
$c_{i}$, there exists a unique set $D_{i}\subseteq\\{0,1,\ldots,n-1\\}$ such
that $x_{i}=1$ is a best response to $n_{i}$ if and only if $n_{i}\in D_{i}$.
Furthermore,

  1. (1)

When $g_{i}$ is concave, $D_{i}$ is a downward-closed interval.

  2. (2)

When $g_{i}$ is convex, $D_{i}$ is an upward-closed interval.

  3. (3)

When $g_{i}$ is sigmoid, $D_{i}$ is an interval.

Conversely, for every set $D_{i}\subseteq\\{0,1,\ldots,n-1\\}$, there exists a
non-decreasing function $g_{i}:[0,n-1]\rightarrow{}_{+}$ and cost $c_{i}$ such
that $x_{i}=1$ is a best response to $n_{i}$ if and only if $n_{i}\in D_{i}$.
Furthermore,

  1. (1)

When $D_{i}$ is a downward-closed interval, there exists such a $g_{i}$ which
is concave.

  2. (2)

When $D_{i}$ is an upward-closed interval, there exists such a $g_{i}$ which
is convex.

  3. (3)

When $D_{i}$ is an interval, there exists such a $g_{i}$ which is sigmoid.

###### Proof.

We write $\Delta g_{i}(z)=g_{i}(z+1)-g_{i}(z)$ for the discrete derivative. By
definition of best responses (recall our tie breaking rule), a player $i$
invests if and only if $U_{i}(1,n_{i})\geq U_{i}(0,n_{i})$, which is
equivalent to

$\displaystyle\Delta g_{i}(n_{i})$ $\displaystyle\geq c_{i}.$ (2)

Thus, letting $D_{i}=\\{z\mid\Delta g_{i}(z)\geq c_{i}\\}$, we obtain that
$x_{i}=1$ is the best response to $z$ iff $z\in D_{i}$, proving the first
claim. We now consider the three special cases:

  1. (1)

When $g_{i}$ is concave, $\Delta g_{i}$ is non-increasing. Therefore, whenever
$\Delta g_{i}(z)\geq c_{i}$, we also have $\Delta g_{i}(z-1)\geq c_{i}$,
meaning that $D_{i}$ is downward closed.

  2. (2)

When $g_{i}$ is convex, $\Delta g_{i}$ is non-decreasing. The rest of the
argument is exactly as for the concave case.

  3. (3)

When $g_{i}$ is sigmoid, $\Delta g_{i}$ is non-decreasing on $[0,\hat{z}]$ and
non-increasing on $[\hat{z},n-1]$, with the maximum attained at $\hat{z}$.
Therefore, $D_{i}$ is an interval.

For the converse, given a set $D_{i}$, define a discrete derivative of $\Delta
g_{i}(z)=2$ if $z\in D_{i}$, and $\Delta g_{i}(z)=0$ if $z\notin D_{i}$.
Normalizing with $g_{i}(0)=0$, and setting $c_{i}=1$, player $i$ will invest
iff $z\in D_{i}$. If $D_{i}$ is an interval, then $g_{i}$ will start out as
the constant 0, have slope 2 over the interval, and then become flat at the
end of the interval. Thus, $g_{i}$ is a sigmoid. If the interval is downward-
closed, then the function is concave; if it is upward-closed, the function is
convex. ∎

The characterization of Lemma 2.3 makes precise our intuition behind
considering concave/convex $g_{i}$. It shows that when $g_{i}$ is concave,
then the _fewer_ neighbors invest, the more $i$ is prone to invest. On the
other hand, when $g_{i}$ is convex, then the _more_ neighbors invest, the more
$i$ is prone to invest. The primary benefit of Lemma 2.3 is that the Network
Design problem can now be considered solely in terms of $D_{i}$ and induced
numbers of investing neighbors, rather than utility functions, simplifying the
arguments below.

######  Definition  (Network Design for Degree Sets (NDDS)).

The problem $\textsc{NDDS}\,(\text{$\mathcal{P}$},\mathcal{X})$ is defined as
follows: Given a graph $G^{\prime}=(V,E^{\prime})$, investment degree sets
$D_{i}$ for all players $i$ consistent with a function property $\mathcal{P}$
(such as convexity, concavity, sigmoid, or general), edge costs $\gamma_{e}$,
desired PSNE class $\mathcal{X}$, and budget $B$, find an edge set $E$ with
$\sum_{e\in E\triangle E^{\prime}}\gamma_{e}\leq B$ such that there exists a
set $I\in\mathcal{X}$ of investing players with

$\displaystyle|\mathcal{N}_{i}^{(G)}\cap I|$ $\displaystyle\in
D_{i}\qquad\text{ for all }i\in I,$ $\displaystyle|\mathcal{N}_{i}^{(G)}\cap
I|$ $\displaystyle\notin D_{i}\qquad\text{ for all }i\notin I.$

Here, $G=(V,E)$ is the modified graph.

Because the investment degree sets $D_{i}$ can be efficiently constructed from
the $g_{i}$ and $c_{i}$ and vice versa, an algorithmic solution or a hardness
result for the $\textsc{NDDS}\,(\text{$\mathcal{P}$},\mathcal{X})$ problem
immediately yields the same result for the corresponding Network Design
problem from Definition 2.2, and vice versa.

##  3\. Hardness Results

In this section, we prove the hardness results from Table 1. Hardness arises
in different ways for different cases, and we treat them separately. For all
versions, the problem is obviously in NP: a set $I$ of investing agents forms
a polynomial-sized witness, and it is easy to verify that (1) for each agent
in $I$, investing is a best response, and (2) $I\in\mathcal{X}$.

####  $\textsc{NDDS}\,(\text{convex/concave},\geq r)$

When the goal is to get at least $r$ agents to invest, NP-hardness follows
from the discussion in Section 2.1. Even when all edge costs
$\gamma_{(i,j)}=\infty$, i.e., the principal cannot add or remove any edges,
it is NP-hard to decide whether the BNPG has an equilibrium in which at least
$r$ agents invest.

####  $\textsc{NDDS}\,(\text{concave},\supseteq S)$

When the goal is to get a superset of a given set $S$ of agents to invest, it
is NP-hard to decide whether a suitable equilibrium exists. Since concave
functions are a special case of sigmoid functions, this result implies the
hardness result for sigmoid functions as well.

$\textsc{NDDS}\,(\text{concave},\supseteq S)$ is NP-hard.

###### Proof.

The reduction is from Independent Set. Given a graph $H=(V_{H},E_{H})$ and an
integer $k$, the problem is to decide if $H$ contains an independent set of
size (at least) $k$, i.e., a set $T\subseteq V_{H}$ such that no pair in $T$
is connected by an edge. For the reduction, we add two nodes $u,\hat{u}$. $u$
has an edge to $\hat{u}$ as well as to all nodes in $V_{H}$; no other edges
are added to $E_{H}$. The degree sets are $D_{v}=0$ for all $v\in
V_{H}\cup\\{\hat{u}\\}$, $D_{u}=\\{0,1,\ldots,k\\}$, and $S=\\{\hat{u}\\}$. We
set all edge addition/removal costs to $\infty$.

If $H$ has an independent set $T$ of size at least $k$ (without loss of
generality, $T$ is inclusion-wise maximal), then setting
$I=T\cup\\{\hat{u}\\}$ gives us a superset of $S$. No $v\in I$ has a neighbor
in $I$, so all of them invest. Each $v\in V_{H}\setminus I$ has at least one
neighbor in $I$, so none of them invest. Finally, $u$ has at least $k+1$
neighbors in $I$, so $u$ does not invest.

Conversely, if a superset $I\supseteq S=\\{\hat{u}\\}$ invests, then $u\notin
I$. Therefore, $u$ must have at least $k+1$ neighbors in $I$; in particular,
$u$ has at least $k$ neighbors in $V_{H}$. Because all of those neighbors are
in $I$, their degrees within $I$ must be $0$, so they must form an independent
set of size at least $k$. This completes the proof of NP-hardness. ∎

####  $\textsc{NDDS}\,(\text{general},\text{all})$

For fully general functions $g_{i}$, even the “easiest” goal — getting _all_
agents to invest — is NP-hard. This immediately implies NP-hardness of the
other cases (getting exactly or at least a subset $S$ or at least $r$ agents
to invest), since their special cases $S=V$ or $r=n$ are hard.

NP-hardness follows from the NP-hardness of the General Factor problem,
established formally by Cornuéjols (1988) (and outlined by Lovász (1972)).
Cornuéjols (1988, Page 2) showed the following result:

Given an undirected graph555Cornuéjols (1988) shows the hardness result to
hold even when $G$ is planar, bipartite, and all nodes have degree 2 or 3. $G$
and sets $D_{i}$ for all nodes $i$, it is NP-hard to decide if $G$ has a
subgraph in which each node $i$ has degree in $D_{i}$.

It is easy to see that the General Factor problem is a special case of our
NDDS problem, by setting $\gamma_{e}=0$ for all edges $e$ in the input graph
$G$ (i.e., allowing arbitrary edge deletions), and setting $\gamma_{e}=\infty$
for all edges $e$ not in the input graph. We therefore obtain as a corollary
of Theorem 3.

$\textsc{NDDS}\,(\text{general},\text{all})$ is NP-hard, even when the cost of
edge removals is 0 and no edges can be added.666Due to the specificity of the
result of Cornuéjols (1988), NP-hardness continues to hold even when the input
graphs are restricted to be planar and bipartite with all nodes having degree
2 or 3.

In the conference version of this paper — which was written prior to us
learning about the work on the General Factor problem (in particular, (Lovász,
1972) and (Cornuéjols, 1988)) — we included a self-contained proof of Theorem
3, via a reduction from Vertex Cover. For completeness, we include this proof
in the appendix.

####  $\textsc{NDDS}\,(\text{convex},\supseteq S)$

Finally, we show that $\textsc{NDDS}\,(\text{convex},\supseteq S)$ is NP-hard.
In contrast with the proof of Theorem 3, the hardness result for convex
functions has to use edge costs other than 0 and $\infty$. The reason is that
for convex sets, higher degrees are always preferable. Consequently, a
principal will never remove edges (even if they are free to remove). On the
other hand, if edge additions are free, the principal’s optimal strategy is
clearly to make $G$ the complete graph. Either this will induce all nodes in
$S$ to invest, or no graph $G$ will.

The problem $\textsc{NDDS}\,(\text{convex},\supseteq S)$ is NP-hard, even when
$\gamma_{(i,j)}=1$ for all $(i,j)\notin E^{\prime}$, and $\gamma_{e}=0$ for
all $e\in E^{\prime}$.

###### Proof.

We prove NP-hardness by a reduction from the $k$-Clique problem. In an
instance of $k$-Clique, we are given a graph $H=(V_{H},E_{H})$ and a positive
integer $k$, and asked if $H$ has a clique of size at least $k$, i.e., a
subset $S\subseteq V_{H}$ of at least $k$ nodes such that $(u,v)\in E$ for all
$u,v\in S,u\neq v$. From $H,k$, we construct an instance of
$\textsc{NDDS}\,(\text{convex},\supseteq S)$, consisting of a graph
$G^{\prime}=(V,E^{\prime})$, investment degree sets $D_{i}$ for each node
$i\in V$, costs $\gamma_{(i,j)}$ for edge addition/removal, and a budget $B$.

The graph $G^{\prime}$ consists of $H$, with a node-disjoint clique on $nk$
nodes added. We call the set of new nodes $V^{\prime}$, and write
$V=V^{\prime}\cup V_{H}$. Thus, the new graph has $nk+n$ nodes. The investment
degree of every node $i$ is $D_{i}=\\{nk+k-1,\ldots,nk+n\\}$. The cost of
adding any non-existing edge $(i,j)$ is $\gamma_{(i,j)}=1$, and the cost for
removing any existing edge $e$ is $\gamma_{e}=0$. The budget is $B=nk^{2}$.
Notice that the $D_{i}$ by Lemma 2.3 indeed correspond to convex functions
$g_{i}$. Finally, the goal is to get a superset of $V^{\prime}$ to invest.

First, assume that $H$ has a clique $S$ of $k$ nodes. Let $E$ consist of all
edges of $G^{\prime}$, plus a complete bipartite graph between $V^{\prime}$
and $S$. This added bipartite graph contains $kn\cdot k=k^{2}n$ edges, so it
satisfies the budget constraint. It is now immediate that each node in
$V^{\prime}\cup S$ has degree at least $nk+k-1$. The nodes in $V_{H}\setminus
S$ have degree at most $n-1$. As a result, setting $I=V^{\prime}\cup S$
satisfies Definition 2.3.

Conversely, let $E$ be a set of edges with $|E\setminus E^{\prime}|\leq
nk^{2}$, and $I\subseteq V^{\prime}$ a set of vertices such that in the graph
$(V,E)$, each node $v\in I$ has at least $nk+k-1$ neighbors in $I$, and each
node $v\notin I$ has at most $nk+k-2$ neighbors in $I$. First, because each
node $v\in V^{\prime}$ started out with degree $nk-1$ and has at least
$nk+k-1$ neighbors in $I$, $E\setminus E^{\prime}$ must contain at least $k$
incident edges for each such $v$. And because $E^{\prime}$ already contained a
clique on $V^{\prime}$, these edges must be between $V^{\prime}$ and $V_{H}$,
so none of them are incident on two nodes of $V^{\prime}$. Therefore,
$E\setminus E^{\prime}$ contains exactly $k$ incident edges on each $v\in
V^{\prime}$.

Let $S$ be the set of neighbors of $V^{\prime}$ in $V_{H}$. First, $|S|\geq
k$, because each node $v\in V^{\prime}$ is adjacent to $k$ nodes in $V_{H}$.
Next, we claim that $I=V^{\prime}\cup S$. First, all nodes in $S$ must be in
$I$. The reason is that each $v\in V^{\prime}$ has degree exactly $nk+k-1$, so
if even one of its neighbors were not in $I$, it couldn’t have the required
$nk+k-1$ neighbors in $I$. Second, no node in $V_{H}\setminus S$ can be in
$I$, because its degree is at most $n-1<nk+k-1$.

For every node $v\in S$, let $k(v)$ be the number of neighbors of $v$ in
$S\cup V^{\prime}$ in the graph $G=(V,E)$. Because $S\subseteq I$, we can
lower-bound $k(v)\geq nk+k-1$. On the other hand, $\sum_{v\in
S}k_{v}\leq|S|\cdot(|S|-1)+nk^{2}$, and because the minimum $k_{v}$ is at most
the average, we get that $nk+k-1\leq\min_{v\in
S}k_{v}\leq(|S|-1)+\frac{nk^{2}}{|S|}$. Rearranging this inequality gives us
that $|S|(nk+k-|S|)\leq nk^{2}$. The left-hand side is a strictly concave
function of $|S|$, and therefore attains its minimum at one of its endpoints
$|S|\in\\{k,n\\}$. At $|S|=k$, the inequality holds with equality, while at
$|S|=n$, it is violated. Therefore, $|S|=k$ is the only feasible solution of
the inequality. Because each $v\in S$ only has $nk$ neighbors in $V^{\prime}$,
and none of its neighbors in $V_{H}\setminus S$ are in $I$, each $v\in S$ must
have $k-1$ neighbors in $S$. In other words, $S$ is a clique of size $k$ in
$H$. ∎

##  4\. Tractable Cases

In this section, we give polynomial-time algorithms for the corresponding
cases in Table 1. At the core of our algorithms lies a construction for the
$\textsc{NDDS}\,(\text{sigmoid},all)$ problem, which is based on a reduction
to the Minimum-Cost Perfect Matching problem. This reduction is a significant
generalization of Tutte’s reduction for finding a subgraph with a given degree
sequence. The Perfect Matching problem is polynomial-time solvable by
utilizing the Blossom Algorithm proposed by Edmonds Edmonds (1965). The
remaining cases are either special cases of
$\textsc{NDDS}\,(\text{sigmoid},all)$, or can be reduced to
$\textsc{NDDS}\,(\text{sigmoid},all)$ fairly directly. We remark that when no
edges can be added, an efficient algorithm was given implicitly as part of the
characterization by Lovász (1970, 1972). An explicit algorithm based on a
reduction to a matching problem was given by Anstee (1985). The fact that we
also allow edge additions increases the complexity of the problem
significantly.

###  4.1. Tractability of $\textsc{NDDS}\,(\text{sigmoid},all)$

$i$$1$$2$$3$$4$$5$$6$$7$$8$$9$$e_{1}$$e_{2}$$e^{\prime}_{3}$$e^{\prime}_{4}$$e^{\prime}_{5}$$e^{\prime}_{6}$$e^{\prime}_{7}$$e^{\prime}_{8}$$e^{\prime}_{9}$ |  $y^{+}_{e^{\prime}_{3},i}$$y^{+}_{e^{\prime}_{4},i}$$y^{+}_{e^{\prime}_{5},i}$$y^{+}_{e^{\prime}_{6},i}$$y^{+}_{e^{\prime}_{7},i}$$y^{+}_{e^{\prime}_{8},i}$$y^{+}_{e^{\prime}_{9},i}$$x^{+}_{i,1}$$x^{+}_{i,2}$$x^{+}_{i,3}$$x^{+}_{i,4}$$x^{+}_{i,5}$$x^{+}_{i,6}$$X^{+}_{i}$ $x^{-}_{i,1}$$x^{-}_{i,2}$$X^{-}_{i}$ $z_{1}$$z_{2}$$z_{3}$$z_{4}$$Z^{+}_{i}$ $y^{-}_{e_{1},i}$$y^{-}_{e_{2},i}$
---|---
Figure 1. Example to illustrate our generalized construction. Left: An example
graph where $d_{G^{\prime}}(i)$ = 2, $D_{i}$ =$\\{4,5,6\\}$, and $n=10$;
Right: the subgraph $H(i)$ associated with $i$.

Consider an instance of $\textsc{NDDS}\,(\text{sigmoid},all)$, consisting of a
graph $G^{\prime}=(V,E^{\prime})$, investment degree sets $D_{i}$, costs
$\gamma_{(i,j)}$ for edge addition/removal, and a budget $B$. The principal
wants to modify $G^{\prime}$ to $G=(V,E)$ (at total cost at most $B$), such
that all agents invest in a PSNE of the corresponding game. We construct an
instance of the weighted perfect matching problem on a graph $H=(V_{H},E_{H})$
and show that the principal has a graph modification of cost at most $B$
available iff $G$ has a perfect matching of total cost at most $B$. Our
construction generalizes Tutte Tutte (1954). We begin by describing Tutte’s
construction, and then present our generalization.

Tutte’s reduction applies to the special case when edges can only be removed,
and furthermore, each investment degree set $D_{v}=\\{d_{v}\\}$ is a
singleton, called the _desired degree_ of $v$. Each node $v$ must have exactly
$\Delta d_{v}:=d_{G^{\prime}}(v)-d_{v}$ of its edges removed. To encode this,
Tutte’s construction adds a node set $X^{-}_{v}$ of $\Delta d_{v}$ nodes
$x^{-}_{v,j},j=1,\ldots,\Delta d_{v}$. Furthermore, it adds two nodes
$y^{-}_{e,v}$, $y^{-}_{e,u}$ for every edge $e=(u,v)$. These two nodes are
connected to each other, and to all nodes in their respective sets
$X^{-}_{v}$, $X^{-}_{u}$. It is clear that the construction takes polynomial
time. Any perfect matching has to match all of the nodes in each $X^{-}_{v}$,
capturing exactly the edges incident on $v$ to be deleted. Because for each
edge $e=(u,v)$, both $y^{-}_{e,v}$ and $y^{-}_{e,u}$ must be matched, either
they are matched to each other (encoding that the edge is not deleted), or
they must _both_ be matched with nodes from the corresponding $X^{-}_{v}$ and
$X^{-}_{u}$ sets. It is now straightforward that the new graph has a perfect
matching iff the desired degree sequence can be obtained by edge removals.
Edge removal costs can be assigned to the edges between $X^{-}_{v}$ and the
$y^{-}_{e,v}$.

Because the addition of edges corresponds to the removal of edges in the
complement graph, a practically identical construction can be used directly if
the goal is only to _add_ , rather than remove edges. However, in
$\textsc{NDDS}\,(\text{sigmoid},all)$, the principal can both add and remove
edges. Furthermore, the investment degree sets $D_{i}$ can be intervals
containing multiple values. This necessitates significant extensions to
Tutte’s construction.

We now describe our generalized construction, where a graph $H=(V_{H},E_{H})$
is constructed from $G^{\prime}$. For every agent $i\in V$, the degree in
$G^{\prime}$ is $d_{G^{\prime}}(i)$, and the degree set is
$D_{i}=\\{L_{i},\ldots,R_{i}\\}$, where $L_{i}$ (resp., $R_{i}$) is the
minimum (resp., maximum) of $D_{i}$. If any set $D_{i}$ is empty, then the
instance clearly has no solution, and this is easy to diagnose. From now on,
we assume that $D_{i}\neq\emptyset$ for all $i$. At the core of the
construction is the union of the Tutte construction for both additions and
removals of edges. Thus, for each edge $e=(i,i^{\prime})\in E^{\prime}$ (a
candidate for removal), we add two nodes $y^{-}_{e,i}$ and
$y^{-}_{e,i^{\prime}}$ with an edge between them; similarly for each node pair
$e^{\prime}=(i,i^{\prime})\notin E^{\prime}$ (a candidate for addition), we
add two nodes $y^{+}_{e^{\prime},i}$ and $y^{+}_{e^{\prime},i^{\prime}}$ with
an edge between them.

Next, we describe the node gadget for a node $i$. An illustrative example is
shown in Figure 1. We add a set $X^{+}_{i}$ of
$\min(R_{i},n-d_{G^{\prime}}(i)-1)$ nodes $x^{+}_{i,j}$ (blue nodes in Figure
1), corresponding to additions of edges, and a set $X^{-}_{i}$ of
$\min(n-L_{i}-1,d_{G^{\prime}}(i))$ nodes $x^{-}_{i,j}$ (green nodes in Figure
1), corresponding to edge removals. These are hard upper bounds on the number
of possible edge additions/removals: for $|X^{+}_{i}|$, the first term arises
because even if all existing edges were deleted, no more than $R_{i}$ new
edges can be safely added; the second term is because there are only
$n-d_{G^{\prime}}(i)-1$ potential edges for addition. The justification is
similar for $|X^{-}_{i}|$. As in Tutte’s construction, we add an edge between
each node $x^{+}_{i,j}$ and each $y^{+}_{e^{\prime},i}$. Similarly, we add an
edge between each node $x^{-}_{i,j}$ and each $y^{-}_{e,i}$. Finally, we add a
complete bipartite graph between $X^{-}_{i}$ and $X^{+}_{i}$.

As in Tutte’s construction, including an edge between $x^{+}_{i,j}$ and
$y^{+}_{e^{\prime},i}$ in a matching corresponds to adding the edge
$e^{\prime}$ (increasing the degree of $i$), and including the edge
$(x^{-}_{i,j},y^{-}_{e,i})$ corresponds to removing the edge $e$, decreasing
the degree of $i$. Because no other edges are incident on
$y^{+}_{e^{\prime},i}$, $y^{-}_{e,i}$, for any edge $e=(i,i^{\prime})$, either
$y^{-}_{e,i}$ is matched with $y^{-}_{e,i^{\prime}}$, or both are matched with
nodes from $X^{-}_{i}$ (resp., $X^{-}_{i^{\prime}}$); similarly for the
$y^{+}_{e,i}$ nodes. The complete bipartite graph between $X^{-}_{i}$ and
$X^{+}_{i}$ allows us to encode that adding one fewer edge and removing one
fewer edge has the same effect on $i$’s degree as adding and removing one more
edge.

We now expand the gadget to encode the set $D_{i}$. The intuition for the
generalized gadget is the following: if $k^{+}_{i}$ nodes in $X^{+}_{i}$ are
matched with nodes $y^{+}_{e^{\prime},i}$, and $k^{-}_{i}$ nodes in
$X^{-}_{i}$ are matched with nodes $y^{-}_{e,i}$, then the new degree of $i$
is $d_{G^{\prime}}(i)+k^{+}_{i}-k^{-}_{i}$. We want to force this number to be
in $D_{i}=[L_{i},R_{i}]$ for every perfect matching. If we let
$\hat{k}^{+}_{i}=|X^{+}_{i}|-k^{+}_{i}$ and
$\hat{k}^{-}_{i}=|X^{-}_{i}|-k^{-}_{i}$ be the number of nodes in $X^{+}_{i}$,
$X^{-}_{i}$ that are matched differently (i.e., not with
$y^{+}_{e^{\prime},i}$, $y^{-}_{e,i}$), then the necessary/sufficient
condition can be expressed as
$\hat{k}^{-}_{i}-\hat{k}^{+}_{i}\in[L_{i}-(d_{G^{\prime}}(i)+|X^{+}_{i}|-|X^{-}_{i}|),R_{i}-(d_{G^{\prime}}(i)+|X^{+}_{i}|-|X^{-}_{i}|)]$.
Furthermore, notice that our gadget will only need to work if at least one of
$\hat{k}^{-}_{i},\hat{k}^{+}_{i}$ is 0, since the complete bipartite graph
between $X^{-}_{i}$, $X^{+}_{i}$ can always be used to ensure this condition.

Let $\sigma_{i}=d_{G^{\prime}}(i)+|X^{+}_{i}|-|X^{-}_{i}|$. A case distinction
on the possible cases of the minimum in the definitions of $|X^{+}_{i}|$,
$|X^{-}_{i}|$ shows that we always have $L_{i}\leq\sigma_{i}\leq R_{i}$.
Therefore, $L_{i}-\sigma_{i}\leq 0\leq R_{i}-\sigma_{i}$. We generate two more
node sets $Z^{+}_{i}$, $Z^{-}_{i}$. $Z^{+}_{i}$ consists of $\sigma_{i}-L_{i}$
nodes $z^{+}_{i,j}$, and $Z^{-}_{i}$ consists of $R_{i}-\sigma_{i}$ nodes
$z^{-}_{i,j}$. There is a complete bipartite graph between $Z^{+}_{i}$ and
$X^{+}_{i}$, as well as between $Z^{-}_{i}$ and $X^{-}_{i}$. In addition,
there is a complete graph on the union of all of the $Z^{+}_{i}$ and
$Z^{-}_{i}$, for all $i$. If the total number of nodes in the construction is
odd, then we add one more node $\hat{z}$ and connect it to all nodes in all of
the $Z^{+}_{i}$ and $Z^{-}_{i}$. The $z^{+}_{i,j}$, $z^{-}_{i,j}$ are there to
match any otherwise unmatched nodes $x^{+}_{i,j}$, $x^{-}_{i,j}$. Whichever
ones of them are not needed can be matched with each other and with $\hat{z}$.

Finally, for every edge $e=(i,i^{\prime})\in G^{\prime}$, we assign a cost of
$\gamma_{e}/2$ to the edges $(x^{-}_{i,j},y^{-}_{e,i})$ and
$(x^{-}_{i^{\prime},j},y^{-}_{e,i^{\prime}})$ (for all $j$); similarly, for
every edge $e^{\prime}=(i,i^{\prime})\notin G^{\prime}$, we assign a cost of
$\gamma_{e^{\prime}}/2$ to the edges $(x^{+}_{i,j},y^{+}_{e^{\prime},i})$ and
$(x^{+}_{i^{\prime},j},y^{+}_{e^{\prime},i^{\prime}})$ (for all $j$). All
other edges have cost 0. The cost bound for the perfect matching is the given
budget $B$. The correctness of this reduction is captured by the following
theorem:

The graph $H$ has a perfect matching of total cost at most $B$ if and only if
there is an edge modification $E$ of the input graph $G^{\prime}$ such that in
$(V,E)$, the degrees of all nodes $i$ are in their respective investment sets
$D_{i}$.

###### Proof.

First, we assume that there is an edge set $E\subseteq V\times V$ such that
$\sum_{e\in E^{\prime}\triangle E}\gamma_{e}\leq B$, and in the graph
$G=(V,E)$, every node $i$ has degree $d_{G}(i)\in D_{i}$. We define a perfect
matching $M$ in $H$.

For edges $e=(i,i^{\prime})\in E\cap E^{\prime}$, the matching includes the
edge $(y^{-}_{e,i},y^{-}_{e,i^{\prime}})$; similarly, for edges
$e^{\prime}=(i,i^{\prime})\notin E,e^{\prime}\notin E^{\prime}$, it contains
the edge $(y^{+}_{e^{\prime},i},y^{+}_{e^{\prime},i^{\prime}})$.

Now focus on one node $i$. Let $k^{+}_{i}$, $k^{-}_{i}$ be the numbers of
edges that were added to (resp., removed from) $i$, i.e., the numbers of edges
incident on $i$ in $E\setminus E^{\prime}$ and $E^{\prime}\setminus E$. Let
$e^{\prime}_{1},\ldots,e^{\prime}_{k^{+}_{i}}$ be an enumeration of the added
edges (in arbitrary order), and $e_{1},\ldots,e_{k^{-}_{i}}$ an enumeration of
the removed edges in arbitrary order. For each $e^{\prime}_{j}$, the matching
$M$ includes the edge $(x^{+}_{i,j},y^{+}_{e^{\prime}_{j},i})$; similarly, for
each $e_{j}$, $M$ includes the edge $(x^{-}_{i,j},y^{-}_{e_{j},i})$. Doing
this for all $i$ ensures that all nodes $y^{+}_{e^{\prime},i}$, $y^{-}_{e,i}$
are matched, and the total cost of all edges is exactly $\sum_{e\in
E^{\prime}\triangle E}\gamma_{e}\leq B$. This cost will not change by the
inclusion of later edges, since they all have cost 0.

Next, let $m_{i}:=\min(|X^{+}_{i}|-k^{+}_{i},|X^{-}_{i}|-k^{-}_{i})$. Notice
that $m_{i}\geq 0$, because our definition of $|X^{+}_{i}|$, $|X^{-}_{i}|$
ensured that no edge set $E$ with $d_{G}(i)\in D_{i}$ could add/remove more
than $|X^{+}_{i}|$ (resp., $|X^{-}_{i}|$) edges. We next add a perfect
matching of $m_{i}$ edges $(x^{+}_{i,k^{+}_{i}+j},x^{-}_{i,k^{-}_{i}+j})$ for
$j=1,\ldots,m_{i}$. At this point, at least one of the sets $X^{+}_{i}$,
$X^{-}_{i}$ is completely matched. For the remaining description, assume that
$X^{-}_{i}$ is fully matched — the other case is symmetric. Now, there are

$\displaystyle|X^{+}_{i}|-k^{+}_{i}-m_{i}$
$\displaystyle\leq|X^{+}_{i}|-|X^{-}_{i}|+(k^{-}_{i}-k^{+}_{i})$
$\displaystyle=(\sigma_{i}-d_{G^{\prime}}(i))+(k^{-}_{i}-k^{+}_{i})$
$\displaystyle=\sigma_{i}-d_{G}(i)$

unmatched nodes in $X^{+}_{i}$. Because $d_{G}(i)\in D_{i}$, it must satisfy
$d_{G}(i)\geq L_{i}$; therefore, because $Z^{+}_{i}$ contains
$\sigma_{i}-L_{i}\geq\sigma_{i}-d_{G}(i)$ nodes, it has enough nodes to
perfectly match the remaining nodes of $X^{+}_{i}$ — we add such a perfect
matching. Finally, we add a perfect matching on the unmatched nodes of all
$Z^{+}_{i}$, $Z^{-}_{i}$ (and $\hat{z}$) — this is possible, because $H$
contains a complete graph on these nodes, the total number of nodes in $H$ is
even, and the number of nodes matched so far is (by definition of a matching)
even. Thus, we have shown that $H$ contains a perfect matching of the desired
cost.

For the converse direction, we assume that $H$ contains a perfect matching $M$
of cost at most $B$. Define edge sets $E^{+}=\\{e^{\prime}=(i,j)\notin
E^{\prime}\mid(y^{+}_{e,i},y^{+}_{e,i^{\prime}})\notin M\\}$ and
$E^{-}=\\{e=(i,j)\in E^{\prime}\mid(y^{-}_{e,i},y^{-}_{e,i^{\prime}})\notin
M\\}$. That is, $E^{+}$ consists of the edges for which addition was encoded
in the Tutte reduction part, and $E^{-}$ of the edges for which removal was
encoded in the Tutte reduction part. Let $E=E^{\prime}\cup E^{+}\setminus
E^{-}$. Because $M$ is a perfect matching, it must include edges of the form
$(x^{+}_{i,j},y^{+}_{e^{\prime},i}),(x^{+}_{i^{\prime},j},y^{+}_{e^{\prime},i^{\prime}})$
for all edges $e^{\prime}=(i,i^{\prime})\in E^{+}$, and edges of the form
$(x^{-}_{i,j},y^{-}_{e,i}),(x^{-}_{i^{\prime},j},y^{-}_{e,i^{\prime}})$ for
all edges $e=(i,i^{\prime})\in E^{-}$. In particular, the total cost of
$E\triangle E^{\prime}$ is exactly $B$.

It remains to show that in the graph $G=(V,E)$, each node $i$ has degree
$d_{G}(i)\in D_{i}$. Let $k^{+}_{i}$ be the number of edges in $E^{+}$
incident on $i$, and $k^{-}_{i}$ the number of edges in $E^{-}$ incident on
$i$. Then, because the $y^{+}_{e^{\prime},i}$ for $e^{\prime}\in E^{+}$ are
_not_ matched to $y^{+}_{e^{\prime},i^{\prime}}$, they must be matched to some
$x^{+}_{i,j}$; similarly, the $y^{-}_{e,i}$ for $e\in E^{-}$ are matched to
some $x^{-}_{i,j}$. In particular, this means that
$k^{+}_{i}\leq|X^{+}_{i}|,k^{-}_{i}\leq|X^{-}_{i}|$. Furthermore, because
$X^{+}_{i}$ and $X^{-}_{i}$ are completely matched, and they can only be
matched with each other and $y^{+}_{e^{\prime},i}$ and $Z^{+}_{i}$
($y^{-}_{e,i}$, or $Z^{-}_{i}$, respectively), we infer that
$(|X^{+}_{i}|-k^{+}_{i})-(|X^{-}_{i}|-k^{-}_{i})\leq\sigma_{i}-L_{i}$ and
$(|X^{-}_{i}|-k^{-}_{i})-(|X^{+}_{i}|-k^{+}_{i})\leq R_{i}-\sigma_{i}$.
Substituting the definition of $\sigma_{i}$, these inequalities rearrange to
$L_{i}\leq d_{G^{\prime}}(i)+k^{+}_{i}-k^{-}_{i}=d_{G}(i)$ and $R_{i}\geq
d_{G^{\prime}}(i)+k^{+}_{i}-k^{-}_{i}=d_{G}(i)$. Thus, we have shown that
$d_{G}(i)\in[L_{i},R_{i}]$, so the degree constraint for $i$ is met. Since
this holds for all $i$, the proof is complete. ∎

The reduction clearly runs in polynomial time (and is in fact fairly
straightforward), and the Minimum-Cost Perfect Matching problem is known to be
solvable in polynomial time Edmonds (1965). Thus, we obtain a polynomial-time
algorithm for the $\textsc{NDDS}\,(\text{sigmoid},all)$ problem, as claimed.
Because convex and concave functions are special cases of sigmoid functions,
$\textsc{NDDS}\,(\text{convex/concave},all)$ are also polynomial-time
solvable.

###  4.2. Tractability of $\textsc{NDDS}\,(\text{sigmoid},=S)$

Finally, we leverage the algorithm from Section 4.1 for the more general
problem $\textsc{NDDS}\,(\text{sigmoid},=S)$.

Consider a hypothetical solution $G=(V,E)$. Then, for every node $i\notin S$,
we must have $|\mathcal{N}_{i}^{(G)}\cap S|\notin D_{i}$. Edges between node
pairs $i,i^{\prime}\notin S$ do not matter. Similarly, because exactly the
nodes of $S$ are supposed to invest, for the purpose of investment decisions
of nodes $i\in S$, edges to nodes not in $S$ do not matter. Thus, as a first
step, an algorithm can add/remove edges between $S$ and $V\setminus S$ of
minimum total cost to ensure that $|\mathcal{N}_{i}^{(G)}\cap S|\notin D_{i}$
for all $i\notin S$. This can be accomplished easily node by node: when
considering node $i$, either the principal will add
$R_{i}+1-d_{G^{\prime}}(i)$ edges or remove $d_{G^{\prime}}(i)-(L_{i}-1)$
edges. In both cases, the minimum-cost edges incident on $i$ will be chosen.
If these additions/removals exceed the budget $B$, then no solution is
possible. Otherwise, they will be performed, and the budget updated to the
remaining budget.

After the removal of these edges, the agents in $V\setminus S$ are irrelevant;
the sole goal is to alter the edges within $S$ at minimum cost to meet the
degree constraints. This is an instance of the problem
$\textsc{NDDS}\,(\text{sigmoid},all)$ on the induced graph $G^{\prime}[S]$,
which can be solved using the algorithm from Section 4.1. Thus, we have proved
the following theorem:

The problem $\textsc{NDDS}\,(\text{sigmoid},=S)$ is polynomial-time solvable.

Again, since convex and concave functions are special cases of sigmoid
functions, the tractability of $\textsc{NDDS}\,(\text{convex/concave},=S)$
follows from Theorem 4.2.

##  5\. Conclusion

The problem of modifying elements of a game structure to achieve desired
outcomes has a long history and interest in both economics and computing, with
mechanism design the classic variation. In mechanism design, a key design
parameter is the payment scheme for the players. The somewhat more recent
literature on market design is often focused on settings where payments are
infeasible, and aims to design market structure, such as the rules of the
matching markets. An even more recent thread considers the problem of
designing signals that modify information available to the players, thereby
inducing particular desirable outcomes. We suggest considering a fourth
element of the game in settings where strategic dependencies among players are
mediated by a network: the design of the network structure. Such design
decisions are commonly inherently constrained by an already existing network,
and we specifically consider the simplest and most natural design action:
adding and removing links. Additionally, to elucidate both the process and the
associated algorithmic mechanics, we further delve deeply into a study of
network design for networked public goods games, with the goal of inducing
desired pure strategy equilibrium outcomes. The significance of our work is
thus both in proposing a novel framework for designing the rules of encounter
specific to networked game theoretic scenarios, and elucidating the
algorithmic complexity of this problem in the particular context of networked
public goods games.

Our work provides an initial step, but leaves open a number of research
questions. First, our focus on adding and removing edges with an additive
addition/removal cost clearly limits the scope of applicability. In general,
one would encounter numerous complications. For example, if the means for
adding edges is through the design of events, then the cost would be incurred
for adding a collection of edges (i.e., organizing an event), rather than
adding each edge independently. Indeed, one could consider a broad space of
reasonable cost functions that generalize additivity, such as submodular
costs. Second, the problem of inducing equilibria through network
modifications is interesting far more broadly than just networked public goods
games. For example, such network design issues arise in congestion games.
Third, we only considered the issue of inducing pure strategy Nash equilibria.
It is, of course, natural to study other equilibrium concepts, such as mixed-
strategy equilibria and correlated equilibria.

## Acknowledgments

This work was partially supported by the National Science Foundation (grants
IIS-1903207 and IIS-1903207) and Army Research Office (MURI grant
W911NF1810208 and grant W911NF1910241).

## References

  * (1)
  * Amelkin and Singh (2019) Victor Amelkin and Ambuj K. Singh. 2019.  Fighting opinion control in social networks via link recommendation. In _Proc. 25th KDD_. 677–685.
  * Anstee (1985) Richard P. Anstee. 1985\.  An Algorithmic Proof of Tutte’s $f$-Factor Theorem.  _J. Algorithms_ 6 (1985), 112–131.
  * Bramoullé and Kranton (2007) Yann Bramoullé and Rachel Kranton. 2007.  Public goods in networks.  _J. Econ. Theory_ 135, 1 (2007), 478–494.
  * Bramoullé et al. (2014) Yann Bramoullé, Rachel Kranton, and Martin D’Amours. 2014\.  Strategic Interaction and Networks.  _Amer. Econ. Rev._ 104, 3 (2014), 898–930.
  * Bredereck and Elkind (2017) Robert Bredereck and Edith Elkind. 2017.  Manipulating Opinion Diffusion in Social Networks. In _Proc. 26th IJCAI_. 894–900.
  * Chen et al. (2016) Chen Chen, Hanghang Tong, B. Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, and Christos Faloutsos. 2016.  Eigen-Optimization on Large Graphs by Edge Manipulation.  _ACM TKDD_ 10, 4 (2016), 49:1–49:30.
  * Cornuéjols (1988) Gérard Cornuéjols. 1988\.  General factors of graphs.  _Journal of Combinatorial Theory, Series B_ 45, 2 (1988), 185–198.
  * Dughmi (2017) Shaddin Dughmi. 2017\.  Algorithmic Information Structure Design: A Survey.  _ACM SIGecom Exchanges_ 15, 2 (2017), 2–24.
  * Edmonds (1965) Jack Edmonds. 1965\.  Paths, trees, and flowers.  _Canadian Journal of Mathematics_ 17 (1965), 449–467.
  * Feldman et al. (2013) Michal Feldman, David Kempe, Brendan Lucier, and Renato Paes Leme. 2013.  Pricing Public Goods for Private Sale. In _Proc. 14th ACM EC_. 417–434.
  * Galeotti et al. (2010) Andrea Galeotti, Sanjeev Goyal, Matthew O. Jackson, Fernando Vega-Redondo, and Leeat Yariv. 2010\.  Network Games.  _The Review of Economic Studies_ 77, 1 (2010), 218–244.
  * Garey and Johnson (1979) Michael Garey and David S. Johnson. 1979.  _Computers and Intractability: A guide to the Theory of NP-completeness_.  Freeman.
  * Garimella et al. (2018) Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. 2018.  Reducing Controversy by Connecting Opposing Views. In _Proc. 27th IJCAI_. 5249–5253.
  * Ghosh and Boyd (2006) Arpita Ghosh and Stephen Boyd. 2006.  Growing Well-Connected Graphs. In _Proc. 45th IEEE Conference on Decision and Control (CDC)_. 6605–6611.
  * Golovach and Mertzios (2017) Petr A. Golovach and George B. Mertzios. 2017.  Graph editing to a given degree sequence.  _Theoretical Computer Science_ 665 (2017), 1–12.
  * Grossklags et al. (2008) Jens Grossklags, Nicolas Christin, and John Chuang. 2008\.  Security and insurance management in networks with heterogeneous agents. In _Proc. 9th ACM EC_. 160–169.
  * Haeringer (2018) Guillaume Haeringer. 2018\.  _Market Design: Auctions and Matching_.  The MIT Press.
  * Kearns et al. (2001) Michael Kearns, Michael L. Littman, and Satinder Singh. 2001\.  Graphical models for game theory. In _Proc. 17th UAI_. 253–260.
  * Levit et al. (2018) Vadim Levit, Zohar Komarovsky, Tal Grinshpoun, and Amnon Meisels. 2018.  Incentive-based search for efficient equilibria of the public goods game.  _Artificial Intelligence_ 262 (2018), 142–162.
  * Lovász (1970) László Lovász. 1970\.  Subgraphs with prescribed valencies.  _Journal of Combinatorial Theory_ 8 (1970), 391–416.
  * Lovász (1972) László Lovász. 1972\.  The factorization of graphs. II.  _Acta Mathematica Academiae Scientiarum Hungarica_ 23, 1-2 (1972), 223–246.
  * Mas-Collel et al. (1995) Andreu Mas-Collel, Michael D. Whinston, and Jerry R. Green. 1995.  _Microeconomic Theory_.  Oxford University Press.
  * Mathieson and Szeider (2012) Luke Mathieson and Stefan Szeider. 2012.  Editing graphs to satisfy degree constraints: A parameterized approach.  _J. Comput. System Sci._ 78, 1 (2012), 179–191.
  * Matteo Castiglioni (2020) Nicola Gatti Matteo Castiglioni, Diodato Ferraioli. 2020.  Election Control in Social Networks via Edge Addition or Removal. In _Proc. 34th AAAI_. AAAI Press.
  * Milchtaich (2015) Igal Milchtaich. 2015\.  Network topology and equilibrium existence in weighted network congestion games.  _International Journal of Game Theory_ 44, 3 (2015), 515–541.
  * Nisan et al. (2007) Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani (Eds.). 2007.  _Algorithmic Game Theory_.  Cambridge University Press.
  * Samuelson (1954) Paul A. Samuelson. 1954\.  The pure theory of public expenditure.  _Review of Economics and Statistics_ 36 (1954), 387–389.
  * Sheldon et al. (2010) Daniel Sheldon, Bistra Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sabharwal, Jon Conrad, Carla Gomes, David Shmoys, William Allen, Ole Amundsen, and William Vaughan. 2010.  Maximizing the Spread of Cascades Using Network Design. In _Proc. 26th UAI_. 517–526.
  * Shoham and Leyton-Brown (2009) Yoav Shoham and Kevin Leyton-Brown. 2009.  _Multiagent Systems_.  Cambridge University Press.
  * Sina et al. (2015) Sigal Sina, Noam Hazon, Avinatan Hassidim, and Sarit Kraus. 2015\.  Adapting the social network to affect elections. In _Proc. 14th AAMAS_. 705–713.
  * Sless et al. (2014) Liat Sless, Noam Hazon, Sarit Kraus, and Michael Wooldridge. 2014\.  Forming coalitions and facilitating relationships for completing tasks in social networks. In _Proc. 13th AAMAS_. 261–268.
  * Stewart (1994) Iain A. Stewart. 1994\.  Deciding whether a planar graph has a cubic subgraph is NP-complete.  _Discrete Mathematics_ 126, 1-3 (1994), 349–357.
  * Tong et al. (2012) Hanghang Tong, B. Aditya Prakash, Tina Eliassi-Rad, Michalis Faloutsos, and Christos Faloutsos. 2012\.  Gelling, and melting, large graphs by edge manipulation. In _Proc. 21st CIKM_. 245–254.
  * Tutte (1954) William Thomas Tutte. 1954\.  A short proof of the factor theorem for finite graphs.  _Canadian Journal of Mathematics_ 6 (1954), 347–352.
  * Yannakakis (1978) Mihalis Yannakakis. 1978\.  Node-and edge-deletion NP-complete problems. In _Proc. 10th ACM STOC_. 253–264.
  * Yu et al. (2020) Sixie Yu, Kai Zhou, P. Jeffrey Brantingham, and Yevgeniy Vorobeychik. 2020.  Computing Equilibria in Binary Networked Public Goods Games. In _Proc. 34th AAAI_. AAAI Press.
  * Zhang et al. (2016) Haifeng Zhang, Yevgeniy Vorobeychik, Joshua Letchford, and Kiran Lakkaraju. 2016.  Data-driven agent-based modeling, with application to rooftop solar adoption.  _Journal of Autonomous Agents and Multiagent Systems_ 30, 6 (2016), 1023–1049.

##  Appendix A Appendix

Here, we provide the proof of Theorem 3.

  * Proof of Theorem 3.

We prove NP-hardness by a reduction from the Vertex Cover (VC) problem. In an
instance of VC, we are given a graph $H=(V_{H},E_{H})$ and a positive integer
$k$, and asked if $H$ has a vertex cover of size at most $k$, i.e., a subset
$S\subseteq V_{H}$ of at most $k$ nodes such that each edge $e\in E_{H}$ has
at least one endpoint in $S$. From $H,k$, we construct an instance of
$\textsc{NDDS}\,(\text{general},\text{all})$, consisting of a graph
$G^{\prime}=(V,E^{\prime})$, investment degree sets $D_{i}$ for each node
$i\in V$, costs $\gamma_{(i,j)}$ for edge addition/removal, and a budget $B$.

The set of nodes $V$ consists of $V_{H}$, one vertex $u_{e}$ for each edge
$e\in E_{H}$, and one additional vertex $w$. The edges $E^{\prime}$ are as
follows:

    * –

$w$ is connected to all nodes in $V_{H}$.

    * –

There is an edge between $v$ and $u_{e}$ if and only if $v$ is an endpoint of
$e$ in $H$.

Let $d_{H}(v)$ be the degree of $v$ in $H$. We define the investment degree
sets for the agents as follows:

    * –

For every $v\in V_{H}$, we let $D_{v}=\\{0,d_{H}(v)+1\\}$.

    * –

For every $u_{e}$, we let $D_{u_{e}}=\\{1,2\\}$.

    * –

$D_{w}=\\{0,1,\ldots,k\\}$.

Finally, we set the costs $\gamma_{e}=0$ for $e\in E^{\prime}$, and
$\gamma_{(i,j)}=\infty$ for $(i,j)\notin E^{\prime}$. The budget is $B=1$ (or
really any non-negative number). Thus, the principal can remove as many edges
as he wants, but cannot add any edges. This completes the reduction, which
obviously runs in polynomial time.

First, assume that $H$ has a vertex cover of size at most $k$. We show that
there is a way to remove edges from $E^{\prime}$ such that each player $i$’s
degree ends up in $D_{i}$. Let $S$ be the vertex cover of $H$. Let $E\subseteq
E^{\prime}$ be the set of all edges _not_ incident on $V_{H}\setminus S$.
Then, $w$ is only incident on edges whose other endpoint is in $S$, so it has
degree at most $k$. Each node $v\in V_{H}\setminus S$ has all its edges
removed, so its degree is $0$. Each node $v\in S$ is connected to $d_{H}(v)$
nodes corresponding to the $d_{H}(v)$ edges incident on $v$ in $H$, plus its
one edge to $w$, so its degree is $d_{H}(v)+1$. Finally, because $S$ is a
vertex cover, each node $u_{e}$ is incident on at least one node $v\in S$, so
its degree is $1$ or $2$. Thus, we have shown that each node $i\in V$ has
degree in $D_{i}$.

For the converse direction, assume that there is a set $E\subseteq E^{\prime}$
of edges such that in $G=(V,E)$, each node $i$ has degree in $D_{i}$. Let
$S=\\{v\in V_{H}\mid(w,v)\in E\\}$ be the set of vertices whose edge to $w$ is
kept. Because the degree of $w$ is in $D_{w}$, we get that $|S|\leq k$. For
each node $v\in V_{H}\setminus S$, at least the edge to $w$ was removed, so
its degree cannot be $d_{H}(v)+1$. Therefore, its degree must be 0, so $E$
cannot contain any edges incident on any $v\in V_{H}\setminus S$. For each
node $v\in S$, at least the edge to $w$ was retained, so its degree cannot be
0. Therefore, its degree must be $d_{H}(v)+1$, so $E$ must contain all edges
incident on all $v\in S$. Finally, because each node $u_{e}$ has degree in
$\\{1,2\\}$ in $(V,E)$, each must have a neighbor in $S$. In other words, each
edge $e\in E_{H}$ has at least one endpoint in $S$. This proves that $S$ is a
vertex cover of $H$. x