Modeling how agents form their opinions is of paramount importance for designing marketing and electoral campaigns. In this work, we present a new framework for opinion formation which generalizes the well-known Friedkin-Johnsen model by incorporating three important features: (i) social group membership, that limits the amount of influence that people not belonging to the same group may lead on a given agent; (ii) both attraction among friends, and repulsion among enemies; (iii) diferent strengths of influence lead from diferent people on a given agent, even if the social relationships among them are the same. We show that, despite its generality, our model always admits a pure Nash equilibrium which, under opportune mild conditions, is even unique. Next, we analyze the performance of these equilibria with respect to a social objective function defined as a convex combination, parametrized by a value ∈ [0, 1], of the costs yielded by the untruthfulness of the declared opinions and the total cost of social pressure. We prove bounds on both the price of anarchy and the price of stability which show that, for not-tooextreme values of , performance at equilibrium are very close to optimal ones. For instance, in several interesting scenarios, the prices of anarchy and stability are both equal to max{2, 1− }/ min{2, 1 } which never exceeds 2 for ∈ [1/5, 1/2]. Moreover, in many settings, we provide even better upper bounds on the prices of anarchy and stability, which are tight under mild assumptions.
In recent years, a lot of attention has been devoted to studying how people form their opinions, and how the social media afect the opinion formation process. Understanding these aspects is of fundamental importance for analysing and forecasting electoral flows and implement suitable electoral campaigns, or for marketing purposes.
Discussion Papers - 22nd International Conference of the Italian Association for Artificial Intelligence (AIxIA 2022) ⋆ This work was partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR “Algorithms, Games, and Digital Markets”, by “GNCS–INdAM” and by the PON R&I 2014-2020 Project TEBAKA "Sistema per acquisizione conoscenze di base del territorio”.
An extended version of this work appears in the proceedings of IJCAI 2022 [
Most of the approaches proposed in the literature usually assume that people try to “imitate”
their “friends”. This is, for example, the case of the celebrated DeGroot (DG) model [
All these models, however, focus on imitative behaviour only. Indeed, there are many
examples in which our opinion is not only influenced by imitation of our friends, but also by
rejection of our “enemies”. One example arises from youth subcultures, where peoples belonging
to two diferent subcultures, even if a strict relation exists among them (e.g., they are relatives
or they are in the same school), try to make opposite choices about style and interests, with
the goal to distinguish each from the other. Another example comes from politics, where the
position of a party about a topic sometimes arises more in opposition to adversaries rather
than from principles and values. To the best of our knowledge, very few works considered this
mixture of attraction and repulsion in opinion formation [
Both examples described above also highlight a fundamental feature of opinion formation that most of the discussed works neglect: membership in social groups. Indeed, followers of a subculture (e.g., hipsters) are used to limit their musical interests to the genre of reference of this subculture (e.g. indie), even if they are influenced by people listening to diferent music styles. Similarly, people belonging to a party usually support only opinions “allowed” by that party, despite the amount of social pressure they may face.
Yet another limitation of most of the considered models is that they assume a strength
of attraction (or dis-attraction) that is the same for each pair of friends (enemies), possibly
diversified only by a scaling factor measuring the weight of the social relationship. However, it
may not be the case that hipster guys are attracted in the same way by emo peers and by geek
peers, even if they all share the same social relationship. Similarly, the position of a right party
on a given topic may be influenced in diferent ways by a center party or by an extreme-right
party, even if the right party shares the same contacts with the other two (e.g., they are always
allied at elections). This degree of generality, but only restricted to attraction phenomenon, has
been considered before only by [
In this work, we tackle all the above limitations by proposing a new, general, model in
which people choose their opinion by trying to simultaneously imitate their “friends” and
distinguish themselves from their “enemies”. We allow opinions to be chosen from a continuous
set (diferently from [
Specifically, we model this opinion formation framework as a cost minimization game with agents, in which each agent belonging to a social group chooses an opinion whose distance from her private belief cannot exceed a certain threshold yielded by the boundaries of the group. In other words, while an agent is allowed to change her/his opinion, this opinion cannot lead this agent too far away from the cluster (social group) she/he feels to belong to.
As a consequence of her choice and of the choices of all the others, each agent experiences a cost which depends on functions: an increasing function (private influence function ), which measures the cost of agent for disagreeing with her own belief, and − 1 functions , for each ̸= (public influence functions ), which measure the cost of the social pressure. In particular, , is increasing (resp., decreasing) when agent is a friend (resp., an enemy) of agent . We stress that, despite of the huge mathematical challenges met in dealing with non-binary enemy relationships (one of the novelty of our model), most of our results only require all these functions to be continuous. Hence, our work provides a significant advancement along the direction of designing new models for opinion formation which may yield a good compromise between simplicity (needed for an analytical study) and expressive power.
Nevertheless, we also focus on special classes of games, that we name well-ordered, which
turn out to enjoy interesting theoretical properties, while still spanning many realistic
settings. Specifically, we consider opinion formation games that include the following additional
properties: (i) the social groups do not intersect (and thus the opinions of the members of a
group are always diferent from the opinions of the members of other groups), and (ii) all cost
functions are strictly convex (i.e., the marginal increment of the cost strictly increases (resp.,
decreases) as the distance between opinions increases). The first property is realized when the
social group membership is suficiently strong to avoid any overlap of the opinions of agents
belonging to diferent groups, despite they may influence each other. The second property
is highly motivated in opinion dynamics, too. Indeed, convex cost functions model scenarios
in which (a) the urgency of fixing the disagreement with close friends quickly grows as the
disagreement becomes larger and larger, and similarly, (b) putting distance among enemies
becomes more and more urgent when their opinions are close to each other. Furthermore, we
point out that convexity is a common assumption in opinion formation games (see, e.g., [
In light of the above considerations, our opinion formation framework and the special case
of well-ordered games are able to include and generalize most of the previously defined models.
Moreover, they can have multiple applications even in settings departing from opinion formation,
e.g., facility location with heterogeneous preferences [
Our contribution. We show that any game induced by our model admits at least a pure Nash equilibrium (i.e., a stable configuration in which each agent cannot reduce her cost via a unilateral change of opinion). We stress that this result does not require convexity or any other restrictive assumption to hold. In general, a game may admit diferent equilibria; however, we show that it is unique in well-ordered opinion formation games (that, diferently from general games, must satisfy some convexity assumptions).
Next, we focus on the evaluation of the quality of equilibria through the concepts of Price
of Anarchy (PoA) and Price of Stability (PoS), by following the literature on the topic (see, e.g.,
[
In this work, we focus on diferent ways to evaluating the quality of an equilibrium. A first
approach uses the utilitarian social cost, defined as the sum of the agents’ costs. This direction
has been taken, e.g., in [
We believe that all these approaches are useful and meaningful. Not only, but it is often useful
and meaningful to have, for example, equilibria that are close to be truthful (or close to be a
consensus) and, at the same time, represent a good compromise for the society as a whole. For
this reason, we propose to measure the performance of an equilibrium by means of the -social
influence cost , obtained by summing the cost of untruthfulness scaled by and the cost of social
pressure (i.e., distance from a consensus) scaled by 1 − , for any ∈ [
Our results highlight how PoA and PoS with respect to -social influence cost vary as the parameters of the system change: this will provide practically useful suggestions about the direction in which possible interventions of a social planner should occur. For example, our results suggest that, in order to guarantee that opinion formation converges to states with good social performance, one should try to avoid enemy relation or one should try to assure that social groups are “closed” as described in the definition of well-ordered games. Hence, the social planner may be interested in designing campaigns to enforce these properties.
Specifically we prove that for extreme values of (i.e., = 0 or = 1), the PoA and the PoS can grow arbitrarily large, as it may be impossible to reach an equilibrium that is a consensus or a truthful profile when considering agents with general cost functions and possessing both attraction and dis-attraction attitudes. Nevertheless, we surprisingly show that the PoA and the PoS are usually not very large when is suficiently far from the extremes. Specifically, we prove that the PoS is always (i.e., we do not require convexity or other assumptions) bounded by mmainx{{22,, 11−− }} = ︁( max {︁ 1 , 1− 1 }︁)︁ . The same bound holds even for the PoA in well-ordered opinion formation games, while in general the PoA can be unbounded. Moreover, when the cost functions obey some additional mild assumptions, better bounds on the PoA are possible. The technique used to prove this result may be of independent interest: a generalization of the primal-dual technique introduced in [24], and applied for the first time in this setting. We additionally show that these bounds are often tight. In the full version, we also provide applications of our general results to specific classes of well-studied games, by proving tight numerical bounds.
Due to space limitation, for all claims in the next sections, proofs are omitted. We refer the interested reader to the full version for more details.
Generalized Opinion Formation Games. Let := [] be a set of agents, where [] denotes
the set {1, . . . , }. Each agent ∈ [] has a private belief ∈ [
We define = (1, . . . , ) to be the private belief vector and let = ((−1 , 1+), . . . , (− , + ))
be the maximum deviation vector. We assume w.l.o.g. that 0 ≤ 1 ≤ . . . ≤ ≤ 1. Each agent
∈ [] declares a public opinion ∈ [
Each agent ∈ [] in an opinion profile incurs in a public influence cost ,() defined as ,() := ∑︀∈[]:̸= , (| − |), where, for any pair (, ) such that ̸= , , : (0, 1] → R≥ 0 is called the (, )-public influence function and satisfies the following properties: (i) , () = ,() for any ∈ (0, 1]; (ii) , is continuous in (0, 1]; (iii) ∃ lim→0+ , () ∈ R≥ 0 ∪ {∞}. Observe that we do not have any constraints on the slope of , . This allows us to model both attraction among friends (when , is increasing), and repulsion among enemies (when , is decreasing). Also, by choosing diferent functions for each pair of agents, we can represent diferent strengths of attraction and repulsion.
Moreover, each agent ∈ [] in an opinion profile incurs also in a private influence cost
,() defined as ,() := (| − |), where : [
Classes of GOF games. Given a GOF game , let ℱ () and () denote the set of non-null public and private influence functions of , respectively. A GOF game is convex if all the functions in ℱ () and () are convex, thus implying that the marginal increment of the cost increases (resp., decreases) as the distance between opinions increases.
A GOF game is unconstrained if − = + = 1 for any ∈ [], i.e., if social group
membership is not considered. is an isolation game if all the functions in ℱ () are
nonincreasing, i.e., every agent wants to be as far as possible from other agents. is an aggregation
game if all the functions in () are non-decreasing, i.e., every agent wants to imitate her
friends. The class of unconstrained aggregation games includes the standard opinion formation
games introduced in [
A GOF game is well-ordered if it is convex, and we can organize the agents in clusters 1, 2, . . . , such that: i each cluster is a non-empty set of consecutive agents; ii for any cluster and , ∈ , we have that each public influence function , is nondecreasing, i.e., the sub-game restricted to each cluster is an aggregation game; iii for any ∈ [ − 1], and any ∈ and ∈ +1, we have that + + − ≤ − , i.e., for any opinion profile , and for any , ∈ [] and ∈ [ − 1] with ∈ and ∈ +1, we have that ≤ +1.
Roughly speaking, in well-ordered games, all groups of agents are organized in disjoint intervals on the line, in such a way that one agent belonging to a group cannot express an opinion outside the corresponding interval. Despite this geometric structure of the agents’ opinions is undoubtedly an extreme choice, it provides a realistic model for many settings. Indeed, it is often the case that changes in the structure of social groups do not occur among existing groups, but only as a side-efect of the birth of new groups, that may be endogenously provoked by alliances between extremists of existing groups (e.g., as for parties), or exogenously by the creation of a new product (e.g., in youth subcultures).
Observe that classical opinion formation games [
Finally, a well-ordered GOF game is regular if all functions in ℱ () and () are continuously
diferentiable (i.e., the left and right derivatives are equal), and the derivative in = 0 is null
for each function ∈ () and function , ∈ ℱ () with , belonging to the same cluster.
Observe that the diferentiability of the cost functions models the absence of “jumps” in the
individual costs while the agents continuously change their public opinions, and it is a standard
assumption in several opinion formation games (see, for instance, [
Pure Nash Equilibria and -Social Influence Cost. Given an opinion profile and ∈ [
Given ∈ (0, 1), the -social influence cost SUM () of the opinion profile is defined as ∑︀( · ,() + (1 − ) · ,()) = 2 ∑︀> , (| − |) + (1 − ) ∑︀ (| − |), i.e., it is a convex combination under parameter of the sum of all the public influence costs and the sum of all the private influence costs. Let () := inf∈SP() SUM (). -Price of Anarchy and -Price of Stability. To evaluate the performance of equilibria with respect to the -social influence, we define the following concepts: the -price of anarchy of game , defined as PoA () := sup∈E() SU M (()) , which is the worst-case ratio between the performance of an equilibrium of and the optimal -social influence cost of , and the -price of stability of game , defined as PoS () := inf∈E() SU M (()) , which is the best-case ratio between the performance of an equilibrium of and the optimal -social influence cost of .
In order to prove that any GOF game possesses an equilibrium, we use a potential function argument. Given a GOF game , a function Φ : SP() → R≥ 0 is a potential function of if Φ( ) − Φ( − , ) = () − (− , ) for any opinion profile , any agent ∈ [], and any strategy of agent . Let Φ be the function such that Φ( ) := ∑︀> , (| − |) + ∑︀ (| − |), for any opinion profile . It is not hard to check that following lemmas hold.
As shown in [25], any global minimum of a potential function is a pure Nash equilibrium. Thus, with the help of Lemma 1 and Lemma 2, we can prove the following theorem.
minimum points of Φ are equilibria.
In the case of well-ordered GOF games, we have a better characterization of the set of equilibria.
with the set of global minimum points of Φ ; (ii) the set of equilibria is a convex set; (iii) if the non-null public influence functions are strictly convex, then there exists a unique equilibrium.
We have that the -price of anarchy can be unbounded, even for unconstrained and convex isolation games with two agents and linear functions.
PoA () = ∞ for any ∈ (0, 1).
Diferently from the -price of anarchy, for the -price of stability we get a tight bound which is parametrized by ∈ (0, 1) and is always finite.
Theorem 4. Given a GOF game , we have that PoS () ≤ mmainx{{22,, 11−− }} . This result is tight.
game with two agents and linear public and private influence functions such that PoS () ≥ max{2, 1− } min{2, 1− } − .
In the following theorem, we show that the upper bound on the -price of stability established in Theorem 4 extends to the -price of anarchy if the considered game is well-ordered.
mmainx{{22,, 11−− }} .
If the considered well-ordered game is also regular, we can obtain a generally better upper
bound on the -price of anarchy, that depends also on the specific public and private influence
functions, and not only on . To prove these bounds, we generalize the primal-dual method
introduced in [24] by incorporating some topological properties of regular well-ordered games.
This approach, which is of independent interest and exports for the first time the primal-dual
method outside the realm of congestion games, shares some similarities with the notion of local
smoothness [
Given , , , ≥ convention that /0 := ∞ if > 0 and /0 := 1 if ≤ 0.
0 and a real function ℎ, let (, ℎ, , ) = · ℎ()+ (− )· ℎ() · ℎ() , with the
PoA () ≤
sup
∈ℱ(),∈(),
,,^,^∈[
Finally, as an application of Theorem 6, we show how our findings apply to some specific
classes of games. The upper bound of Theorem 6 can be applied to derive tight bounds on the
-price of anarchy of aggregation games with influence functions of type , where > 1 is
ifxed and ≥ 0 depends on the agent indexes (i.e., := for private influence functions and
:= , for public ones); we stress that such influence functions have been already considered
for standard opinion formation games (see, for instance, [
In this work, we provided a new model for opinion formation that encompasses social group membership, and both attraction and repulsion among agents. In this way, we try to model many aspects of opinion formation that occur in real-world examples, such as youth subcultures or political parties. We proved that equilibria always exist and provided tight bounds on their quality.
We believe that our model can be useful for analyzing and forecasting the difusion of opinion in social networks, and suggesting specific strategies for marketing (e.g., for target advertising [30]) and for election control [31]. Another interesting direction would be to embed our opinion formation process in an evolving setting: this would give useful hints on the processes that lead to radical changes in cultures and styles. heterogeneous majority dynamics, in: WINE, 2017, pp. 30–43. [23] V. Auletta, D. Ferraioli, G. Greco, Reasoning about consensus when opinions difuse through majority dynamics, in: IJCAI, 2018, pp. 49–55. [24] V. Bilò, A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games, Theory of Computing Systems 62 (2018) 1288 – 1317. [25] D. Monderer, L. S. Shapley, Potential games, Games and Economic Behavior 14 (1996) 124–143. [26] T. Roughgarden, F. Schoppmann, Local smoothness and the price of anarchy in splittable congestion games, Journal of Economic Theory 156 (2015) 317–342. [27] V. Bilò, C. Vinci, On the impact of singleton strategies in congestion games, in: ESA, 2017, pp. 17:1–17:14. [28] V. Bilò, L. Moscardelli, C. Vinci, Uniform mixed equilibria in network congestion games with link failures, in: ICALP, 2018, pp. 146:1–146:14. [29] F. Benita, V. Bilò, B. Monnot, G. Piliouras, C. Vinci, Data-driven models of selfish routing:
Why price of anarchy does depend on network topology, in: WINE, 2020, pp. 252–265. [30] D. Kempe, J. M. Kleinberg, E. Tardos, Maximizing the spread of influence through a social network, Theory of Computing 11 (2015) 105–147. [31] B. Wilder, Y. Vorobeychik, Controlling elections through social influence, in: AAMAS, 2018, pp. 265–273.