# bounding_the_inefficiency_of_compromise__017345d3.pdf

Bounding the Inefficiency of Compromise

Ioannis Caragiannis University of Patras caragian@ceid.upatras.gr

Panagiotis Kanellopoulos CTI & University of Patras kanellop@ceid.upatras.gr

Alexandros A. Voudouris University of Patras voudouris@ceid.upatras.gr

Social networks on the Internet have seen an enormous growth recently and play a crucial role in different aspects of today s life. They have facilitated information dissemination in ways that have been beneficial for their users but they are often used strategically in order to spread information that only serves the objectives of particular users. These properties have inspired a revision of classical opinion formation models from sociology using game-theoretic notions and tools. We follow the same modeling approach, focusing on scenarios where the opinion expressed by each user is a compromise between her internal belief and the opinions of a small number of neighbors among her social acquaintances. We formulate simple games that capture this behavior and quantify the inefficiency of equilibria using the well-known notion of the price of anarchy. Our results indicate that compromise comes at a cost that strongly depends on the neighborhood size.

1 Introduction Opinion formation has been the subject of much research in sociology, economics, physics, and epidemiology. Due to the widespread adoption of the Internet and the subsequent blossoming of social networks, it has recently attracted the interest of researchers in AI (e.g., see [Auletta et al., 2016; Schwind et al., 2015; Tsang and Larson, 2014]) and CS at large (e.g., see [Bindel et al., 2015; Mossel and Tamuz, 2014; Olshevsky and Tsitsiklis, 2009]). An influential model that captures the adoption of opinions in a social context has been proposed by Friedkin and Johnsen [1990]. According to this, each individual has an internal belief on an issue and publicly expresses an opinion; internal beliefs and public opinions are modeled as real numbers. In particular, the opinion an individual expresses follows by averaging between her internal belief and the opinions expressed by her social acquaintances. Recently, Bindel et al. [2015] show that this behavior can be explained through a game-theoretic lens: averaging between the internal belief of an individual and the opinions in her social circle is simply a strategy that minimizes an implicit cost for the individual.

Bindel et al. [2015] use a quadratic function to define this cost. This function is equal to the total squared distance of the opinion expressed by the individual from her belief and the opinions expressed in her social circle. In a sense, this behavior leads to opinions that follow the majority of her social acquaintances. Bindel et al. [2015] consider a static snapshot of the social network. In contrast, Bhawalkar et al. [2013] implicitly assume that the opinion of an individual depends on a small number of acquaintances only, her neighbors. So, in their model, opinion formation co-evolves with the neighborhood for each individual: her neighborhood consists of those who have opinions similar to her belief. Then, the opinion expressed is assumed to minimize the same cost function used by Bindel et al. [2015], taking into account the neighborhood instead of the whole social circle. We follow the co-evolutionary model of [Bhawalkar et al., 2013], but we deviate from their cost definition and instead consider individuals that seek to compromise with their neighbors. Hence, we assume that each individual aims to minimize the maximum distance of her expressed opinion from her belief and each of her neighbors opinion. Like [Bhawalkar et al., 2013], we assume that opinion formation co-evolves with the social network. The neighborhood of each individual consists of the k players with the closest opinions to her belief. Naturally, these modeling decisions lead to the definition of strategic games, which we call kcompromising opinion formation (or, simply, k-COF) games. Each individual is a (cost-minimizing) player with the opinion expressed as her strategy. Technical contribution. We study questions related to the existence, computational complexity, and quality of equilibria in k-COF games. We show that there exist simple 1-COF games that do not admit pure Nash equilibria and, furthermore, that even in games where equilibria exist, their quality may be suboptimal, i.e., the price of stability (defined in [Anshelevich et al., 2008]) is strictly greater than 1. We also show that there is a representation of each 1-COF game as a directed acyclic graph, in which every pure Nash equilibrium corresponds to a path between two designated nodes. Hence, the problems of computing the best or worst pure Nash equilibrium (or even of computing whether such an equilibrium exists) are equivalent to simple path computations that can be performed in polynomial time. These results appear in

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

