Inducing Equilibria in Networked Public Goods Games through Network Structure Modification

2020·Arxiv

ABSTRACT

ABSTRACT

Networked publicgoods games model scenarios in which self-interested agents decide whether or how much to invest in an action that ben-efits 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 [18, 22]. 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 [3, 4, 9], 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) her1 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 spe-cific 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 [21].

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. The full summary of our main results is presented in Table 1.

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 [24]. An important class of these are graphical games, where a player’s utility only depends on the actions of her network neighbors [16]. 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 [3, 10, 17]. Bramoullé and Kranton [3] 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. [10] 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. [29] 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. They proposed a heuristic to compute approximate equilibria in general games. However, they did not consider modifying the network structure to induce certain Nash equilibria. Grossklags et al. [13] 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 selfprotection, 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., [21]) 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 [14], payments, as in traditional mechanism design [21], or the structure of information available to the players [7].

Anoter relevant line of research is network design. An interesting subclass is network design with fair cost-sharing [2]. Network design has also been applied to model security applications. Hota and Sundaram [15] focused on designing an optimal network topology that minimizes the expected fraction of attacked nodes, where the probability of a node being attacked is a function of its security investment as well as the investments by its neighbors.

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. [23] aim to modify the network so as to maximize the spread of cascades, while [6, 12, 27] aim to alter the spectral gap of the network to make it more or less connected. Along similar lines, Bredereck and Elkind [5] 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., [19, 25] 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 [1], 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. [11], who aim to decrease opinion polarization by connecting pairs of individuals with differing opinions. Sless et al. [26] 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 spe-cific 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. [4]. They found that the smallest eigenvalue 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 , 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 [20] studied equilibrium existence as a function of network topology in weighted network congestion games.

2 MODEL

2.1 Binary Networked Public Goods Game

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

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

(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 the action chosen by player the joint pure strategy profile of all players.

(3) For each player i, a non-decreasing utility function

As is standard in the literature on networked public goods [3], 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 be the set of neighbors of i in the graph G; then, we can define to be the number of neighbors who invest under x. When G, 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:

The second term () simply captures the cost that i incurs from investing herself. Eachis 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, will have additional properties, such as being concave or convex, and we discuss such properties in Section 2.3. Observe that each function can be represented using O(n) values, so the entire BNPG game (including the graph structure) can be represented using

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

Definition 2.1. In a BNPG game, a pure strategy Nash Equilibrium (PSNE) is an action profile1, 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 X is a PSNE. For notational convenience, we interpret X both as a set of strategy vectors the subset of investing players , whichever is notationally more convenient. We are interested in the following classes of PSNE: all: Every player invests, i.e., X = {{1, 2, . . . ,n}}. = S: Exactly a given set S of players invests (and the other players do not), i.e., X = {S}. All players investing is the special case S = {1, . . . ,n}. of players invests; other players may also invest. Here, players invest. Here, In general, even without the ability to modify G, deciding if a BNPG has an equilibrium in X is NP-hard. This can be seen most directly with the following example (see also Section 3.2 of [3]): Each cost is 1, and each the PSNE are exactly the strategy profiles x in which independent sets of G invest. Therefore, if 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 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 X. Formally, an input graph on the agents is given. Each node pair (i, j) has an associated cost , this is the cost for removing the edge , while for the cost for adding the edge . When the principal produces a graph G = (V, E), the cost of doing so is . The principal is given a budget B not to be exceeded. The goal is to solve the following problem:

Definition 2.2 (Network Design for BNPG). Given a BNPG instance, edge costs, desired PSNE class X, and budget B, find an edge set such that the BNPG game on (V, E) has at least one PSNE in X.

The general costsadmit many natural special cases: by setting ), we can prohibit the removal (or addition) of edges. By setting 0, we can allow unlimited removal (or addition) of edges. And by setting 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 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.2). In most scenarios, additional properties. Among the most common of these are: is concave, the returns for additional investments of neighbors are diminishing. The incentive structures in binary best-shot games [10] can be captured by concave

is convex, the returns for additional investments of neighbors are increasing.

