key: cord-0638491-m8bss32i
authors: Maiti, Arnab; Dey, Palash
title: On Binary Networked Public Goods Game with Altruism
date: 2022-05-01
journal: nan
DOI: nan
sha: 939302202a524854085277be34c912fa8d80ca4e
doc_id: 638491
cord_uid: m8bss32i

In the classical Binary Networked Public Goods (BNPG) game, a player can either invest in a public project or decide not to invest. Based on the decisions of all the players, each player receives a reward as per his/her utility function. However, classical models of BNPG game do not consider altruism, which players often exhibit and can significantly affect equilibrium behavior. Yu et al. [24] extended the classical BNPG game to capture the altruistic aspect of the players. We, in this paper, first study the problem of deciding the existence of a Pure Strategy Nash Equilibrium (PSNE) in a BNPG game with altruism. This problem is already known to be NP-complete. We complement this hardness result by showing that the problem admits efficient algorithms when the input network is either a tree or a complete graph. We further study the Altruistic Network Modification problem, where the task is to compute if a target strategy profile can be made a PSNE by adding or deleting a few edges. This problem is also known to be NP-complete. We strengthen this hardness result by exhibiting intractability results even for trees. A perhaps surprising finding of our work is that the above problem remains NP-hard even for bounded degree graphs when the altruism network is undirected, but becomes polynomial-time solvable when the altruism network is directed. We also show some results on computing an MSNE and some parameterized complexity results. In summary, our results show that it is much easier to predict how the players in a BNPG game will behave compared to how the players in a BNPG game can be made to behave in a desirable way.

In a binary networked public goods (in short BNPG) game, a player can either decide to invest in a public project or decide not to invest in it. Every player however incurs a cost for investing. Based on the decision of all the players, each player receives a reward as per his/her externality function. The net utility is decided based on the reward a player receives and the cost a player incurs. Usually, the externality function and cost of investing differ for every player, making the BNPG game heterogeneous. In some scenarios, the externality function and cost of investing can be the same for every player, making the BNPG game fully homogeneous. Many applications of public goods, for example, wearing a mask [12] , getting vaccinated [3] , practicing social distancing [5] , reporting crimes etc., involve binary decisions. Such domains can be captured using BNPG game. A BNPG game is typically modeled using a network of players which is an undirected graph [11] . We also observe that there are some societies where few people wear masks and/or get themselves vaccinated, and there are some other societies where most people wear masks and get themselves vaccinated [4, 23] . This can be attributed to differences in altruistic behavior among various societies [2, 6] . In an altrusitic society, people consider their as 23:2 On Binary Networked Public Goods Game with Altruism well as their neighbors' benefit to take a decision. For example, young adults may wear a mask not only to protect themselves but also to protect their elderly parents and young children at home. Altruism can be modeled using an altruistic network which can be either an undirected graph or a directed graph [24] . Symmetric altruism (respectively asymmetric altruism) occurs when the altruistic network is undirected (respectively directed). The utility that a player receives depends on both the input network and the (incoming) incident edges in the altruistic network.

We study the BNPG game with altruism for two different problem settings. First, we look at the problem of deciding the existence of Pure Strategy Nash Equilibrium (PSNE) in the BNPG game with altruism. In any game, determining a PSNE is an important problem as it allows a social planner to predict the behaviour of players in a strategic setting and make appropriate decisions. It is known that deciding the existence of PSNE in a BNPG game (even without altruism) is NP-Complete [25] . This paper mainly focuses on deciding the existence of PSNE in special networks like trees, complete graphs, and graphs with bounded circuit rank. The circuit rank of an undirected graph is the minimum number of edges that must be removed from the graph to make it acyclic.

In the second problem setting, also known as Altruistic Network Modification (in short ANM), we can add or delete an edge from the altruistic network, and each such operation has a non-negative cost associated with it. The aim here is to decide if a target strategy profile can be made a PSNE by adding or deleting edges with certain budget constraints. This problem was first studied by [24] where they showed that ANM is an NP-Complete problem. This problem enables policymakers to strategically run campaigns to make a society more altruistic and achieve desirable outcomes like everyone wearing a mask and getting vaccinated. This paper mainly focuses on ANM in sparse input networks like trees and graphs with bounded degree. We show that the problem of deciding the existence of PSNE in BNPG game with asymmetric altruism is polynomial-time solvable if the input network is either a tree [Theorem 4], complete graph [Theorem 7] or graph with bounded circuit rank [ Theorem 6] . Moreover, in Theorem 4, we formulated a non-trivial ILP and depicted a greedy polynomial time algorithm [Algorithm 1] to solve it. This strengthens the tractable results for tree, complete graph and graph with bounded circuit rank in [25, 18] as the previous results were depicted for BNPG games without altruism. However, the problem is open for graphs with bounded