Section 3. In Sections 4 and 5, we present upper and lower bounds on the price of anarchy (introduced by Koutsoupias and Papadimitriou [1999]) of k-COF games that suggest a linear dependence on k. Our upper bound on the price of anarchy exploits, in a non-trivial way, linear programming duality in order to lower-bound the optimal social cost. For the fundamental case of 1-COF games, we obtain a tight bound of 3. Related work. De Groot [1974] proposed a framework that models the opinion formation process, where each individual has a real number as opinion and updates it based on a weighted averaging procedure. Subsequently, Friedkin and Johnsen [1990] refined the model by assuming that each individual has a private belief and expresses a (possibly different) public opinion that depends on her belief and the opinions of people to whom she has social ties. More recently, Bindel et al. [2015] studied this model and proved that, again for the setting where beliefs and opinions are reals, the repeated averaging process leads to an opinion vector that can be thought of as the unique equilibrium in a corresponding opinion formation game. Deviating from the assumption that opinions depend on the whole social circle, Bhawalkar et al. [2013] consider co-evolutionary opinion formation games, where as opinions evolve so does the neighborhood of each person. This model is conceptually similar to previous ones that have been studied by Hegselmann and Krause [2002] and Holme and Newman [2006]. Both Bindel et al. [2015] and Bhawalkar et al. [2013] show constant bounds on the price of anarchy of the games they study. In contrast, the modified cost function we use in order to model compromise yields considerably higher price of anarchy. A series of recent papers from the Econ CS community consider discrete models with binary opinions. Chierichetti et al. [2013] consider discrete preference games, where beliefs and opinions are binary and study questions related to the price of stability. For these games, Auletta et al. [2015] characterize the social networks where the belief of the minority can emerge as the opinion of the majority. Auletta et al. [2016] generalize discrete preference games so that players are not only interested in agreeing with their neighbors and more complex constraints can be used to represent the players preferences. Bil o et al. [2016] extend co-evolutionary formation games to the discrete setting. Other models assume that opinion updates depend on the entire social circle of each individual, who consults a small random subset of social acquaintances; see the recent paper by Fotakis et al. [2016] and the survey of Mossel and Tamuz [2014]. In spite of the extensive related literature in many different disciplines, we believe that our model captures the tendency to compromise more accurately.

2 Preliminaries

A compromising opinion formation game defined by the k nearest neighbors (henceforth, called k-COF game) is played by a set of n players whose beliefs lie on the line of real numbers. Let s = (s1, s2, . . . , sn) Rn be the vector containing the players beliefs such that si si+1 for each i [n 1].

Let z = (z1, z2, . . . , zn) Rn be a vector containing the (deterministic or randomized) opinions expressed by the players; these opinions define a state of the game. We denote by z i the opinion vector obtained by removing zi from z. In an attempt to simplify notation, we omit k from all relevant definitions. Given vector z (or a realization of it in case z contains randomized opinions), we define the neighborhood Ni(z, s) of player i to be the set of k players whose opinions are the closest to the belief of player i breaking ties arbitrarily (but consistently). For each player i, we define Ii(z, s) as the shortest interval of the real line that includes the following points: the belief si, the opinion zi, and the opinion zj for each player j Ni(z, s). Furthermore, let ℓi(z, s) and ri(z, s) be the players with the leftmost and rightmost point in Ii(z, s), respectively. For example, ℓi(z, s) can be equal to either player i or some player j Ni(z, s), depending on whether the leftmost point of Ii(z, s) is si, zi, or zj. In the following, we present the relevant definitions for the case of possibly randomized opinion vectors; clearly, these can be simplified whenever z consists entirely of deterministic opinions. Given a k-COF game with belief vector s and the opinion vector z, the cost of player i is defined as

E[costi(z, s)] = E max j Ni(z,s)

|zi si|, |zj zi|

= E max |zi si|, |zri(z,s) zi|, |zi zℓi(z,s)| .

For the special case of 1-COF games, we denote by σi(z, s) (or σ(i) when z and s are clear from context) the player (other than i) whose opinion is closest to the belief si of player i, i.e., σ(i) is the only member of Ni(z, s). In this case, the cost of player i can be simplified as

E[costi(z, s)] = E max |zi si|, |zσi(z,s) zi| .

We say that an opinion vector z consisting entirely of deterministic opinions is a pure Nash equilibrium if no player i has any incentive to unilaterally deviate to a deterministic opinion z i in order to decrease her cost, i.e.,

costi(z, s) costi((z i, z i), s),