Sigmoid For many natural scenarios, such as the adoption of innovations [30], the are neither concave nor convex on their entire domain. Instead, begins convex, with increasing returns to more investors, but eventually reaches saturation and diminishing returns. We call such a functionthere exists some ˆis convex on and concave on . Note that sigmoid functions subsume both concave functions (with ˆ) and convex functions (with ˆ

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, and denote them by is convex/concave/sigmoid, the investment degree sets have particularly nice forms, captured by the following lemma:

Lemma 2.3. For every non-decreasing function , there exists a unique set that is a best response toif and only if. Furthermore,

(1) When is concave, is a downward-closed interval. (2) When is convex, is an upward-closed interval. (3) When is sigmoid, is an interval.

Conversely, for every set , there exists a non-decreasing function is a best response to if and only if . Furthermore,

which is concave. (2) When is an upward-closed interval, there exists such a

which is convex. (3) When is an interval, there exists such awhich is sigmoid.

Proof. We write for the discrete derivative. By definition of best responses (recall our tie breaking rule), a player i invests if and only if , which is equivalent to

Thus, letting , we obtain that the best response to , proving the first claim. We now consider the three special cases:

(1) Whenis concave, is non-increasing. Therefore, whenever , we also have , meaning that is downward closed.

(2) When is convex, is non-decreasing. The rest of the argument is exactly as for the concave case.

(3) When is sigmoid, is non-decreasing on increasing on , with the maximum attained at ˆz. Therefore, is an interval.

For the converse, given a set , define a discrete derivative of . Normalizing with 0, and setting will invest iff If is an interval, then will start out as the constant 0, have slope 2 over the interval, and then become flat at the end of the interval. Thus, 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 . It shows that when concave, then the fewer neighbors invest, the more i is prone to invest. On the other hand, when 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 and induced numbers of investing neighbors, rather than utility functions, simplifying the arguments below.

lem NDDS (P, X) is defined as follows: Given a graph investment degree sets for all players i consistent with a function property P (such as convexity, concavity, sigmoid, or general), edge costs, desired PSNE class X, and budget B, find an edge set such that there exists a set of invest- ing players with

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

Because the investment degree sets can be efficiently constructed from the and vice versa, an algorithmic solution or a hardness result for the NDDS (P, 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)

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 , 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.

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.

Proof. The reduction is from Independent Set. Given a graph and an integer k, the problem is to decide if H contains an independent set of size (at least) k, i.e., a set that no pair in T is connected by an edge. For the reduction, we add two nodes has an edge to ˆu as well as to all nodes in no other edges are added to . The degree sets are all . We set all edge addition/removal costs to

If H has an independent set T of size at least k (without loss of generality, T is inclusion-wise maximal), then setting gives us a superset of has a neighbor in I, so all of them invest. Each 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 invests, then fore, u must have at least k + 1 neighbors in I; in particular, u has at least k neighbors in . 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.

NDDS (general, all). For fully general functions, we show that 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.

Proof. We prove NP-hardness by a reduction from the Vertex Cover (VC) problem. In an instance of VC, we are given a graph and a positive integer k, and asked if H has a vertex cover of size at most k, i.e., a subset of at mostk nodes such that each edge has at least one endpoint in S. From H,k, we construct an instance of NDDS (general, all), consisting of a graph , investment degree sets for each node for edge addition/removal, and a budget B.

The set of nodes V consists of , one vertex for each edge , and one additional vertex w. The edges are as follows:

• w is connected to all nodes in • There is an edge between if and only if v is an endpoint of e in H.

Let be the degree ofv in H. We define the investment degree sets for the agents as follows:

• For every • For every • Finally, we set the costs . 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 such that each player i’s degree ends up in be the vertex cover of H. Let be the set of all edges not incident on is only incident on edges whose other endpoint is in S, so it has degree at most k. Each node has all its edges removed,

so its degree is 0. Each node is connected to corresponding to the edges incident on v in H, plus its one edge to w, so its degree is 1. Finally, because S is a vertex cover, each node is incident on at least one node degree is 1 or 2. Thus, we have shown that each node degree in

For the converse direction, assume that there is a set edges such that in G = (V, E), each node i has degree in be the set of vertices whose edge to w is kept. Because the degree of , we get that For each node , at least the edge to w was removed, so its degree cannot be 1. Therefore, its degree must be 0, so E cannot contain any edges incident on any each node , at least the edge to w was retained, so its degree cannot be 0. Therefore, its degree must be contain all edges incident on all . Finally, because each node has degree in {1, 2} in (V, E), each must have a neighbor in S. In other words, each edge has at least one endpoint in S. This proves that S is a vertex cover of

Finally, we show that NDDS is NP-hard. In contrast with the proof of Theorem 3.2, the hardness result for convex functions has to use edge costs other than 0 and . 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.

Theorem 3.3. The problem NDDS is NP-hard, even when

Proof. We prove NP-hardness by a reduction from thek-Cliqe problem. In an instance of k-Cliqe, we are given a graph H = and a positive integer k, and asked if H has a clique of size at least k, i.e., a subset of at least k nodes such that , we construct an instance of NDDS , consisting of a graph investment degree sets for each node addition/removal, and a budget B.

The graph consists of H, with a node-disjoint clique on nk nodes added. We call the set of new nodes , and write . Thus, the new graph has nk +n nodes. The investment degree of every node . The cost of adding any non-existing edge 1, and the cost for removing any existing edge 0. The budget is . Notice that the by Lemma 2.3 indeed correspond to convex functions Finally, the goal is to get a superset of

First, assume that H has a clique S of k nodes. Let E consist of all edges of, plus a complete bipartite graph betweenadded bipartite graph contains edges, so it satisfies the budget constraint. It is now immediate that each node indegree at least 1. The nodes in have degree at most 1. As a result, setting satisfies Definition 2.4.

Conversely, let E be a set of edges with a set of vertices such that in the graph (V, E), each node at least 1 neighbors in I, and each node has at most 2 neighbors in I. First, because each node out with degree 1 and has at least 1 neighbors in I, must contain at least k incident edges for each such v. And because already contained a clique on , these edges must be between , so none of them are incident on two nodes of . Therefore, contains exactly k incident edges on each

Let S be the set of neighbors of each nodeis adjacent to . Next, we claim that . First, all nodes in S must be in I. The reason is that each has degree exactly 1, so if even one of its neighbors were not in I, it couldn’t have the required 1 neighbors in I. Second, no node in , because its degree is at most

For every nodebe the number of neighbors ofv in in the graph , we can lower-bound 1. On the other hand, and because the minimum is at most the average, we get that . Rearranging this inequality gives us that . The left-hand side is a strictly concave function of |S|, and therefore attains its minimum at one of its endpoints , 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 has nk neighbors in , and none of its neighbors in 1 neighbors in S. In other words, S is a clique of size

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 NDDS (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 [8]. The remaining cases are either special cases of NDDS (sigmoid, all), or can be reduced to NDDS (sigmoid, all) fairly directly.

4.1 Tractability of NDDS (sigmoid,all)

Consider an instance of NDDS (sigmoid, all), consisting of a graph , investment degree sets for edge addition/removal, and a budget B. The principal wants to modify 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 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 [28]. 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 is a singleton, called the desired degree of v. Each node v must have exactly of its edges removed. To encode this, Tutte’s construction adds a node set . Furthermore, it adds two nodes every edge e = (u,v). These two nodes are connected to each other, and to all nodes in their respective sets . It is clear that the construction takes polynomial time. Any perfect matching has to match all of the nodes in each , capturing exactly the edges incident on v to be deleted. Because for each edge e = (u,v), both 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 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 the

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 NDDS (sigmoid,all), the principal can both add and remove edges. Furthermore, the investment degree sets can be intervals containing multiple values. This necessitates significant extensions to Tutte’s construction.

We now describe our generalized construction, where a graph is constructed from. For every agent gree in , and the degree set is ) is the minimum (resp., maximum) of . If any set is empty, then the instance clearly has no solution, and this is easy to diagnose. From now on, we assume that At the core of the construction is the union of the Tutte construction for both additions and removals of edges. Thus, for each edge (a candidate for removal), we add two nodes and with an edge between them; similarly for each node pair (a candidate for addition), we add two nodes and with an edge between them.

Next, we describe the node gadget for a nodei. An illustrative example is shown in Figure 1. We add a set nodes (blue nodes in Figure 1), corresponding to additions of edges, and a set (green nodes in Figure 1), corresponding to edge removals. These are hard upper bounds on the number of possible edge additions/removals: for , the first term arises because even if all existing edges were deleted, no more than new edges can be safely added; the second term is because there are only 1 potential edges for addition. The justification is similar for . As in Tutte’s con- struction, we add an edge between each node Similarly, we add an edge between each node Finally, we add a complete bipartite graph between

As in Tutte’s construction, including an edge between in a matching corresponds to adding the edge (increasing the degree of i), and including the edge corresponds to removing the edge e, decreasing the degree of i. Because no other edges are incident on , for any edge is matched with , or both are matched with nodes from ); similarly for the nodes. The complete bipartite graph between 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.