Our work is related to [25] who initiated the study of computing a PSNE in BNPG games. Their results were strengthened by [18] who studied the parameterized complexity of deciding the existence of PSNE in BNPG game. Recently, [22] studied about public goods games in directed networks and showed intractibility for deciding the existence of PSNE and for finding MSNE. Our work is also related to [24] who intiated the study of Altruistic Network Modification in BNPG game. [16, 21] also discussed different ways to capture altruism. In the non-altruistic setting, [14] worked on modifying networks to induce certain classes of equilibria in BNPG game. Our work is part of graphical games where the fundamental question is to determine the complexity of finding an equilibrium [8, 9, 13] . Our model is also related to the best-shot games [7] as it is a special case of BNPG game. [11, 17, 20, 15] also discussed some important variations of graphical games.

Let [n] denote the set {1, . . . , n}. Let G = (V, E) be an input network with n vertices (each denoting a player). The input network is always an undirected graph. Let H = (V, E ′ ) be an altruistic network on the same set of n vertices. The altruistic network can be directed or undirected graph. An undirected edge between u, v ∈ V is represented by {u, v}. Similarly a directed edge from u to v is represented by (u, v) . N v is the set of all neighbours (resp. out-neighbours) of the vertex v in an undirected (resp. directed) altrusitic network H. Note that N v is a subset of neightbours of v in G. A Binary Networked Public Goods (BNPG) game with asymmetric (resp. symmetric) altruism can be defined on the input graph G and the directed (resp. undirected) altruistic network H as follows. We are given a set

On Binary Networked Public Goods Game with Altruism of players V, and the strategy set of every player in V is {0, 1}. For a strategy profile

In this paper, we will be using playing 1 (resp. 0), investing (resp. not investing) and strategy

is a non-decreasing externality function in x and a, c v ∈ R + ∪{0} are constants. c v can also interpreted as the cost of investing for player v. We denote a BNPG game with altruism by

In this paper, we study a general case of BNPG game called heterogeneous BNPG game where every player v ∈ V need not have the same externality function g v (.) and constant c v . If nothing is mentioned, by BNPG game, we are referring to a heterogeneous BNPG game. In this paper, we also study a special case of BNPG game called fully homogeneous BNPG game where

In this paper, we mainly focus on pure-strategy Nash Equilibrium (PSNE). A strategy profile x = (x v ) v∈V is said to be a PSNE of a BNPG game with altruism if the following holds true for all v ∈ V and for all

In this paper, we also look at ε-Nash Equilibrium. Let ∆ v be a distribution over that strategy set {0, 1}. We define Supp(∆ v ) to be the support of the distribution ∆ v , that is,

In this paper we study a special case of Altruistic Network Modification (ANM) which was also studied by [24] . If nothing is mentioned, by ANM, we are referring to the special case which we will now discuss. We are given a target profile x * , BNPG game on an input graph G, an initial altruistic network H, a cost function C(.) and budget B. In this setting, we can add or delete an edge e from H and each such operation has a nonnegative cost C(e) associated with it. We denote an instance of ANM with altruism by

The aim of ANM with altruism is to add and delete edges in H such that x * becomes a PSNE and the total cost for adding and delete these edges is atmost B. Note that if the altruism is asymmetric (resp. symmetric), then we can add or delete directed (resp. undirected) edges only. Also note that it is not allowed to add any edge between two nodes u, v if {u, v} / ∈ E.