where by (z i, z i) we denote the opinion vector in which player i chooses the opinion z i and all other players choose the opinions they have according to vector z. Similarly, a possibly randomized opinion vector z is a mixed Nash equilibrium if for any player i and any deviating deterministic opinion z i we have

E[costi(z, s)] Ez i[costi((z i, z i), s)].

The social cost of the opinion vector z is defined as the total cost experienced by all players, i.e.,

E[SC(z, s)] =

i=1 E[costi(z, s)].

Let z be a deterministic opinion vector that minimizes the social cost; we will refer to it as the optimal opinion vector.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

The price of anarchy (Po A) of a k-COF game over pure Nash equilibria is defined as the ratio between the social cost of its worst (in terms of the social cost) pure Nash equilibrium and the optimal social cost, i.e.,

Po A(s) = sup z PNE

SC(z, s) SC(z , s),

where PNE denotes the set of pure Nash equilibria. The price of stability (Po S) over pure Nash equilibria is defined as the ratio between the social cost of the best pure equilibrium (in terms of social cost) and the optimal social cost, i.e.,

Po S(s) = inf z PNE SC(z, s) SC(z , s).

Similarly, the price of anarchy and the price of stability over mixed Nash equilibria are defined as

Po A(s) = sup z MNE

E[SC(z, s)]

SC(z , s) , Po S(s) = inf z MNE E[SC(z, s)]

where MNE denotes the set of mixed Nash equilibria. Then, the price of anarchy and the price of stability of k COF games, for a fixed k, are defined as the supremum of Po A(s) and Po S(s) over all belief vectors s. We now state useful properties of pure Nash equilibria. Lemma 1. In any pure Nash equilibrium z of a k-COF game with belief vector s, a. zi lies in the middle of interval Ii(z, s), for each player i; b. zi zi+1, for any i [n 1]; c. Ni(z, s) = {j, ..., j + k} \ {i} with i k j i; d. sℓi(z,s) zi sri(z,s), for each player i. The first property follows trivially by the definition of the cost function. Below, we give the proof of the second property of Lemma 1; the remaining proofs (as well as many proofs in the following) are omitted due to lack of space.

Proof of Lemma 1b. To simplify notation, we abbreviate ℓi(z, s) and ri(z, s) by ℓ(i) and r(i), respectively. For the sake of contradiction, let us assume that zi+1 < zi for a pair of players i and i + 1. Then, it cannot be the case that the leftmost endpoint of the interval Ii(z, s) of player i is at the left of (or coincides with) the leftmost endpoint of interval Ii+1(z, s) of player i + 1 and the rightmost endpoint of Ii(z, s) is at the left of (or coincides with) the rightmost endpoint of Ii+1(z, s). In other words, it cannot be the case that min{si, zℓ(i)} min{si+1, zℓ(i+1)} and max{si, zr(i)} max{si+1, zr(i+1)} hold simultaneously. Since, by the first property, points zi and zi+1 lie in the middle of the corresponding intervals, we would have zi zi+1, contradicting our assumption. So, at least one of the two inequalities between the interval endpoints above must not hold. In the following, we assume that min{si, zℓ(i)} > min{si+1, zℓ(i+1)} (the case where max{si, zr(i)} > max{si+1, zr(i+1)} is symmetric). Our assumption implies that zℓ(i+1) < si si+1, and, subsequently, that zℓ(i+1) < zℓ(i). Hence, the opinion at the leftmost endpoint of interval Ii+1(z, s) cannot belong to player i + 1, i.e., ℓ(i + 1) = i + 1; see also Figure 1.

zℓ(i+1) zℓ(i) si zi+1 zi si+1

Figure 1: Example of the argument used in the proof of Lemma 1b. An arrow connects the belief of a player to her opinion.

Since ℓ(i+1) does not belong to Ii(z, s), there are at least k players different than i+1 and i that have opinions at distance strictly less than si zℓ(i+1) from belief si. All these players are also at distance strictly less than si+1 zℓ(i+1) from belief si+1. This contradicts the fact that the opinion of player ℓ(i+ 1) is among the k closest opinions to si+1.

3 Existence, Complexity, and Quality of Equilibria

In this section, we focus entirely on 1-COF games. We first warm up with a negative statement: pure Nash equilibria may not exist. The construction in the proof of the next statement is inspired by [Bhawalkar et al., 2013].