Figure 1: Example to illustrate our generalized construction. Left: An example graph where Right: the subgraph H(i) associated with i.

We now expand the gadget to encode the set . The intuition for the generalized gadget is the following: if matched with nodes are matched with nodes , then the new degree of . We want to force this number to be in for every perfect matching. If we let ˆbe the number of nodes in that are matched differently (i.e., not with ), then the necessary/sufficient condition can be expressed as ˆFurthermore, notice that our gadget will only need to work if at least one of ˆis 0, since the complete bipartite graph between can always be used to ensure this condition.

Let . A case distinction on the possible cases of the minimum in the definitions of shows that we always have . Therefore, We generate two more node sets consists of nodesconsists of . There is a complete bipartite graph between , as well as between In addition, there is a complete graph on the union of all of the and . If the total number of nodes in the construction is odd, then we add one more node ˆz and connect it to all nodes in all of the are there to match any otherwise unmatched nodes. Whichever ones of them are not needed can be matched with each other and with ˆz.

Finally, for every edge , we assign a cost of to the edges ); similarly, for ev- ery edge , we assign a cost of 2 to the edges ). 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:

Theorem 4.1. 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 such that in (V, E), the degrees of all nodes i are in their respective investment sets

Proof. First, we assume that there is an edge set that , and in the graph G = (V, E), every node i has degree . We define a perfect matching M in H.