▶ Definition 1 (Circuit Rank). [18] Let the number of edges and number of vertices in a graph G be m and n respectively. Then circuit rank is defined to be m − n + c (c is the number 3

In this section, we present the results for deciding the existence of PSNE and finding MSNE in BNPG game with altruism. [25] showed that the problem of checking the existence of PSNE in BNPG game without altruism is polynomial time solvable when the input network is a tree. We now provide a non-trivial algorithm to show that the problem of checking the existence of PSNE in BNPG game with asymmetric altruism is polynomial time solvable when the input network is a tree.

▶ Theorem 4. The problem of checking the existence of PSNE in BNPG game with asymmetric altruism is polynomial time solvable when the input network is a tree.

is said to be a valid configuration if there exists a strategy profile x ′ = (x ′ v ) v∈V such that the following holds true:

The number of neighbours of u and v playing 1 in x ′ is n u and n v respectively ▷ None of the players in the sub-tree rooted at v deviate from their strategy in x ′ Note that the root node r doesn't have a parent. Hence, we consider an imaginary parent p with x p = 0 and g p (x) = 0 for all x ⩾ 0. Hence if there is a tuple in the table of root node r then we can conclude that there is a PSNE otherwise we can conclude that there is no PSNE.

Leaf nodes: We add a tuple (x u , n u , Table for the leaf node can be clearly constructed in polynomial time.

Non-leaf nodes: For each tuple (x u , n u , x v , n v ) we do the following. If there is no child

to the table of v. Otherwise we do the following. Let U 1 be the set of children u ′ of v which have tuples of the type (x v , n v , 1, n u ′ ) in their table but don't have tuples of the type (x v , n v , 0, n u ′ ). Let U 0 be the set of children u ′ of v which have tuples of the type (x v , n v , 0, n u ′ ) in their table but don't have tuples of the type (x v , n v , 1, n u ′ ). Let U be the set of children u ′ of v which have tuples of the type (x v , n v , 1, n u ′ ) and (x v , n v , 0, n u ′ ) in their table. First let us consider the case when x v = 1. Now for each u ′ ∈ (U 1 ∪ U ) ∩ N v , we find the tuple (1, n v , 1, n u ′ ) in its table so that a · ∆g u ′ (n u ′ ) is maximized and let this value be y u ′ . Similarly for each u ′ ∈ (U 0 ∪ U ) ∩ N v , we find the tuple (1, n v , 0, n u ′ ) in the table so that a · ∆g u ′ (n u ′ − 1) is maximized and let this value be z u ′ . Also ∀u ′ ∈ (U 1 ∪ U 0 ∪ U ) \ N v , C V I T 2 0 1 6

On Binary Networked Public Goods Game with Altruism y u ′ = z u ′ = 0. If u ∈ N v then y u = a · ∆g u (x u + n u − 1) otherwise y u = 0. Now we include the tuple (x u , n u , x v = 1, n v ) in the table if the optimal value of the following ILP is at least

The above ILP can be solved in polynomial time as follows. First sort the values a u ′ = |y u ′ − z u ′ | in non-increasing order breaking ties arbitrarily and order the vertices in U as {u 1 , . . . , u |U | } as per this order, that is, a ui ⩾ a uj if i ⩽ j. Then we traverse the list of values in non-increasing order and for the u ′ corresponding to the value, we choose

For a more detailed description, please see the Algorithm 1. Now we show the correctness. Consider an optimal solution x * . Let i be the smallest number such that x ui 1 = 1 as per our algorithm and in optimal solution it is 0. Similarly let i ′ be the smallest number such that x u i ′ 1 = 0 as per our algorithm and in optimal solution it is 1. We now swap the values of the variables x ui 1 and x

in the optimal solution without decreasing the value of the objective function. Let us assume that i < i ′ . Then it must be the case that y ui > z ui otherwise ∀j > i, we will have x uj 1 = 1 as per our algorithm. Hence by swapping in the optimal solution, the value of the objective function increases by at least a ui − a u i ′ which is a non-negative quantity. Similarly when i ′ < i, it must be the case that y ui ⩽ z ui otherwise ∀j > i, we will have x uj 1 = 0 as per our algorithm. Hence by swapping in the optimal solution, the value of the objective function increases by at least a u i ′ − a ui which is a non-negative quantity. By repeatedtly finding such indices i, i ′ and then swaping the value of x ui 1 and x

in the optimal solution leads to our solution.

An analogous procedure exists for the case where

The above ILP can be solved in polynomial time as follows. First sort the values a u ′ = |y u ′ − z u ′ | in non-increasing order breaking ties arbitrarily and order the vertices in U as

Then we traverse the list in non-increasing order and for the u ′ corresponding to the value, we choose

Now we show the correctness. Consider an optimal solution x * . Let i be the smallest number such that x ui 1 = 1 as per our algorithm and in optimal solution it is 0. Similarly let i ′ be the smallest number such that x u i ′ 1 = 0 as per our algorithm and in optimal solution it is 1. We now swap the values of the variables x ui 1 and x

in the optimal solution without increasing the value of the objective function. Let us assume that i < i ′ . Then it must be the case that y ui ⩽ z ui otherwise ∀j > i, we will have x uj 1 = 1 as per our algorithm. Hence by swapping in the optimal solution, the value of the objective function decreases by at least a ui − a u i ′ which is a non-negative quantity. Similarly when i ′ < i, it must be the case that y ui > z ui otherwise ∀j > i, we will have x uj 1 = 0 as per our algorithm. Hence by swapping in the optimal solution, the value of the objective function increases by at least a u i ′ − a ui which is a non-negative quantity. By repeatedtly finding such indices i, i ′ and then swapping the value of x ui 1 and x

in the optimal solution leads to our solution.

As mentioned earlier if there is any tuple in the table of the root r, then we conclude that there is a PSNE otherwise we conclude that there is no such PSNE. ◀ Algorithm 1 ILP Solver

x ui 0 ← 0 and x ui 1 ← 1 10: else 11: if y ui > z ui then 12: x ui 0 ← 0 and x ui 1 ← 1 13: else 14: x ui 0 ← 1 and 

Proof. In the proof of Theorem 1, just discard those entries from the table of u ∈ S which don't have x u = x ′ u and n u = n ′ u . ◀ [18] showed that the problem of checking the existence of PSNE in BNPG game without altruism is polynomial time solvable when the input network is a graph with bounded circuit rank. By using the algorithm in Theorem 1 as a subroutine and extending the ideas of [18] to our setting, we show the following.

▶ Theorem 6. The problem of checking the existence of PSNE in BNPG game with asymmetric altruism is polynomial time solvable when the input network is a graph with bounded circuit rank. 

This can be decided by a polynomial time algorithm due to Corollary 5. We return yes if such a PSNE exists.

If no such PSNE exists for every choice of pair of tuples t and s, then we return no. The running time of our algorithm is n O(d) . Now we show that our algorithm returns correct output for every input instance.

In one direction, let there be a PSNE

This implies that our algorithm will return yes.

In the other direction, let our algorithm return yes. This means for a pair of 25, 18] showed that the problem of checking the existence of PSNE in BNPG game without altruism is polynomial time solvable when the input network is a complete graph. By extending their ideas to our setting, we show the following. 

In one direction, suppose there is a PSNE x * with k players playing 1, then there is a subset I 1 ⊆ V of at least k players such that ∀v ∈ I 1 , c v ⩽ ∆g v (k − 1) + a · u∈Nv ∆g u (k − 1). Therefore, |R 1 (k)| ⩾ k. Now in x * we have |V| − k players who are playing 0. It implies that there a subset I 2 ⊆ V of at least |V| − k players such that ∀v ∈ I 2 , c v ⩾ ∆g v (k) + a · u∈Nv ∆g u (k). Therefore, |R 0 (k)| ⩾ |V| − k. Now observe that a player v / ∈ R 1 (k) plays 0 in x * otherwise v would deviate from its decision. This implies that v ∈ R 0 (k) as v does not deviate from playing 0 (recall, x * is a PSNE).

In the other direction, let it be the case that |R 1 (k)| ⩾ k, |R 0 (k)| ⩾ |V| − k and |R 0 (k) \ R 1 (k)| = |V \ R 1 (k)|. Now let us construct a strategy profile x * = (x v ) v∈V as follows. First, ∀v ∈ V \ R 1 (k), set x v = 0. Now consider a subset I ⊆ R 1 (k) ∩ R 0 (k) such that |I| = |V| − k − |V \ R 1 (k)|. We always can choose such a subset I due to the following: 

Now, ∀v ∈ I, set x v = 0. For the rest of the k players who are not part of both I and V \ R 1 (k), we set their strategies as 1. Now we claim that x * is a PSNE. A player v with x v = 1 won't deviate as they are part of R 1 (k). Similarly, a player v with x v = 0 won't deviate as they are part of R 0 (k). Hence x * is a PSNE.

Having proved our claim, we now present the polynomial time algorithm. First check whether the strategy profile where all players do not invest is PSNE or not. This can checked in polynomial time. If it is not a PSNE, then check whether the strategy profile where all players invest is PSNE or not. This can also be checked in polynomial time. If it is not a PSNE, then check whether there is a k such that 0 < k < |V|, |R 1 (k)| ⩾ k, |R 0 (k)| ⩾ |V| − k and |R 0 (k) \ R 1 (k)| = |V \ R 1 (k)|. If there is such a k, then there exists a PSNE otherwise there is no PSNE. ◀

The problem of deciding the existence of BNPG game with altruism where the atruistic network is empty is known to be NP-Complete [25] . Therefore, we look at the deciding the complexity of finding an ε-Nash equilibrium in BNPG game with symmetric altruism. We show that it is PPAD-Hard. Towards that, we reduce from an instance of Directed public goods game which is known to be PPAD-hard [22] . In directed public goods game, we are given a directed network of players and the utility

▶ Theorem 8. It is PPAD-hard to find an ε-Nash equilibrium of the BNPG game with symmetric altruism, for some constant ε > 0.

Let the constant a be 1. ∀u ∈ V, c uin = 1 + 2ε and c uout = p. Now define the functions g w (.) as follows:

Now we show that given any ε-Nash equilibrium of the BNPG game with altruism , we can find an ε-Nash equilibrium of the directed public goods game in polynomial time. Let (∆ u ) u∈V ′ be an ε-Nash equilibrium of the BNPG game with symmetric altruism. For all v ∈ {u in : u ∈ V}, we have the following:

Hence 1 can't be in the support of ∆ v . Therefore ∀u ∈ V, ∆ uin (0) = 1. Now we show that (∆ u ) u∈V is an ε-Nash equilibrium of the directed public goods game where ∆ u = ∆ uout ∀u ∈ V. Now consider a strategy profile (x v ) v∈V ′ such that ∀u ∈ V, we have x uin = 0. Now let (x v ) v∈V be a strategy profile such that ∀u ∈ V we have x u = x uout . Then we have the following:

Using the above equality and the fact that ∀u ∈ V, ∆ uin (0) = 1, we have

1}, for all x u ∈ Supp(∆ u ), we have the following:

Hence, given any ε-Nash equilibrium of the BNPG game with symmetric altruism , we can find an ε-Nash equilibrium of the directed public goods game in polynomial time. This concludes the proof of this theorem. ◀

In this section, we present the results for Altruistic Network Modification. First let us call ANM with altruism as heterogeneous ANM with altruism whenever the BNPG game is heterogeneous. Similarly let us call ANM with altruism as fully homogeneous ANM whenever the BNPG game is fully homogeneous. [18] depicted a way to reduce heterogeneous BNPG game to fully homogeneous BNPG game. By extending their ideas to our setting, we show Lemmata 9-11 which will be helpful to prove the theorems on hardness in this section.

Using this instance, we create an instance

of fully homogeneous ANM with asymmetric altruism. First we set a ′ = a and B ′ = B.

Next we construct the graph G ′ = (V ′ , E ′′ ) as follows. 1) ). We now recursively define a function g(.) as follows.

. Now we construct the altruistic network H ′ = (V ′ , E) as follows:

). For remaining edges e which are allowed to be added to H ′ , C ′ (e) = B + 1.

This completes the description of fully homogeneous ANM with asymmetric altruism. We now claim that the instance of heterogeneous ANM with asymmetric altruism is a yes instance iff the instance of fully homogeneous ANM with asymmetric altruism is a yes instance.