Theorem 2. There exists a 1-COF game with no pure Nash equilibria.

We continue to present a polynomial-time algorithm that determines whether a 1-COF game admits pure Nash equilibria, and, in case it does, allows us to compute the best and worst pure Nash equilibrium with respect to the social cost. We do so by establishing a correspondence between pure Nash equilibria and source-sink paths in a suitably defined directed acyclic graph. Assume that we are given neighborhood information according to which each player i has either player i 1 or player i + 1 as neighbor. From Lemma 1c, such a neighborhood structure is necessary in a pure Nash equilibrium. We claim that this information is enough in order to decide whether there is a consistent opinion vector that is a pure Nash equilibrium or not. All we have to do is to use Lemma 1a and obtain n equations that relate the opinion of each player to her belief and her neighbor s opinion. These equations have a unique solution which can then be verified whether it indeed satisfies the neighborhood conditions or not. So, the main idea of our algorithm is to cleverly search among all possible neighborhood structures that are not excluded by Lemma 1c for one that defines a pure Nash equilibrium. For integers 1 a b < c n, let us define the segment C(a, b, c) to be the set of players {a, a + 1, ..., c} together with the following neighborhood information for them: σ(p) = p + 1 for p = a, ..., b and σ(p) = p 1 for p = b + 1, ..., c. See Figure 2 for an example. It can be easily seen that the neighborhood information for all players at a pure Nash equilibrium can always be decomposed into disjoint segments. Importantly, given the neighborhood information in segment C(a, b, c) and the beliefs of its players, the opinions they could have in any pure Nash equilibrium that contains this segment is uniquely defined using Lemma

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

s1 z1 s2 z2 z3 s3 z4 s4

Figure 2: Graphical representation of a segment C(1, 2, 4).

1a (as zi = (si + zσ(i))/2). This opinion vector is not necessarily consistent to the given neighborhood structure. We call segment C(a, b, c) legit if a = 2, c = n 1 (so that it can be part of a decomposition) and the uniquely defined opinions are consistent to the neighborhood information of it. A decomposition of neighborhood information for all players will consist of consecutive segments C(a1, b1, c1), C(a2, b2, c2), ..., C(at, bt, ct) so that a1 = 1, ct = n, aℓ= cℓ 1 + 1 for ℓ= 2, ..., t. Such a decomposition will yield a pure Nash equilibrium if it consists of legit segments and, furthermore, the uniquely defined opinions of players in consecutive segments is consistent to the neighborhood information in both of them. Now, consider the directed graph G that has two special nodes designated as the source and the sink, and a node for each legit segment C(a, b, c). Note that G has O(n3) nodes. The source node is connected to all segment nodes C(1, b, c) while all segment nodes C(a, b, n) are connected to the sink. An edge from segment node C(a, b, c) to segment node C(a , b , c ) exists if a = c + 1 and the uniquely defined opinions of players in the two segments are consistent to the neighborhood information in both of them. By the definition of segments and of its edges, G is acyclic. Based on the discussion above, there is a bijection between pure Nash equilibria and source-sink paths in G. In addition, we can assign a weight to each node of G that is equal to the total cost of the players in the corresponding segment. Then, the total weight of a source-sink path is equal to the social cost of the corresponding pure Nash equilibrium. Hence, standard algorithms for computing shortest or longest paths in directed acyclic graphs can be used not only to detect whether a pure Nash equilibrium exists, but also to compute the equilibrium of best or worst social cost. Theorem 3. Given a 1-COF game, deciding whether a pure Nash equilibrium exists can be done in polynomial time. Furthermore, computing a pure Nash equilibrium of highest or lowest social cost can be done in polynomial time as well. Example 1. Consider a 1-COF game with four players with belief vector s = (0, 3, 4, 7). According to the discussion above, there are 10 segments of the form C(a, b, c) with 1 a b < c 4, but it can be shown that only 3 of them are legit; these are C(1, 1, 2), C(3, 3, 4), and C(1, 2, 4). For example, segment C(1, 1, 4) corresponds to the opinion vector (1, 2, 3, 5) which is not consistent to the neighborhood information σ(2) = 1 in the segment. The resulting directed acyclic graph G, appears in Figure 3 and implies that there exist two pure Nash equilibria for this 1-COF game, namely the opinion vectors (1, 2, 5, 6) and ( 5

3 ). We conclude this section by stating that even the best equilibrium can be inefficient. Inefficiency of (worst) equilibria will be the subject of the upcoming two sections. Theorem 4. The price of stability of 1-COF games is at least 17/15.

