Friend of My Friend: Network Formation with Two-Hop Benefit

Abstract

How and why people form ties is a critical issue for understanding the fabric of social networks. In contrast to most existing work, we are interested in settings where agents are neither so myopic as to consider only the benefit they derive from their immediate neighbors, nor do they consider the effects on the entire network when forming connections. Instead, we consider games on networks where a node tries to maximize its utility taking into account the benefit it gets from the nodes it is directly connected to (called direct benefit), as well as the benefit it gets from the nodes it is acquainted with via a two-hop connection (called two-hop benefit). We call such games Two-Hop Games. The decision to consider only two hops stems from the observation that human agents rarely consider “contacts of a contact of a contact” (3-hop contacts) or further while forming their relationships. We consider several versions of Two-Hop games which are extensions of well-studied games. While the addition of two-hop benefit changes the properties of these games significantly, we prove that in many important cases good equilibrium solutions still exist, and bound the change in the price of anarchy due to two-hop benefit both theoretically and in simulation.

1 Introduction

How and why people form ties is a critical issue for understanding the fabric of social networks. In various models, including public good games (see e.g., [8, 12, 17] and the references therein), stable matching (see e.g., [6, 16]), and others [5], it is often assumed that people make strategic decisions or form friendships/partnerships based on the benefit they derive from their immediate neighbors, independent of the rest of the network. On the opposite end of the spectrum, many game-theoretic models such as [15] and its many extensions (see [7] and references therein) consider players that form a network with the goal of maximizing their influence over nodes that can be far away from them, i.e., caring not just about their local neighborhood but about their position in the entire network. In many settings, however, agents are neither so myopic as to consider only the benefit they get from their immediate connections alone, nor do they form relations considering the effects on the whole network. For example, one of the aspects people consider when forming a relationship is the two-hop benefit they can get from the friends of such a friend. This is especially important in the world of business, but also occurs naturally when forming everyday friendships and collaborations: we judge people by the company they keep, and become better friends with those whose friends we like as well. Inspired by such settings, we consider games on networks where a node tries to maximize its utility taking into account the benefit it gets from the nodes it is directly connected to (called direct benefit), as well as the benefit it gets from the nodes it is acquainted with via a two-hop connection (called two-hop benefit). We will call such games Two–Hop Games.

Before formally defining Two–Hop games, we point out a difference between two concepts - one being the ability to form a relationship with someone, and another being the ability to extract benefit out of a direct or two-hop acquaintance. The ability to form a relationship indicates whether two agents can interact directly with each other (due to geographical proximity, etc.) The ability to extract benefit out of a direct or two-hop acquaintance instead tells us about how compatible the agents are with each other. We distinguish between these two concepts by having two arbitrary undirected graphs:

• Connection Graph(G _C ): The edges in this graph denote which pairs of agents are able to form connections/relationships with each other.

• Friendship Graph(G _F ): The edges in this graph indicate whether two agents are compatible with each other. If they are compatible, then they can derive benefit if they are connected either directly or via a two-hop connection. Thus G _F governs the utility extracted from acquaintances (the formation of which is governed by G _C ).

Two–Hop Games

Now we will formally define Two-Hop games. Each Two-Hop game is defined by the following: We have a Connection Graph (G _C ) and a Friendship Graph (G _F ) as described above, both having the same node set. These nodes are the players of the game. We want to model the case where different friendships and relationships can be of different strength. Thus the strategy of a node, say u, consists of choosing to contribute to each of its adjacent edges (u v) in G _C , with an amount $0\leq x^{uv}_{u}\leq 1$. The total contribution that a node can make is limited by a constant k. The contribution $x^{uv}_{u}$ represents the effort u puts into its relationship with v. Note that we restrict the contributions of u to edges adjoining u in G _C , as those are the nodes that u can connect to directly. We can represent the strategy of u in a compact way using a vector $\mathbf {x_{u}}=(x_{u}^{uv})$ with number of components equal to the degree of u in G _C . As usual, x _−u =(x ₁,⋯ ,x _u−1,x _u+1,⋯ ,x _n ) denotes the strategies of all other nodes except u. We restrict ${\sum }_{(uv)\ni u}x^{uv}_{u} = \min (k, d_{u})$ where d _u is the degree of u in G _C . The limit of k represents the fact that any person has only finite time/resources at his disposal to form acquaintances, and thus can contribute at most k effort in total. The objective of a node u is to maximize its utility given by

$$\begin{array}{@{}rcl@{}} U_{u}(\mathbf{x_{u}}, \mathbf{x_{-u}}) &=& \sum\limits_{(uw)\in G_{F}\cap G_{C}} r_{uw}\left(x^{uw}_{u}, x^{uw}_{w}\right)\\&&+\sum\limits_{\begin{array}{c}(uw)\in G_{F}\\(uv), (vw)\in G_{C}\end{array}} s_{uvw}\left(x^{uv}_{u}, x^{uv}_{v}, x^{vw}_{v}, x^{vw}_{w}\right) \end{array} $$

(1)

The function $r_{uw}(x^{uw}_{u}, x^{uw}_{w})$ represents the strength of the direct relationship between u and w: this depends only on the effort that u and w put into the relationship. The function $s_{uvw}(x^{uv}_{u}, x^{uv}_{v}, x^{vw}_{v}, x^{vw}_{w})$ represents the strength of a bond between u and w formed due to a mutual friend v. The strength of such a two-hop acquaintance can potentially depend on all the intermediate efforts on the 2-link path. Thus the utility of a node u is the total strength of its (direct and 2-hop) relationships with all of its neighbors in G _F , i.e., the nodes who actually benefit node u. Note that the two-hop benefit over all two-hop paths between u and w adds up: a larger number of mutual friends increases how much people can influence each other, a larger number of internal referrals increases the chances that a job-seeker gets an interview, etc. We are interested in the following two types of Two-Hop games.

• Sum Two–Hop Games (S2H Games):

  $$\begin{array}{@{}rcl@{}} r_{uv}\left(x^{uv}_{u},x^{uv}_{v}\right) &=& x^{uv}_{u}+x^{uv}_{v} \end{array} $$

  (2)
  $$\begin{array}{@{}rcl@{}} s_{uvw}\left(x^{uv}_{u}, x^{uv}_{v}, x^{vw}_{v}, x^{vw}_{w}\right) &=& \alpha \cdot\left(x^{uv}_{u}\cdot x^{vw}_{v} + x^{vw}_{w}\cdot x^{uv}_{v}\right) \end{array} $$

  (3)

  We call 0≤α≤1 the two-hop benefit factor. It represents the intuitive notion that a two-hop acquaintance between u and w via v should yield less benefit than a direct acquaintance. Equation (2) defines the strength of a relationship as the addition of strengths in each direction: strength in the direction $u\rightarrow v$ is given by $x^{uv}_{u}$, and in the reverse direction given by $x^{uv}_{v}$. Similarly the term $x^{uv}_{u}\cdot x^{vw}_{v}$ in (3) represents the strength of the two-hop acquaintance between u and w via v in the direction $u\rightarrow v\rightarrow w$ (e.g., how likely information is to pass from u to w via v). The term $x^{vw}_{w}\cdot x^{uv}_{v}$ is the strength of this indirect relationship in the other direction.

  If not for the 2-hop effect, S2H Games would be a simple variation of network contribution games [5] (see Section 2 for further details) and it is not difficult to show that in such a game, a Nash Equilibrium always exists and its Price of Anarchy is 1. As we show in this paper, however, the addition of 2-hop benefit changes the properties of this game.

• Min Two–Hop Games (M2H Games):

  $$\begin{array}{@{}rcl@{}} r_{uv}\left(x^{uv}_{u}, x^{uv}_{v}\right) &=& \min\left(x^{uv}_{u},x^{uv}_{v}\right) \end{array} $$

  (4)
  $$\begin{array}{@{}rcl@{}} s_{uvw}\left(x^{uv}_{u}, x^{uv}_{v}, x^{vw}_{v}, x^{uw}_{w}\right) &=& \alpha\cdot \min\left(x^{uv}_{u},x^{uv}_{v}\right) \cdot \min\left(x^{vw}_{v},x^{vw}_{w}\right) \end{array} $$

  (5)

  In M2H games, a relationship is only strong if both participants contribute a lot of effort. As before, the strength of a 2–hop effect is the product of the strengths of the two relationships in the 2–link path, attenuated by a factor α∈[0,1].

  Without the 2-hop effect, this game is essentially a fractional version of k-stable matching (see Section 2 for details). As discussed in Section 2, existing work on stable matching immediately implies various results about the existence and quality of equilibrium for such a game. However, just as with S2H games, the addition of 2-hop benefit greatly changes the properties of this game.

To assess the quality of a solution M in S2H and M2H games, we will use social welfare, given by $U(M) = {\sum }_{u} U_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$. For S2H games, we will focus on the existence and the quality of Nash Equilibria (NEs). For M2H games, however, using the concept of 2-strong Nash Equilibrium, also called pairwise equilibrium [21], makes more sense to consider than the concept of Nash equilibrium. A pairwise equilibrium (PE) is a solution stable with respect to deviations by any pair of players, as well as any single player. This is consistent with previous work on such games: if we think of integral versions of these games (where $x_{u}^{uv}$ is constrained to be in {0,1}) as network formation games, then S2H corresponds to a game where a node can unilaterally form a link and reap the benefits of this link, while M2H corresponds to a game in which both endpoints of a link are needed to form this link. Traditionally pairwise equilibria have been used to analyze the latter types of games [5, 13] simply due to the fact that any single-player deviation would not be able to create a new link. Similarly, in our fractional version of M2H, it is reasonable to expect for a pair of people (u,v) to increase the level of their friendship at the same time, thus increasing $\min (x_{u}^{uv}, x_{v}^{uv})$. Thus for M2H games, we study pairwise equilibria and investigate their quality compared to the optimal solution. We call the ratio between the quality of the worst pairwise equilibrium and the optimal solution 2-PoA to differentiate it from the PoA (price of anarchy) with respect to Nash Equilibria.

Our Contribution

We define Two-Hop games, which are natural generalizations of well-studied games. As mentioned above, S2H games without any two-hop benefit reduce to simple network contribution games; thus they are potential games, an integral NE always exists for them, and they have Price of Anarchy (PoA) of 1. As we show in Section 3, despite the introduction of two-hop benefit, a NE always exists for general S2H games. However, an integral NE may no longer exist, and S2H games are not potential games (except for some special cases: see Theorem 4).

The introduction of two-hop benefit also changes the behavior of PoA. For the important special cases of $G_{F}\subseteq G_{C}$ (I can connect to all of my friends) and $G_{C}\subseteq G_{F}$ (I can only connect to friends), we show a tight PoA bound of 1+α k, and in the very nice case when G _F and G _C are complete graphs, the PoA is $\frac {1+\alpha k}{1+\alpha (k-1)}$. As we show in Theorem 5, in general for S2H games PoA decreases as the overlap between G _F and G _C increases, i.e., PoA decreases as nodes get more opportunities to form acquaintances with nodes they are compatible with. For example, if every node has at least k/2 nodes which are its neighbors in both G _F and G _C , then the PoA is at most 1+2α k. Note that for the most reasonable values of α the PoA bounds above are rather small. For example, we can often assume that a single direct friendship brings more benefit than connecting to someone solely because of the 2-hop contacts being made; this is quantified by assuming that $\alpha \leq \frac {1}{k}$ since any node can have at most k friends. For this range of α, the above PoA bounds become merely 2 and 3. We further consider weighted S2H games (See Section 3.2) in which different acquaintances can potentially yield different intrinsic benefit, and show that the results obtained for S2H games also hold for weighted games when $G_{F}\subseteq G_{C}$.

Because of its connection to many-to-many stable matching, it is not difficult to show that for M2H games without 2-hop benefit an integral pairwise equilibrium (PE) always exists, and 2-PoA is at most 2. For general M2H games with 2-hop benefit, however, we show that an integral PE may not exist (existence of a fractional PE for this and related games is an important open question). For the cases when PE does exist, our main result for M2H games proves that 2-PoA for the important case of $G_{C}\subseteq G_{F}$ is at most 2+2α k, which for the “reasonable” range of α∈[0,1/k] mentioned above evaluates to at most 4.

For weighted versions, we also carried out simulations by scattering nodes uniformly in a unit square and experimented with different classes of weight functions which depend on the distance between the nodes. We found that although the worst-case PoA bounds could be quite high, the average quality of equilibria was very close to the optimum. We also found that although integral NE may not exist for S2H games, in our simulations for majority of the instances it did exist, and simple dynamics converged to it extremely quickly in almost all instances. Our simulations also showed that as two-hop benefit decreases, nodes transition from forming small interconnected clusters to forming more of a “backbone” tree-like network.

Remark

Instead of assuming a limit of k on the contributions that each node can make, we can instead consider the case when the limits are different for each node, say k _u for node u. In this case all of our results hold with k replaced by $\max _{u} k_{u}$, except the cases 1 and 3 of Theorem 5, where we will mention the difference in the bounds in the discussion following the proof.

2 Related Work and Impact of Two-Hop Benefit

Network formation games, and games on networks more generally, have been studied extensively. In many network formation games, nodes connect to each other with the goal of maximizing their utility, which depends on their position in the whole network. For example, it may depend on the average distance to the rest of the nodes, or on various other notions of centrality and node “importance”. [15] studies the setting where nodes try to minimize their average distance to the other nodes by building network links, however the fixed link cost for each link they decide to build acts as a damping factor. [15] goes on to analyze how the existence and the quality (Price of Anarchy) of Nash equilibria varies with respect to the connection cost of establishing each new link. The authors in [13] analyzed the bilateral connection version (i.e., building a link requires both endpoints to cooperate) of the above model in [15] and bounded the efficiency of pairwise (2-strong Nash) equilibria along with the range of link costs to guarantee the existence of such equilibria. The authors in [22] consider the scenario where each node has a budget for purchasing links and different preferences for connecting to different nodes, with nodes trying to purchase adjacent edges to connect to the nodes that matter the most. The version considered in [7] is similar to [22] except that the nodes aim for maximizing their betweenness centrality. For further examples of the approach where nodes have the goal of maximizing their utility based on their position in the whole network, see [3, 9, 14, 19] and the references in [7].

On the other hand, in many models of the network formation games, the agents are concerned only about the direct benefit they derive from their immediate neighbors. One such class of models is stable matching and its variants. Stable matching was introduced in [16] under the basic setting of nodes partitioned into two sets (i.e., a bipartite graph), with each node having preferences over the nodes from the other set, and each node desiring to get matched (i.e., get assigned) to at most one node from the other set as high as possible in its preference list. The stable matching problem investigates the possibility of stable outcomes (called stable matchings) in this setting, where stability corresponds to no two nodes prefering each other over their present partners. Different variants of stable matching problems have been studied intensively over the last few decades. On the algorithmic side, existence, efficient algorithms, and improvement dynamics for stable matchings over bipartite graphs have been of interest (for references, see standard textbooks such as [18, 23, 25]). Many-to-one and many-to-many versions of stable matching have also been studied in the literature and it has been shown that stable matchings exist when the underlying graph is bipartite [6, 26, 27]. Another example of network formation games where the agents are concerned only about the benefit derived from their immediate neightbours are network contribution games introduced in [5]. Here authors study 2-strong Nash equilibria under the setting of each node having a constraint on the total budget it can invest on adjoining edges in order to maximize its utility. For more examples, see [2, 4, 8, 11, 12, 17].