For edges , the matching includes the edge ; similarly, for edges , it contains the edge

Now focus on one node be the numbers of edges that were added to (resp., removed from) i, i.e., the numbers of edges incident on meration of the added edges (in arbitrary order), and enumeration of the removed edges in arbitrary order. For each the matching M includes the edge ; similarly, for each includes the edge . Doing this for all i ensures that all nodes are matched, and the total cost of all edges is exactly . This cost will not change by the inclusion of later edges, since they all have cost 0.

Next, let. Notice thatcause our definition of ensured that no edge set E with could add/remove more than We next add a perfect matching of . At this point, at least one of the sets pletely matched. For the remaining description, assume that fully matched — the other case is symmetric. Now, there are

unmatched nodes in , it must satisfy ; therefore, because nodes, it has enough nodes to perfectly match the remaining nodes of — we add such a perfect matching. Finally, we add a perfect matching on the unmatched nodes of all 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.

matching M of cost at most B. Define edge sets That is, consists of the edges for which addition was encoded in the Tutte reduction part, and of the edges for which removal was encoded in the Tutte reduction part. Let Because M is a perfect matching, it must include edges of the form for all edges , and edges of the form for all edges particular, the total cost of

It remains to show that in the graph G = (V, E), each node i has degree be the number of edges in on the number of edges in incident on i. Then, be- cause the matched to , they must be matched to some ; similarly, the are matched to some . In particular, this means that thermore, because are completely matched, and they can only be matched with each other and respectively), we infer that . Substituting the definition of , these inequalities rearrange to and . Thus, we have shown that , 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 [8]. Thus, we obtain a polynomial-time algorithm for the NDDS (sigmoid, all) problem, as claimed. Because convex and concave functions are special cases of sigmoid functions, NDDS (convex/concave, all)are also polynomial-time solvable.

4.2 Tractability of NDDS (sigmoid, = S)

Finally, we leverage the algorithm from Section 4.1 for the more general problem NDDS (sigmoid, = S).

Consider a hypothetical solution G = (V, E). Then, for every node , we must have . Edges between node pairs do not matter. Similarly, because exactly the nodes of S are supposed to invest, for the purpose of investment decisions of nodes, edges to nodes not in S do not matter. Thus, as a first step, an algorithm can add/remove edges between S and V \ S of minimum total cost to ensure that can be accomplished easily node by node: when considering nodei, either the principal will add edges or remove 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 \ 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 NDDS (sigmoid, all) on the induced graph, which can be solved using the algorithm from Section 4.1. Thus, we have proved the following theorem:

Theorem 4.2. The problem NDDS(sigmoid, = S) is polynomial-time solvable.