source sink

C(1, 1, 2) C(3, 3, 4)

Figure 3: The directed acyclic graph G for Example 1.

4 Upper Bounds on the Price of Anarchy

In the proof of the upper bound on the price of anarchy of k-COF games, we relate the social cost of any deterministic opinion vector, including the optimal one, to a quantity that depends only on the beliefs of the players and can be thought of as the cost of the truthful opinion vector (in which the opinion of every player is equal to her belief). Consider an n-player k-COF game with belief vector s = (s1, ..., sn). For player i, we denote by ℓ (i) and r (i) the integers in [n] that are such that ℓ (i) i r (i), r (i) ℓ (i) = k, and |sr (i) sℓ (i)| is minimized. The proof of the next lemma exploits linear programming and duality.

Lemma 5. Consider a k-COF game and let s = (s1, . . . , sn) denote the belief vector and z be any deterministic opinion vector. Then, SC(z, s) 1 2(k+1) Pn i=1 |sr (i) sℓ (i)|.

Furthermore, we can show that for any pure Nash equilibrium z of a k-COF game, we have that SC(z, s) 2 Pn i=1 |sr (i) sℓ (i)|. By combining this statement with Lemma 5, we obtain the following theorem.

Theorem 6. The price of anarchy of k-COF games over pure Nash equilibria is at most 4(k + 1).

For the case of 1-COF games we can prove a stronger statement using a similar proof roadmap but simpler (and shorter) arguments. We denote by η(i) the player (other than i) that minimizes the distance |si sη(i)|; note that η(i) {i 1, i + 1}.

Lemma 7. Consider a 1-COF game and let s = (s1, . . . , sn) denote the belief vector and z be any deterministic opinion vector. Then, SC(z, s) 1

3 Pn i=1 |si sη(i)|.

Proof. We call a player i with zi / [si 1, si+1] a kangaroo player and associate the quantity excessi with her. If zi [sj, sj+1] for some j > i, we say that the players in the set Ci = {i + 1, ..., j} are covered by player i and define excessi = zi sj. Otherwise, if zi [sj 1, sj] for some j < i, we say that the players in the set Ci = {j, ..., i 1} are covered by player i and define excessi = sj zi. Let K be the set of kangaroo players and C the set of players that are covered by a kangaroo; these need not be disjoint. We now partition the players not in K C into the set L of large players i with costi(z, s) 1

3(|si sη(i)|) and the set S that contains the remaining small players. See Figure 4. We proceed to prove five useful claims.

Claim 8. Let i S such that σ(i) K. Then, costi(z, s) + excessσ(i) 1

3|si sη(i)|.

Proof. We assume that σ(i) > i (the other case is symmetric). If zσ(i) > sσ(i), then costi(z, s) = max{|si zi|, |zi

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

s1 s2 z1 z3 s3 z2 z4 s4 z5 s5

Figure 4: Kangaroos, covered, large, and small players: 1 K, 2 K C, 3 C, 4 S, and 5 L.

zσ(i)|} 1 2(zσ(i) si) > 1 2(sσ(i) si) 1 3|si sη(i)|, which contradicts the fact that i is a small player. Hence, zσ(i) [si, sσ(i)], otherwise player i would be covered. Let j be the player with the leftmost belief that is covered by player σ(i). Then, excessσ(i) = sj zσ(i). We have costi(z, s) + excessσ(i) = max{|si zi|, |zi zσ(i)|} + sj zσ(i) 1 2(zσ(i) si)+ 1

2(sj zσ(i)) 1

3|si sη(i)|.

Claim 9. Let i S such that σ(i) L or σ(i) C\K. Then, costi(z, s)+costσ(i)(z, s) 1

3(|si sη(i)|+|sσ(i) sη(σ(i))|).