However, in this paper we are interested in settings where agents may neither be concerned about the actions of remote nodes nor be so myopic as to consider only the benefit they derive from their immediate neighbors. Two-Hop games fall under this category. The decision to consider only two hops stems from the observation that human agents rarely consider “contacts of a contact of a contact” (3-hop contacts) or further while forming their relationships. As mentioned above, we distinguish between the ability of a pair of agents to interact directly (represented by the connection graph G _C ) and their capability of being able to derive benefit if they are connected directly or via a two-hop connection (represented by the friendship graph G _F ). The friendship graph G _F can be seen as a social context which dictates the benefits obtained by the nodes by playing a game on the connection graph G _C . Some other work which explores different forms of social context are [10] and [20]. In this work, the cost of a node in a resource-sharing game depends on its own cost and the costs of its “friends”, where friend nodes are its neighbors in an underlying social network.

Let us describe the impact that introducing two-hop benefit with social context can have. Without two-hop benefit, the utility of a node u in S2H games becomes

$$\begin{array}{@{}rcl@{}} U_{u}(\mathbf{x_{u}},\mathbf{x_{-u}}) =\sum\limits_{\begin{array}{c}(uv)\in u\\(uv)\in G_{C}\cap G_{F}\end{array}} \left(x^{uv}_{u}+x^{uv}_{v}\right) \end{array} $$

(6)

This is most closely related to one of the models for network contribution games considered in [5] where the authors also consider that the utility obtained by a node from contributing an edge is given by $c^{uv}\cdot (x^{uv}_{u}+x^{uv}_{v})$ where c ^uv>0 is an edge-specific constant. S2H games without two-hop benefit can be seen as a variation of this game where we have c ^uv=1 if $(uv)\in G_{C}\cap G_{F}$ and 0 otherwise, however we place an additional upper bound of 1 on $x^{uv}_{u}$’s along with a limit ${\sum }_{(uv)\in u}x^{uv}_{u}=k$. In [5], when the utility function of a node u is given by ${\sum }_{(uv)\in u}c^{uv}(x^{uv}_{u}+x^{uv}_{v})$, the authors prove that a (integral) Nash Equilibrium always exists and that the PoA is 1. Here by integral NE we mean that $x^{uv}_{u}$’s are restricted to {0,1}. Although we place an additional constraint of $x^{uv}_{u}\leq 1$, using similar techniques it is easy to show that for S2H games with α=0 (i.e., no two-hop benefit) an integral NE always exists and PoA is 1. With addition of two-hop benefit, we can view S2H games as an extension of such network contribution games: we show that a NE still exists (although it may not be integral), and that the PoA does not increase by too much.

For M2H games, if we do not have any two-hop benefit then the utility of a node becomes

$$\begin{array}{@{}rcl@{}} U_{u}(\mathbf{x_{u}},\mathbf{x_{-u}}) = \sum\limits_{(uv)\in G_{F}\cap G_{C}} x^{uv} = \sum\limits_{(uv)\in G_{F}\cap G_{C}} \min(x^{uv}_{u}, x^{uv}_{v}) \end{array} $$

(7)

For k=1, the version of this with edge weights becomes equivalent to stable matching. More precisely, it becomes the “correlated” version of stable matching [1] for which a stable matching is known to exist for arbitrary graphs, and the 2-PoA (quality of stable matching compared to the optimum one) is bounded by 2 [4]. For k>1, this becomes a many-to-many version of stable matching, where each node is allowed to match with k partners. Many-to-one and many-to-many versions of stable matching have been studied in the literature and it has been shown that stable matchings exist when the underlying graph is bipartite [6, 26, 27]. In fact, many bilateral network formation games can also be interpreted in the stable matching framework. However, to the best of our knowledge the correlated version of many-to-many stable matching has not been studied before. Nevertheless, it is easy to show using the techniques from [4] that existence of integral stable matching and the same bound on 2-PoA still holds. This even holds for fractional stable matching, by which we mean that a node u is allowed to choose an adjacent edge with a fractional amount $0\leq x^{uv}_{u}\leq 1$ such that ${\sum }_{(uv)\ni u}x^{uv}_{u}=k$, and an edge (u v) is present in a matching with fraction $\min (x^{uv}_{u}, x^{uv}_{v})$. This is a precise generalization of the usual notions of stable matching and pairwise equilibrium, since a single node can destroy or weaken an edge, but both endpoints are required to form or strengthen an edge. With the introduction of two-hop benefit, an integral pairwise equilibrium may no longer exist; however we show that the quality of pairwise equilibrium remains good in the instances when they do exist.

3 Sum Two–Hop Games

Recall that in S2H games, the utility U _u (x _u ,x _−u ) of a node u is obtained by substituting (2) and (3) into (1) which gives us

$$\begin{array}{@{}rcl@{}} U_{u}(\mathbf{x_{u}},\mathbf{x_{-u}}) &=& \sum\limits_{(uv)\in G_{C}\cap G_{F}} \left(x^{uv}_{u}+x^{uv}_{v}\right)\\&& + \alpha \cdot{} \sum\limits_{\begin{array}{c}(uv), (vw)\in G_{C}\\ s.t. \,\,(uw)\in G_{F}\end{array}} \left(x^{uv}_{u}\cdot x^{vw}_{v} + x^{vw}_{w}\cdot x^{uv}_{v}\right) \end{array} $$

(8)

We introduce some more notation which will prove useful later. Define the quantities $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ and $U^{in}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ as:

$$\begin{array}{@{}rcl@{}} U^{out}_{u}(\mathbf{x_{u}}, \mathbf{x_{-u}}) &=&\sum\limits_{(uv)\in G_{F}\cap G_{C}} x^{uv}_{u} + \alpha \cdot \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\(uv),(vw)\in G_{C}\end{array}} x^{uv}_{u} \cdot x^{vw}_{v} \end{array} $$

(9)

$$\begin{array}{@{}rcl@{}} U^{in}_{u}(\mathbf{x_{u}}, \mathbf{x_{-u}}) &=&\sum\limits_{(uv)\in G_{F}\cap G_{C}} x^{uv}_{v}+ \alpha \cdot \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\ (uv),(vw)\in G_{C}\end{array}}{x^{vw}_{w} \cdot x^{uv}_{v}} \end{array} $$

(10)

Note that

$$\begin{array}{@{}rcl@{}} U_{u}(\mathbf{x_{u}}, \mathbf{x_{-u}}) = U^{out}_{u}(\mathbf{x_{u}}, \mathbf{x_{-u}}) + U^{in}_{u}(\mathbf{x_{u}}, \mathbf{x_{-u}}) \end{array} $$

(11)

$U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ can be interpreted as the share of the utility of node u that u gets by virtue of its own contributions, i.e., this is the share of utility U _u (x _u ,x _−u ) in which the contributions made by u play a role. Similarly, $U^{in}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ can be interpreted as the share of the utility U _u (x _u ,x _−u ) independent of the contributions made by u. Let us define U ^out(M) for any solution M as ${\sum }_{u} U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ and U ⁱⁿ(M) as ${\sum }_{u} U^{in}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$. Furthermore, it can be observed that

$$\begin{array}{@{}rcl@{}} U(M) = 2\cdot U^{out}(M) = 2\cdot U^{in}(M) \end{array} $$

(12)

Without any two-hop benefit, there always exists an integral pure NE for S2H games (i.e., a NE in which all the contributions are either 0 or 1) and they are exact potential games. Integral NE’s represent an important combinatorial case where the contributions of the agents take fixed values, i.e., either I am or I am not a friend of someone. Such solutions make sense in some applications in which a relationship either exists or does not (e.g., having a physical network link between two parties), but for less tangible relationships such as friendships, fractional solutions make sense as well. For our game, even after introducing two-hop benefit (i.e., α>0), we can prove that a NE always exists for S2H games using Proposition 20.3 of [24]. However, all NE may be fractional, and this ceases to be a potential game.

Theorem 1

For S2H games, a pure Nash Equilibrium always exists.

Proof

We begin the proof by defining some notation. Let d _u denote the degree of node u in G _C . If $v_{1}, v_{2},\ldots , v_{d_{u}}$ are neighbors of u in G _C then the strategy space of u is a set of d _u -dimensional vectors given by:

$$\begin{array}{@{}rcl@{}} S_{u} = \{\mathbf{x_{u}}: \mathbf{\underline{0}}\preceq \mathbf{x_{u}}\preceq \mathbf{\underline{1}} \,\, \textit{and} \sum\limits_{(uv_{i})\ni u}x^{uv_{i}}_{u}= \min\{k, d_{u}\}\} \end{array} $$

(13)

where by $\mathbf {\underline {0}}$ and $\mathbf {\underline {1}}$ we denote the vectors with all components zero and one respectively. Let S denote S ₁×S ₂×…×S _n . Define a preference relation ≽ _u for a node u on the set S as follows: For x,y∈S, we have y≽ _u x whenever the utility of the node u in the outcome y is at least as much as its utility in the outcome x.

We will prove that a NE exists for S2H games using Proposition 20.3 of [24]. Proposition 20.3 of [24] states that we have a (pure) Nash Equilibrium whenever the strategy space S _u of each node is a non-empty, compact, convex set and the preference relation ≽ _u continuous and quasi-concave on S _u for each node u. We will explain the terms as we will encounter them in the proof. We will prove the existence of NE by showing that each of these conditions hold for S2H games.

• S _u is a non-empty, compact and convex set for each node u: If there are no isolated nodes in G _C , as we have assumed already, then the set S _u is not empty as seen from (13). Since S _u is also a closed and bounded set, it is also a compact set. From (13), we can also see that it is a convex set.

• The preference relation ≽ _u is continuous for each node u: Let $\{\mathbf {x}^{k}\}\text {} _{k=0}^{\infty }$ denote a sequence of strategy profiles x ¹,x ²,⋯ with each strategy profile in the sequence $\{\mathbf {x}^{k}\}\text {} _{k=0}^{\infty }$ belonging to set S. Now let us define by what is meant by preference relation ≽ _u for a node u being continuous on S (definition taken from Section 1.7 of [24]). Suppose there are two strategy profile sequences $\{\mathbf {x}^{k}\}\text {} _{k=0}^{\infty }$ and $\{\mathbf {y}^{k}\}\text {} _{k=0}^{\infty }$ converging to x∈S and y∈S respectively such that $\mathbf {x}^{k} \succeq _{u} \mathbf {y}^{k}$ for all k. If this also implies x≽ _u y for any two such sequences of strategy profiles then the preference relation ≽ _u is said to be continuous. Recall that $\mathbf {x}^{k} \succeq _{u} \mathbf {y}^{k}$ means $U_{u}(\mathbf {x}^{k}) \geq U_{u}(\mathbf {y}^{k})$. Now for S2H games, the utility function U _u (x) is continuous in x. This continuity implies x≽ _u y where x,y∈S are limits of two sequences $\{\mathbf {x}^{k}\}\text {} _{k=0}^{\infty }$ and $\{\mathbf {y}^{k}\}\text {} _{k=0}^{\infty }$ such that $\mathbf {x}^{k} \succeq _{u} \mathbf {y}^{k}$ for all k. Thus for any node u, the preference relation ≽ _u is continuous.

• The preference relation ≽ _u is quasi-concave on S _u : Let us define B _u (x _u ,x _−u )={y _u ∈S _u :(y _u ,x _−u )≽ _u x}. Informally, if we fix x _−u then the set B _u (x _u ,x _−u ) is the set of strategies for u for which u gets at least as much utility as it gets by playing x _u . The preference relation ≽ _u is said to be quasi-concave on S _u if B _u (x _u ,x _−u ) is convex for each x∈S. Thus to prove that ≽ _u is quasi-concave on S _u , we have to prove that if (y _u ,x _−u )≽ _u x and (z _u ,x _−u )≽ _u x hold true then (λ y _u +(1−λ)z _u ,x _−u )≽ _u x holds true (where 0≤λ≤1). This follows from the linearity of U _u (x _u ,x _−u ) in x _u given x _−u , i.e.,

  $$\begin{array}{@{}rcl@{}} U_{u}(\lambda \mathbf{y_{u}} &+& (1-\lambda) \mathbf{z_{u}}, \mathbf{x_{-u}}) \\ &=& \sum\limits_{(uv)\in G_{C}\cap G_{F}} (\lambda(y^{uv}_{u}+ x^{uv}_{v})+ (1-\lambda)(z^{uv}_{u}+ x^{uv}_{v}))\\ &&+\sum\limits_{\begin{array}{c}(uv), (vw)\in G_{C}\\ s.t. \,\,(uw)\in G_{F}\end{array}}\alpha \lambda (y^{uv}_{u}\cdot x^{vw}_{v} + x^{uv}_{v}\cdot x^{vw}_{w})\\ &&+\sum\limits_{\begin{array}{c} (uv), (vw)\in G_{C}\\ s.t. \,\,(uw)\in G_{F}\end{array}} \alpha (1-\lambda) (z^{uv}_{u}\cdot x^{vw}_{v} + x^{uv}_{v}\cdot x^{vw}_{w}) \\ &=&\lambda \cdot U_{u}(\mathbf{y_{u}}, \mathbf{x_{-u}}) + (1-\lambda) \cdot U_{u}(\mathbf{z_{u}}, \mathbf{x_{-u}})\\ &\geq& \lambda \cdot U_{u}(\mathbf{x})+ (1-\lambda) \cdot U_{u}(\mathbf{x}) \geq U_{u}(\mathbf{x}) \end{array} $$

  (14)

  Hence the preference relation ≽ _u is quasi-concave on S _u for each node u.

Thus we have shown that for each node u, its strategy space S _u is a non-empty, compact, convex set and the preference relation ≽ _u is continuous and quasiconcave on S _u . Thus by proposition 20.3 of [24], a (pure) NE exists for S2H games. □

Theorem 2

There are instances of the general S2H game which do not admit any integral pure Nash equilibrium.

Proof

We will describe the construction of an instance of S2H games for arbitrary k such that an integral NE does not exist for such instances. Figure 1 shows such an instance but for k=2. To construct an instance for arbitrary k, consider three nodes u, v, w such that the edges (u v), (v w) and (w u) exist in G _C but not in G _F , i.e. (u v),(v w),(u w)∈G _C ∖G _F . We will call the triangle formed by (u v),(v w),(u w) as the central triangle. The node u is further connected to k nodes outside the central triangle in G _C , with these edges also belonging to G _F . We will call these nodes as satellite nodes of u (e.g., in Fig. 1, nodes u ₁ and a are satellite nodes of u). Similarly v and w will have their own k satellite nodes. Among these satellite nodes, we select nodes u ₁,⋯ ,u _k−1 and connect them further to k nodes using edges in $G_{C}\cap G_{F}$. We will call these k nodes as subordinate nodes of the satellite node under consideration (e.g., Fig. 1, satellite node u ₁ has y and z as its subordinate nodes). Each node of the central triangle is connected in G _F to all the subordinate nodes of its satellite nodes, however these edges do not belong to G _C . Note that there exists a special satellite node for each node of the central triangle such that it has no subordinate nodes. For example satellite node a is such a node corresponding to u. Each vertex of the central triangle is further connected in G _F to satellite nodes of the vertex of the central triangle in clockwise direction. These edges belong to G _F but not in G _C . For example, node u is connected to satellite nodes of v (only in G _F but not in G _C ). To summarize the notation for Fig. 1, the solid edges belong to $G_{C}\cap G_{F}$, semi-solid edges belong to G _C and dotted edges belong to G _F . We choose 1/k<α<1/(k−1).