Again, since convex and concave functions are special cases of sigmoid functions, the tractability of NDDS (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.

REFERENCES

[1] Victor Amelkin and Ambuj K. Singh. 2019. Fighting opinion control in social networks via link recommendation. In Proc. 25th. 677–685.

[2] Elliot Anshelevich, Anirban Dasgupta, Jon Kleinberg, Eva Tardos, Tom Wexler, and Tim Roughgarden. 2008. The price of stability for network design with fair cost allocation. SIAM J. Comput. 38, 4 (2008), 1602–1623.

[3] Yann Bramoullé and Rachel Kranton. 2007. Public goods in networks. Journal of Economic Theory 135, 1 (2007), 478–494.

[4] Yann Bramoullé, Rachel Kranton, and Martin D’Amours. 2014. Strategic Inter- action and Networks. American Economic Review 104, 3 (2014), 898–930.

[5] Robert Bredereck and Edith Elkind. 2017. Manipulating Opinion Diffusion in Social Networks. In Proc. 26th. 894–900.

[6] 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 Transactions on Knowledge Discovery from Data 10, 4 (2016), 49:1–49:30.

[7] Shaddin Dughmi. 2017. Algorithmic Information Structure Design: A Survey. ACM SIGecom Exchanges 15, 2 (2017), 2–24.

[8] Jack Edmonds. 1965. Paths, trees, and flowers. Canadian Journal of Mathematics 17 (1965), 449–467.

[9] Michal Feldman, David Kempe, Brendan Lucier, and Renato Paes Leme. 2013. Pricing Public Goods for Private Sale. In Proc. 14th. 417–434.

[10] 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.

[11] Kiran Garimella, Gianmarco De Francisci Morales, Aristides Gionis, and Michael Mathioudakis. 2018. Reducing Controversy by Connecting Opposing Views. In Proc. 27th. 5249–5253.

[12] Arpita Ghosh and Stephen Boyd. 2006. Growing Well-Connected Graphs. In Proc. 45th IEEE Conference on Decision and Control (CDC). 6605–6611.

[13] Jens Grossklags, Nicolas Christin, and John Chuang. 2008. Security and insur- ance management in networks with heterogeneous agents. In Proc. 9th. 160–169.

[14] Guillaume Haeringer. 2018. Market Design: Auctions and Matching. The MIT Press.

[15] Ashish R. Hota and Shreyas Sundaram. 2016. Optimal network topologies for mitigating security and epidemic risks. In 2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 1129–1136.

[16] Michael Kearns, Michael L. Littman, and Satinder Singh. 2001. Graphical models for game theory. In Proc. 17th. 253–260.

[17] Vadim Levit, Zohar Komarovsky, Tal Grinshpoun, and Amnon Meisels. 2018. Incentive-based search for efficient equilibria of the public goods game. Arti-ficial Intelligence 262 (2018), 142–162.

ACKNOWLEDGMENTS

This work was partially supportedby the National Science Foundation (grants IIS-1903207 and IIS-1903207) and Army Research Of-fice (MURI grant W911NF1810208 and grant W911NF1910241).

[18] Andreu Mas-Collel, Michael D. Whinston, and Jerry R. Green. 1995. Microeconomic Theory. Oxford University Press.

[19] Nicola Gatti Matteo Castiglioni, Diodato Ferraioli. 2020. Election Control in Social Networks via Edge Addition or Removal. In Proc. 34th. AAAI Press.

[20] Igal Milchtaich. 2015. Network topology and equilibrium existence in weighted network congestion games. International Journal of Game Theory 44, 3 (2015), 515–541.

[21] Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani (Eds.). 2007. Algorithmic Game Theory. Cambridge University Press.

[22] Paul A. Samuelson. 1954. The pure theory of public expenditure. Review of Economics and Statistics 36 (1954), 387–389.

[23] Daniel Sheldon, Bistra Dilkina, Adam N. Elmachtoub, Ryan Finseth, Ashish Sab- harwal, 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. 517–526.

[24] Yoav Shoham and Kevin Leyton-Brown. 2009. Multiagent Systems. Cambridge University Press.

[25] Sigal Sina, Noam Hazon, Avinatan Hassidim, and Sarit Kraus. 2015. Adapting the social network to affect elections. In Proc. 14th. 705–713.

[26] Liat Sless, Noam Hazon, Sarit Kraus, and Michael Wooldridge. 2014. Forming coalitions and facilitating relationships for completing tasks in social networks. In Proc. 13th. 261–268.

[27] 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. 245–254.

[28] William Thomas Tutte. 1954. A short proof of the factor theorem for finite graphs. Canadian Journal of Mathematics 6 (1954), 347–352.

[29] Sixie Yu, Kai Zhou, P. Jeffrey Brantingham, and Yevgeniy Vorobeychik. 2020. Computing Equilibria in Binary Networked Public Goods Games. In Proc. 34th. AAAI Press.

[30] 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.