Proof. We assume that σ(i) > i (the other case is symmetric). If zσ(i) > sσ(i), then costi(z, s) = max{|si zi|, |zi zσ(i)|} 1 2(zσ(i) si) > 1 2(sσ(i) si) 1 3|si sη(i)|, which contradicts the fact that i is a small player. Hence, zσ(i) [si, sσ(i)], otherwise player i would be covered. Then, costi(z, s) + costσ(i)(z, s) = max{|si zi|, |zi zσ(i)|} + max{|sσ(i) zσ(i)|, |zσ(i) zσ(σ(i))|} zσ(i) zi + sσ(i) zσ(i) = sσ(i) zi. Since i is small, we have zi < si + 1

3(sσ(i) si) and we get costi(z, s) + costσ(i)(z, s) 2 3(sσ(i) si) 1

3|si sη(i)| + 1

3|sσ(i) sη(σ(i))|.

Claim 10. Let i K. Then, costi(z, s) excessi 1

3(|si sη(i)| + P j Ci |sj sη(j)|).

Proof. We assume that zi > si (the other case is symmetric). Let ℓbe the player with the rightmost belief that is covered by i. Then, excessi = zi sℓ. We have costi(z, s) excessi = max{|si zi|, |zi zσ(i)|} (zi sℓ) sℓ si = Pℓ 1 j=i(sj+1 sj) 1

3(|si sη(i)|+P j Ci |sj sη(j)|).

Let N(S) = {j [n] : σ(i) = j for i S}.

Claim 11. N(S) does not contain small players.

Proof. Assume otherwise that σ(i) S for some player i S. Without loss of generality σ(i) > i. If zσ(i) sσ(i), then costi(z, s) 1

2|zσ(i) si| 1

2|sσ(i) si| 1

3|si sη(i)| contradicting the fact that i S. So, zσ(i) < sσ(i). Also, zσ(i) si (since neither i is covered nor σ(i) is kangaroo). Since σ(i) is small, sσ(i) zσ(i) < 1 3|sσ(i) sη(σ(i))| 1 3(sσ(i) si), i.e., zσ(i) > 2

3si. Hence, costi(z, s) 1 2(zσ(i) si) > 1

3(sσ(i) si), which contradicts i S.

Claim 12. For every two players i, i S, σ(i) = σ(i ).

Proof. Assume otherwise and let σ(i) = σ(i ) = j with i < i . If zj [si, si ], then the cost of either i or i is at least 1

2(si si), contradicting the fact that both players are small. Hence, zj [si, si ]. Notice that sj [si, si ] as well, otherwise either i or i would be covered by j. Now the fact that i and i are small implies that costi(z, s)+costi (z, s) <

1 3|si sη(i)| + 1

3|si sη(i )| 1

3(sj si) + 1

3(si sj) = 1 3(si si). On the other hand, costi(z, s) + costi (z, s) 1 2(zj si) + 1

2(si zj) = 1

2(si si), a contradiction.

Using T as an abbreviation of L (C \ K), we have

i=1 costi(z, s)

costi(z, s) + excessσ(i)

costi(z, s) + costσ(i)(z, s)

i K (costi(z, s) excessi) + X

i L\N(S) costi(z, s)

i S:σ(i) K |si sη(i)|

|si sη(i)| + |sσ(i) sη(σ(i))|

|si sη(i)| + X

j Ci |sj sη(j)|

i L\N(S) |si sη(i)|

i=1 |si sη(i)|,

as desired. The first inequality follows by the player classification and due to Claims 11 and 12. The second one follows by Claims 8, 9, and 10, and by the definition of large players. The third one follows since the players enumerated in the first two sums at its left cover the whole set S (by Claim 11).

Theorem 13. The price of anarchy of 1-COF games over pure Nash equilibria is at most 3.

Proof. Let us consider a 1-COF game with n players and belief vector s. Let z be an optimal opinion vector and recall that η(i) is the player that minimizes the distance |si sη(i)|. By Lemma 7, we have

SC(z , s) 1

i=1 |si sη(i)|. (1)

Now, consider any pure Nash equilibrium z of the game. We will show that

i=1 |si sη(i)|. (2)

The theorem will then follow by (1) and (2). In particular, we will show that costi(z, s) |si sη(i)| for each player i. Let us assume that η(i) = i 1; the case η(i) = i+1 is symmetric. We distinguish between four cases.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

Case I: σ(i) = i 1. By Lemma 1d, we have si 1 zi si. Then, clearly, costi(z, s) = |si zi| |si si 1| as desired.