Fig. 1

An integral NE does not exist for S2H game. Example shown for k=2. Note 1/k<α<1/(k−1)

Now let us prove that an integral NE does not exist for such a construction. In this proof, by $u\rightarrow v$ we will mean $x^{uv}_{u}=1$. Since we are considering only integral contributions, a satellite node, say u ₁, has to choose k edges for its contributions from k+1 adjoining edges. Thus u ₁ makes a full contribution to at least k−1 subordinate nodes of u ₁. Now we claim that a vertex of the central triangle, say u, always contributes 1 to the edges leading to all its satellite nodes, except a, in any candidate solution for NE. To prove this claim, we show that if there is any satellite node, say u ₁ (except a), such that $x^{u u_{1}}_{u}=0$ then u can always increase its utility by making $x^{u u_{1}}_{u}=1$ by making its contribution to some other edge 0. To see it, notice that:

• Node u cannot contribute to (u a) and not to (u u ₁) because in such a case, by making $x^{ua}_{u}=0$ node u can lose utility by 1 and it can more than compensate for this loss by making $x^{u u_{1}}=1$ as it increases its utility by at least 1+α(k−1). This is because now u obtains an additional direct benefit of 1 by contributing to (u u ₁) and also gets the two-hop benefit of α(k−1) obtained from the two-hop paths of nature $u\rightarrow u_{1}\rightarrow p$ where p is a subordinate node of u ₁ as u ₁ contributes 1 to at least k−1 of its subordinate nodes.

• Node u would rather prefer contributing to (u u ₁) instead of (u w) because node u does not obtain any utility by contributing to (u w) as there is no direct or two-hop benefit to be obtained by contributing to (u w). There is no benefit for u in contributing to (u w) because (u w)∉G _F and no node connected to w in G _F (solid or dotted edges) has a two-hop path from u in G _C . Thus u can always make $x^{u u_{1}}_{u}=1$ instead of contributing to (u w) and get the additional utility of 1+α(k−1) as explained in the previous case.

• Suppose node u contributes 1 to edge (u v) and not to (u u ₁). Then in this case by reducing contribution to (u v) to 0, node u can lose only two-hop benefit as (u v)∈G _C ∖G _F , thus there being no direct benefit obtained by contributing to (u v). The two-hop benefit that node u can lose is at most α k because of destroying paths of the nature $u\rightarrow v\rightarrow p$ since there are at most k such paths. Thus, if u removes its contribution from (u v) and instead contributed to (u u ₁) then it gets a utility of 1+α(k−1) (as explained in the previous case) which more than compensates for its loss of at most α k utility due to our assumption that 1/k<α<1/(k−1).

Thus node u makes a contribution of 1 to the edges leading to all of its satellite nodes except a in any candidate solution for NE. Similarly, node v (and node w) makes a contribution of 1 to the edges leading to all of its satellite nodes except b (except c) in any candidate solution for NE. Thus to examine the possibility of NE, we only need to examine where the vertices of the central triangle make their remaining one contribution. In fact, the only choices for the remaining contribution for node u are edges (u a) and (u v) (and not edge (u w)) because it can always choose to contribute 1 to edge (u a) to get a direct benefit of 1 instead of contributing to edge (u w) from which it gets no utility as argued above. Similarly the only choices for the remaining contribution for node v (node w) are edges (v b),(v w) (edges (w u),(w c)). Now we will show that no combination of these choices is possible in a candidate solution for NE. For convenience we will call edges (u v),(v w),(u w) as the edges of the central triangle. Consider the following cases:

• u chooses (u a), v chooses (v b) and w chooses (w c). In such a case, u would prefer to remove its contribution from (u a) to contribute to (u v) instead. This is because in this process u gains the two-hop benefit of α k>1 from the satellite nodes of v which is more than the utility of 1 that it loses by removing its contribution to (u a).

• Suppose none of the edges (u a),(v b),(w c) were chosen for the remaining contributions, i.e. u chooses (u v), v chooses (v w), w chooses (w u). In this situation, by contributing to (v w), node v gets an utility (only two-hop benefit) of α(k−1) by virtue of establishing two-hop paths to (k−1) satellite nodes of w where w makes its (k−1) contributions (i.e., nodes w ₁,⋅,w _k−1). However, by removing its contribution to (v w) and instead choosing to contribute to (v b) gets v an utility of 1 which is more than the utility of α(k−1) it loses by removing its contribution to (v w). This is because we have assumed α<1/(k−1).

• Other then the above two cases, at least one and at most two edges from (u a),(v b),(w c) are chosen for the remaining contributions by nodes u,v,w. To cover both these cases, without the loss of generality assume that (u a) is chosen and (w c) is not chosen whereas (v b) may or may not be chosen. This means that u chooses (u a) and w chooses (w u) to contribute. Now if v has chosen (v b) then as explained in the first case above, u can remove its contribution to (u a) and choose to contribute to (v w) instead, increasing its utility in this process. Otherwise, if v has chosen (v w) to contribute then v can remove its contribution from (v w) to contribute to (v b) instead to increase its utility as explained in the second case above.

Thus we have shown that none of the combinations of choices for the remaining contributions of nodes u,v,w can lead to an integral NE, which was the only step remaining to be proven for non-existence of integral NE in this construction. Hence we have proven that there may not exist an integral NE for S2H games. □

Theorem 3

The general S2H game is not a potential game.

Proof

We give an instance where better-response dynamics can cycle, thus establishing that this is not a potential game. Figure 2 shows such an instance of S2H games. In this instance, we have k=2. Now we will describe the construction and later prove that such a cycle of states exists for this instance.

Fig. 2

Example showing that the S2H game is not a potential game. Example shown for k=2. Note that this is a partially drawn figure: not all the adjoining edges of the nodes of the central pentagon are shown except for the node u. Also, both the nodes p and q have a subgraph attached to them outside the central pentagon, analogous to subgraph formed by the nodes u ₁, u ₂, a, b around the node u.The complete example is a symmetric figure. In this example, it is possible for the nodes to exhibit a cycle of better responses, thus leading to the conclusion that the S2H game is not a potential game

Figure 2 consists a cycle of vertices p—q—u—v—w—p. We call this cycle C ₁. The total number of vertices in C ₁ is 5 (although the proof works with C ₁ hav+ing any odd number of vertices greater than 3.) We further stitch one more cycle C ₂ through these vertices by connecting each vertex to a vertex two positions ahead of it in C ₁. Since we have chosen the total number of vertices in C ₁ as an odd number greater than 3, this process ensures that connecting this way indeed creates another cycle. All the edges of C ₁ and C ₂ are in G _C ∖G _F . Each of the vertices of C ₁, say u, is connected in G _C ∖G _F to two special nodes u ₁, u ₂ which we call as satellite nodes of u. Similarly other vertices of C ₁ have their own satellite nodes with analogous notation (not all of these are pictured in the figure). Each satellite node is further connected in G _C ∖G _F to another node (for example u ₁ is connected to a) which we will call subordinate nodes of the satellite node under consideration. So, the total number of nodes in the example is 5⋅5=25. Now let us describe the edges in G _F . Each vertex of C ₁ is connected in G _F ∖G _C to subordinate nodes of its satellite nodes. For example, u is connected to a and b. In addition, each vertex of C ₁ is connected in G _F ∖G _C to satellite nodes of two vertices of C ₁ in clockwise direction, for example, node q is connected to u ₁, u ₂, v ₁, v ₂ (again, not all such edges are shown in the figure). In Fig. 2, the edges that are in G _C ∖G _F are shown in solid pattern and the edges that are in G _F ∖G _C are shown in dotted pattern. Note that since $G_{F}\cap G_{C}=\emptyset$, no node can obtain any direct benefit from connecting to a neighbor.

Let us choose the initial strategies of the nodes. We choose the strategies of satellite and subordinate nodes as follows: For the lack of choice, u ₁ contributes 1 to both (u u ₁) and (u ₁ a). Let every satellite node follow analogous strategies. Consider a subordinate node, say a. Again for the lack of choice, a contributes 1 to (u ₁ a). Let other subordinate nodes follow analogous strategies. We choose the initial strategies of the vertices of C ₁ as follows: let all the vertices of C ₁ except p and q contribute 1 to the edges leading to their satellite nodes. However, let node q contribute 1 to edges (q u), (q v) and let node p contribute to edges (p p ₁), (p u). Let us call this initial state as S ₀. Beginning with S ₀, we will show that better-response dynamics can lead to a cycle of states.

• In the first state transition, let u remove its contributions from edges (u u ₁), (u u ₂) and contribute 1 to (u v), (u w) instead. Observe that if u completely removes its contribution from the edge (u u ₁) then it loses an utility of α. This is because it loses the two-hop benefit obtained from the path $u\rightarrow u_{1}\rightarrow a$. However if u chooses to contribute to (u v) then it increases its utility by 2α because of the the two-hop benefit obtained from the paths $u\rightarrow v\rightarrow v_{1}$ and $u\rightarrow v\rightarrow v_{2}$. Using this, we conclude that if u removes its contributions from edges (u u ₁), (u u ₂) and contribute 1 to (u v), (u w) instead, then u increases its utility by 2(2α−α)=2α. Let us call this state S ₁.

• However, the transition from S ₀ to S ₁ destroys all the benefit node p had been getting in S ₀ by contributing to edge (p u). This is because in state S ₁ node p does not obtain any direct benefit by contributing to (p u) as (p u)∈G _C ∖G _F and it also does not obtain any two-hop benefit in S ₂ by contributing to (p u) as the node u does not contribute to any edge (u t) s.t. (u t)∈G _F (See (8) to see how two-hop benefit is computed). Rather than getting no benefit by contributing to (p u), node p would move this contribution to edge (p p ₂). This is because in this process p increases its utility by α due to a two-hop benefit of α obtained by establishing two-hop path directed to the subordinate node of p ₂ via p ₂. For the similar reason, node q would prefer moving its contribution from edge (q u) to edge (q q ₁). Thus in the next transition, nodes p and q move their contributions from the edges leading from them to u to edges (p p ₂) and (q q ₁) respectively. Let us call this state S ₂.

• Notice that the state S ₂ is isomorphic to S ₀ in the sense that in S ₂ nodes q and u play the roles that p and q respectively played in S ₀.

Thus we have shown that better-response dynamics can cycle in S2H games, and thus S2H games are not potential games. □

However, we now give a family of instances for which S2H games are exact potential games and an integral NE exists. Proving that the total utility changes in a fixed proportion to the change in the utility of a node u when u changes its strategy is the crucial component of proving that a game has an exact potential function. Thus to prove that a family of S2H games has an exact potential function, it would be sufficient to ensure that when a node u changes its strategy, the change in the utility of neighbors is proportional to the change in the utility of node u. This occurs, for example, if G _F is the complete graph, since then all nodes are affected by all others, and thus the change in utility for me is similar to the change in utility for the other nodes in the graph. In fact, as we show in the following Theorem 4, it is even enough that G _F always joins all pairs of nodes which have a potential two-hop path in G _C . In other words, if we let d _C (u,v) denote the distance between u and v in G _C , then the following holds.

Theorem 4

If d _u ≥k for all nodes and if the condition d _C (u,v)≤2 implies (uv)∈G _F for all the pairs of nodes then the S2H game is an exact potential game and an integral NE exists.

Proof

First we will prove the potential game part of the theorem. The condition “ d _C (u,v)≤2 implies (u v)∈G _F ” tells us that

$$\begin{array}{@{}rcl@{}} (uv)\in G_{C} &\Rightarrow& (uv)\in G_{F} \end{array} $$

(15)

$$\begin{array}{@{}rcl@{}} (uv), (vw)\in G_{C} &\Rightarrow& (uw)\in G_{F} \end{array} $$

(16)

Thus the utility of node u given by (8) takes the following simpler form where the summations just depend on G _C :

$$\begin{array}{@{}rcl@{}} U_{u}(\mathbf{x_{u}},\mathbf{x_{-u}}) &=&{}\sum\limits_{(uv)\in G_{C}} \left(x^{uv}_{u} + x^{uv}_{v}\right)\\ &&+ \alpha \cdot {}\sum\limits_{\begin{array}{c}(uv), (vw)\in G_{C}\\w\neq u\end{array}} \left(x^{uv}_{u}\cdot x^{vw}_{v} + x^{vw}_{w} \cdot x^{uv}_{v}\right) \end{array} $$

(17)

We have introduced the versions of $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ and $U^{in}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ in (9) and (10). The versions of these quantities after applying the constraints given by (15) and (16) are:

$$\begin{array}{@{}rcl@{}} U^{out}_{u}(\mathbf{x_{u}},\mathbf{x_{-u}}) &=& \sum\limits_{(uv)\in G_{C}} x^{uv}_{u} + \alpha \cdot \sum\limits_{\begin{array}{c}(uv), (vw)\in G_{C} \\ w \neq u \end{array}} x^{uv}_{u}\cdot x^{vw}_{v} \end{array} $$

(18)

$$\begin{array}{@{}rcl@{}} &=& \min(k, d_{u}) + \alpha \cdot \sum\limits_{\begin{array}{c}(uv), (vw)\in G_{C}\\ w \neq u \end{array}} x^{uv}_{u}\cdot x^{vw}_{v} \end{array} $$

(19)

$$\begin{array}{@{}rcl@{}} U^{in}_{u}(\mathbf{x_{u}},\mathbf{x_{-u}}) &=& \sum\limits_{(uv)\in G_{C}} x^{uv}_{v} + \alpha \cdot \sum\limits_{\begin{array}{c}(uv), (vw)\in G_{C}\\w \neq u \end{array}} x^{uv}_{v}\cdot x^{vw}_{w} \end{array} $$

(20)

We have also defined $U^{out}(M)={\sum }_{u} U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$. Note that (18) represents that part of the utility of u (given by (17)) which depends on the contributions made by u, whereas (20) is the remaining part which does not depend on contributions made by u. Thus in a NE, a node u must choose a strategy that maximizes $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ given the contributions of other nodes. Also, using (12) we have U(M)=2⋅U ^out(M). Thus in order to look at the behaviour of U(M) after a node changes its strategy, it is sufficient to look at the behaviour of U ^out(M) and in turn at $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ for every node.

Notice that $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ depends only on the contributions of u and its neighbors. Thus when the node p changes its strategy, $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ changes only for p and for those nodes which are neighbors of p. Let set N(p) denote the set of neighbors of p. Now let us investigate how $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ changes for p and the nodes in N(p):