In one direction, let heterogeneous ANM with asymmetric altruism be a yes instance.

was removed from H, then remove (u i , u j ) from H ′ . Now we show that x ′ becomes a PSNE. For all i ∈ [n], let the number of neighbours of v i playing 1 in x * be n vi . Then the number of neighbouts of u i playing 1 in x ′ is 2 + (i − 1)n + n vi . Now for all i ∈ [n] such that x ′ ui = x vi = 1, we have ∆g(2 + (i − 1)n + n vi ) + a uj ∈Nu i ∆g(2 + (j − 1)n + n vj + x ′ uj − 1) = ∆g vi (n vi ) + a vj ∈Nv i ∆g vj (n vj + x vj − 1) ⩾ c. Hence u i doesn't deviate from playing 1. Similarly for all i ∈ [n] such that x ′ ui = x vi = 0, we have ∆g(2 + (i − 1)n + n vi ) + a uj ∈Nu i ∆g(2 + (j − 1)n + n vj + x ′ uj ) = ∆g vi (n vi ) + a vj ∈Nv i ∆g vj (n vj + x vj ) ⩽ c. Hence u i doesn't deviate from playing 0. Remaining nodes u in G ′ don't deviate from playing 1 as ∆g(0) and ∆g(1) is at least c. Hence fully homogeneous ANM with asymmetric altruism is a yes instance.

In other direction, let fully homogeneous ANM with asymmetric altruism be a yes instance. First observe that an edge not having both the endpoints in the set {u i : i ∈ [n]} can't be added to H ′ otherwise the total cost of the edges added would exceed B. For all

, let the number of neighbours of v i playing 1 in x * be n vi . Then the number of neighbouts of u i playing 1 in x ′ is 2 + (i − 1)n + n vi . Now for all i ∈ [n] such that x ′ ui = x vi = 1, we have ∆g vi (n vi ) + a vj ∈Nv i ∆g vj (n vj + x vi − 1) = ∆g(2 + (i − 1)n + n vi ) + a uj ∈Nu i ∆g(2 + (j − 1)n + n vj + x ′ uj − 1) ⩾ c. Hence v i doesn't deviate from playing 1. Similarly for all i ∈ [n] such that x ′ ui = x vi = 0, we have ∆g vi (n vi ) + a vj ∈Nu i ∆g vj (n vj + x vj ) = ∆g(2 + (i − 1)n + n vi ) + a uj ∈Nu i ∆g(2 + (j − 1)n + n vj + x ′ uj ) ⩽ c. Hence v i doesn't deviate from playing 0. Hence heterogeneous ANM with asymmetric altruism is a yes instance. ◀

Proof.

Using this instance, we create an instance

of fully homogeneous ANM with symmetric altruism. First we set a ′ = a and B ′ = B.

Next we construct the graph G ′ = (V ′ , E ′′ ) as follows.

). We now recursively define a function g(.) as follows.

. Now we construct the altruistic network H ′ = (V ′ , E) as follows:

For remaining edges e which are allowed to be added to H ′ , C ′ (e) = B + 1.

This completes the description of fully homogeneous ANM with symmetric altruism. We now claim that the instance of heterogeneous ANM with symmetric altruism is a yes instance iff the instance of fully homogeneous ANM with symmetric altruism is a yes instance.

In one direction, let heterogeneous ANM with symmetric altruism be a yes instance. For

, let the number of neighbours of v i playing 1 in x * be n vi . Then the number of neighbouts of u i playing 1 in x ′ is 2 + (i − 1)n + n vi . Now for all i ∈ [n] such that x ′ ui = x vi = 1, we have ∆g(2 + (i − 1)n + n vi ) + a uj ∈Nu i ∆g(2 + (j − 1)n + n vj + x ′ uj − 1) = ∆g vi (n vi ) + a vj ∈Nv i ∆g vj (n vj + x vj − 1) ⩾ c. Hence u i doesn't deviate from playing 1. Similarly for all i ∈ [n] such that x ′ ui = x vi = 0, we have ∆g(2 + (i − 1)n + n vi ) + a uj ∈Nu i ∆g(2 + (j − 1)n + n vj + x ′ uj ) = ∆g vi (n vi ) + a vj ∈Nv i ∆g vj (n vj + x vj ) ⩽ c. Hence u i doesn't deviate from playing 0. Remaining nodes u in G ′ don't deviate from playing 1 as ∆g(0) and ∆g(1) is at least c. Hence fully homogeneous ANM with symmetric altruism is a yes instance.

In other direction, let fully homogeneous ANM with symmetric altruism be a yes instance. First observe that an edge not having both the endpoints in the set {u i : i ∈ [n]} can't be added to H ′ otherwise the total cost of the edges added would exceed B. For all i, j ∈ [n], if {u i , u j } was added to H ′ , then add {v i , v j } to H. Similarly for all i, j ∈ [n], if {u i , u j } was removed from H ′ , then remove {v i , v j } from H. Now we show that x * becomes a PSNE. For all i ∈ [n], let the number of neighbours of v i playing 1 in x * be n vi . Then the number of neighbouts of