Case II: σ(i) = i + 1 and σ(i 1) = i. By Lemmas 1b and 1d, we have si 1 zi 1 si zi. Since player i has player i + 1 as neighbor, we have |zi+1 si| |si zi 1|. Hence, costi(z, s) = |zi si| |zi+1 si| |si zi 1| |si si 1|.

Case III: σ(i) = i + 1, σ(i 1) = i 2, and costi(z, s) costi 1(z, s). By the definition of the function σ and Lemma 1b, we have zi 2 zi 1 si 1 si zi zi+1. We have

costi(z, s) 2 costi 1(z, s) costi(z, s) = |si 1 zi 2| |zi si| |zi si 1| |zi si| = |si si 1|.

The second inequality follows since player i 2 (instead of i) is the neighbor of player i 1.

Case IV: σ(i) = i+1, σ(i 1) = i 2, and costi(z, s) > costi 1(z, s).

costi(z, s) < 2 costi(z, s) costi 1(z, s) = |zi+1 si| |si 1 zi 1| |si zi 1| |si 1 zi 1| = |si si 1|.

The second inequality follows since player i+1 (instead of i 1) is the neighbor of player i.

This completes the proof.

5 Lower Bounds on the Price of Anarchy

We now present lower bounds on the price of anarchy over pure and mixed Nash equilibria. We provide full proofs for the case of pure Nash equilibria in 1-COF games only.

Theorem 14. The price of anarchy of 1-COF games over pure Nash equilibria is at least 3.

Proof. Let λ (0, 1) and consider a 1-COF game with 6 players and belief vector s = ( 10 λ, 10 λ, 2 λ, 2+ λ, 10+λ, 10+λ). This game is depicted in Figure 5. We can show that the opinion vector z = ( 10 λ, 10 λ, 6 λ, 6+λ, 10+λ, 10+λ) is a pure Nash equilibrium with social cost SC(z, s) = 8. The first two players suffer zero cost as they follow each other and their opinions coincide with their beliefs; the same holds also for the last two players. For the third player, it is σ(3) {1, 2} since |z1 s3| = |z2 s3| = 8 < |z4 s3| = 8 + 2λ and z3 is in the middle of the interval [ 10 λ, 2 λ]; hence, cost3(z, s) = 4. Similarly, we have σ(4) {5, 6}, z4 lies in the middle of the interval [2+λ, 10+λ] and cost4(z, s) = 4. Hence, z is indeed a pure Nash equilibrium. Now, consider the opinion vector

z = 10 λ, 10 λ, 2 λ

3 , 10 + λ, 10 + λ

Figure 5: The 1-COF game that is used to derive the lower bounds on the price of anarchy over pure and mixed Nash equilibria. Each point corresponds to a belief and [x] denotes that x players have a particular belief.

which yields a social cost of SC( z, s) = 8+4λ

3 ; here, again, the first and last two players have zero cost, but players 3 and 4 now each have cost 4+2λ

3 since they follow each other. The optimal social cost is at most SC( z) and, hence, the price of anarchy is at least SC(z,s)

SC( z,s) = 3 1+λ/2. The theorem follows by setting λ arbitrarily close to 0.

We now consider the case of mixed Nash equilibria and we remark that the next lower bound is greater than the upper bound of Theorem 13 on the price of anarchy over pure Nash equilibria. Hence, allowing randomized strategies may lead to more inefficient outcomes and, therefore, there is a clear separation between the classes of pure and mixed Nash equilibria. The proof relies again on the 1-COF game presented in Figure 5. Theorem 15. The price of anarchy of 1-COF games over mixed Nash equilibria is at least 6. We conclude this section with lower bounds on the price of anarchy of k-COF games, with k 2. Theorem 16. The price of anarchy of k-COF games over pure Nash equilibria is at least k + 1 for k 3, and at least 18/5 for k = 2. Theorem 17. The price of anarchy of k-COF games over mixed Nash equilibria is at least k + 2 for k 3, and at least 24/5 for k = 2.