• First let us consider node p. Suppose p changes its strategy from x _p to y _p . Using (19), we get the following:

  $$\begin{array}{@{}rcl@{}} U^{out}_{p}(\mathbf{y_{p}},\mathbf{x_{-p}}) &-& U^{out}_{p}(\mathbf{x_{p}},\mathbf{x_{-p}}) \\ &=&\sum\limits_{\begin{array}{c}(pv), (vw)\in G_{C}\\w \neq p \end{array}}\alpha y^{pv}_{p}\cdot x^{vw}_{v}-{}\sum\limits_{\begin{array}{c}(pv), (vw)\in G_{C}\\w \neq p \end{array}}\alpha x^{pv}_{p}\cdot x^{vw}_{v} \\ &=&\sum\limits_{v\in N(p)} \alpha y^{pv}_{p} \sum\limits_{\begin{array}{c}w\in N(v)\\w\neq p \end{array}} x^{vw}_{v}- \sum\limits_{v\in N(p)} \alpha x^{pv}_{p} \sum\limits_{\begin{array}{c} w\in N(v)\\w\neq p \end{array}} x^{vw}_{v} \\ &=& \sum\limits_{v\in N(p)} \alpha (y^{pv}_{p}-x^{pv}_{p}) \cdot (\min(k, d_{v}) - x^{pv}_{v}) \\ &=& \sum\limits_{v\in N(p)} \alpha (y^{pv}_{p}-x^{pv}_{p}) \cdot \min(k, d_{v}) \\ & & + \sum\limits_{v\in N(p)} \alpha \left(x^{pv}_{p}-y^{pv}_{p}\right) x^{pv}_{v} \end{array} $$

  Also note that the theorem statement assumes that $\min (k, d_{v})=k$ for every node. Thus the first summation in the above equation reduces to zero giving us

  $$\begin{array}{@{}rcl@{}} U^{out}_{p}(\mathbf{y_{p}},\mathbf{x_{-p}}) - U^{out}_{p}(\mathbf{x_{p}},\mathbf{x_{-p}}) = \sum\limits_{v\in N(p)} \alpha \left(x^{pv}_{p}-y^{pv}_{p}\right) x^{pv}_{v} \end{array} $$

  (21)

• Now consider the nodes in N(p). Using (19) to sum the quantity $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ over all the neighbors of u before and after p changes its strategy. The terms that change are the terms which depend on the contributions of p. Hence the cumulative change in the utilities of node in N(p) after p changes its strategy is given by:

  $$\begin{array}{@{}rcl@{}} \sum\limits_{v\in N(p)} \alpha x^{vp}_{v} \sum\limits_{z\in N(p),z\neq v} y^{pz}_{p} - \sum\limits_{v\in N(p)} \alpha x^{vp}_{v} \sum\limits_{z\in N(p),z\neq v} x^{pz}_{p} \end{array} $$

  However ${\sum }_{z\in N(p),z\neq v} y^{pz}_{p} = k-y^{pv}_{p}$ and similarly ${\sum }_{z\in N(p),z\neq v} x^{pz}_{p} = k-x^{pv}_{p}$. Using this in the above equation, the change in the value of cumulative $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ of the neighbors of p is given by

  $$\begin{array}{@{}rcl@{}} {}\sum\limits_{v\in N(p)} \alpha x^{vp}_{v} \left(k-y^{pv}_{p}\right) -{}\sum\limits_{v\in N(p)} \alpha x^{vp}_{v} \left(k-x^{pv}_{p}\right) &=&{}\sum\limits_{v\in N(p)} \alpha x^{vp}_{v} \left(x^{pv}_{p}-y^{pv}_{p}\right)\\ \end{array} $$

  (22)

As argued before, $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ changes only for p and its neighbors. Thus using (21) and (22) we can conclude that U ^out(M) increases by 2⋅$\left (U^{out}_{p}(\mathbf {y_{p}},\mathbf {x_{-p}}) - U^{out}_{p}(\mathbf {x_{p}},\mathbf {x_{-p}})\right )$ and thus U(M) increases by $4\cdot \left (U^{out}_{p}(\mathbf {y_{p}},\mathbf {x_{-p}})-\right .$ $\left . U^{out}_{p}(\mathbf {x_{p}},\mathbf {x_{-p}})\right )$ using (12). This proves that if d _u ≥k for all nodes and if the condition d _C (u,v)≤2 implies (u v)∈G _F for all the pairs of nodes then the S2H game is a potential game and U(M) and Φ(M)=U(M)/4 is an exact potential function.

Now we will prove how the existence of potential function implies the existence of an integral NE in this case. Notice that the above analysis also applies verbatim if we restrict the contribution variables $x^{uv}_{u}$ to take the values only from the set {0,1}. Hence a potential function exists and implies the existence of an integral NE for the integral version of the game. Let us denote this integral NE by M. We will now show that this integral NE is also a NE if we allow the contributions to be fractional. To prove this, we show that in the fractional case, given x _−u , there exists at least one strategy x _u for node u such that the contributions of u are integral and choosing x _u maximizes the utility of node u. Thus in M, if u could improve its utility when fractional contributions are allowed then in fact u could have also improved its utility by choosing a strategy in which contributions are integral. This would contradict our initial assumption of M being an NE for the integral version of the game and in turn prove that M is also an NE when fractional contributions are allowed. Thus now the only part that is to be proved is to show that in the fractional case, given x _−u , there exists at least one strategy x _u for node u such that the contributions of u are integral and choosing x _u maximizes the utility of node u.

As mentioned before, in a NE M, a node u must choose a strategy that maximizes $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ given x _−u . From (18), $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ can alternatively be expressed as

$$\begin{array}{@{}rcl@{}} U^{out}_{u}(\mathbf{x_{u}},\mathbf{x_{-u}}) = \sum\limits_{(uv)\in G_{C}} x^{uv}_{u} \cdot \left(1 + \sum\limits_{\begin{array}{c}(vw)\in G_{C}\\ w \neq u \end{array}}x^{vw}_{v}\right) \end{array} $$

(23)

Let us denote ${\sum }_{(vw)\in G_{C}, w \neq u}x^{vw}_{v}$ by c _v . Notice that since x _−u are fixed, the terms c _v ’s are constants. Thus applying the constraints of S2H games, the problem of maximizing $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ for u becomes a problem of choosing a strategy x _u which solves the following optimization problem

$$\begin{array}{@{}rcl@{}} & & \text{maximize} \,\,\, \sum\limits_{(uv)\ni u, (uv)\in G_{C}} x^{uv}_{u} \cdot c_{v} \\ & & \text{s.t.}\,\,\, 0\leq x^{uv}_{u} \leq 1 \,\,\text{and}\,\, \sum\limits_{(uv)\in u}x^{uv}_{u} = \min(k, d_{u}) \end{array} $$

It is easy to see that if we sort the elements in {c _v :(u v)∈u,(u v)∈G _C } in descending order and choose the top $\min (k, d_{u})$ terms from the sorted array and set the contributions $x^{uv}_{u}$’s of node u corresponding to these terms as 1, with other contributions set to 0 then this strategy solves the above problem. Note that this strategy is integral, i.e., the contributions are chosen from the set {0,1}. As argued before, given fixed x _−u , the strategies that maximize U _u (x _u ,x _−u ) are exactly the strategies that maximize $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$, and thus we have shown that there exists a strategy x _u that maximizes U _u (x _u ,x _−u ) such that all the contributions of u are integral. As discussed before, this was the remaining step to be proven in order to show that M is also an NE when fractional contributions are allowed, and hence we have proved our claim. □

3.1 Price of Anarchy

To begin with, we give a quick overview of the results of this section. We know that without any two-hop benefit, the PoA of S2H games is 1. We will first show that with two-hop benefit, PoA can become unbounded for arbitrary G _F and G _C if $G_{F}\cap G_{C} = \emptyset$. However we will later prove that as the overlap between G _F and G _C increases then the PoA for S2H games decreases and for the interesting cases of $G_{F}\subseteq G_{C}$ and $G_{C}\subseteq G_{F}$, PoA becomes 1+α k. Increasing the overlap between G _F and G _C can be interpreted as nodes getting more opportunities to become directly acquainted with the nodes they are compatible with.

Claim

For S2H games, PoA can be infinite if $G_{F}\cap G_{C} = \emptyset$.

Proof

Figure 3 shows an instance of S2H games such that $G_{F}\cap G_{C}=\emptyset$ and the PoA is infinite. In this instance, we have k=1, and three nodes u, v, w are connected to a central node z in G _C . However, G _F consists of only (u v). Thus $G_{F}\cap G_{C}=\emptyset$. For analyzing this example, we will take $p\rightarrow q$ to mean $x^{pq}_{p}=1$. It can be verified that whenever we have $z\rightarrow w$, $u\rightarrow z$ and $v\rightarrow z$ then it is a NE and has zero utility. However an optimum solution is $u\rightarrow z, z\rightarrow v, w\rightarrow z$ which has utility 2α. Thus the PoA is infinite for this instance. □

Fig. 3

The example showing that the PoA for S2H games can be infinite when $G_{C}\cap G_{F} = \phi$

Now we will show that as the overlap between G _F and G _C increases then the PoA for S2H games decreases and for the interesting cases of $G_{F}\subseteq G_{C}$ and $G_{C}\subseteq G_{F}$, PoA becomes 1+α k. First, we formally quantify what we mean by overlap between G _F and G _C . Let F _v denote the degree of v in $G_{F}\cap G_{C}$. We define overlap between G _F and G _C as $\rho (G_{F}, G_{C}) = \min _{v} F_{v}$. We now give PoA bounds for several interesting cases:

Theorem 5

For the S2H game,

• 1. For arbitrary G _F and G _C , PoA $\leq 1+\alpha k \cdot \frac {k}{\min (k,\rho (G_{F},G_{C}))}$ . Thus when there is a large overlap between G _F and G _C , say ρ(G _F ,G _C )≥k/2 then we have PoA ≤1+2αk.

• 2. Furthermore, if $G_{C} \subseteq G_{F}$ or $G_{F} \subseteq G_{C}$ then PoA ≤1+αk.

• 3. For the special case of G _F =G _C =K _n , we have PoA $=\frac {1+\alpha k}{1+\alpha (k-1)}$.

First, we give a brief outline of the proof of Theorem 5. For arbitrary G _F and G _C , the PoA bound will follow by simple observations on the minimum utility obtained by a node in a NE and its maximum attainable utility. This PoA bound can be large for a small overlap because even if a node is capable of getting little direct benefit because of its small degree in $G_{F}\cap G_{C}$ (which is a lower bound on minimum utility obtained by it in a NE), it can still get a large two-hop benefit (hence large maximum attainable utility) by connecting to a lot of its friends via G _C ∖G _F . However this changes in $G_{C}\subseteq G_{F}$ because G _C ∖G _F =∅. This also changes with $G_{F}\subseteq G_{C}$ because here if a node can get a large two-hop benefit by connecting to a lot of friends in G _C then it must have a lot of frinds, and therefore its degree in $G_{F}\cap G_{C}$ must be high. Thus these cases result in a much improved bound on PoA regardless of the overlap size. Now we will proceed to prove each of the above cases in details.

Proof (Theorem 5)

Using (12), PoA can be expressed as

$$\begin{array}{@{}rcl@{}} PoA = \max_{M\text{is a NE}}\frac{U^{out}(OPT)}{U^{out}(M)} \end{array} $$

(24)

Recall that we have defined F _u as $|\{(uv)\in u: (uv)\in G_{F}\cap G_{C}\}|$, i.e. F _u quantifies the degree of u in $G_{F}\cap G_{C}$. Let us define q _u as $\min (k, F_{u})$. Since F _u is at least as much as the overlap ρ(G _F ,G _C ), we have:

$$\begin{array}{@{}rcl@{}} q_{u} = \min(k,F_{u}) \geq \min(k, \rho(G_{F}, G_{C})) \end{array} $$

(25)

□

Lemma 1

In any NE, $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})\geq q_{u}$.

Proof (Lemma 1)

Notice from (10) that $U^{in}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ is independent of the strategy chosen by u. Thus a node u in a NE must choose a strategy which maximizes $U^{out}_{u}$. Now if $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}}) < q_{u}$ in some NE M then u can simply make $x^{uv}_{u}=1$ for any q _u edges from the set $\{(uv)\ni u: (uv)\in G_{F}\cap G_{C}\}$ to increase $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ and in turn increasing its utility. This contradicts M being an NE, hence proving that $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}}) \geq q_{u}$ in any NE.

Having proved Lemma 1, now let us continue the proof of Theorem 5. Let us consider the first case, i.e., suppose G _F and G _C are arbitrary. Consider a NE M. We already have $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})\geq q_{u}$ in any NE M. Now let us calculate the maximum value that $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ can take in any solution. An upper bound on the value of the two-hop benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ in any solution is given by

$$\begin{array}{@{}rcl@{}} \alpha \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\ (uv),(vw)\in G_{C}\end{array}}x^{uv}_{u} \cdot x^{vw}_{v} &\leq& \alpha \sum\limits_{(uv)\in G_{C}} \left[x^{uv}_{u} \sum\limits_{(vw)\in G_{C}} x^{vw}_{v}\right]\\&\leq& \alpha \sum\limits_{(uv)\in G_{C}} x^{uv}_{u} \cdot k \leq \alpha k^{2}\\ \end{array} $$

(26)

Thus the two-hop benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ in any solution can be at most α k ². We also know that the direct benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ in any solution can be at most q _u using the definition of q _u . Thus we get $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}}) \leq q_{u}+\alpha k^{2}$ in any solution. We already know using Lemma 1 that $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}}) \geq q_{u}$ in a NE. The ratio of these two bounds is 1+α k⋅k/q _u . Using (25), we get that this ratio is less than $1+\alpha k\cdot k/\min (k,\rho (G_{F}, G_{C}))$. Using this in (24), we get

$$\begin{array}{@{}rcl@{}} PoA \leq 1+\alpha k\cdot \frac{k}{\min(k,\rho(G_{F}, G_{C}))} \end{array} $$

(27)

Now suppose we have $G_{C} \subseteq G_{F}$. Let us compute an upper bound on the value of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ in any solution. When $G_{C} \subseteq G_{F}$, an upper bound on the two-hop benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ in any solution is given by

$$\begin{array}{@{}rcl@{}} \alpha \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\(uv),(vw)\in G_{C}\end{array}} x^{uv}_{u} \cdot x^{vw}_{v} \leq \alpha \sum\limits_{(uv)\in G_{C}} [x^{uv}_{u} \sum\limits_{(vw)\in G_{C}}x^{vw}_{v}] \leq \alpha k \cdot \sum\limits_{(uv)\in G_{C}} x^{uv}_{u}\\ \end{array} $$

(28)

But since $G_{C} \subseteq G_{F}$, every adjoining edge of u in G _C is also in G _F . Thus ${\sum }_{(uv)\in G_{C}} x^{uv}_{u} \leq q_{u}$. Using this in (28), we conclude that the value of two-hop benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ in any solution can be at most α k⋅q _u . We already know that direct benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}}) \leq q_{u}$ using the definition of q _u . Thus $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})\leq q_{u} (1+\alpha k)$ in any solution (in particular an optimum solution). We also know that $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})\geq q_{u}$ in a NE from Lemma 1. Combining these observations, we have

$$\begin{array}{@{}rcl@{}} PoA \leq 1+\alpha k \end{array} $$

(29)

Now suppose $G_{F} \subseteq G_{C}$. Let us compute an upper bound on the value of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ in any solution. Now the value of the two-hop benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ in any solution can be bounded as follows:

$$\begin{array}{@{}rcl@{}} \alpha \sum\limits_{(uw)\in G_{F}} \sum\limits_{(uv),(vw)\in G_{C}} x^{uv}_{u} x^{vw}_{v} \leq \alpha \sum\limits_{(uw)\in G_{F}} \sum\limits_{(uv),(vw)\in G_{C}} x^{uv}_{u} &\leq& \alpha \sum\limits_{(uw)\in G_{F}} k \\ \Rightarrow \alpha \sum\limits_{(uw)\in G_{F}} \sum\limits_{(uv),(vw)\in G_{C}} x^{uv}_{u} x^{vw}_{v} &\leq& \alpha F_{u} k \end{array} $$

(30)

Combining this with (26), we get that when $G_{F}\subseteq G_{C}$ the two-hop benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ in any solution is upper bounded by $\min (\alpha k^{2},\alpha k F_{u})$ which can also be expressed as α k q _u using (25). We already know that direct benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}}) \leq q_{u}$ in any solution using the definition of q _u . Thus we have $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})\leq q_{u}(1+\alpha k)$ in any solution (in particular an optimum solution). We also know that $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})\geq q_{u}$ in a NE from Lemma 1. Combining these observations, we have

$$\begin{array}{@{}rcl@{}} PoA \leq 1+\alpha k \end{array} $$

(31)

When G _F =K _n and G _C =K _n , we have $q_{u} = \min (k, n-1)$. The value of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ in a NE can be lower bounded by

$$\begin{array}{@{}rcl@{}} U^{out}_{u}(\mathbf{x_{u}}, \mathbf{x_{-u}}) &=& \sum\limits_{(uv)\in G_{F}\cap G_{C}} x^{uv}_{u} + \alpha \cdot \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\ (uv),(vw) \in G_{C}\end{array}} x^{uv}_{u} \cdot x^{vw}_{v} \\ &\geq& q_{u} + \alpha \cdot \sum\limits_{(uv)\in G_{C}} x^{uv}_{u} \sum\limits_{(vw)\in G_{C}, w\neq u}x^{vw}_{v} \\ &\geq& q_{u} + \alpha \cdot \sum\limits_{(uv)\in G_{C}} x^{uv}_{u} \cdot (k-1) \\ &\geq& q_{u} + \alpha q_{u} \cdot (k-1) \end{array} $$

(32)

When G _F =G _C =K _n , for an upper bound on $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ in any solution (in particular an optimum solution), we can use the upper bound of q _u (1+α k) we had derived on $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ for $G_{F}\subseteq G_{C}$, since G _F =G _C =K _n is a special case of $G_{F}\subseteq G_{C}$. Combining this upper bound with (32), we get

$$\begin{array}{@{}rcl@{}} PoA \leq \frac{1+\alpha k}{1+\alpha (k-1)} \end{array} $$

(33)

□

Note that if we have different budget constraints k _u on the total contributions of different nodes, instead of a single budget k for everyone, then almost all of our results hold with k replaced by $k_{max} = \max _{u} k_{u}$. The only exceptions are that the bound for S2H games with arbitrary G _F and G _C becomes $1+\alpha k_{max} \cdot \frac {k_{max}}{\min (k_{min},\rho (G_{F},G_{C}))}$ and the bound when both of them are complete graphs changes to (1+α k _{m i n} )/(1+α(k _{m i n} −1)), where and $k_{min}=\min _{u} k_{u}$.

Theorem 6

The bounds on the price of anarchy in Theorem 5 are asymptotically tight.

Proof

To begin, we will investigate the case when G _F and G _C can be arbitrary. For this case, the PoA is upper bounded by $1+\alpha k\cdot k/\min (k, \rho (G_{F}, G_{C})$, see Theorem 5. We have already discussed before that PoA can be infinite when ρ(G _F ,G _C )=0 using Fig. 3. Now we will describe how to construct an instance to demonstrate the tightness for any non-zero value of ρ(G _F ,G _C ).

Consider Fig. 4 where nodes have been divided into five sets A, B, C, D ₁, D ₂. Let set B contain q≤k nodes. Let set D ₁, D ₂ contain k nodes each. Let set C contain k−q nodes. Let set A contain the remaining n−3k nodes. A solid bidirectional arrow between two sets denotes that all the nodes in one set are connected with all the nodes in the other set in $G_{F}\cap G_{C}$. In Fig. 4, such solid bidirectional arrows exist between set A and B, set $B\cup C$ and set $D_{1}\cup D_{2}$. The semi-solid bidirectional arrow between set A and D ₁ denotes that all the nodes from set A are connected with all the nodes in set D ₁ only in G _F but not in G _C . The dotted bidirectional arrow between A and C denotes that all the nodes from A are connected with all the nodes in C in G _C but not in G _F . Note that there exist no edges in either G _F or G _C between the nodes belonging to the same set. From (8), in S2H games a node u has an opportunity to obtain two-hop benefit only if it is a vertex of a triangle uvw such that (u v),(v w)∈G _C and (u w)∈G _F but the two-hop benefit it actually obtains depends on the contributions made by the nodes u, v, w. Thus in Fig. 4, the only nodes that have an opportunity to obtain two-hop benefit are the nodes from set A and D ₁.

Fig. 4

Tight example for PoA of S2H games for arbitrary G _F and G _C . A solid, semi-solid, and dotted bidirectional arrow between two sets means these two sets form a complete bipartite graph with edges in $G_{F}\cap G_{C}$, G _F ∖G _C , and G _C ∖G _F respectively. The overlap is given by ρ(G _F ,G _C )=q and is dictated by the number of nodes in set B. As described in the proof of Theorem 6, in the worst Nash Equilibrium, the nodes in set B end up contributing to the edges leading to the nodes in set D ₂ and no node obtains any two-hop benefit. This key observation leads to an asymptotically tight bound on the PoA of S2H games with G _F and G _C

Recollect that for an instance, the overlap ρ(G _F ,G _C ) is the minimum number of neighbors a node has in $G_{F}\cap G_{C}$ in that instance. By the construction of the instance in Fig. 4, the overlap ρ(G _F ,G _C ) for this instance is given by the degree of a node in set A in $G_{C}\cap G_{F}$, and thus ρ(G _F ,G _C )=q for this instance. To analyze the PoA for this instance, we will use the alternate definition of PoA for S2H games given by (24). Recollect that U ^out(M) is given by ${\sum }_{u} U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ where U ^out(x _u ,x _−u ) is given by (9).

We will now construct two solutions: M ^∗ and M, such that M ^∗ is an optimal solution and M is a NE. We will show that the ratio U ^out(M ^∗)/U ^out(M) can be taken arbitrarily close to the PoA bound in Theorem 5, as desired.

Let solution M ^∗ be as follows: Any node in set A, D ₁, D ₂ has exactly k adjoining edges in G _C , thus it contributes 1 to all these edges. Let each node in B and C contribute 1 to the k adjoining edges that lead to nodes in D ₁. Now let us compute U ^out(M ^∗). Notice that in M ^∗ each node in B, C, D ₁, D ₂ contributes to the edges that are in G _C as well as G _F . Hence in M ^∗, the expression ${\sum }_{(uv)\in G_{F}\cap G_{C}} x^{uv}_{u}$ evaluates to k for any node u that belongs to $B\cup C\cup D_{1}\cup D_{2}$. However, in M ^∗ any node u∈A contributes to exactly q edges that are in $G_{F}\cap G_{C}$, i.e., the edges connecting u to the nodes in set B. Thus in M ^∗ the expression ${\sum }_{(uv)\in G_{F}\cap G_{C}} x^{uv}_{u}$ evaluates to q for any node u∈A. Thus if we sum the expression ${\sum }_{(uv)\in G_{F}\cap G_{C}} x^{uv}_{u}$ over all the nodes, we get (n−3k)q+3k⋅k=n q+3k(k−q). We already mentioned that the only nodes that have an opportunity to obtain two-hop benefit are the nodes in A and D ₁. Now recall that in Fig. 4, for every node u∈A and w∈D ₁, we have (u w)∈G _F . In the solution M ^∗ just described above, we have that

$$\begin{array}{@{}rcl@{}} x^{uv}_{u} x^{vw}_{v} = 1 \text{ and} (uw)\in G_{F} \,\,\,\,\,\, \forall u\in A, v\in B\cup C, w\in D_{1} \end{array} $$

(34)

Hence in M ^∗, for a node u∈A we have

$$\begin{array}{@{}rcl@{}} \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\ (uv), (vw)\in G_{C}\end{array}} x^{uv}_{u} x^{vw}_{v} = k^{2} \end{array} $$

(35)

Using the above equation, we get that in M ^∗ the following holds:

$$\begin{array}{@{}rcl@{}} \sum\limits_{u\in A\cup D_{1}} \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\ (uv), (vw)\in G_{C}\end{array}} x^{uv}_{u} x^{vw}_{v} = (n-3k) k^{2} \end{array} $$

(36)

Thus in total,

$$\begin{array}{@{}rcl@{}} U^{out}(M^{*}) &=& nq + 3k(k-q) + \alpha (n-3k) k^{2} \\ &\geq& (n-3k)\cdot (q + \alpha k^{2}) \end{array} $$

(37)

Now we construct a NE M as follows: Let all the nodes have the same strategy they follow in M ^∗ except that let the nodes in B and C contribute 1 to the edges leading to the nodes in D ₂. Note that in M, for any node u the expression ${\sum }_{(uv)\in G_{F}\cap G_{C}} x^{uv}_{u}$ (the direct benefit of u) takes the same value as it has in M ^∗. However notice that in M no node obtains two-hop benefit, thus we have

$$\begin{array}{@{}rcl@{}} U^{out}(M) = nq + 3k (k-q) = (n-3k)q + 3k^{2} \end{array} $$

(38)

Now we will show that M is indeed a NE: none of the nodes can change their strategies to increase their utility. Consider a node in $A\cup D_{1}\cup D_{2}$. While analyzing solution M ^∗, we argued that such a node does not have a choice for strategy in any solution but to contribute 1 to all the adjoining edges in G _C . Thus a node belonging to sets $A\cup D_{1}\cup D_{2}$ cannot change its strategy. A node $u\in B\cup C$ cannot receive any 2-hop benefit, and so it simply tries to maximize the direct benefit that depends on its contributions, i.e., $U_{u}^{out}$. Since it cannot get any 2-hop benefit, from this node’s point of view contributing to any k edges gives the same utility, and so M is a NE.

Using (37) and (38), we get

$$\begin{array}{@{}rcl@{}} \frac{U^{out}(M^{*})}{U^{out}(M)} \geq \frac{1+\alpha k\cdot k/q}{1+\frac{3k^{2}}{(n-3k)q}} \end{array} $$

(39)

Note that in this instance we had $q=\min (k, \rho (G_{F},G_{C}))$. Thus from (39), by increasing n, we can construct instances to reach within arbitrary precision of the upper bound on PoA given by 1+α k⋅k/m i n(k,ρ(G _F ,G _C ).

Now let us prove that the upper bound of 1+α k on PoA for $G_{F}\subseteq G_{C}$ and $G_{C}\subseteq G_{F}$ is tight. To prove this, we will describe an instance with G _F =G _C , thus covering both cases $G_{F}\subseteq G_{C}$ and $G_{C}\subseteq G_{F}$. The scheme of such an instance is depicted in Fig. 5. This instance consists of two complete tripartite graphs, with each partition consisting of k nodes. Sets A ₁, B ₁, C ₁ constitutes one of the tripartite graphs and sets A ₂, B ₂, C ₂ constitutes another tripartite graphs. Sets A ₁ and A ₂ also constitute a complete bipartite graph. Similarly sets B ₁,B ₂ (and sets C ₁,C ₂) constitute a complete bipartite graph. To analyze the PoA for this instance, we will use the alternate definition of PoA for S2H games given by (24). Recollect that U ^out(M) is given by ${\sum }_{u} U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ where $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ is given by (9).

Fig. 5

Tight example for PoA for the S2H game when G _F =G _C . Solid bidirectional arrow between two sets means these two sets form a complete bipartite graph. The key observation for this example is that in the worst Nash Equilibrium, all the nodes in set A ₁ contribute to the edges leading to set A ₂ and vice versa with analogous contributions for the nodes in the sets B ₁, B ₂, C ₁, C ₂. Thus in the worst NE, no node obtains any two-hop benefit. This observation leads to the bound of 1+α k being tight

The direct benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ is given by ${\sum }_{(uv)\in G_{C}\cap G_{F}}x^{uv}_{u}$ which can be at most k in any solution. From (26) the two-hop benefit component has an upper bound of α k ² in any solution. Combining these observations, $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})\leq k(1+\alpha k)$ in any solution (in particular an optimum solution). This implies that for our instance if we could find a solution in which every node obtains an utility of exactly k(1+α k) then it is an optimum solution. Now we will construct such a solution. Let all the nodes in set A ₁ contribute 1 to all the edges leading to the nodes in set B ₁. Note that this does not violate the constraint of S2H games that ${\sum }_{(uv)\in G_{c}} x^{uv}_{u}=k$ as each partition consists of exactly k nodes. Also, let all the nodes in set B ₁ (set C ₁) contribute 1 to all the edges leading to the nodes in set C ₁ (set A ₁). Let the nodes in sets A ₂, B ₂, C ₂ make analogous contributions. Let us denote this solution by M ^∗. Since G _F =G _C , the two-hop benefit component of a node u in M ^∗ is given by

$$\begin{array}{@{}rcl@{}} \alpha \cdot \sum\limits_{\begin{array}{c}(uv), (vw)\in G_{C}\\ w\neq u \end{array}} x^{uv}_{u}\cdot x^{uv}_{v} \,=\, \alpha \cdot \sum\limits_{(uv)\ni u} x^{uv}_{u} \cdot \sum\limits_{(vw)\in G_{C}, w\neq u} x^{vw}_{v} \,=\, \alpha \cdot \sum\limits_{(uv)\ni u} x^{uv}_{u} \cdot k \,=\, \alpha k^{2} \end{array} $$

In the above series of equalities, the second equality follows from the first one using the fact that in the solution M ^∗, at most one endpoint of an edge contributes to it. It is straightforward to see that the direct-benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ which is given by ${\sum }_{(uv)\in G_{C}\cap G_{F}}x^{uv}_{u}$ is exactly k for each node in solution M ^∗. Thus $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ for each node u is k(1+α k) in the solution M ^∗. As argued before, this proves that M ^∗ is an optimum solution. Thus U ^out(M ^∗)=n k(1+α k).

Now we will construct a NE, denoted by M, in which each node u obtains $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ exactly equal to k. Thus we will have U ^out(M)=n k. Combining it with U ^out(M ^∗)=n k(1+α k) proves the tightness of PoA bound of 1+α k. Now let us construct such a NE M. To construct M, let all the nodes in A ₁ contribute 1 to all the edges leading to nodes in A ₂ and vice versa. Let the nodes in all other partitions make analogous contributions. Now let us prove that M is a NE. Since the network is symmetric, to prove that M is a NE, it is sufficient to show changing its strategy cannot increase utility for any one node. Hence without loss of generalization, consider a node u∈A ₁. The only part of the utility U _u (x _u ,x _−u ) (See (8)) which depends on the contributions of u is expressed by $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u})}$. Hence to prove that the utility of u cannot increase by changing its strategy, it is sufficient to prove that $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u})}$ cannot increase by changing its strategy.