Hence v i doesn't deviate from playing 0. Hence heterogeneous ANM with symmetric altruism is a yes instance. ◀ ▶ Lemma 11. Given an instance of heterogeneous ANM with symmetric altruism such that input network has maximum degree 3, cost c v of investing is same for all players v in the heterogeneous BNPG game and there are three types of externality functions, we can reduce the instance heterogeneous ANM with symmetric altruism to an instance of fully homogeneous ANM with symmetric altruism such that the input network has maximum degree 13.

be an instance of heterogeneous ANM with symmetric altruism. Let us partition V into three sets V 1 , V 2 and V 3 such that ∀i ∈ [3] and ∀v ∈ V i , we have

Using this instance, we create an instance (

of fully homogeneous ANM with symmetric altruism. First we set a ′ = a and B ′ = B.

Next we construct the graph G ′ = (V ′ , E ′′ ) as follows.

It is easy to observe that the maximum degree of G ′ is 13. Let f (x) = 1 + ⌊ x−2 4 ⌋ and h(x) = x − (2 + 4(f (x) − 1)). We now recursively define a function g(.) as follows.

. Now we construct the altruistic network H ′ = (V ′ , E) as follows:

For remaining edges e which are allowed to be added to H ′ , C ′ (e) = B + 1.

This completes the description of fully homogeneous ANM with symmetric altruism. We now claim that the instance of heterogeneous ANM with symmetric altruism is a yes instance iff the instance of fully homogeneous ANM with symmetric altruism is a yes instance.

In one direction, let heterogeneous ANM with symmetric altruism be a yes instance. For

, let the number of neighbours of v i playing 1 in x * be n vi . Then the number of neighbouts of u i playing 1 in x ′ is 2 + 4(p(i) − 1) + n vi . Now for all i ∈ [n] such that

Hence u i doesn't deviate from playing 0. Remaining nodes u in G ′ don't deviate from playing 1 as ∆g(0) and ∆g(1) is at least c. Hence fully homogeneous ANM with symmetric altruism is a yes instance.

In other direction, let fully homogeneous ANM with symmetric altruism be a yes instance. 

Hence v i doesn't deviate from playing 1. Similarly for all i ∈ [n] such that x ′ ui = x vi = 0, we have ∆g p(i) (n vi ) + a vj ∈Nu i ∆g p(j) (n vj + x vj ) = ∆g(2 + 4(p(i) − 1) + n vi ) + a uj ∈Nu i ∆g(2 + 4(p(j) − 1) + n vj + x ′ uj ) ⩽ c. Hence v i doesn't deviate from playing 0. Hence heterogeneous ANM with symmetric altruism is a yes instance. ◀ ANM with asymmetric altruism is known to be NP-complete when the input network is a clique [24] . We show a similar result for trees by reducing from Knapsack problem.

▶ Theorem 12. For the target profile where all players invest, ANM with asymmetric altruism is NP-complete when the input network is a tree and the BNPG game is fully homogeneous.

Proof. We reduce from the decision version of the KNAPSACK Problem. In Knapsack problem, we are give a set of items 1, . . . , n with profits p 1 , . . . p n and weights w 1 , . . . w n . The aim is to check whether there exists a subset S of items such that i∈S p i ⩾ P and i∈S w i ⩽ W . Now we create an instance of ANM with asymmetric altruism. We set a = 1. The input graph G (V,E) is defined as follows

Let the initial altruistic graph H(V, E ′ ) be empty. Let the target profile x * have all the players investing (i.e, playing 1). Now we define the functions g u (.) for all u ∈ V. g u2n+1 (x) = 0 for all x ⩾ 0. For all i ∈ [n], g ui (x) = x · p i for all x ⩾ 0. For all i ∈ [n], g un+i (x) = x · P for all x ⩾ 0. For all i ∈ [2n + 1], c ui = P . Now we define the cost of the introducing an atruistic edge. The cost of introducing the edge (u 2n+1 , u i ) is w i . For remaining edges e which are allowed to be added to H, cost of adding e is 0. Let the total budget be W . This completes the description of the instance of ANM with asymmetric altruism. Now we show that KNAPSACK Problem is a yes instance iff ANM with asymmetric altruism is a yes instance. In other direction, let KNAPSACK problem be a yes instance. Then there is a subset S of items such that i∈S p i ⩾ P and i∈S w i ⩽ W . Now if we introduce the set of altruistic edges {(u 2n+1 , u i ) : i ∈ S} ∪ {(u i , u n+i ) : i ∈ [n]}, then the target profile becomes a PSNE and the total of introducing these edges is at most B. Hence ANM with asymmetric altruism is a yes instance.

In the other direction, let the ANM with asymmetric altruism be a yes instance. Then there is a set of altruistic edges S ′ of total cost at most B such that when they are introduced the target profile becomes a PSNE. Let S := {i : (u 2n+1 , u i ) ∈ S ′ }. Hence if the subset S of items is chosen then we have i∈S p i ⩾ P and i∈S w i ⩽ W . Hence the KNAPSACK problem is a yes instance.

Applying Lemma 9 concludes the proof of this theorem. ◀ ANM with symmetric altruism is known to be NP-complete when the input network is a clique [24] . We show a similar result for trees by reducing from Knapsack problem.

▶ Theorem 13. For the target profile where all players invest, ANM with symmetric altruism is NP-complete when the input network is a tree and the BNPG game is fully homogeneous.

Proof. We reduce from the decision version of the KNAPSACK Problem. In Knapsack problem, we are give a set of items 1, . . . , n with profits p 1 , . . . p n and weights w 1 , . . . w n . The aim is to check whether there exists a subset S of items such that i∈S p i ⩾ P and i∈S w i ⩽ W . Now we create an instance of ANM with symmetric altruism as follows. We set a = 1. The input graph G (V,E) is defined as follows

Let the initial altruistic graph H(V, E ′ ) be empty. Let the target profile x * have all the players investing (i.e, playing 1). Now we define the functions g u (.) for all u ∈ V. g u2n+1 (x) = 0 for all x ⩾ 0. For all i ∈ [n], g ui (x) = x · p i for all x ⩾ 0. For all i ∈ [n], g un+i (x) = x · P for all x ⩾ 0. For all i ∈ [2n + 1], c ui = P . Now we define the cost of the introducing an atruistic edge. For all i ∈ [n], the cost of introducing the edge {u 2n+1 , u i } is w i . For all i ∈ [n], the cost of introducing the edge {u n+i , u i } is 0. Let the total budget be W . This completes the description of the instance of ANM with symmetric altruism. Now we show that KNAPSACK Problem is a yes instance iff ANM with symmetric altruism is a yes instance. In other direction, let KNAPSACK problem be a yes instance. Then there is a subset S of items such that i∈S p i ⩾ P and i∈S w i ⩽ W . Now if we introduce the set of altruistic edges {{u 2n+1 , u i } : i ∈ S} ∪ {{u n+i , u i } : i ∈ [n]}, then the target profile becomes a PSNE and the total of introducing these edges is at most B. Hence ANM with symmetric altruism is a yes instance.

In the other direction, let the ANM with symmetric altruism be a yes instance. Then there is a set of altruistic edges S ′ of total cost at most B such that when they are introduced the target profile becomes a PSNE. Let S := {i : {u 2n+1 , u i } ∈ S ′ }. Hence if the subset S of items is chosen then we have i∈S p i ⩾ P and i∈S w i ⩽ W . Hence the KNAPSACK problem is a yes instance.

Applying Lemma 10 concludes the proof of this theorem. ◀ is a clause C j = (l j 1 ∨ l j 2 ∨ l j 3 ) which is not satisfied. Hence {h(l j 1 ), y j }, {h(l j 1 ), y j }, {h(l j 1 ), y j } are not added to H. But then y j would deviate from playing 1 which is a contradiction. Hence f is a satisfying assignment. Hence the instance of (3, B2)-SAT is a yes instance.

Applying Lemma 11 concludes the proof of this theorem. ◀

We complement the previous result by showing that ANM with asymmetric altruism is FPT for the parameter maximum degree of the input graph.

▶ Theorem 15. For any target profile, ANM with asymmetric altruism can be solved in time 2 ∆/2 · n O (1) where ∆ is the maximum degree of the input graph.

Proof. [24] showed that solving an instance of asymmetric altruistic design is equivalent to solving n different instances of Minimum Knapsack problem and each of these instances have at most ∆ + 1 items. In Minimum Knapsack problem, we are give a set of items 1, . . . , k with costs p 1 , . . . p k and weights w 1 , . . . w k . The aim is to find a subset S of items minimizing i∈S w i subject to the constraint that i∈S p i ⩾ P . We assume that i∈ [k] p i ⩾ P otherwise we don't have any feasible solution. Let us denote the optimal value by OP T . Let W := i∈[k] w i . Now consider the following integer linear program which we denote by ILP w :

The above integer linear program can be solved in time 2 k/2 · k O(1) [10] . Now observe that for all w ⩾ OP T , the optimal value OP T w of ILP w is at least P . Similarly for all w < OP T , the optimal value OP T w of the ILP w is less than P . Now by performing a binary search for w on the range [0, W ] and then solving the above ILP repeatedly, we can compute OP T in time 2 k/2 · log W · k O (1) . See Algorithm 2 for more details.

As discussed earlier, an Instance of asymmetric altruistic design is equivalent to solving n different instances of Minimum Knapsack problem and each of these instances have at most ∆ + 1 items. Hence ANM with asymmetric altruism can be solved in time 2 ∆/2 · |x| O (1) where x is the input instance of ANM with asymmetric altruism. ◀ We conclude our work by discussing about the approxibimility of ANM with symmetric altruism. [24] showed a 2 + ε approximation algorithm for ANM with symmetric altruism when the target profile has all players investing. However, for arbitrary target profile they showed that ANM with symmetric altruism is NP-complete when the input network is a complete graph and the budget is infinite. We show a similar result for graphs with bounded degree by reducing from (3, B2)-SAT. . We now create an which is not satisfied. Hence {h(l j 1 ), y j }, {h(l j 1 ), y j }, {h(l j 1 ), y j } are not added to H. But then y j would deviate from playing 1 which is a contradiction. Hence f is a satisfying assignment. Hence the instance of (3, B2)-SAT is a yes instance.

Applying Lemma 11 concludes the proof of this theorem. ◀

In this paper, we first studied the problem of deciding the existence of PSNE in BNPG game with altruism. We depicted polynomial time algorithms to decide the existence of PSNE in trees, complete graphs and graphs with bounded We also that the problem of finding MSNE in BNPG game with altruism is PPAD-Hard. Next we studied Altruistic Network modification. We showed that ANM with either symmetric or asymmetric altruism is NP-complete for trees. We also showed that ANM with symmetric altruism is para-NP-hard for the parameter maximum degree whereas ANM with asymetric altruism is FPT for the parameter maximum degree.

One important research direction in ANM is to maximize the social welfare while ensuring that the target profile remains a PSNE. Another research direction is to improve the approximation algorithms of [24] for ANM with asymmetric altruism for trees and graphs with bounded degree. Another interesting future work is to look at other graphical games by considering altruism.

Approximation hardness of short symmetric instances of max-3sat

Social pressure, altruism, free-riding, and noncompliance in mask wearing by us residents in response to covid-19 pandemic

Externalities and compulsary vaccinations

Why do so many Americans refuse to wear face masks? Politics is part of it -but only part

Social distancing as a public good under the covid-19 pandemic

Altruism and vaccination intentions: Evidence from behavioral experiments

Optimal equilibria of the best shot game

The complexity of computing a nash equilibrium

Nash equilibria in graphical games on trees revisited

Exact exponential algorithms

Network games. The review of economic studies

Concept of public goods can be experimentally put to use in pandemic for a social cause

Pure nash equilibria: Hard and easy games

Inducing equilibria in networked public goods games through network structure modification

Efficient equilibria in a public goods game

Public goods: A survey of experimental research

Incentive-based search for efficient equilibria of the public goods game

On parameterized complexity of binary networked public goods game

Parameterized algorithms for kidney exchange

Supermodular network games

On the windfall of friendship: inoculation strategies on social networks

Public Goods Games in Directed Networks

Coronavirus: Why some countries wear face masks and others don

Altruism design in networked public goods games

Computing equilibria in binary networked public goods games

We now show that ANM with symmetric altruism is known to be para-NP-hard for the parameter maximum degree of the input network even when the BNPG game is fully homogeneous. Towards that, we reduce from an instance of (3, B2)-SAT which is known to be NP-complete [1] . (3, B2) -SAT is the special case of 3-SAT where each variable x i occurs exactly twice as negative literalx i and twice as positive literal x i . ▶ Theorem 14. For the target profile where all players invest, ANM with symmetric altruism is known to be para-NP-hard for the parameter maximum degree of the input network even when the BNPG game is fully homogeneous.Proof. To show the NP-hardness, we reduce from an instance of (3, B2)-SAT which we denote by (. We now create an instance of ANM with symmetric altruism as follows. Let the initial altruistic network H be empty and a = 0.5. Input graph G =(V,E) for the input BNPG game is as follows:Now observe that the degree of every vertex in G is at most 3. We now define (c v ) v∈V andTarget profile x * has all the players investing. Now define the cost of adding edges to H. Cost of adding an edge from the setThis completes the construction of the instance of ANM with symmetric altruism. Now we prove that the instance of (3, B2)-SAT is a yes instance iff the instance of ANM with symmetric altruism is a yes instance. In one direction, let (3, B2)-SAT be a yes instance and its satisfying assignment be f :, we now do the following:The total cost of adding the above edges is n(2 + c). It is easy to observe that after adding the above edges, x * becomes a PSNE. Hence the instance of ANM with symmetric altruism is a yes instance.In the other direction, let ANM with symmetric altruism be a yes instance. First observe that for all i ∈ Solve ILP w and ILP w+1 .

if OP T w < P and OP T w+1 ⩾ P then 6: return w + 1 7: else if OP T w < P and OP T w+1 < P then 8: ℓ ← w + 1 9: w ← ⌊ ℓ+r 2 ⌋ 10:else 11: r ← w 12: w ← ⌊ ℓ+r 2 ⌋ 13:end if 14: end while instance of ANM with symmetric altruism as follows. Let the initial altruistic network H be empty and a = 2. Input graph G =(V,E) for the input BNPG game is as follows: Now we prove that the instance of (3, B2)-SAT is a yes instance iff the instance of ANM with symmetric altruism is a yes instance. In one direction, let (3, B2)-SAT be a yes instance and its satisfying assignment be f :, we now do the following:▷ Let h −1 (z i ) be part of the clauses C j and C j ′ . Then add the edgesIt is easy to observe that after adding the above edges, x * becomes a PSNE. Hence the instance of ANM with symmetric altrusim is a yes instance.In the other direction, let ANM with symmetric altruism be a yes instance. First observe that for all i ∈