6 Conclusion and Open Problems We have introduced the class of k-COF games. Our findings indicate that the quality of their equilibria grows linearly with the neighborhood size k. Still, there exists a gap between our lower and upper bounds for k 2 and closing this gap is a challenging technical task. Furthermore, we know that mixed equilibria are strictly worse for 1-COF games but we have been unable to prove upper bounds on their price of anarchy. Is their price of anarchy still linear? Also, whether the price of stability depends on k or is at most a (small) constant is an interesting and wide open question. Another natural question is about the complexity of pure Nash equilibria in k-COF games for k 2. We conjecture that there exists a polynomial time algorithm for computing them, but finding such an algorithm remains elusive.

Acknowledgements This work was partially supported by Caratheodory research grant E.114 from the University of Patras and by a Ph D scholarship from the Onassis Foundation. The first author would like to thank Pino Persiano for fruitful discussions at early stages of this work.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)

References [Anshelevich et al., 2008] Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Eva Tardos, Tom Wexler, and Tim Roughgarden. The price of stability for network design with fair cost allocation. SIAM Journal on Computing, 38(4):1602 1623, 2008. [Auletta et al., 2015] Vincenzo Auletta, Ioannis Caragiannis, Diodato Ferraioli, Clemente Galdi, and Giuseppe Persiano. Minority becomes majority in social networks. In Proceedings of the 11th International Conference on Web and Internet Economics (WINE), pages 74 88, 2015. [Auletta et al., 2016] Vincenzo Auletta, Ioannis Caragiannis, Diodato Ferraioli, Clemente Galdi, and Giuseppe Persiano. Generalized discrete preference games. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pages 53 59, 2016. [Bhawalkar et al., 2013] Kshipra Bhawalkar, Sreenivas Gollapudi, and Kamesh Munagala. Coevolutionary opinion formation games. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), pages 41 50, 2013. [Bil o et al., 2016] Vittorio Bil o, Angelo Fanelli, and Luca Moscardelli. Opinion formation games with dynamic social influences. In Proceedings of the 12th International Conference on Web and Internet Economics (WINE), pages 444 458, 2016. [Bindel et al., 2015] David Bindel, Jon M. Kleinberg, and Sigal Oren. How bad is forming your own opinion? Games and Economic Behavior, 92:248 265, 2015. [Chierichetti et al., 2013] Flavio Chierichetti, Jon M. Kleinberg, and Sigal Oren. On discrete preferences and coordination. In Proceedings of the 14th ACM Conference on Electronic Commerce (EC), pages 233 250, 2013. [De Groot, 1974] Morris H. De Groot. Reaching a consensus. Journal of the American Statistical Association, 69(345):118 121, 1974. [Fotakis et al., 2016] Dimitris Fotakis, Dimitris Palyvos Giannas, and Stratis Skoulakis. Opinion dynamics with local interactions. In Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI), pages 279 285, 2016. [Friedkin and Johnsen, 1990] Noah E. Friedkin and Eugene C. Johnsen. Social influence and opinions. Journal of Mathematical Sociology, 15(3-4):193 205, 1990. [Hegselmann and Krause, 2002] Rainer Hegselmann and Ulrich Krause. Opinion dynamics and bounded confidence models, analysis, and simulation. Journal of Artificial Societies and Social Simulation, 5(3), 2002. [Holme and Newman, 2006] Petter Holme and M. E. J. Newman. Nonequilibrium phase transition in the coevolution of networks and opinions. Physical Review E, 74, 2006. [Koutsoupias and Papadimitriou, 1999] Elias Koutsoupias and Christos H. Papadimitriou. Worst-case equilibria. In Proceedings of the 16th Annual Conference on Theoretical

Aspects of Computer Science (STACS), pages 404 413, 1999. [Mossel and Tamuz, 2014] Elchanan Mossel and Omer Tamuz. Opinion exchange dynamics. ar Xiv: 1401.4770, 2014. [Olshevsky and Tsitsiklis, 2009] Alex Olshevsky and John N. Tsitsiklis. Convergence speed in distributed consensus and averaging. SIAM Journal on Control and Optimization, 48(1):33 55, 2009. [Schwind et al., 2015] Nicolas Schwind, Katsumi Inoue, Gauvain Bourgne, S ebastien Konieczny, and Pierre Marquis. Belief revision games. In Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI), pages 1590 1596, 2015. [Tsang and Larson, 2014] Alan Tsang and Kate Larson. Opinion dynamics of skeptical agents. In Proceedings of the 13th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 277 284, 2014.

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence (IJCAI-17)