As argued before, the direct benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ can be at most k in any solution. In M, the direct benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ is exactly k. Hence if u can at all improve its utility by changing its strategy, then after changing the strategy, the two-hop benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ must go positive from its value of 0 in M. Now we will show that this cannot happen, which will prove that u cannot change its strategy. To see this, notice that whenever u changes its strategy in M, it must happen that it decreases its contributions on some of the edges leading to nodes in A ₂ and increases its contributions on some of the edges leading to nodes in B ₁ or C ₁. Let (u v) be among such edges where u increases its contribution. Without loss of generalization, let v∈B ₁. However its contribution to (u v) cannot make the two-hop benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ positive because in M the node v∈B ₁ does not make any contributions to edges of the type (v w) such that (u w)∈G _F (See (9)). This holds irrespective of u’s other contributions. Thus any change in the strategy of u cannot make the two-hop benefit component of $U^{out}_{u}(\mathbf {x_{u}},\mathbf {x_{-u}})$ positive which was the only remaining part while proving the tightness of PoA bound of 1+α k. Thus we have proved that the PoA bound of 1+α k is tight for $G_{F}\subseteq G_{C}$ and $G_{C}\subseteq G_{F}$. □

3.2 Weighted S2H Games

Sometimes a person can have different levels of intrinsic interest in different acquaintances. We incorporate this scenario into S2H games by having a positive weight f ^uv on each edge (u v)∈G _F . We call this extension as Weighted S2H Games. The utility of a node U _u (x _u ,x _−u ) in Weighted S2H games is given by:

$$\begin{array}{@{}rcl@{}} U_{u}(\mathbf{x_{u}}, \mathbf{x_{-u}}) &=&\sum\limits_{(uv)\in G_{C}\cap G_{F}} \left(x^{uv}_{u} + x^{uv}_{v}\right)f^{uv} \\&&+\alpha \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\ (uv), (vw)\in G_{C}\end{array}}{} \left(x^{uv}_{u} x^{vw}_{v}+ x^{vw}_{w} x^{uv}_{v}\right) f^{uw} \\ \end{array} $$

(40)

It is not difficult to see that the argument for the existence of NE for Weighted S2H games is the same as the argument for the existence of NE of S2H games. Also, despite having arbitrary weights on the edges of G _F , whenever we have $G_{F}\subseteq G_{C}$ the PoA proves to be at most 1+α k as it was in the absence of weights. Here by $G_{F}\subseteq G_{C}$, we mean that the unweighted version of G _F is a subset of G _C . Because of having arbitrary positive weights on the edges of G _F we do not treat the case of G _F =G _C =K _n (i.e., the unweighted G _F is equal to K _n ) separately but view it as a special case of $G_{F}\subseteq G_{C}$. Thus we get the following results:

Theorem 7

For Weighted S2H games, a Nash Equilibrium always exists.

Theorem 8

For Weighted S2H games, whenever $G_{F} \subseteq G_{C}$ we have PoA ≤1+αk.

Proof Theorem 8

We first introduce some notation. Analogous to (9) and (10) we define $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ and $U^{in}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ for Weighted S2H games:

$$\begin{array}{@{}rcl@{}} U^{out}_{u}(\mathbf{x_{u}}, \mathbf{x_{-u}}) &=&\sum\limits_{(uv)\in G_{F}\cap G_{C}} f^{uv}\cdot x^{uv}_{u} + \alpha \cdot \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\ (uv),(vw)\in G_{C}\end{array}} f^{uw}\cdot x^{uv}_{u} \cdot x^{vw}_{v}\\ \end{array} $$

(41)

$$\begin{array}{@{}rcl@{}} U^{in}_{u}(\mathbf{x_{u}}, \mathbf{x_{-u}}) &=&\sum\limits_{(uv)\in G_{F}\cap G_{C}} f^{uv} \cdot x^{uv}_{v} + \alpha \cdot \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\(uv),(vw)\in G_{C}\end{array}} f^{uw} \cdot x^{vw}_{w} \cdot x^{uv}_{v}\\ \end{array} $$

(42)

The definitions of U ^out(M), U ⁱⁿ(M) are the same as the ones in Section 3.1. We also have $U_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}}) = U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}}) + U^{in}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$. Lemma 12 also holds for Weighted S2H games. Let d _u be the degree of node u in G _C . Let E _u denote the edge set adjoining u in $G_{F}\cap G_{C}$. Define W _u as

$$\begin{array}{@{}rcl@{}} W_{u} = \max_{S\subseteq E_{u}\,\,s.t.\,|S|\leq \min(k, d_{u})} \sum\limits_{(uv)\in S}f^{uv} \end{array} $$

(43)

In other words, if we compute the cumulative weight of the member edges for each of the subsets of E _u with at most $\min (k, d_{u})$ edges then W _u is the maximum value of cumulative weight of member edges for any such set. This is the maximum direct benefit that node u could possibly attain from its incident edges. Now we will prove Lemma 2 and Lemma 3 which will help us prove Theorem 8.

Lemma 2

For Weighted S2H games, $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}}) \geq W_{u}$ in any NE.

Proof Lemma 2

Notice from (41) and (42) that $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ is the only part of the utility obtained by u that depends on the contributions made by u whereas $U^{in}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ is independent of the contributions of u. Hence a node u in a NE M must choose a strategy that maximizes $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ given the strategies played by the other nodes. If in M, we have $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}}) < W_{u}$ then the node u can increase $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ (and in turn its utility as $U^{in}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}})$ doesn’t change) by simply making a contribution of 1 to the edges that add up to W _u . This is a contradiction hence we have proved our claim. □

Lemma 3

For Weighted S2H games, whenever $G_{F}\subseteq G_{C}$ , $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}}) \leq W_{u}$ (1+αk).

Proof Lemma 3

Recall that ${\sum }_{(uv)\ni u} x^{uv}_{u} \leq \min (k,d_{u})$. Using this constraint and the definition of W _u , we have that for any solution ${\sum }_{(uv)\in G_{F}\cap G_{C}} f^{uv}\cdot x^{uv}_{u} \leq W_{u}$. Now we claim that for any solution

$$\begin{array}{@{}rcl@{}} \alpha \cdot \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\ (uv),(vw)\in G_{C}\end{array}} f^{uw} \cdot x^{vw}_{v} \cdot x^{uv}_{u} \leq \alpha k W_{u} \end{array} $$

(44)

Note that the above inequality combined with the observation ${\sum }_{(uv)\in G_{F}\cap G_{C}} f^{uv}\cdot x^{uv}_{u} \leq W_{u}$ proves the lemma. To show that this inequality always holds, consider the quantity c ^uw defined as:

$$\begin{array}{@{}rcl@{}} c^{uw} &=& \sum\limits_{v:(uv),(vw)\in G_{C}} x^{uv}_{u} x^{vw}_{v} \end{array} $$

(45)

Since the total contributions of any node are at most k and each $x^{vw}_{v}\leq 1$, then clearly $c^{uw}\leq {\sum }_{(uv)\ni u} x^{uv}_{u}\leq k$ for every u,w. Now consider fixing node u, and summing c ^uw over all w such that (u,w)∈G _F . This equals ${\sum }_{(uv)\ni u} [x^{uv}_{u} {\sum }_{(vw)\ni v} x^{vw}_{v}]$, which is at most k ².

Now let us prove that (44) holds. The left hand side of (44) can be rewritten as

$$\begin{array}{@{}rcl@{}} \alpha \cdot \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\ (uv),(vw)\in G_{C}\end{array}} {}f^{uw} \cdot x^{vw}_{v} \cdot x^{uv}_{u} &=& \alpha \cdot \sum\limits_{(uw)\in G_{F}} f^{uw} \cdot{} \sum\limits_{\begin{array}{c}(uv),(vw)\in G_{C}\\ w\neq u \end{array}} x^{uv}_{u} x^{vw}_{v} \\ &=& \alpha \cdot \sum\limits_{(uw)\in G_{F}} f^{uw} c^{uw} \end{array} $$

(46)

Since each c ^uw is bounded by k and their sum is bounded by k ², the above quality is maximized when c ^uw is set to k for the k edges (u,w)∈G _F with maximum value f ^uw, and set to 0 otherwise. Since $G_{F}\subseteq G_{C}$, then these are exactly the edges considered in W _u , and so the above quality is bounded by α k W _u , as desired. □

From Lemma 3, we have that in an optimum solution, $U^{out}_{u}(\mathbf {x_{u}}, \mathbf {x_{-u}}) \leq W_{u}$ (1+α k) for any node u. Combining this with Lemma 2 we get that PoA for Weighted S2H games is at most 1+α k, proving Theorem 8. □

Although we proved the upper bound of 1+α k on the PoA for the weighted S2H games with $G_{F}\subseteq G_{C}$, the same result does not easily extend to the case of $G_{C}\subseteq G_{F}$. This is because when $G_{C}\subseteq G_{F}$, the weights on the edges in G _F ∖G _C make it difficult to bound the two-hop benefit obtained by the nodes along the lines of (30), unlike the unweighted version.

4 Min Two-Hop (M2H) Games

Recall that M2H games are a natural extension of fractional stable matching games obtained by introducing two-hop benefit. Denoting $\min (x^{uv}_{u}, x^{uv}_{v})$ by x ^uv, the utility U _u (x _u ,x _−u ) of a node u in M2H games can be written as:

$$\begin{array}{@{}rcl@{}} U_{u}(\mathbf{x_{u}}, \mathbf{x_{-u}}) = \sum\limits_{(uv)\in G_{C}\cap G_{F}}x^{uv} + \alpha \cdot \sum\limits_{\begin{array}{c}(uv), (vw)\in G_{C}\\ (uw)\in G_{F}\end{array}} x^{uv}\cdot x^{vw} \end{array} $$

(47)

We will call the first summation in (47) as direct benefit of node u and the term with the coefficient of α in (47) as two-hop benefit of node u. Recall from Section 1 that we use the concept of pairwise equilibria (PE’s) to assess the quality of a solution in M2H games, denoting the ratio between the worst PE and the optimal solution as 2-PoA. Recall that in an integral PE all the contributions are either 0 or 1. An integral PE exists for M2H games without two-hop benefit (see Related Work). With two-hop benefit, we construct an instance of M2H games which does not admit any integral pure NE by adapting Example 1 from [11] which is an instance of stable roommates problem such that no stable matchings exist. We also give 2-PoA bounds in Thm 10 for some important cases to assess the quality of PE’s whenever they exist.

Theorem 9

There exist instances of M2H games that do not admit any integral pairwise equilibrium.

Proof

To construct an instance of M2H games where an integral PE does not exist, consider a pentagon constituted by nodes u,v,w,y,z (see Fig. 6). We will refer to this pentagon as the central pentagon. All the edges of the central pentagon are in $G_{C}\cap G_{F}$. These and the other edges that are in $G_{C}\cap G_{F}$ are shown in solid pattern in Fig. 6. Each vertex of the central pentagon has three other nodes connected to it in $G_{F}\cap G_{C}$ which we will refer as the satellite nodes of the vertex under consideration. For example v _a , v _b and v _c are the satellite nodes of the vertex v. Each satellite node is connected to 3 further nodes which we will refer as subordinate nodes of the satellite node under consideration. In Fig. 6, for convenience we have shown the subordinate nodes v _a1, v _a2, v _a3 of only one satellite node v _a , see the expanded view of the balloon pointed by the dark arrow. All other balloons consist of analogous connections networks. A vertex of the central pentagon is connected in G _F ∖G _C to all the subordinate nodes of its satellite nodes. These and the other edges that are in G _F ∖G _C are shown in dotted pattern. In addition, a vertex of the central pentagon is also connected in G _F ∖G _C to exactly one satellite node of the vertex of the central pentagon in clockwise direction. For example, vertex u is connected in G _F ∖G _C to v _a , vertex v is connected in G _F ∖G _C to w _a and so on. We set k=4 and choose 0<α<1. Now we will show that an integral PE does not exist for this instance.

Fig. 6

Example showing that an integral PE may not exist for M2H game. Example shown for k=4. Each “petal” in the figure (e.g., the ones around v _a , v _b , and v _c represent a gadget which is illustrated on the top right of the figure for node v _a . In this example, it is possible to show that the only candidates for an integral PE are the solutions where the node v contributes 1 to the edges (v _a v),(v _b c),(v _c v) (and analogous observations hold for the nodes u, w, y, z). Now each node of the central pentagon has a remaining budget of 1 for which they face a choice between the two adjoining edges of the central pentagon. The proof of Theorem 9 uses this observation along with the structure of the example to prove that no integral PE can exist for this example

To begin with, notice that for the lack of choice, all the satellite nodes and subordinate nodes contribute 1 to all the adjoining edges in G _C . Due to these nodes having a fixed strategy in any solution, we need not analyze these nodes for changing the strategy. Thus we will be concerned about the strategies of only the nodes that are the vertices of the central pentagon. Now we claim that in any candidate solution for an integral PE, node v will contribute 1 to edges $(v v_{a})$, (v v _b ) and (v v _c ). This is for the following reason: its contribution to each of these edges, say (v v _a ), fetches it a direct benefit of 1 and a two-hop benefit of 3α as $x^{vv_{a}}\cdot x^{v_{a} v_{a1}} = x^{vv_{a}}\cdot x^{v_{a} v_{a2}} = x^{vv_{a}}\cdot x^{v_{a} v_{a3}} = 1$ (refer to (47) to see how two-hop benefit is calculated). Thus contributing to (v v _a ) fetches v an utility of 1+3α in every solution. However contributing to edge (v u) (or edge (v w)) can fetch u an utility of at most 1 (or 1+α). Thus in any candidate solution for PE, v will contribute 1 to edges (v v _a ), (v v _b ) and (v v _c ). Analogous conclusions hold for the other vertices of the central pentagon. Hence to examine the possibility of an integral PE, we only need to look at the last remaining contribution that these vertices make. For the remaining contribution, each vertex of the central pentagon has to choose between two edges of the central pentagon that it is part of. Recall that it cannot contribute on the dotted edges as the dotted edges are in G _F but not in G _C . Given these choices for the remaining contributions for the vertices of the central pentagon, now we will show that any of the resulting solutions cannot be an integral PE. To see this, let us make a simple observation that after each vertex of the central pentagon chooses one of the adjoining edges of the pentagon to make its last contribution, there is at least one vertex such that if it contributes to edge e of the central pentagon then the other endpoint does not contribute to it.

Without loss of generality, say this vertex is v and it contributes to (v w) but w does not contribute to (v w). Thus v does not get any direct or two-hop benefit by contributing to (v w) by using (47). Now we have two cases: u contributing to (u v) or (u z). We will show that both cases do not lead to an integral PE.

• u contributes to (u v): Here v can choose to contribute to (u v) instead of (v w), thus making $x^{uv}=\min (x^{uv}_{u}, x^{uv}_{v})=1$ to gain a direct benefit of 1 whereas its previous contribution to (v w) fetched v no utility. Thus this case does not result in an integral PE.

• u contributes to (u z): Here we will show that both u and v can instead choose to contribute to (u v) and increase their utility, thereby proving that this case does not lead to an integral PE. By contributing to (u z) node u cannot get any two-hop benefit as there is no other neighbor of z in G _C from which there is an edge to u in G _F (Refer (47) to see when a node can obtain two-hop benefit). However, it can get a direct benefit of 1 if z also happens to be contributing to (u z), resulting in $x^{uz}=\min (x^{uz}_{u}, x^{uz}_{z})=1$. Thus its contribution (u z) can fetch node u an utility of at most 1. Now suppose u and v choose to contribute to (u v), making $x^{uv}=\min (x^{uv}_{u}, x^{uv}_{v})=1$. Thus both u and v get a direct benefit of 1 by their contribution to (u v). This leads to an increase in the utility of v as its earlier contribution to edge (v w) did not fetch any utility to v as argued before. In addition to the direct benefit of 1, node u also gets a two-hop benefit of α because now the term $x^{uv} x^{vv_{a}}$ becomes 1 and we have $(u v_{a})\in G_{F}$. Thus in this process, node u gains a total utility of 1+α which more than compensates for the utility of 1 that it could have been getting by contributing to (u z). Thus both u and v improve their utility in this process and hence this case does not lead to an integral PE.

Hence we have shown that an integral PE does not exist for the instance shown in Fig. 6 thus proving that an integral PE may not exist for M2H games. □

Theorem 10

For the M2H game:

• – If $G_{C}\subseteq G_{F}$ then 2-PoA ≤2+2αk.

• – For the special case of G _F =G _C =K _n , a PE always exists and 2-PoA tends to $\frac {1+\alpha k}{1+\alpha (k-1)}$ as $n\rightarrow \infty$.

Proof Thm 10

, Proof of case $G_{C}\subseteq G_{F}$] First let us introduce some notation. Let us define the quantities P(M) and S(M) for a solution M as:

$$\begin{array}{@{}rcl@{}} P(M) &=& \sum\limits_{u} \sum\limits_{v:(uv)\in G_{C}\cap G_{F}} x^{uv} \end{array} $$

(48)

$$\begin{array}{@{}rcl@{}} S(M) &=& \sum\limits_{u} \sum\limits_{\begin{array}{c}(uw)\in G_{F}\\ (uv), (vw)\in G_{C}\end{array}} \alpha x^{uv} x^{vw} \end{array} $$

(49)

The quantity P(M) is the combined direct benefit in M of all the nodes, and S(M) is the combined two-hop benefit in M of all the nodes. Note that U(M)=P(M)+S(M). We will prove the 2-PoA bound for $G_{C}\subseteq G_{F}$ in two steps. In the first step, we will prove that for any optimum solution M ^∗ and a PE M, we have P(M ^∗)≤2⋅U(M). Then in the second step, we will prove that S(M ^∗)≤2α k⋅U(M). Combining these two steps with the observation U(M ^∗)=P(M ^∗)+S(M ^∗) proves the desired 2-PoA bound.

Now let us prove P(M ^∗)≤2⋅U(M). Let $y^{uv}_{u}$’s (or $r^{uv}_{u}$’s) denote the contributions made by u in M ^∗ (or in M). Similarly, let $y^{uv}\!=\min (y^{uv}_{u}, y^{uv}_{v})$ and $r^{uv} = \min (r^{uv}_{u}, r^{uv}_{v})$. Tobeginwith, we claim that for an edge $(uv)\in G_{F}\cap G_{C}$ s.t. y ^uv >r ^uv, at least one of its endpoints, say u obtains a direct benefit of exactly $\min (k, d_{u})$ in M (note that no node can obtain a direct benefit of more than $\min (k, d_{u})$). In other words, for every edge (u v) ∈ B, at least one of its endpoints belongs to set A where we define set A and B as follows:

$$\begin{array}{@{}rcl@{}} A &=& \{u: \sum\limits_{(uv)\ni u} r^{uv} = \min\{k,d_{u}\}\} \\ B &=& \{(uv)\in G_{C}\cap G_{F}: y^{uv} > r^{uv}\} \end{array} $$

Suppose this claim is not true and that for some edge (u v)∈B node u (and node v) obtains a direct benefit less than $\min (k, d_{u})$ (less than $\min (k,d_{v})$) in the PE M. Since we have $G_{C}\subseteq G_{F}$, this implies that ${\sum }_{(uw)\ni u} r^{uw} \!\!< \min (k, d_{u})$ and ${\sum }_{(vy)\ni v} r^{vy} \!\!< \min (k, d_{v})$. Now combining ${\sum }_{(uw)\ni u} r^{uw} \!\!< \min (k, d_{u})$ with the constraint ${\sum }_{(uw)\ni u} r^{uw}_{u} = \min (k, d_{u})$ we get that there must exist an edge in G _C adjoining u, say (u z) s.t. $r^{uz}_{u} > r^{uz}$. Similarly, for v, there must exist an adjoining edge in G _C , say (v p) s.t. $r^{vp}_{v} > r^{vp}$. Now let us break the analysis intwo two cases:

• Let (u z)=(u v) but (v p)≠(u v): Since (u z)=(u v) we have $\min (r^{uv}_{u}, r^{uv}_{v}) < r^{uv}_{u}$, i.e. $r^{uv}_{v} \!\!< r^{uv}_{u}$. We already have $r^{vp}_{v} \!\!> r^{vp}_{p}$. Now, let v decrease $r^{vp}_{v}$ by an infinitesimal quantity 𝜖 and increase $r^{vp}_{v}$ by 𝜖. Notice that since $r^{vp}_{v} > \min (r^{vp}_{v}, r^{vp}_{p})$ decreasing $r^{vp}_{v}$ by a tiny constant does not change the utility of v. However since $r^{uv}_{v} < r^{uv}_{u}$, increasing $r^{uv}_{v}$ by 𝜖 increases r ^uv (i.e., $\min (r^{uv}_{u}, r^{uv}_{v})$. Given that (u v) is also in G _F , in this process the direct benefit of v increases, increasing the utility of v in turn. This contradicts our assumption of M being a PE.

• Let (u z)≠(u v) and (v p)≠(u v): The analysis of this case is similar to the previous case, except that both u and v simultaneously will be able to increase their contributions to (u v) by a tiny constant (this is permitted as for (u v)∈B we have r ^uv<1) and both will be able to increase their utility. This contradicts our assumption of M being a PE.

Hence we have proved that for every edge (u v)∈B, at least one of its endpoints belongs to A. Because of this, the following inequality must hold:

$$\begin{array}{@{}rcl@{}}\sum\limits_{(uv)\in B} y^{uv} \leq \sum\limits_{u\in A} \sum\limits_{\begin{array}{c}(uv)\ni u \\ (uv)\in B \end{array}} y^{uv} \end{array} $$

(50)

Now consider the edges $(uv)\in G_{F}\cap G_{C}$ which are not in B.

$$\begin{array}{@{}rcl@{}} \sum\limits_{(uv)\in B} y^{uv} + \sum\limits_{\begin{array}{c}(uv)\in G_{F}\cap G_{C}\\ (uv)\not\in B \end{array}} y^{uv} &\leq& \sum\limits_{u\in A} \sum\limits_{\begin{array}{c}(uv)\ni u\\ (uv)\in B \end{array}} y^{uv} + \sum\limits_{\begin{array}{c}(uv)\in G_{F}\cap G_{C}\\(uv)\not\in B \end{array}} y^{uv} \\ \implies \sum\limits_{(uv)\in G_{F}\cap G_{C}} y^{uv} &\leq& \sum\limits_{u\in A} \sum\limits_{(uv)\ni u} y^{uv} + \sum\limits_{u\not\in A}\sum\limits_{\begin{array}{c}(uv)\ni u\\ (uv)\not\in B \end{array}} y^{uv}\\ \end{array} $$

(51)

Let us analyze the terms that appear on the right hand side of (51):

• First let us consider the terms ${\sum }_{(uv)\ni u} y^{uv}$ for u∈A. We know that this is in total at most $\min \{k,d_{u}\}$, since this is the largest amount u can contribute to all the incident edges. However, by definition of A, we also know that $\min \{k,d_{u}\}={\sum }_{(uv)\ni u} r^{uv}$. Thus, this term is at most ${\sum }_{(uv)\ni u} r^{uv}$. This is at most the direct benefit obtained by u in M since $G_{C}\subseteq G_{F}$ and hence is at most U _u (r _u ,r _−u ).

• Now consider the terms ${\sum }_{(uv)\ni u} {(uv)\not \in B} y^{uv}$ for u∉A. Since we are only summing over edges not in B, and by definition of B this means that y ^uv≤r ^uv, then the above term is at most ${\sum }_{(uv)\ni u} r^{uv}$. As argued in the previous case, this upper bound is at most U _u (r _u ,r _−u ) for $G_{C}\subseteq G_{F}$.

Using the above, we get

$$\begin{array}{@{}rcl@{}}\sum\limits_{(uv)\in G_{F}\cap G_{C}}\!\!\! y^{uv}\!\!\! &\leq& \sum\limits_{u\in A} U_{u}(\mathbf{r_{u}},\mathbf{r_{-u}}) + \sum\limits_{u\notin A} U_{u}(\mathbf{r_{u}},\mathbf{r_{-u}}) \\ &\implies& P(M^{*})/2\leq U(M) \end{array} $$

Hence we have proved that P(M ^∗)≤2⋅U(M) for M2H games whenever $G_{C}\subseteq G_{F}$.

Now let us prove that S(M ^∗)≤2α k⋅U(M) for M2H games whenever $G_{C}\subseteq G_{F}$. Consider the two-hop benefit obtained in M ^∗ by a particular node u. It can be bounded as

$$\begin{array}{@{}rcl@{}} \sum\limits_{\begin{array}{c}(uv)\ni u, (vw)\ni v\\(uw)\in G_{F}, w\neq u \end{array}} \alpha y^{uv} y^{vw} \leq \left(\sum\limits_{(uv)\ni u} \alpha y^{uv} \right) \sum\limits_{(vw)\ni v} y^{vw} \leq \left( \sum\limits_{(uv)\ni u} y^{uv} \right)\cdot \alpha k\\ \end{array} $$

(52)

Because $G_{C}\subseteq G_{F}$, we have that ${\sum }_{(uv)\ni u} y^{uv}$ is at most the direct benefit obtained by u in M ^∗. Thus summing the above bound over all the nodes, we get S(M ^∗)≤α k P(M ^∗). We have already proved that P(M ^∗)≤2⋅U(M). Thus we have S(M ^∗)≤2α k U(M).

Thus we have proved that whenever $G_{C}\subseteq G_{F}$, we have P(M ^∗)≤2⋅U(M) and S(M ^∗)≤2α k U(M). Combining these observations with U(M ^∗)=P(M ^∗)+S(M ^∗), we get the desired 2-PoA bound of 2+2α k. □

Proof (Thm 10, Proof of case G _C =G _F =K _n )

Now consider the case of G _F =G _C =K _n . For the existence of a PE, it can be verified that every node making a contribution of k/(n−1) to every adjacent link is a PE. Now we give a brief outline of how to prove the bound on 2-PoA. We will assume that n is large enough, in particular at least 2k. Thus every node has degree of at least 2k−1. First we prove that when G _F =G _C =K _n , for a pairwise equilibrium, if two nodes u and v satisfy ${\sum }_{(uw)\ni u}x^{uw} < k$ and ${\sum }_{(vw)\ni v}x^{vw} < k$ respectively then x ^uv=1. We use this claim to bound the cardinality of the set T defined by $T = \{u: {\sum }_{(uw)\ni u}x^{uw} < k\}$. Then using this bound on cardinality, we bound the utility U(M) obtained in a PE M from which the 2-PoA bound will follow. Now we will proceed to the proof.

We claim that when G _F =G _C =K _n , for a pairwise equilibrium, if two nodes u and v satisfy ${\sum }_{(uw)\ni u}x^{uw} < k$ and ${\sum }_{(vw)\ni v}x^{vw} < k$ respectively then x ^uv=1. To see this, notice that whenever ${\sum }_{(uw)\ni u}x^{uw} < k$, there exists an edge (u z) such that $x^{uz}_{u} > x^{uz}_{z}$ and thus u can decrease its contribution $x^{uz}_{u}$ without affecting its utility. Such an edge exists because otherwise if $x^{uz}_{u} \leq x^{uz}_{z}$ holds for all the adjoining edges of u then ${\sum }_{(uw)\ni u}\min (x^{uw}_{u}, x^{uw}_{w})$ will become equal to $\min (k,d_{u})$ using the fact that ${\sum }_{(uw)\ni u}x^{uw}_{u}=k$. Thus whenever ${\sum }_{(uw)\ni u}x^{uw} < k$, there exists an edge adjoining u such that u can can decrease its contribution $x^{uz}_{u}$ without affecting its utility. Suppose for v also similar inequality holds, i.e. ${\sum }_{(vw)\ni v}x^{vw} < k$. In such a case, if the mutual consent x ^uv is less than 1 then u and v can increase their contributions to (u v) without decreasing the utility obtained because of their contributions from other edges. This would be a contradiction to our assumption of pairwise equilibrium. Thus we have proved the claim that for G _F =G _C =K _n , in any PE, if two nodes u and v satisfy ${\sum }_{(uw)\ni u}x^{uw} < k$ and ${\sum }_{(vw)\ni v}x^{vw} < k$ respectively then x ^uv=1. We will call an edge (u v) with mutual consent x ^uv=1 as “full” edge. We have just proved that all the nodes belonging to the set $T = \{u: {\sum }_{(uw)\ni u}x^{uw} < k\}$ form a clique in the sense that all the edges between such nodes are full. Each node in this set can have at most k−1 full edges adjoining it because if it were k for any node u in set T then we will have ${\sum }_{(uw)\ni u}x^{uw} = k$, contradicting the criterion for a node to be included in T. Thus, |T|≤k.

Let us denote the cardinality of T by q, which is at most k as argued above. For large n, the cardinality of $\bar {T}$ (complement of T) will also be at least k. For each node u in $\bar {T}$, the direct benefit component of U _u (x _u ,x _−u ) is exactly k. Thus the cumulative direct-benefit component of the nodes in $\bar {T}$ is given by $k\cdot |\bar {T}|$. Now the two-hop benefit component of a node u in $\bar {T}$ would be

$$\begin{array}{@{}rcl@{}} \alpha \sum\limits_{\begin{array}{c}(uv)\ni u\\ v\in \bar{T}\end{array}} x^{uv} \sum\limits_{(vw)\ni v, w\neq u} x^{vw} + \alpha \sum\limits_{\begin{array}{c}(uv)\ni u\\ v\in T \end{array}} x^{uv} \sum\limits_{(vw)\ni v, w\neq u} x^{vw} \\ \geq \alpha \sum\limits_{\begin{array}{c}(uv)\ni u\\ v\in \bar{T}\end{array}} x^{uv}\cdot (k-1) + \alpha \sum\limits_{\begin{array}{c}(uv)\ni u\\ v\in T \end{array}} x^{uv} \cdot (q-2) \end{array} $$

The above inequality holds because for a node $v\in \bar {T}$ we have ${\sum }_{(vw)\ni v} x^{vw}=k$ and for a node v∈T we have ${\sum }_{(vw)\ni v} x^{vw} \geq q-1$. Expressing q−2 as (k−1)−(k−q+1), a lower bound on the two-hop benefit component of a node u in $\bar {T}$ can be further expressed as

$$\begin{array}{@{}rcl@{}} \alpha \sum\limits_{(uv)\ni u} x^{uv}(k-1) - \alpha \sum\limits_{\begin{array}{c}(uv)\ni u\\ v\in T \end{array}} x^{uv}(k-q+1) \,=\, \alpha k(k-1) - \alpha \sum\limits_{\begin{array}{c}(uv)\ni u\\ v\in T \end{array}} x^{uv} (k-q+1)\\ \end{array} $$

(53)

Adding it over all the nodes in $\bar {T}$, the cumulative two-hop benefit obtained by nodes in $\bar {T}$ is lower bounded by

$$\begin{array}{@{}rcl@{}} \alpha k (k-1)\cdot |\bar{T}| - \alpha \sum\limits_{\begin{array}{c}(uv)\ni u\\ u\in \bar{T}, v\in T \end{array}} x^{uv} (k-q+1) \,\geq\, \alpha k(k-1)\cdot |\bar{T}| - \alpha q(k-q+1)^{2} \\ \end{array} $$

(54)

The above inequality holds because for any node in T, it is contributing q−1 to edges to other nodes in T, and thus can only contribute at most k−q+1 to edges to nodes in $\bar {T}$. Thus, the total contributions on edges between T and $\bar {T}$ are at most q(k−q+1).

Adding it to the cumulative direct benefit component $k\cdot |\bar {T}|$ of all the nodes in $\bar {T}$, the total utility of all the nodes in $\bar {T}$, and thus the utility U(M) of a PE M is lower bounded by

$$\begin{array}{@{}rcl@{}} U(M)\geq k|\bar{T}| + \alpha k(k-1)\cdot |\bar{T}| - \alpha q(k-q+1)^{2} \end{array} $$

(55)

It is easy to see that an upper bound on the utility U(M ^∗) of an optimum solution M ^∗ is given by

$$\begin{array}{@{}rcl@{}} U(M^{*}) \leq n (k+\alpha k^{2}) \end{array} $$

(56)

From (55) and (56), we obtain

$$\begin{array}{@{}rcl@{}} \frac{U(M)}{U(M^{*})} \geq \frac{|\bar{T}|}{n}\cdot\frac{1+\alpha (k-1)}{1+\alpha k} - \frac{\alpha q(k-q+1)^{2}}{n (k+\alpha k^{2})} \end{array} $$

(57)

As n grows, $|\bar {T}|/n \rightarrow 1$ and the second term in the above bound decreases, thus we get

$$\begin{array}{@{}rcl@{}} 2\text{-PoA} \rightarrow \frac{1+\alpha k}{1+\alpha (k-1)} \,\,\,\,\,\, \text{as} \,\,\, n\rightarrow \infty \end{array} $$

(58)

□

5 Empirical Findings

We begin by presenting the models and the settings used for the simulations we carried out for our experiments. Then we will present the findings that we obtained, relating them to the theoretical results for Weighted S2H and Weighted M2H games.

Let us start by describing the base model that we use for the simulations. In the base model, we consider networks of 100 nodes placed uniformly at random inside a unit square. Thus each node corresponds to a point (x,y) inside a unit square. Each node has an edge joining to every other node in the network. These edges have weights f ^uv which depend on the distance d(u,v) between the nodes. We will specifically consider the following three kinds of weight functions:

• 1. Inverse: For the inverse weight function, we set f ^uv=1/d(u,v).

• 2. Exponential: For the exponential weight function, we set $f^{uv} = \frac {e^{-d(u,v)}-e^{-\sqrt {2}}}{1-e^{-\sqrt {2}}}$. The weight function has been normalized to take value 1 when d(u,v)=0 and 0 when $d(u,v)=\sqrt {2}$, with $\sqrt {2}$ being the largest distance between any two nodes located in a unit square.

• 3. Linear: For the linear weight function, we set $f^{uv}=1-d(u,v)/\sqrt {2}$. Again, the weight function has been normalized to take value 1 when d(u,v)=0 and 0 when $d(u,v)=\sqrt {2}$.

The attenuation with respect to distance becomes steeper as the weight functions change from linear to exponential to inverse. In the model that we consider for simulations, we allow the variables $x^{uv}_{u}$ to take values only from {0,1}, i.e. we allow the system to converge only to integral equilibria. We set k=3. The nodes in this base model engage in either S2H or M2H games.

Now we describe the settings for the simulations. For each new instance of simulations, we start by placing 100 nodes uniformly at random inside a unit square. Then in the second step, the values of its contributions are set for each node u. Here we explore two possibilities: for a node u, either we choose any other three nodes randomly and make u contribute (with a contribution of 1) to the edges joining to these nodes or we make u’s contributions as 1 on the edges joining u to the three closest nodes. Note that as k=3, a node can contribute 1 corresponding to only three adjoining edges. After this initial assignment of the variables, a random permutation of nodes is generated in the third step. In each iteration of the instance the nodes are examined in the order given by this permutation. When a node u gets examined, we execute a better response for node u (if a better response exists for node u) where a node u increases its contribution $x^{uv}_{u}$ to 1 on some edge (u v) by removing its contribution on some other edge. Note that this better response is executed for M2H games only if it is a better response also for node v, since for M2H games we are interested in pairwise deviations.

If none of the nodes have any better response, then it means we have found a NE (PE) for Weighted S2H (Weighted M2H) games. We run the simulations for a large number of iterations, typically 500−1000. We found that whenever an instance converged, it took a much less number of iterations, typically of the order of 10 iterations. Hence we consider that an instance is not likely to converge if it fails to converge within 500 iterations.

We will evaluate the simulations based on two criteria:

• Existence of an (integral) equilibrium: If a simulation instance converges within 1000 iterations, it implies we have found a NE if it was an instance of Weighted S2H games (or a PE for Weighted M2H games). However, if a simulation instance does not converge, then it may or may not have an equilibrium. Based on how many instances converged for a model under consideration, we can evaluate the likelihood of an instance for that model to have an equilibrium.

• Price of Anarchy: If we are considering an instance of Weighted S2H games that converges (to a NE M) then the utility U(M) of the resultant NE is given by adding the utilities obtained by all the nodes. Computationally it is difficult to compute the worst NE as well as optimum solution in our settings. However if we take the ratio of U(M) to an upper bound U(M ^∗) on the value of an optimum solution then we have a bound on the quality on the resultant NE. We will slightly abuse the notation to call this ratio as the price of anarchy in this section. Thus in this section, price of anarchy means the quality of the solution to which the simulation converged. An upper bound on U(M ^∗) for Weighted S2H games is given by ${\sum }_{u} 2(1+\alpha k)\cdot (w_{u1}+w_{u2}+w_{u3})$ where w _u1,w _u2,w _u3 are the maximum 3 values of weight functions among the weights of the edges adjoining a node u. To see why this is an upper bound, notice that the maximum utility that a node u can obtain is given by 2(1+α k)⋅(w _u1+w _u2+w _u3) as per (40). We will see that the average value of the equilibria whenever the instances converged is close to the value of an optimum solution. For the instances of Weighted M2H games, we evaluate the upper bound on U(M ^∗) in the similar way except that the upper bound on U(M ^∗) is given by ${\sum }_{u} (1+\alpha k)\cdot (w_{u1}+w_{u2}+w_{u3})$. We will examine how the average value of the equilibria obtained varies with α.

Now we present the results of the simulations in Section 5.1 and Section 5.2.

5.1 Existence of an (Integral) Equilibrium

Although in Section 3 we gave an instance of S2H games where an integral NE does not exist, we found that in simulations better-response dynamics converge to an integral NE almost all of the time, at least for the types of graph structures that are considered in the simulation settings. To give specific numbers, we found that for linear, exponential, and inverse weight functions, we have convergence for 99 %, 97 % and 73 % of the simulation instances for Weighted games. Moreover, the convergence, when it occurs, is extremely fast: all the instances either converged within 10 rounds, or did not converge within 500 iterations. The same is not true for Weighted games: over 65 percent of our instances did not converge to a PE even after 5000 rounds. Thus, in the settings that we examine, we found that we are much more likely to have an (integral) NE in games (with extremely fast convergence to a stable solution) compared to Weighted games. See Fig. 7 and Fig. 8 for some typical outcomes. We explore these outcomes in details later.

Fig. 7

Typical pairwise equilibria computed for the Weighted M2H games with linear weight function and (Left) α=1/2 (Middle) α=1/8 (Right) α=1/16

Fig. 8

Typical NE computed for the Weighted S2H games with linear weight function (Left) and exponential weight function (Middle) and inverse weight function (Right) with α=1/6

5.2 Price of Anarchy

The quality of NEs that our simulations converged to was extremely close to the quality of the an optimal solution, usually within a few percent of the centralized optimal solution, indicating that our theoretical bounds are truly only for the worst case, not average case. Table 1 shows the average values of the equilibria obtained for our simulations when the weight functions are linear. The values for exponential and inverse weight functions also showed similar trends. We can see that on average, the value of the equilibria obtained is very close to the value of an optimum solution. The values are also consistent with worst-case PoA being 1+α k, which decreases as α decreases. As α decreases, the NEs and optimum solutions both converge to nodes following the strategy of contributing to edges leading to their closest neighbors. Thus there is less tendency to deviate from the strategy in OPT, resulting in better equilibria.

Table 1 Average value of equilibria obtained with α for n=100, k=3 for linear weight functions. PoA here refers to the ratio between the computed NE and the optimum solution

As α decreases or as the weight functions become steeper from linear to exponential to inverse, we also observed that nodes increasingly form a “backbone”-type network by connecting to the closest nodes. We explain this as follows: As α decreases, the contribution of two-hop benefit to node utility starts losing its significance. When α is small, nodes simply attempt to connect to their closest k nodes and little clustering takes place, instead forming a backbone-type of network. This effect is especially pronounced in M2H games (see Fig. 7). In Fig. 7, for α=1/2, two-hop benefit plays a significant part in the utility obtained by a node. Because of the bidirectional nature of contributions, the structures that can increase two-hop benefit for a node in M2H games are cliques – as it is easy to see in a clique, a node is a part of maximum possible k(k−1) two-hop paths. However, for α=1/8 and α=1/16 in Fig. 7, two-hop benefit plays increasingly insignificant role in node utility, thus the outcome is a backbone-type network as predicted. It would be interesting to investigate further if a phase transition occurs as α decreases, where the clustering effect suddenly disappears, or whether it disappears gradually.

We plot the effect of increasing the steepness of weight functions in Fig. 8, where as the weight functions become steeper the nodes increasingly form a “backbone”-type of network by connecting to the k closest nodes. Although the rationale is similar to the effect of decreasing α with M2H games, there are slight differences between Figs. 7 and 8 as they correspond to equilibria of S2H and M2H games respectively. For steeper weight functions with S2H games, two-hop benefit plays a significant part in node utility but it manifests in a slightly different way than M2H games. In S2H games, the nature of contributions is unidirectional, thus a node has no control over incoming (one-hop or two-hop) paths. Thus if a node u were to contribute on an edge (u v) where the other endpoint v has already contributed, then u can be a part of at most (k−1) outgoing two-hop paths through node v. However, if a node u were to contribute on an edge (u v) such that v does not contribute to (u v), then u can be a part of k outgoing paths through node v. Thus in S2H games, in order to obtain a higher two-hop benefit as encouraged by a less steep (linear) weight function, nodes tend to contribute to edges where the other endpoint does not contribute, thus reducing the tendency of nodes to form cliques and also making the edges that get contributed close to 2k n. This leads to a dense network with higher connectivity in a typical outcome, as shown in Fig. 8 for linear weight functions. Note that such a typical outcome also has higher number of unidirectional (orange-blue) edges as predicted. When the weight functions become steeper, two-hop benefit contribution to node utility becomes increasingly insignificant, thus nodes tend to contribute to the edges leading to closest k neighbors. If v is among k closest neighbors of u then u is also highly likely to be among k closest neighbors of v because of the nature of node distribution (random in a unit square) – thus it is highly likely that an edge that gets contributed to, gets contributed from both its endpoints as two-hop benefit becomes insignificant. This can be observed in increasing percentage of blue-colored edges (denoting contribution from both endpoints) in Fig. 8 as weight functions change from linear to exponential to inverse (increasing their steepness). Most of the contributed edges being bidirectional with nodes connecting to k closest neighbors also means a typical outcome in S2H games with steep weight function (e.g., inverse weight function) resembles to a typical outcome with small α in M2H games as observed from the rightmost subfigures sof Fig. 7 and Fig. 8.

Let us summarize the simulation results. We investigated Weighted S2H and Weighted M2H games with nodes scattered uniformly at random inside a unit square. We used three different classes of weight functions – linear, exponential and inverse with the attenuation of weight function becoming steeper with distance as they change from linear to exponential to inverse. We found that for Weighted S2H games, we are much more likely to have an (integral) NE compared to Weighted M2H games. The quality of NEs that our simulations converged to was extremely close – usually within a few percent – of the centralized optimal solution. We also saw that as α decreases or as the weight functions go from linear to exponential to inverse, the nodes stop forming “clusters” and instead form a “backbone”-type network resulting from their connecting to the closest possible neighbors.

6 Conclusion

Most game theoretic versions of network formation games consider agents deriving benefit either from their immediate neighborhood or from the entire network. In many settings, however, the agents are neither so myopic as to only consider their benefit from direct connections, nor so far-sighted as to consider their benefit from the entire network, including their connections to agents which are 3 or more hops away. Motivated by this, we defined Two-Hop games where nodes try to maximize a combination of direct benefit (i.e., benefit obtained from their immediate neighborhood) and two-hop benefit (i.e., benefit obtained from two-hop neighborhood). We considered two specific versions of two-hop games, namely S2H and M2H games, which can be interpreted as natural extensions of well-studied games. We studied both these versions while distinguishing between the ability of two nodes to form connections (represented by the Connection Graph G _C ) and the ability of two nodes to be of mutual benefit (represented by the Friendship Graph G _F ).

For both S2H games and M2H games, we showed that the introduction of two-hop benefits significantly changes their properties. Among other results, we showed that for S2H games a fractional Nash Equilibrium still exists (although an integral Nash equilibrium may not exist after introducing two-hop benefit) and the price of anarchy (PoA) significantly reduces as the overlap between G _F and G _C increases, converging to 1+α k for several important cases. For M2H games, the corresponding bound on the PoA was 2+2α k. Here α is the two-hop benefit factor, with higher values of α indicating higher contribution of two-hop benefit to node utility. For some intuitive simulation settings, we also found that the actual quality of equilibria of converged instances was very close to the optimum, although the theoretical worst-case bounds could be much higher. We also observed in our simulations that as the contribution of two-hop benefit decreases, nodes tend to form backbone-like structure by connecting to k closest neighbors.

There are several important open questions that should be considered in future work. One immediate and important question that is still unanswered is whether a fractional pairwise equilibrium exists for M2H games, as we know that some instances of M2H games do not admit an integral pairwise equilibrium. Similarly, as S2H also do not admit integral Nash equilibria in some instances, it would be interesting to know if good quality approximate equilibria exist for S2H and M2H games. Long-term challenges include considering different utility structures for two-hop games and exploring the effect of two-hop benefit on other well-studied games.