# Influence and Counter-Influence in Networks

Christophe Bravard, Jacques Durieu, Sudipta Sarangi, Corinne Touati

► To cite this version:

Christophe Bravard, Jacques Durieu, Sudipta Sarangi, Corinne Touati. Influence and Counter-Influence in Networks. 2024, 42 p. hal-04733885

HAL Id: hal-04733885

https://inria.hal.science/hal-04733885v1

Submitted on 28 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
**Influence and**
**Counter-Influence in Networks**

By Christophe Bravarda, Jacques Durieua, Sudipta Sarangib, and
Corinne Touati
# Influence and Counter-Influence in Networks*

Christophe Bravard<sup>a</sup>, Jacques Durieu<sup>a</sup>, Sudipta Sarangi<sup>b</sup>, Corinne Touati<sup>c</sup>

July 23, 2024

## Abstract

We study influence competition between two players: a designer who can shape the pattern of interaction between a set of agents and influence them, and an adversary who can counter-influence these agents. Creating the network and influencing agents are both costly activities for the two players. The final opinion and the vote of the agents depend on how the two players influence them as well as the opinion of their neighbors. Agent votes determine the payoffs of the two players and to win the designer must obtain the vote of all the agents. We begin by assuming that the designer has the better influence technology, and subsequently relax this assumption. We find that optimal strategies depend on the different costs incurred by the players, as well as who has the advantage in influence technology. We also study what happens when links between agents can arise randomly with a known exogenous probability, taking away some of the designer's control over the network. We provide conditions under which the results of the benchmark model are preserved. Next, we modify two additional assumptions: (1) requiring the designer to only secure a majority of the votes, and (2) allowing the agents interact for several rounds before casting the final vote. In both cases, the designer needs fewer resources to win the game.

<sup>a</sup>Univ. Grenoble Alpes, INRAE, CNRS, Grenoble INP, GAEL, 38000 Grenoble, France. <sup>b</sup>DIW Berlin and Department of Economics, Virginia Tech Blacksburg VA 24061 - 0316, USA. <sup>c</sup>Inria. Corresponding author email: ssarangi@vt.edu.

**JEL Classification:** D74, D85.

**Key Words:** Influential players, Network design.

<footnote>*We would like to thank Eric Bahel, Pascal Billand, Niloy Bose, Michel Grabisch, Hans Haller, Matt Kovach, Madhav Marathe, KS Malikarjuna Rao, Agnieszka Rusinowska and Gerelt Tserenjigmid for helpful suggestions.</footnote>
# 1 Introduction

Differences of opinion are a way of life and people frequently try to persuade others to adopt their way of thinking. In this paper, we model this phenomenon using two players who both influence a set of agents to vote for their opinion. Imagine, for instance, a politician who wishes to convince others to vote in favor of her bill, while a rival politician may want to counter-influence them against the bill. A manager in a firm might want a particular marketing strategy, and influence others in its favor while another member might influence others in favor of a different strategy. Such a phenomenon can also occur in social media. A social media influencer builds their own network and promotes certain products on it. A rival influencer cannot alter the influencer's network but can certainly promote other products within the first influencer's network. Our model captures another important aspect: agents are not just influenced by the two players; they are embedded in a network and can also affect each other's opinions before they vote.

Consider, for example, the case of a parliamentary assembly where the majority party has a narrow majority, and the adoption of a specific bill requires a unanimous vote of the members of this party. Then, the leader of the majority party aims to persuade other party members to vote for the bill.<fnref n="1" /> Clearly, he has the ability to influence the opinion of party members on a particular issue. Moreover, the leader of the majority party has the authority to shape the interaction pattern among party members by organizing appointments to special committees or by providing a platform for members to deliberate on relevant issues. He can also organize work meetings to present the bill and emphasize its importance to specific members of the party. Then, he can ask participants to contact other party members they are close to and share information about the bill. Note that the members of the majority party may also be pressured by opponents of the bill to abstain or vote against it. It is noteworthy that the network in which politicians are embedded plays a crucial role in their vote. Indeed, many studies point to a social and mimetic dimension in the determination of legislators' votes. Each legislator tends to vote to some extent like the legislators with whom he or she is in contact. For example, Cohen and Malloy (2014) find that networks play an important role in the behavior of US senators, especially in close votes. This result underscores the fact that when every vote can be critical to an outcome, the influence of networks is particularly powerful. Similarly, Battaglini et al. (2023) find that a legislator is more likely to abstain when the majority of his neighbors

<footnote n="1">¹As underlined by Barber and McCarty (2016, p. 62) and Pearson (2015), in both the U.S. House and the Senate, party leaders have become increasingly powerful and, as such, can apply greater pressure on members to vote along party lines (see also Aldrich, 1996, Rohde, 1991).</footnote>
abstain.

We consider a model involving two players: a designer (*De*) and an adversary (*Ad*). They engage in a sequential competition, aiming to influence agents in a trinary choice scenario (0, 1 or no opinion). Here, *De* wants the agents to vote 1, while *Ad* tries to avoid this outcome. Thus, the interaction between *De* and *Ad* takes the form of a *zero-sum game*: either *De* will win the voting game or *Ad* will win. Note that neither *De* nor *Ad* themselves votes in the game. *De* makes two decisions: she sets up the network by *forming links* between agents, and *influences* a subset of them. Then, *Ad* decides which agents he *will influence*. Forming links and exerting influence are both costly activities. The influence activities of *De* and *Ad* determine the initial opinion of agents. Each agent then communicates with his neighbors. The agent's final opinion is a convex combination of his initial opinion and the opinions of his neighbors. Thus, the agents are not simply dummy players. They also play the role of secondary influencers. Finally, each agent votes on the basis of his final opinion. This type of rule is commonly employed in models of influence and social learning, where the focus is often on studying the propagation of influence among non-strategic agents (see Jackson and Yariv, 2007, Golub and Jackson, 2010, Grabisch et al., 2018).

In our benchmark model, we make the following assumptions. First, *De* wins the zero-sum game when all agents vote 1, i.e., *De* must achieve unanimous support for 1. Second, when both *De* and *Ad* exert influence on an agent, the latter prioritizes *De* over *Ad*. This can be interpreted as the superiority of *De* in influence technology. Each of these assumptions is relaxed in a subsequent extension section.

Our first (and main) result concerns the Subgame Perfect Equilibrium (SPNE) of the sequential move game where *De* forms the network and influences agents in the first stage, and *Ad* influences agents in the second stage. In particular, we characterize the strategies employed by *De* in the SPNE, i.e., her optimal strategies. These strategies depend on the cost of forming links relative to the cost of influencing agents for *De* and the cost of influencing agents for *Ad*. In particular, if the cost of forming links is high relative to the cost of influencing agents for *De*, her optimal strategy is to form no links and influence each agent. The cost of influencing agents for *Ad* determines the maximum number of agents he can influence. When this maximum number of agents is low, the optimal strategy for *De* is to form a partial-star network. In such a network, some agents are isolated, they have no links, and some agents, the peripherals, have a single link with one central agent. *De* influences the center, the isolated agents, and some of the peripheral agents. This strategy allows *De* to benefit from not having to influence more agents than the maximum number of agents that *Ad* can influence. When this maximum number of agents is high, the optimal strategy for *De* is to form a quasi-core-periphery net-
work. In such a network, agents in the core are linked among themselves, while each agent
in the periphery has a single link with an agent in the core. In addition, *De* exclusively exerts
influence on agents within the core. This specific strategy minimizes the number of agents that
*De* influences, since *Ad* can influence all the neighbors of each agent that are not influenced
by *De*.

Our second result serves as a robustness check of our main result, since we allow agents that are not linked in the original network built by *De* to interact with positive probability that is common knowledge. In other words, additional links can randomly appear after *De* has made her choices. We provide an upper bound on the probability of unwanted links that allows us to preserve our main results.

In the extension section, we first allow for repeated interactions among the agents. We show
that, for sufficiently low link formation costs, the number of agents that *De* must influence in
an optimal strategy is lower than in our benchmark model. Indeed, there are situations where
*De* only needs to influence one agent to obtain a unanimous vote. Next, we examine the case
where *De* wins when a majority of the agents vote 1. We establish that the optimal strategies
for *De* are qualitatively similar to those of the benchmark model, but less costly, as they involve
either fewer links or a smaller number of agents to influence. Finally, we assume that *Ad* has
the superior influence technology. Consequently, when an agent is influenced by both *De* and
*Ad*, he believes *Ad*. This assumption considerably modifies *De*'s optimal strategies. Thus,
*De* builds either a network where each agent has the same number of neighbors and influences
all the agents, or a network where the agents are divided into two groups and each member
of the first group is influenced by *De* and forms *k* links with the other members of his group,
while each member of the other group is not influenced by *De* and forms *k'* < *k* links with the
agents in the first group.

To the best of our knowledge, this is the first paper to introduce competition influencers.
However, it relates to multiple strands of the existing literature.

In the first strand, network protection is orchestrated by a designer, mirroring the structure
of our model. Dziubiński and Goyal (2013, 2017) focus on the optimal design and defense
of networks, assuming the presence of an intelligent attacker or adversary, akin to our model.
In these models, the designer is responsible for forming links between the agents and must
undertake measures to protect them, ensuring their survival. The designer's objective is to
maximize the size of connected components in the network obtained as a result of the attacks of
the adversary. Goyal and Vigier (2014) extend the work of Dziubiński and Goyal by allowing
the attacks (or threats) to spread like a contagion. Bravard, Charoin, and Touati (2016) modify
Dziubiński and Goyal's (2013) model by considering a situation where the adversary targets
links rather than nodes, and the designer has to protect links rather than nodes. Hoyer and De
Jaegher (2016) also explore a framework in which a designer must build the network with the
objective of maintaining connectivity in the event of potential attacks. In their model, certain
parts of the network remain intrinsically vulnerable: they cannot be protected by the designer.
The authors characterize the optimal networks in the event of links or nodes being removed by
examining different cost ranges. In contrast to these articles, in our model we are interested in
the opinion of each agent. The designer's objective is not to preserve the connectivity of the
network but to influence (directly or indirectly) the agents. Moreover, in our model the agents
also play a role since they influence each other and their vote determines the final outcome of
the game between influencers.

The second strand of literature involves decentralized protection carried out by individual
agents within the network. Cabrales, Gottardi, and Vega-Redondo (2017) study the propaga-
tion of attacks in networks of financial firms where financial risk can spread between connected
firms. Baccara and Bar-Isaac (2008) explore how the connectivity of criminal networks in-
creases vulnerability because of external threats. Agents make connectivity-related decisions
in these models. In Acemoglu, Malekian, and Ozdaglar (2016) agents are connected but in a
random network. Agents have to invest in protection to be immune which depends on their
links and the probability of being infected in the random network. In Haller and Hoyer (2019)
group members individually sponsor costly links and form an information network. An ad-
versary aims to disrupt the information flow within the network by deleting some of the links.
The authors study how the group as a whole responds to such a common enemy. In contrast
to these papers, we introduce a distinctive perspective with a two-player game involving a de-
signer and an adversary, both focusing on influencing agents rather than maintaining/removing
connectivity.

The third strand of literature focuses on the spread of misinformation through social media. Bloch et al. (2018) study a situation where there are two types of players: those who are biased in favor of the message 1 and those who are not biased. Each player can either transmit the message or block it. Biased players have an interest in transmitting messages that only favor 1, while unbiased players only transmit messages they find credible. Bloch et al. show that the social network acts as a filter, limiting the spread of untrustworthy messages compared to a situation where the message would be spread to the entire population by a single sender. Bravard et al. (2023) modify this framework by assuming that players are aware of the biases of their neighbors. Acemoglu et al. (2024) present a model of online sharing where agents observe an article on a social network and decide whether to share it or not. The article may contain misinformation, and agents gain utility from social media interactions but lose utility if they
spread misinformation. The agents are not biased, but have different prior beliefs. The authors analyze the policy that a regulator should adopt to limit the spread of misinformation given that social media wants to maximize the virality of messages. In contrast to previous work, we want to model the competition between two players who want to persuade agents in a social network. Our goal is to explore the optimal strategies of a player who can both shape the interaction structure of the agents and influence them to resist competing messages. Furthermore, in one of our extensions we consider that the network is not given or fully controlled by the designer by letting random links occur.

The rest of the paper is organized as follows. In Section 2, we introduce the model setup. In Section 3, we establish results for the benchmark model and also present a robustness check taking into account the possibility of unwanted links. In Section 4, we deal with our three extensions. We conclude in Section 5. All proofs are provided in the appendix.

## 2 Model Setup

Let $\llbracket a, b \rrbracket = \{\ell \in \mathbb{N}, a \le \ell \le b\}$. Moreover, let $\lfloor x \rfloor$ and $\lceil x \rceil$ be respectively the largest integer less than $x$ and the smallest integer greater than $x$. Further, for every set $X$, $\#X$ is its cardinality.

**Players and Agents.** We assume that there are two players or primary influencers called respectively the *Designer*, *De/she*, and the *Adversary*, *Ad/he*. Both *De* and *Ad* act strategically. In addition to these two players, there is a set of agents $\mathcal{N} = \llbracket 1, n \rrbracket, n \ge 4$. In the following, we will describe the behavior of these $n$ agents which is non-strategic in nature.

**Networks.** We assume that agents are located on an undirected network. An undirected network $g$ is a pair $(\mathcal{N}, E(g))$, where $E(g) \subseteq \mathcal{N} \times \mathcal{N}$ is the set of links. We denote by $G[\mathcal{N}]$ the set of all networks with $\mathcal{N}$ as the set of agents. A link between two agents $i$ and $j$ is interpreted as the existence of a relationship between these agents. With a slight abuse of notation, we denote by $ij$ the link between agents $i$ and $j$ in $g$, i.e., $ij \in E(g)$. Let $\mathcal{A}(g)$ be an $n \times n$ adjacency matrix of the undirected network $g$, that is, for every $(i,j) \in \mathcal{N} \times \mathcal{N}$, $\mathcal{A}_{i,j}(g) \in \{0,1\}$, where $\mathcal{A}_{i,j}(g) = 1$ if and only if $ij \in E(g)$. By convention, $\mathcal{A}_{i,i}(g) = 0$. Clearly, $\mathcal{A}(g)$ is symmetric.

Let $\mathcal{N}_i(g) = \{j \in \mathcal{N} : ij \in E(g)\}$ be the set of neighbors of agent $i \in \mathcal{N}$. We say that $i$ is an isolated agent in $g$ when $\#\mathcal{N}_i(g) = 0$. A path $P_{i,j}(g)$ between agents $i = i_0$ and $j = i_m$, is a sequence of links of the type $i_0 i_1, \dots, i_\ell i_{\ell+1}, \dots, i_{m-1} i_m$ where each link $i_\ell i_{\ell+1} \in E(g)$. The length of a path is the number of links it contains. A cycle is a path where $i$ and $j$ coincide. A network $g$ is connected if there exists a path between $i \in \mathcal{N}$ and $j \in \mathcal{N} \setminus \{i\}$ for every pair
(i, j). A subnetwork $g[\mathcal{N}'] = (\mathcal{N}', E(g[\mathcal{N}']))$ of network $g$ is a network such that $\mathcal{N}' \subseteq \mathcal{N}$ and for $i, j \in \mathcal{N}'$, we have $ij \in E(g[\mathcal{N}'])$ if and only if $ij \in E(g)$. The (geodesic) distance between agents $i$ and $j$ in $g$, $d(i, j; g)$, is the length of any shortest path joining them.

Let us now present some specific architectures. The *empty network*, $g^e$, is a network where all agents have formed no links. In the *complete network* $g$, $A_{i,j}(g) = 1$ for every $i \in \mathcal{N}$ and $j \in \mathcal{N} \setminus \{i\}$. A *star* is a network where there is a *central agent*, $i_c$, who has formed links with all other agents and there are no links between $i$ and $j$ for $i, j \in \mathcal{N} \setminus \{i_c\}$. Agents in $\mathcal{N} \setminus \{i_c\}$ are called *peripheral agents*. A *partial-star* $g$ is a network where $\mathcal{N}$ admits a partition into two subsets $\mathcal{X}$ and $\mathcal{N} \setminus \mathcal{X}$ such that $g[\mathcal{X}]$ is a *star* and agents in $\mathcal{N} \setminus \mathcal{X}$ are isolated in $g$. We illustrate a *star* in Figure 1 (a), and a *partial-star* in Figure 1 (b) where $\mathcal{X}$ contains all agents colored white and $\mathcal{N} \setminus \mathcal{X}$ contains all agents colored black. Partial-stars with special properties play a crucial role in our paper. In these particular partial-stars, the *center*, $i_c$, belongs to a special set of agents called $\mathcal{Y}$ that contains all isolated agents and $p$ agents that are peripheral. Moreover, all agents in $\mathcal{N} \setminus \mathcal{Y}$ are peripheral agents. Thus, in the following definition we need the value of $p$ and the set $\mathcal{Y}$.

<figure><img src="image_2.png" /><figcaption>Figure 1: Illustrations of Stars and Partial-stars</figcaption></figure>

**Definition 1** For $p \in [1, n-2]$, and $\mathcal{Y} \subset \mathcal{N}$, $g$ is a $(p, \mathcal{Y})$-partial-star when it is a partial-star and $\mathcal{Y}$ contains the central agent, $i_c$, $p$ peripheral agents, and all the isolated agents of $g$.

Note that since $g$ is a partial-star, peripheral agents in $\mathcal{Y}$ and $\mathcal{N} \setminus \mathcal{Y}$ are only connected to $i_c$.

Let us illustrate this definition with network $g^1$, drawn in Figure 2 (a). Agents colored white belong to $\mathcal{Y} = [1, 5]$, and agents colored black belong to $\mathcal{N} \setminus \mathcal{Y} = [6, 13]$. We observe that $g^1$ is a partial-star. The number of peripheral agents in $g^1[\mathcal{Y}]$, $p$, is $\#[2, 3] = 2$. Finally, each agent in $\mathcal{N} \setminus \mathcal{Y}$ is linked to $i_c$.

We now present specific networks called *quasi-core-periphery networks* that are close to the core-periphery networks widely used in the literature. In a core-periphery network, the set of agents is divided into two disjoint subsets: the core and the periphery. Agents in the core have at least as many neighbors within the core as in the periphery, and agents in the periphery
<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /><figcaption>Figure 2: Illustrations of $(p, \mathcal{Y})$-partial-star and $(q, \mathcal{Y})$-MQC</figcaption></figure>

are only connected to nodes in the core. In a quasi-core-periphery network, all these properties are preserved, but unlike a star network, not all links involve the same (central) agent. In the next definition, we present specific quasi-core-periphery networks that minimize the number of links, given that each member of the core, called $\mathcal{Y}$, has $q$ times more neighbors that belong to $\mathcal{Y}$ than neighbors that belong to $\mathcal{N} \setminus \mathcal{Y}$. Moreover, each agent in $\mathcal{N} \setminus \mathcal{Y}$ is connected to only one agent belonging to $\mathcal{Y}$.

**Definition 2** For $q \in (0, 1]$ and $\mathcal{Y} \subset \mathcal{N}$, $g$ is a $(q, \mathcal{Y})$-quasi-core-periphery network if $g$ admits a partition of $\mathcal{N}$ into two subsets, $\mathcal{Y}$ and $\mathcal{N} \setminus \mathcal{Y}$, called the core and the periphery respectively, and for every non-isolated $i \in \mathcal{N}$, there are $j, k \in \mathcal{N} \setminus \{i\}$, with $A_{j,k}(g) = 1$. Moreover, the following properties hold:

(Q1) for every $j \in \mathcal{Y}$, $\sum_{\ell \in \mathcal{Y}} A_{j,\ell}(g) \ge q \sum_{\ell \in \mathcal{N} \setminus \mathcal{Y}} A_{j,\ell}(g)$; and

(Q2) for every $j \in \mathcal{N} \setminus \mathcal{Y}$, $\sum_{j \in \mathcal{Y}} A_{i,j}(g) = 1$ and $\sum_{j \in \mathcal{N} \setminus \mathcal{Y}} A_{i,j}(g) = 0$.

A network $g$ is a $(q, \mathcal{Y})$-minimal-QC, denoted by $(q, \mathcal{Y})$-MQC, if it is a $(q, \mathcal{Y})$-quasi-core-periphery network with a smaller number of links.<fnref n="2" />

Note that a $(q, \mathcal{Y})$-MQC is not a partial-star since there are $j, k \in \mathcal{N} \setminus \{i\}$, with $A_{jk} = 1$. Moreover, we do not exclude the possibility that there are isolated agents in $\mathcal{Y}$. An important property of $(q, \mathcal{Y})$-MQC is that there are $n - \#\mathcal{Y}$ links between agents in $\mathcal{Y}$ and agents in $\mathcal{N} \setminus \mathcal{Y}$, and at least $\lfloor \frac{q(n - \#\mathcal{Y})}{2} \rfloor$ links between agents in $\mathcal{I}_{De}$.

We claim that $g^2$ in Figure 2 (b) is a $(1, \lfloor 1, 4 \rfloor)$-MQC network. In $g^2$, agents in $\lfloor 1, 4 \rfloor$, colored

<footnote n="2">²This definition does not imply anything about the existence of $(q, \mathcal{X})$-MQC networks. In Appendix A.1, we define a class of networks that are $(q, \mathcal{X})$-MQC and provide a constructive algorithm that ensures their existence.</footnote>
white belong to $\mathcal{Y}$, and agents in $[5, 14]$, colored black belong to $\mathcal{N} \setminus \mathcal{Y}$. We have $q = 1$. Hence, $g^2[\mathcal{Y}]$ is connected, and (Q1) holds since each agent in $[1, 4]$ is linked with a number of agents in $[1, 4]$ that is at least equal to the number of agents in $[5, 14]$ with whom he is linked. Moreover, (Q2) is satisfied since each agent in $[5, 14]$ is linked with exactly one agent in $[1, 4]$. Finally, there is no $(1, [1, 4])$-quasi-core-periphery network with a smaller number of links than $g^2$.

**Strategies of the Players.** One of the crucial features of our paper concerns the possibilities for the primary influencers to modify the agents’ initial opinions. In addition, $De$ has the ability to shape the interaction structure of the agents, i.e., to create the network $g$. The set of agents influenced by $De$ is denoted by $\mathcal{I}_{De} \subseteq \mathcal{N}$. Similarly, the set of agents influenced by $Ad$ is denoted by $\mathcal{I}_{Ad} \subseteq \mathcal{N}$.

Formally, a strategy for $De$, $s$, is a mapping that assigns to $\mathcal{N}$ a pair $(g[s], \mathcal{I}_{De}[s]) \in G[\mathcal{N}] \times 2^{\mathcal{N}}$. When there is no ambiguity, we write $(g, \mathcal{I}_{De})$ instead of $(g[s], \mathcal{I}_{De}[s])$. Let $S^{De}$ be the set of strategies of player $De$. $S^{De}$ is defined as the set of mappings from $\mathcal{N}$ to $G[\mathcal{N}] \times 2^{\mathcal{N}}$.

Similarly, a strategy for $Ad$ is a mapping, $\sigma$ that assigns to each pair $(g, \mathcal{I}_{De})$ a set of agents $\mathcal{I}_{Ad} \subseteq \mathcal{N}$. Let $S^{Ad}$ be the set of strategies of player $Ad$, i.e., $S^{Ad}$ is defined as the set of mappings from $G[\mathcal{N}] \times 2^{\mathcal{N}}$ to $2^{\mathcal{N}}$.

Given $\mathcal{N}$, every pair of strategies $(s, \sigma)$ induces a triple $(g[s], \mathcal{I}_{De}[s], \mathcal{I}_{Ad}[\sigma])$, denoted by $(g, \mathcal{I}_{De}, \mathcal{I}_{Ad})$ when there is no ambiguity.

We now present different strategies that play an important role in our analysis. In the *complete influence-empty network strategy*, $De$ forms the empty network and influences all agents. In a $(q, \mathcal{Y})$-influence-MQC network strategy, $De$ forms a $(q, \mathcal{Y})$-MQC network and influences agents in $\mathcal{Y}$. In a $(p, \mathcal{Y})$-influence-partial-star strategy, $De$ forms a $(p, \mathcal{Y})$-partial-star and influences agents in $\mathcal{Y}$.

**Initial Opinion of Agents.** We assume that before players $De$ and $Ad$ influence agent $i$, the latter has no opinion, $\emptyset$. If $i$ is influenced neither by $De$, nor by $Ad$, his initial opinion, $\theta_i$, continues to be $\emptyset$.<fnref n="3" /> If only $De$ (or $Ad$) influences agent $i$, then the initial opinion of $i$ is 1 (or 0). Suppose agent $i$ is influenced by both primary influencers, i.e., $i \in \mathcal{I}_{De} \cup \mathcal{I}_{Ad}$. Then, in this game of influence and counter-influence there are only two possibilities: either $De$ is successful or $Ad$ is successful.<fnref n="4" /> First, $De$ has a greater ability to influence than $Ad$ (for instance because of better technology), and $\theta_i = 1$ when $i \in \mathcal{I}_{De} \cup \mathcal{I}_{Ad}$. This case is presented

<footnote n="3">³The results obtained in the benchmark model are not qualitatively affected by the assumption that agents have no initial opinion and maintain this opinion when not influenced.</footnote>

<footnote n="4">⁴We ignore the case where both $De$ and $Ad$ cancel out each other influence. This is akin to analyzing the model where these players belong to the set of uninfluenced agents and therefore is ignored here.</footnote>
in the next section. Second, Ad has a greater ability to influence an agent than De, and $\theta_i = 0$, when $i \in \mathcal{I}_{De} \cup \mathcal{I}_{Ad}$. This case is examined in the extension section. Thus, in our benchmark model, the initial opinion of each agent $i$ is given by

$$ \theta_i = \begin{cases} 1 & \text{if } i \in \mathcal{I}_{De}, \\ 0 & \text{if } i \in \mathcal{I}_{Ad} \setminus \mathcal{I}_{De}, \\ \emptyset & \text{if } i \notin \mathcal{I}_{De} \cup \mathcal{I}_{Ad}. \end{cases} $$

The n-uple $\theta = (\theta_i)_{i \in \mathcal{N}}$ summarizes the initial opinion of every agent $i \in \mathcal{N}$.

**Final Opinion of Agents.** Each agent $i$ forms his final opinion by taking into account his own initial opinion, $\theta_i$, and the weighted average of his neighbors’ initial opinion. We denote by $\mathcal{N}(k, \theta) = \{j \in \mathcal{N} : \theta_j = k, k \in \{\emptyset, 0, 1\}\}$ the set of agents with initial opinion $k$. The set of neighbors of agent $i$ with $k \in \{\emptyset, 0, 1\}$ as initial opinion is denoted by $\mathcal{N}_i^k(g) = \{j \in \mathcal{N}_i(g) \cap \mathcal{N}(k, \theta)\}$. Moreover, when $\mathcal{N}_i^0(g) \cup \mathcal{N}_i^1(g) \neq \emptyset$, let

$$ \bar{\Theta}_i = \frac{1}{\#\mathcal{N}_i^0(g) + \#\mathcal{N}_i^1(g)} \sum_{j \in \mathcal{N}_i^0(g) \cup \mathcal{N}_i^1(g)} \theta_j $$

be the weighted average opinion of $i$’s neighbors. Thus, we assume that $i$ forms his opinion without considering his neighbors that have no initial opinion, that is agents $j \in \mathcal{N}_i(g)$ for whom $\theta_j = \emptyset$. We assume that the final opinion of agent $i \in \mathcal{N}$, $\theta_i^F$, is obtained from the following rule:

$$ \theta_i^F = \begin{cases} (1 - \alpha)\theta_i + \alpha\bar{\Theta}_i & \text{if } \theta_i \neq \emptyset \text{ and } \mathcal{N}_i^0(g) \cup \mathcal{N}_i^1(g) \neq \emptyset, \\ \bar{\Theta}_i & \text{if } \theta_i = \emptyset \text{ and } \mathcal{N}_i^0(g) \cup \mathcal{N}_i^1(g) \neq \emptyset, \\ \theta_i & \text{otherwise,} \end{cases} \quad (1) $$

where $\alpha \in (\frac{1}{2}, 1]$.<fnref n="5" /> Note that in Equation (1), if $\mathcal{N}_i^0(g) \cup \mathcal{N}_i^1(g) = \emptyset$, then agent $i$’s final opinion depends only on his initial opinion, i.e., if none of the neighbors of agent $i$ has any opinion, then agent $i$ considers only his initial opinion. We let $\theta^F = (\theta_i^F)_{i \in \mathcal{N}}$.

**Voting behavior of agents.** We assume that after all possible influences are taken into account, each agent votes for an outcome in line with his final opinion. Let $v_i(\theta_i^F)$ be the vote of agent $i$, we have

$$ v_i(\theta_i^F) = \begin{cases} 1 & \text{if } \theta_i^F \ge 1/2, \\ 0 & \text{if } \theta_i^F < 1/2, \\ \emptyset & \text{if } \theta_i^F = \emptyset. \end{cases} \quad (2) $$

<footnote n="5">⁵Note that if $\alpha < \frac{1}{2}$, then there is no possibility for an agent $i$ to modify its initial opinion. Hence, we do not consider this case.</footnote>
The vote of agent $i$ can be interpreted as his realized/chosen action. The $n$-uple $v = (v_1(\theta_1^F), \dots, v_n(\theta_n^F))$ provides the vote of every agent $i \in \mathcal{N}$. Following (2), for $k \in \{\emptyset, 0, 1\}$, we denote the set of agents who vote $k$ by $\mathcal{N}(k, v) = \{j \in \mathcal{N} : v_j(\theta_j^F) = k\}$.

**Payoff of De and Ad.** Forming links and influencing agents are both costly actions. More precisely, De's cost function depends on the number of links she forms and the number of agents she influences. The cost that De incurs when he forms $\sharp E(g)$ links and influences $\sharp \mathcal{I}_{De}$ agents is $C(\sharp E(g), \sharp \mathcal{I}_{De})$, where $C(\cdot, \cdot)$ is strictly increasing and convex in each of its argument. Given that the overall cost function is convex, for simplicity, we sometimes assume that it is linear in its two components: $C(\sharp E(g), \sharp \mathcal{I}_{De}) = \sharp E(g)c_L + \sharp \mathcal{I}_{De}c_{De}$, where $c_L > 0$ is the unit cost of forming each link, and $c_{De} > 0$ is the cost that De incurs for each agent she influences.

Moreover, we let $c_{Ad} > 0$ be the cost incurred by Ad for each agent he influences. In other words, the cost function of Ad is linear.<fnref n="6" />

The benefits of players only depend on the vote of the agents while the costs incurred by each player only depend on his strategy. Clearly, $\theta^F$ and $v$ are entirely determined by the strategies of De and Ad, hence we have $\theta^F[s, \sigma]$ and $v[s, \sigma]$. We assume that De wins if and only if every agent votes 1, an assumption we relax in the extension section. The payoff of De, for choosing $s$ when Ad chooses $\sigma$ is

$$u(v[s, \sigma]) = \begin{cases} 1 - C(\sharp E(g), \sharp \mathcal{I}_{De}) & \text{if } \mathcal{N}(1, v) = \mathcal{N}, \\ -C(\sharp E(g), \sharp \mathcal{I}_{De}) & \text{otherwise.} \end{cases} \quad (3)$$

Note that unanimity requires that every agent, even those with no initial opinion, must vote 1. We assume that the maximal cost incurred by De is always lower than 1, i.e., $C(\frac{n(n-1)}{2}, n) < 1$ in order to let her use any possible strategy. Similarly, the payoff of Ad when he chooses $\sigma$ and De chooses $s$ is

$$U(v[s, \sigma]) = \begin{cases} 1 - c_{Ad} \sharp \mathcal{I}_{Ad} & \text{if } \mathcal{N}(1, v) \neq \mathcal{N}, \\ -c_{Ad} \sharp \mathcal{I}_{Ad} & \text{otherwise.} \end{cases} \quad (4)$$

Let $k_{Ad} = \lfloor 1/c_{Ad} \rfloor$. Clearly, $k_{Ad}$ is the maximal number of agents that Ad has an incentive to influence in our benchmark model. We assume that $k_{Ad} \ge 1$, therefore, Ad always has an incentive to influence at least one agent if this guarantees that a unanimous vote for 1 can be avoided. To sum up, De and Ad have opposite incentives: De wants all agents to vote 1, while Ad wants at least one agent not to vote 1.

<footnote n="6">⁶Our results do not change qualitatively if we assume that the cost of influencing agents for Ad is strictly increasing.</footnote>
**Timing of the Game.** There are three stages in this game.

**Stage 1.** *De* chooses her strategy: builds the network, and influences a subset of agents.

**Stage 2.** *Ad* observes the strategy of *De* and influences a subset of agents.

**Stage 3.** Given their initial opinion, agents interact and form their final opinion and vote.

At the end of these three stages, *De* and *Ad* obtain their payoffs.

**Subgame Perfect Nash Equilibrium (SPNE).** An SPNE is a pair $(s_*, \sigma_*)$ that prescribes the following strategic choices. In Stage 2, given network *g*, *Ad* plays a best response<fnref n="7" /> $\sigma_*$ to $s(\mathcal{N})$:

$$ \sigma_* \in \arg\max_{\sigma \in S^{Ad}} \{U(v[s, \sigma])\}. $$

*De* obtains $u(v[s, \sigma_*])$ when she chooses *s*. In Stage 1, *De* plays $s_*$ such that

$$ s_* \in \arg\max_{s \in S^{De}} \{u(v[s, \sigma_*])\}. $$

**Example 1 Criminal Organization vs Police.**<fnref n="8" /> We consider criminals who belong to a hierarchical organization, with a leader (*De*), confronted by the police (*Ad*). The members of the criminal organization have two choices: be loyal (action 0) to the organization or be disloyal (action 1). *De* may use physical coercion to deter disloyalty among members of the organization (agents), but the effectiveness of such measures depends on *De*'s ability to use surveillance and pressure to convince disloyal members that they will be punished. Surveillance and pressure can be applied to each agent, but often at a high cost. An alternative strategy for *De* is to exert surveillance and pressure only on specific agents and to develop a network among the members of the organization in order to spread the opinion that his surveillance capacity is high. This strategy requires that *De* is able to design, at least in part, the interaction structure between the agents.<fnref n="9" /> Clearly, each agent is more likely to remain loyal if he believes *De* has a high ability to effectively detect and punish disloyalty. In addition, the criminal organization is under constant threat from the police, who have the ability to send criminals to prison. As a result, members of the criminal organization may be pressured by police who want to make the criminal organization ineffective.

To simplify the analysis, we consider two polar situations in which only one of the two players is able to punish. Specifically, in situation S1, player *De* is more powerful than player *Ad* and

<footnote n="7">⁷Since *Ad* best responds against the strategy chosen by *De*, his strategy can be interpreted as the worst possibility that *De* would face. Hence, *De* can be seen as an infinitely risk-averse player.</footnote>

<footnote n="8">⁸This example is inspired by Baccara and Bar-Isaac, 2008.</footnote>

<footnote n="9">⁹This assumption is consistent with the framework of Baccara and Bar-Isaac (2008).</footnote>
only *De* has the ability to punish the members of the criminal organization. By contrast, in situation S0, only player *Ad* is able to punish the members of criminal organization. It follows that $\theta_i = 1$ means that *i* has an initial opinion/belief in favor of S1 and $\theta_i = 0$ means that agent *i* has an initial opinion/belief in favor of S0. We assume that *De* and *Ad* have the ability to influence agents' (initial) beliefs about the occurrence of S1 (and S0), either by exerting pressure or by monitoring them. In the absence of influence, an agent has no initial opinion. Moreover, *De* must win the loyalty of all members of the organization, whereas the deviation of one agent is enough for the police to achieve their objective. The agents can follow the decision rule given in Equation (1) or a most sophisticated one as follows. We assume that in S1 and S0, each agent receives a fixed wage *w*. Denote by $Pu_{De} > 0$ and $Pu_{Ad} > 0$, the amount of the punishment imposed by the criminal organization and the police respectively. The expected payoff of agent *i* who chooses to be loyal is $w - \theta_i^F \times Pu_{Ad}$, and his expected payoff is $w - (1 - \theta_i^F) \times Pu_{De}$ when he chooses to be disloyal. Clearly, agent *i* is loyal if and only if $w - \theta_i^F \times Pu_{Ad} \ge w - (1 - \theta_i^F) \times Pu_{De}$, i.e., $\frac{\theta_i^F}{1-\theta_i^F} \ge \frac{Pu_{Ad}}{Pu_{De}}$. Let $Pu_{Ad} = Pu_{De}$. Then, $\frac{\theta_i^F}{1-\theta_i^F} \ge 1$, and agent *i* chooses loyalty when $\theta_i^F > \frac{1}{2}$ as in Equation (2).

# 3 Model Analysis

Let us begin by providing an example to illustrate the importance of network architectures in determining how players *De* and *Ad* influence the agents. Specifically, we assume that *De* takes the architecture of the network as given.

**Example 2** Suppose that $k_{Ad} = n$ and $\alpha = 1$ in Equation (1), i.e., only the opinion of the neighbors matter for the final opinion. The cost function is given by $C(\#\mathcal{I}_{De}) = \#\mathcal{I}_{De} \times c_{De}$, with $1 - n c_{De} > 0$. Hence, the designer can influence everyone. We examine some specific architectures for network *g*, that illustrate crucial points that *De* must take into account when determining her optimal strategy.

1. Let *g* be the empty network. In an SPNE, *De* has to influence all agents. In that case, *Ad* has no incentive to influence anyone because it is a costly act, and given *De*'s strategy, he cannot persuade any agent to vote 0.

2. Let *g* be a star, with $i_c$ the center of this star. In equilibrium, *De* must influence $i_c$, otherwise all neighbors of $i_c$ vote 0 if he is influenced by *Ad*. Since $\alpha = 1$, when *De* influences $i_c$, she ensures that every agent in $N \setminus \{i_c\}$ votes 1. Moreover, in an SPNE, *De* must influence at least as many neighbors of $i_c$ as *Ad* to obtain $\bar{\Theta}_{i_c} \ge 1/2$. If this is not the case, $i_c$ votes 0. Thus, *De* influences $\lceil \frac{n-1}{2} \rceil$ of the neighbors of $i_c$ and *Ad*
does not influence any agent. Note that if $k_{Ad} = 2$, then $De$ influences only 2 peripheral agents in addition to the central agent.

3. Let $g$ be the complete network. Then, $De$ has to influence half of the population plus one agent. First, consider agent $i \notin \mathcal{I}_{De}$. Since $g$ is complete, $i$ has $n-1$ neighbors. In equilibrium, $De$ must obtain $\bar{\Theta}_i \ge \frac{1}{2}$. We have $\bar{\Theta}_i = \frac{\#\mathcal{I}_{De}}{n-1} \ge \frac{1}{2}$, that is $\#\mathcal{I}_{De} \ge \lfloor \frac{n-1}{2} \rfloor$. Second, consider agent $i \in \mathcal{I}_{De}$. We have $\bar{\Theta}_i = \frac{\#\mathcal{I}_{De}-1}{n-1} \ge \frac{1}{2}$, that is $\#\mathcal{I}_{De} \ge \lfloor \frac{n+1}{2} \rfloor$. Consequently, $De$ must influence $\lfloor \frac{n+1}{2} \rfloor$ agents.

From this example, we can make some observations about situations where only the opinions of neighbors matter.

1. Every agent influenced by $De$ has at least as many neighbors who are also influenced by $De$ as those who are not.

2. Agents not influenced by $De$ must be linked with agents influenced by $De$. Obviously, it is better for $De$ if the former have no connections to each other.

It follows from points 1 and 2 that, in equilibrium, unless $De$ influences a minimum number of agents, it is impossible to achieve a unanimous vote for 1. Similarly, when $De$ has the option to create the network, some strategies are excluded from being part of the SPNE. In particular, according to point 2, $De$ has no incentive to connect agents she does not influence. Thus, the complete network will never arise in an SPNE. Similarly, if the cost of link formation is significantly lower than the cost of influencing agents, the empty network where all agents are influenced by $De$ cannot arise in an SPNE. In this case, the latter strategy of $De$ will be more costly than the strategy where $De$ builds the complete network and influences a number of agents that is equal to one plus half of the agents or the maximum number of attacks of $Ad$. Finally, in a star (or partial star), if $\alpha = 1$ and $k_{Ad} < \lfloor \frac{n-1}{2} \rfloor$, $De$ does not influence $\lfloor \frac{n-1}{2} \rfloor$ peripheral agents in addition to the central agent, but $k_{Ad}$ peripheral agents.

We now systematically investigate the optimal strategies chosen by $De$ and $Ad$ when $De$ has the ability to form the network. First, we analyze our benchmark model in which the social network contains only links formed by $De$. Second, we introduce the possibility that links that are not formed by $De$ appear. This scenario is used to check the robustness of the results derived from our benchmark model.

## 3.1 *De* Creates the Social Network

Since we want to find the SPNE, we start with the optimal strategy of $Ad$. First, since $C(\frac{n(n-1)}{2}, n) < 1$, for any strategy adopted by $Ad$, $De$ has a strategy that allows her to obtain
a strictly positive payoff, and therefore a strictly negative payoff to Ad since $c_{Ad} > 0$. In particular, De can play the complete influence-empty network strategy, and Ad cannot avoid a unanimous vote for 1, since for every agent $i$ influenced by both De and Ad, $\theta_i = 1$ holds. Since Ad cannot avoid strictly negative payoffs in equilibrium by influencing even one agent, Ad must play influence no agents to obtain a zero payoff in equilibrium. The following result summarizes this observation.

**Lemma 1** Suppose the payoff functions of players De and Ad are given by Equations (3) and (4) respectively. In an SPNE, Ad always chooses to influence no agents, and the strategy of De is such that for every agent $i \in \mathcal{N}$, $\theta_i^F = 1$.

Let $\Xi \subseteq G[\mathcal{N}] \times 2^{\mathcal{N}}$ be the set of pairs $(g, \mathcal{I}_{De})$ for which Ad's best response is to influence no agents. With a slight abuse of notation, we refer to as a winning strategy of De as any pair $(g, \mathcal{I}_{De})$ such that all agents vote 1 implying that Ad has no incentive to influence any agents. Moreover, $(g, \hat{\mathcal{I}}_{De})$ is a minimal winning strategy if it is a winning strategy, and for any winning strategy $(g', \hat{\mathcal{I}}_{De})$, we have $\#E(g) \le \#E(g')$. Finally, an optimal strategy is a winning strategy minimizing the cost of De, that is a strategy of De that is an SPNE. Formally, $(g^*, \mathcal{I}_{De}^*)$ is an optimal strategy for De if and only if

$$ (g^*, \mathcal{I}_{De}^*) \in \arg\min\{C(\#E(g), \#\mathcal{I}_{De}) : (g, \mathcal{I}_{De}) \in \Xi\}. $$

In the following, we denote by $(g^*, \mathcal{I}_{De}^*)$ a typical pair in $\Xi$ that minimizes the cost function. In the next result, we provide a minimizing program whose solution is the optimal strategy for De. Recall that for any agent influenced by both players, we have $\theta_i = 1$, and Ad has no incentive to influence more than $k_{Ad}$ agent. From this it calls that the maximum number of neighbors of $i$ that Ad can influence is $k_{B1}(i, g) = \min\{k_{Ad}, \#\mathcal{N}_i(g) \setminus \mathcal{I}_{De}\}$. Moreover, let $\kappa = 2\alpha - 1$. Thus, $\kappa \in (0, 1]$ since $\alpha \in (1/2, 1]$. Clearly, for every agent $i \in \mathcal{I}_{De}$, we must have $\mathcal{N}_i^1(g) \ge \lceil \kappa \mathcal{N}_i^0(g) \rceil$ to obtain $\theta_i^F = 1$, that is the number of neighbors of $i$ in $\mathcal{I}_{De}$ has to be greater than $\kappa$ times the number of neighbors of $i$ in $\mathcal{N} \setminus \mathcal{I}_{De}$.

**Proposition 1** Suppose that payoff functions of players De and Ad are given by Equations (3) and (4) respectively. Then, in an equilibrium, we have $\#(\mathcal{N}_i(g) \cap \mathcal{I}_{De}) \le \lceil \frac{n}{2} \rceil$ for every $i \in \mathcal{I}_{De}$. Moreover, strategy, $(g, \mathcal{I}_{De})$, is an optimal strategy for De if and only if it is a solution of the following minimizing program:
$$ \begin{array}{ll} \underset{(g, \mathcal{I}_{De}) \in G[\mathcal{N}] \times 2^{\mathcal{N}}}{\arg \min} & C(\#E(g), \#\mathcal{I}_{De}) \qquad (\text{Prg}) \\ & \text{s.t.} \end{array} $$

$$ \forall i \in \mathcal{I}_{De}, \#(\mathcal{N}_i(g) \cap \mathcal{I}_{De}) \geq \kappa k_{B1}(i, g), \qquad (\text{Cons. 1}) $$

$$ \forall i \in \mathcal{N} \setminus \mathcal{I}_{De}, \exists j \in \mathcal{I}_{De}, \mathcal{N}_i(g) = \{j\}. \qquad (\text{Cons. 2}) $$

The above proposition allows us to rule out several architectures that cannot belong to the set of optimal strategies. More precisely, each agent, who is not influenced by *De*, has to be connected with exactly one agent that *De* influences (Cons. 2). Similarly, agents influenced by *De* have to satisfy a ratio between their neighbors influenced by *De* and their neighbors who are not; this ratio is given in (Cons. 1).

For characterizing optimal strategies, we begin by examining the numbers of agents influenced by *De*, $\#\mathcal{I}_{De}$, that appear in an optimal strategy. Then, for each possible value of $\#\mathcal{I}_{De}$, we provide the minimal number of links required in any optimal strategy. Finally, using these facts we establish that there exist only three possible optimal candidate strategies.

In the next proposition, we show that the minimal number of agents that *De* has to influence in an optimal strategy, $\#\mathcal{I}_{De}^{\min}$, is equal to $\bar{x} = \bar{x}(\kappa, n)$ with

$$ \bar{x} = \arg \min_{x \in [1, n]} \left\{ x \left\lfloor \frac{x-1}{\kappa} \right\rfloor \geq n - x \right\}. \qquad (5) $$

Note that in Inequality (5) the left-hand side is the maximum number of agents in $\mathcal{N} \setminus \mathcal{I}_{De}$ whose final opinion is modified by that of the agents in $\mathcal{I}_{De}$ without them being able to modify the final opinion of the agents in $\mathcal{I}_{De}$. The right-hand side of Inequality (5) is the total number of agents that are not influenced by *De*. In Lemma 4 (see Appendix A.2), we establish that either $\bar{x} = \lceil \sqrt{\kappa n} \rceil$ or $\bar{x} = \lceil \sqrt{\kappa n} \rceil + 1$. Moreover, when $\alpha = 1$, i.e., $\kappa = 1$, we have $\bar{x} = \sqrt{n}$.

**Proposition 2** In any optimal strategy, the minimal number of agents *De* must influence is:

$$ \#\mathcal{I}_{De}^{\min} = \min\{\bar{x}, \lceil \kappa k_{Ad} \rceil + 1\}. $$

We now provide an intuition for this result. There are two possible necessary conditions for obtaining a winning strategy (and therefore an optimal strategy for *De*).

1. Suppose that the maximum number of agents that *Ad* can influence, $k_{Ad}$, is low compared to the number of neighbors of agent $i \in \mathcal{I}_{De}$. Then, *De* must ensure that the
number of agent i's neighbors in $\mathcal{I}_{De}$ is at least equal to the maximum number of attacks of $Ad$ (weighted by $\kappa$). Furthermore, a strategy such as the influence-partial-star strategy, where only one agent (influenced by $De$) is connected to agents not influenced by $De$, reaches the value $\lceil \kappa k_{Ad} \rceil + 1$.

2. Suppose that the maximum number of agents that $Ad$ can influence, $k_{Ad}$, is large compared to the number of neighbors of each agent in $\mathcal{I}_{De}$. Each agent influenced by $De$ must have a number of neighbors who belong to $\mathcal{I}_{De}$ (weighted by $\kappa$) that is at least equal to the number of his neighbors who are not in $\mathcal{I}_{De}$. Moreover, due to (Cons. 2), agents in $\mathcal{I}_{De}$ have $n - \#\mathcal{I}_{De}$ links with agents that are not influenced by $De$. Since an agent $i \in \mathcal{I}_{De}$ has at most $\#\mathcal{I}_{De} - 1$ neighbors in $\mathcal{I}_{De}$, the minimal number of agents influenced by $De$ that leads to an optimal strategy is given by Inequality (5).

We now present the minimal winning strategies, i.e., the minimal number of links that $De$ has to form in a winning strategy given the number of agents she influences, $\mathcal{I}_{De}$.

**Proposition 3** For $\#\mathcal{I}_{De} \ge \#\mathcal{I}_{De}^{\min}$, any minimal winning strategy has at least $L^{\min}(\#\mathcal{I}_{De})$ links with

$$L^{\min}(\#\mathcal{I}_{De}) = \min \left( \left\lceil \frac{\kappa(n - \#\mathcal{I}_{De})}{2} \right\rceil, \left\lceil \kappa k_{Ad} \right\rceil \right) + n - \#\mathcal{I}_{De}. \quad (6)$$

The minimal number of links that $De$ has to form, given $\mathcal{I}_{De}$, takes into account two types of links. Thus, the first term in (6) represents the links between agents influenced by $De$, while the second term in (6) represents the links between agents influenced by $De$ and those that are not. More precisely, there are two cases.

1. Suppose that $k_{Ad}$ is large compared to the number of neighbors of agents in $\mathcal{I}_{De}$. Then, the sum of degrees in the sub-network $g[\mathcal{I}_{De}]$, i.e., the number of links between agents in $\mathcal{I}_{De}$ has to be equal to $n - \#\mathcal{I}_{De}$ (weighted by $\kappa$), so there are $(n - \#\mathcal{I}_{De})/2$ links (weighted by $\kappa$) between agents in $\mathcal{I}_{De}$. Moreover, there are $n - \#\mathcal{I}_{De}$ links between agents in $\mathcal{I}_{De}$ and agents in $\mathcal{N} \setminus \mathcal{I}_{De}$ by (Cons. 2) given in Proposition 1.

2. Suppose that $k_{Ad}$ is low compared to the number of neighbors of $i \in \mathcal{I}_{De}$. Then, $i \in \mathcal{I}_{De}$ has to form links with at least $k_{Ad}$ (weighted by $\kappa$) agents in $\mathcal{I}_{De}$. Again by (Cons. 2) we know that there are $n - \#\mathcal{I}_{De}$ links between agents in $\mathcal{I}_{De}$ and agents in $\mathcal{N} \setminus \mathcal{I}_{De}$.

We now provide an example which establishes that there are situations where it is not possible to reach the bound $L^{\min}(\#\mathcal{I}_{De})$.

**Example 3** Let $\mathcal{N} = [1, 27]$, $k_{Ad} = 27$, and $\kappa = 3/7$. By Proposition 2, we have $\#\mathcal{I}_{De}^{\min} = \lceil \sqrt{3/7 \times 27} \rceil = 4$. Similarly, by Proposition 3, $L^{\min}(\#\mathcal{I}_{De}^{\min}) = 23 + \lceil 3/14 \times 23 \rceil = 28$.
Obviously, by (Cons. 2), 23 links are required between agents in $\mathcal{I}_{De}^{\min}$ and agents in $\mathcal{N} \setminus \mathcal{I}_{De}^{\min}$.
Suppose now that there are only 5 links between agents in $\mathcal{I}_{De}^{\min}$. Then, two agents in $\mathcal{I}_{De}^{\min}$ have
formed links with 3 agents in $\mathcal{I}_{De}^{\min}$, and two agents in $\mathcal{I}_{De}^{\min}$ have formed links with 2 agents in
$\mathcal{I}_{De}^{\min}$. The former may form links with at most 14 agents in $\mathcal{N} \setminus \mathcal{I}_{De}^{\min}$ and the latter may form
links with at most $2 \times [2 \times 7/3] = 8$ agents in $\mathcal{N} \setminus \mathcal{I}_{De}^{\min}$. Consequently, one agent in $\mathcal{N} \setminus \mathcal{I}_{De}^{\min}$
does not satisfy (Cons. 2), and $L^{\min}(\#\mathcal{I}_{De}^{\min})$ is not a sufficient number of links for obtaining a
winning strategy.

From Propositions 2 and 3, we establish the main result of this section.<fnref n="10" />

**Theorem 1** For any given parameters $n$, $\alpha$ and $k_{Ad}$, one of the following strategies is optimal:

1. the complete influence-empty network strategy, or

2. a $(p, \mathcal{I}_{De})$ influence-partial-star strategy, with $\#\mathcal{I}_{De} \ge \#\mathcal{I}_{De}^{\min}$ and $p \ge \lceil \kappa k_{Ad} \rceil$, or

3. a $(\kappa, \mathcal{I}_{De})$ influence-minimal-quasi-core periphery network strategy, with $\#\mathcal{I}_{De} \ge \#\mathcal{I}_{De}^{\min}$.

To simplify the presentation of the intuition behind this result, we assume that $\alpha = 1$, and $De$'s cost function is linear. It is clear that the complete-influence-empty network strategy is an optimal strategy when the relative cost $c_L/c_{De}$ is very high. When $c_L/c_{De}$ is not too high, there are two possibilities.

1. Suppose $k_{Ad}$ is low and $De$ has an incentive to form links. Then, $De$ forms a star network where the central agent is linked to all other agents and influences $k_{Ad}$ peripheral agents, i.e., $\#\mathcal{I}_{De} = k_{Ad} + 1$. Here, $De$ benefits from not having to influence more agents than $k_{Ad}$, i.e., the maximum number of agents that $Ad$ can influence. For example, when $k_{Ad} = 1$, it is sufficient for $De$ to influence only the center of the star and one peripheral agent to achieve a unanimous vote for 1.<fnref n="11" />

2. Suppose $k_{Ad} = n$, i.e., $k_{Ad}$ is large, and $De$ has an incentive to form links. Then, $De$ builds a minimal quasi-core-periphery network and influences the ⌊√*n*⌋ agents in the core. Agents in $\mathcal{I}_{De}$ are connected to each other to minimize the number of links formed by $De$.

<footnote n="10">¹⁰In the working paper, we provide an example showing that each type of strategy presented in the theorem is optimal. We also present the exact optimal strategies for $De$ when the cost function is linear.</footnote>

<footnote n="11">¹¹Similarly, when $k_{Ad} = 2$, $(2, \llbracket 1, 5 \rrbracket)$-partial-star $g^1$ drawn in Figure 2 (a), where $\mathcal{I}_{De} = \llbracket 1, 5 \rrbracket$, guarantees $De$ a unanimous vote for 1.</footnote>
## 3.2 Adding Random Links

In this section we want to explore the possibility that *De* does not fully control the network formation. In fact, in any social situation, agents may have a chance to meet each other and form a connection even if the designer has not established a connection between them. Therefore, we assume that unlinked agents have a non-negative probability of forming links $\omega \in [0, 1]$, altering the neighborhood created by *De* for each agent. Probability $\omega$ is i.i.d., i.e., the random meetings between agents leading to links are independent events. Moreover, $\omega$ is common knowledge, in particular, it is known by *De*. Finally, we assume that the cost function of *De* is linear and $k_{Ad} = n$. In this section, we consider the following timing of the game:

**Stage 1.** *De* chooses her strategy $(g, \mathcal{I}_{De})$, knowing that any link not formed by her in *g* occurs with probability $\omega$;

**Stage 2.** Nature randomly forms a link between every pair of agents $(i, j)$ who are not linked in *g* with probability $\omega$;

**Stage 3.** *Ad* observes the agents influenced by *De*, the network she has formed, as well as the random links added by Nature before choosing his strategy.

The timing of the game and $k_{Ad} = n$ together ensure that *De* does not obtain a strictly positive payoff when the network (and the set of influenced agents) obtained after Nature's move is no longer a winning strategy.

First, for computing the expected payoffs of *De* and *Ad*, we need to define a realization $g^\omega$ of *g*, where network *g* is a subnetwork of $g^\omega$. Let $\lambda(g^\omega | g, \omega)$ be the probability that $g^\omega$ is realized given probability $\omega$ and that *De* has built network *g*. We have:

$$ 
\begin{aligned}
\lambda(g^\omega | g, \omega) &= \prod_{ij \in E(g^\omega) \setminus E(g)} \omega \prod_{i'j' \notin E(g^\omega)} (1-\omega) \\
&= \omega^{\#E(g^\omega) \setminus E(g)} (1-\omega)^{\frac{n(n-1)}{2} - \#E(g^\omega)}.
\end{aligned} 
\quad (7) $$

A winning realization is a pair $(g^\omega, \mathcal{I}_{De})$ where *Ad* has no strategy that allows him to ensure that at least one agent in the realized network $g^\omega$ will vote 0 when *De* has influenced agents in $\mathcal{I}_{De}$. Let $R(g, \mathcal{I}_{De})$ be the set of realizations associated with $g$.<fnref n="12" /> Let $WR(g; \mathcal{I}_{De}) \subseteq R(g, \mathcal{I}_{De})$ be the set of winning realizations of *g* given $\mathcal{I}_{De}$. Assuming that the cost function

<footnote n="12">¹²($g^\omega, \mathcal{I}_{De}$) can be seen as a winning strategy in the benchmark model where *De* forms network $g^\omega$ and influence agents in $\mathcal{I}_{De}$.</footnote>
of De is linear, her expected payoff is given by:

$$ \mathbb{E}u(\boldsymbol{\theta}^{\mathrm{F}}[s, \sigma]) = \sum_{g^{\omega} \in \mathrm{WR}(g, \mathcal{I}_{De})} \lambda(g^{\omega} | g, \omega) - c_{De} \sharp \mathcal{I}_{De} - c_{L} \sharp E(g). \quad (8) $$

Similarly, the expected payoff of Ad is:

$$ \mathbb{E}U(\boldsymbol{\theta}^{\mathrm{F}}[s, \sigma]) = 1 - \sum_{g^{\omega} \in \mathrm{WR}(g, \mathcal{I}_{De})} \lambda(g^{\omega} | g, \omega) - \sharp \mathcal{I}_{Ad} c_{Ad}. \quad (9) $$

At first glance it might seem that De will view the possibility of the occurrence of such unwanted links always being harmful. Indeed, when the number of agents De has influenced is lower than the number of agents she does not influence, the probability that “bad” links (which involve agents non influenced by De) is higher than the probability that “good” links (which involve only agents influenced by De) occur. However, the possibility that unwanted links can occur is not always harmful for De. For instance, suppose that $\alpha = 1$ and for $\omega = 0$, the optimal strategy of De is the complete influence-empty network strategy. However, if $\omega = \frac{n(n-1)}{2}$ is sufficiently close to 1, then De has an incentive to influence only $\lfloor n/2 \rfloor + 1$ agents instead of influencing all the agents to obtain that a unanimous vote of 1. In this case, the probability that the complete network occurs is sufficiently high and De obtains a higher payoff with this strategy than with the complete influence-empty network strategy. We now provide a lower bound for $\omega$ such that the strategies that are candidates for being optimal are the same as those given in Theorem 1. This statement highlights the continuity in the results obtained in our benchmark model when $\omega$ is sufficiently small.

**Proposition 4** Suppose that $\omega \le \frac{c_L}{4n}$. Then, the candidate strategies for being optimal are the same as those given in Theorem 1.

Moreover, it is worth noting that in Proposition 4, $\omega$ depends on $n$. Let us illustrate this point when $\alpha = 1$. Consider, for example, a $(1, \mathcal{I}_{De})$-influence-MQC strategy where $\sharp \mathcal{I}_{De} = \lfloor \sqrt{n} \rfloor$. When this strategy is played by De, and a link occurs, the probability that this link is formed between any agent $i \in \mathcal{N}$ and an agent $j \in \mathcal{N} \setminus \mathcal{I}_{De}$ is at least $1 - \frac{\lfloor \sqrt{n} \rfloor}{\binom{n}{2}} \ge 1 - \frac{\sqrt{n}+1}{n}$. Notice that $\lim_{n \to +\infty} 1 - \frac{\sqrt{n}+1}{n} = 1$. In other words, when the number of agents is very large and a link occurs, the probability that it involves an agent in $\mathcal{N} \setminus \mathcal{I}_{De}$ becomes very large when De uses a $(1, \mathcal{I}_{De})$-influence-MQC strategy with $\sharp \mathcal{I}_{De} = \lfloor \sqrt{n} \rfloor$. Obviously, this type of link makes such a strategy inefficient.

We now illustrate the probabilistic case in a specific situation where $\alpha = 1$, $\mathcal{N} = \lfloor 1, 4 \rfloor$, thus $\sharp \mathcal{I}_{De}^{\min} = 2$. Clearly, $\sharp \mathcal{I}_{De} \in \lfloor 2, 4 \rfloor$ and De always obtains $1 - 4c_{De}$ when she influences 4 agents. Note that De does not form any links between agents who are not influenced by her.
<figure><img src="image_5.png" /><figcaption>Figure 3: Networks for the Probabilistic Model when $\mathcal{N} = [1, 4]$</figcaption></figure>

Let us explore in turn the cases where $\mathcal{I}_{De} = 2$ and $\mathcal{I}_{De} = 3$ and provide the probability of achieving a network that is resistant to Ad attacks.

1. $\mathcal{I}_{De} = 2$, say $\mathcal{I}_{De} = \{1, 2\}$. Note that there are only two networks where all agents vote 1 – up to a relabeling of agents: $g^0$ and $g^7$ in Figure 3. When $De$ forms no links, then the probability that $g^0$ or $g^7$ occur is $2\omega^3(1-\omega)^2$. When $De$ forms one link, she has two possibilities: either she forms a link between two agents in $\mathcal{I}_{De}$, or she forms a link between an agent in $\mathcal{I}_{De}$ and an agent in $\mathcal{N} \setminus \mathcal{I}_{De}$. The former leads to a probability of obtaining $g^0$ or $g^7$ equal to $2\omega^2(1-\omega)^2$, and the latter leads to a probability of obtaining $g^0$ or $g^7$ equal to $\omega^2(1-\omega)^2$. Consequently, $De$ always has an incentive to form a link between two agents she influences. When $De$ forms two links, she has two possibilities: either she forms a link between two agents in $\mathcal{I}_{De}$ and one link between an agent in $\mathcal{I}_{De}$ and an agent in $\mathcal{N} \setminus \mathcal{I}_{De}$, or both links are between an agent in $\mathcal{I}_{De}$ and an agent in $\mathcal{N} \setminus \mathcal{I}_{De}$. In both cases the probability of obtaining $g^0$ or $g^7$ is equal to $\omega(1-\omega)^2$. Further, when $De$ forms three links, the probability that $g^0$ or $g^7$ occurs is $(1-\omega)^2$. When $De$ forms $g^7$, network $g^0$ cannot occur and the probability that the realized network is $g^7$ is $(1-\omega)^2$. Thus, $De$ faces the same probability of success forming $g^0$ as forming $g^7$, while $g^0$ allows her to save a costly connection. Moreover, if $De$ forms more than 4 links, then she cannot obtain a winning realization given $\mathcal{I}_{De} = 2$. Consequently, it is suboptimal for $De$ to form more than 3 links.

2. $\mathcal{I}_{De} = 3$, say $\mathcal{I}_{De} = \{1, 2, 3\}$. We draw in Figure 3 the different networks where all agents vote 1 when $\mathcal{I}_{De} = \{1, 2, 3\}$ up to a relabeling of agents. By using similar arguments as in the previous point and the list of networks $g^1$ to $g^{10}$ we obtain the following results.<fnref n="13" /> When $De$ forms no links the probability that all agents vote 1 is

<footnote n="13">¹³Here we indicate the probability associated with the strategy of $De$ that maximizes the probability of getting all</footnote>
$\omega^6 + 6\omega^2(1 - \omega)^2 + 6\omega^4(1 - \omega)$. When $De$ forms 1 link the probability that all agents vote 1 is $\omega + \omega(1 - \omega)$. When $De$ forms 2 links the probability that all agents vote 1 is: $\max\{1 - \omega(1 - \omega)^2, 1 - (1 - \omega)^3\}$. When $De$ forms 3 links, she can ensure to obtain that all agents vote 1 with network $g^2$. It is also possible when she forms 4, 5 or 6 links.

Let us now provide the optimal strategies of $De$ for some specific sets of parameters. More precisely, we assume that $N = \llbracket 1, 4 \rrbracket$. We define the following strategies for $De$: $S_1$: $\mathcal{I}_{De} = \{1, 2\}, E(g) = \{12, 13, 24\}$, $S_2$: $\mathcal{I}_{De} = \{1, 2, 3\}, E(g) = \{12, 13, 34\}$, and $S_3$: $\mathcal{I}_{De} = \{1, 2, 3\}, E(g) = \{12, 13\}$, $S_4$: $\mathcal{I}_{De} = \{1, 2, 3\}, E(g) = \emptyset$, and $S_5$: $\mathcal{I}_{De} = \{1, 2, 3, 4\}, E(g) = \emptyset$. In the following table, we provide an optimal strategy for $De$ up to a relabeling of agents for several value of $\omega$ and $c_L$ given that $c_{De} = 0.07$.

<table><thead><tr><th>c<sub>L</sub></th><th>1/1000</th><th>1/100</th><th>11/100</th></tr></thead><tbody><tr><th>1/1000</th><td>S<sub>1</sub></td><td>S<sub>1</sub></td><td>S<sub>5</sub></td></tr><tr><th>87/100</th><td>S<sub>2</sub></td><td>S<sub>3</sub></td><td>S<sub>4</sub></td></tr><tr><th>99/100</th><td>S<sub>4</sub></td><td>S<sub>4</sub></td><td>S<sub>4</sub></td></tr></tbody></table>

Let us provide some observations through these examples.

1. When the probability of unwanted links is very low, the optimal strategy is the same as in the benchmark model, and depends on the relative cost of $c_L$ and $c_{De}$ (see Proposition 4).

2. When the probability of unwanted links is very high, then the optimal strategy is to play $S_4$: $De$ forms no links, and influences a number of agents that allow her to obtain that each agent votes 1 in the complete network. In this case, $De$ will incur lower costs than in the benchmark model if $c_{De}$ is sufficiently low relative to $c_L$.

3. When the probability of unwanted links is moderate, some intermediate strategies, where $De$ influences a number of agents in $\llbracket \mathcal{I}_{De}^{\min} + 1, n - 1 \rrbracket$ become optimal. In particular, in $S_3$, $De$ influences 3 agents, $3 > \#\mathcal{I}_{De}^{\min}$. Moreover, the number of links and the number of agents $De$ influences depend on the relative cost of $c_L$ and $c_{De}$.

# 4 Extensions

In this section, we systematically address and relax, one by one, the three key assumptions made in the benchmark model. First, we assume that agents do not have to vote following their

<footnote>agents to vote 1.</footnote>
initial interactions, but rather after a finite number of interaction periods. Second, we relax the unanimity assumption by allowing *De* to win if a majority of the agents vote for 1. Third, we assume that an agent, influenced by both *De* and *Ad*, follows the opinion of *Ad*, i.e., *De* is no longer a better influencer than *Ad*.

## 4.1 Reach Unanimity in Several Periods

Our benchmark model raises a natural question: What is *De*'s optimal strategy if the final vote of the agents does not have to take place immediately after their first interaction, but after several interactions? Specifically, *De* must obtain a unanimous vote at a specific time period *T*. Thus, we assume a process with *T* + 1 periods, where the opinion of agent *i* at period *t* ∈ [0, *T*] is denoted by $\theta_i^t$, with $\theta_i^0 = \theta$ and $\theta_i^T = \theta_i^F$. At each period $t \in [0, T]$, the agents vote or choose an action, but only the vote cast at period *T* determines the payoffs of *De* and *Ad*.<fnref n="14" /> Votes in periods before *T* are non-binding, while votes at *T* are binding. Each agent observes the votes or actions made by her neighbors at time *t* − 1 and adjusts her opinion at time *t* in response to these observations. To simplify the presentation, in this section, we restrict our attention to $\alpha = 1$ and $k_{Ad} = n$. In line with our benchmark model, we have for $t \in [0, T]$,

$$v_i^t = v_i^t(\theta_i^t) = \begin{cases} 1 & \text{if } \theta_i^t \ge 1/2, \\ 0 & \text{if } \theta_i^t < 1/2, \\ \emptyset & \text{if } \theta_i^t = \emptyset, \end{cases} \quad (10)$$

and $v_i^0 = \theta_i^0 = \theta_i$. In contrast to our benchmark model, we allow for a non-binding vote of agents after the initial stage of opinion formation.

Let us denote the vector that summarizes the non-binding vote of agents at period $t \in [0, T - 1]$ by $v^t = (v_1^t, \dots, v_n^t)$, and the vector of binding votes is denoted by $v = v^T = (v_1^T, \dots, v_n^T)$. Moreover, let $V_i^k(g; t) = \{j \in \mathcal{N}_i(g) : v_j^t = k\}$ be the set of neighbors of agent *i* who vote $k \in \{0, 1, \emptyset\}$ at period *t*. Recalling that $\alpha = 1$, we have for $t \in [0, T]$,

<footnote n="14">¹⁴During the first *T* − 1 periods, the agents’ vote do not affect the players’ payoffs. This type of informative vote without consequences, called a straw poll, occurs in certain decision-making processes, like an initial round of voting to seek opinions, followed by more discussions before a final vote is cast. For instance, such a process is often followed in universities while making tenure decisions.</footnote>
<figure><img src="image_6.png" /><figcaption>Figure 4: $i_1$-triangle-networks and Strategy</figcaption></figure>

$$ \theta_i^{t+1} = \begin{cases} \frac{1}{\#\mathcal{V}_i^0(g; t) + \#\mathcal{V}_i^1(g; t)} \sum_{j \in \mathcal{V}_i^0(g; t) \cup \mathcal{V}_i^1(g; t)} v_j^t & \text{if } \mathcal{V}_i^0(g; t) \cup \mathcal{V}_i^1(g; t) \neq \emptyset, \\ \theta_i^t & \text{otherwise.} \end{cases} \quad (11) $$

Finally, we preserve the payoff function given in Equations (3) and (4). We now present a specific network architecture, up to a relabeling of agents, that allows us to define a useful strategy for the rest of this section. Recall that $P_{i_1, i_m} = i_1 i_2, i_2 i_3, i_{m-1} i_m$ is a path between agents $i_1$ and $i_m$.

**Definition 3** Let $\gamma = 3 + \lfloor \frac{n-4}{2} \rfloor$. A $i_1$-triangle-network $g$

(O1) contains the subnetworks $g(\{i_4, \dots, i_\gamma\}) = P_{i_4, i_\gamma}$, and $g(\{i_{\gamma+1}, \dots, i_n\}) = P_{i_\gamma+1, i_n}$. Also, $g(\{i_1, i_2, i_3\})$ which is a triangle, i.e., a cycle that contains links $i_1 i_2, i_1 i_3$, and $i_2 i_3$;

(O2) in addition network $g$ contains links $i_1 i_\gamma$ and $i_1 i_{\gamma+1}$.

By construction, $d(i_1, i_\ell; g) \le \lfloor \frac{n-3}{2} \rfloor$ for all $\ell \in \lfloor 4, n \rfloor$. We illustrate these types of networks through the $i_1$-triangle-network $g$ drawn in Figure 4 (a). We have $N = \lfloor i_1, i_9 \rfloor$, hence $\gamma = 3 + \lfloor \frac{9-4}{2} \rfloor = 6$. Subnetwork $g(\{i_4, i_5, i_6\}) = P_{i_4, i_6}$ is colored gray, subnetwork $g(\{i_7, i_8, i_9\}) = P_{i_7, i_9}$ is colored black, and $g(\{i_1, i_2, i_3\})$ colored white is a cycle. Links $i_1 i_6$ and $i_1 i_7$ are colored green.

The strategy where $De$ influences a unique agent, $i_1$, is called an *influence-i$_1$-triangle strategy*. Figure 4 (b) presents network $g$ in which $De$ influences agent $i_1$.
**Proposition 5** Suppose that at period *t* agents vote according to Equation (10) and form their beliefs according to Equation (11).

1. De must influence at least one agent to ensure that all agents choose 1 in a finite number of periods.

2. Suppose that De influences only one agent.

(a) Any network *g* designed by De that leads to *N*(1, *v*) = *N* in a finite number of periods must be connected and contains at least *n* links.

(b) Moreover, there exists a network *g*, with $\#E(g) = n$, that leads to $\mathcal{N}(1, \mathbf{v}) = \mathcal{N}$ in a finite number of periods.

By inspecting the proof of this proposition, an influence-$i_1$-triangle strategy leads all agents to vote 1 in $2 + (\max_{i_\ell \in \mathcal{N}} d(i_1, i_\ell; g))$ periods. We illustrate this convergence process of voting in the next example.

<figure><img src="image_7.png" /><figcaption>Figure 5: Vote Process with an Influence-$i_1$-triangle Strategy</figcaption></figure>

**Example 4** Let $\mathcal{N} = \{1, 9\}$, $\alpha = 1$, and $k_{Ad} = n$. Suppose that $De$ uses an influence-$i_1$-triangle strategy and $Ad$ influences all agents. We represent the situation at $t=0$ in Figure 5 where black colored agents have their initial opinion equal to 0, while the white colored agent has his initial opinion equal to 1. Figure 5 illustrates the evolution of the change in agents’ opinions over time for $t=0, \dots, 5$, and shows the various stages until a unanimous vote for 1 is obtained. For example, players $i_2$, $i_3$, $i_6$, and $i_7$ have two neighbors, including $i_1$. Since $i_1$ votes 1 at $t=0$, each of them has an opinion equal to 1 at $t=1$. The process continues until period 5 using the same logic – note that $\max_{i_\ell \in \mathcal{N}} d(i_1, i_\ell; g) = 3$. Thus, in equilibrium, $Ad$
has no incentive to influence agents since it is costly and does not prevent agents from voting unanimously for 1. Clearly, it is possible to increase the speed of convergence of the process by increasing the number of agents influenced by *De* or the number of links she forms. Thus, if *De* adds a link between $i_4$ and $i_9$, the process converges to a unanimous vote for 1 at $t = 4$. Similarly, if *De* influences agents $i_6$ and $i_7$, then the process converges to a unanimous vote for 1 at $t = 2$.

Next, we show that *De* only needs to influence two agents when she builds a connected acyclic network to obtain that all agents vote 1 in a finite number of periods.

**Example 5** Let $\mathcal{N} = [1, 10]$, $\alpha = 1$, and $k_{Ad} = n$. Suppose that *De* builds a network which contains a path and influences agents 1 and 2 as represented in Figure 6 at $t = 0$. Colored black agents have their initial opinion equal to 0, while colored white agents have their initial opinion equal to 1. Figure 6 illustrates the evolution of the change in agents’ opinions over time for $t = 0, \dots, 4$ until a unanimous vote in favor of 1 is obtained. Clearly, when *De* uses this strategy, the unanimity of the agents to vote 1 is achieved in $\lceil \frac{n-2}{2} \rceil = 5$ periods.

<figure><img src="image_8.png" /><figcaption>Figure 6: Vote Process When Two Agents Are Influenced by *De*</figcaption></figure>

In summary, if we allow the agents to interact several times instead of just once before they vote, *De* can acquire the unanimous vote she needs to win using fewer resources. The network of agents acts as a powerful secondary influencer, saving the designer resources. Thus, repeated interaction between agents favors *De*.
## 4.2 Influencing Only the Majority

In this section, we consider a situation where $De$ obtains a strictly positive payoff if and only if at least half of the population, i.e., ⌈n/2⌋ agents, votes 1.<fnref n="15" /> We restrict our attention to the case where the cost function of $De$ is linear. The majority rule is incorporated into the model by modifying $De$'s payoff function as follows

$$u_{\text{Maj}}(\mathbf{v}[s, \sigma]) = \begin{cases} 1 - c_L \#E(g) - c_{De} \#\mathcal{I}_{De} & \text{if } \#\mathcal{N}(1, \mathbf{v}) \ge \lceil \frac{n}{2} \rceil, \\ -c_L \#E(g) - c_{De} \#\mathcal{I}_{De} & \text{otherwise.} \end{cases} \quad (12)$$

The payoff function of $Ad$ is modified similarly:

$$U_{\text{Maj}}(\mathbf{v}[s, \sigma]) = \begin{cases} 1 - c_{Ad} \#\mathcal{I}_{Ad} & \text{if } \#\mathcal{N}(1, \mathbf{v}) < \lceil \frac{n}{2} \rceil, \\ -c_{Ad} \#\mathcal{I}_{Ad} & \text{otherwise.} \end{cases} \quad (13)$$

Following the arguments given in Lemma 1, in the SPNE $Ad$ does not influence any agent. Let us begin by providing some properties of the winning strategies of $De$ based on the size of $\mathcal{I}_{De}$.

1. If $\mathcal{I}_{De} = \emptyset$, then there exists no winning strategy for $De$.

2. If $\mathcal{I}_{De} = \{i_c\}$, then consider a partial-star where $i_c$ is the central agent with ⌈n/2⌋ peripheral agents. Let all other agents be isolated. This constitutes a winning strategy (regardless of the value of $\alpha$).

3. If $\#\mathcal{I}_{De} \in [2, \lfloor n/2 \rfloor - 1]$, then consider a partial-star where $i_c$ is the central agent with ⌈n/2⌋-\#\mathcal{I}_{De}+1 peripheral agents. Let all other agents be isolated. $De$ influences \#\mathcal{I}_{De}-1 isolated agents and the central agent. This constitutes a winning strategy (regardless of the value of $\alpha$).

4. If \#\mathcal{I}_{De} \ge \lfloor n/2 \rfloor, then the empty network is a winning strategy.

In contrast to the benchmark model, there is always a winning strategy where $De$ builds a partial-star which is less costly than any winning strategy where $De$ builds a minimal-quasi-core periphery network. Indeed, in the majority case, the center of the partial-star, $i_c$, does not need to vote 1. Thus, property (Q1) is no longer required. Consequently, $De$ can influence $i_c$ and connect him to any number of agents she does not influence to get a majority of votes – $De$ can also influence some isolated agents in the partial-star. Moreover, for a given $\mathcal{I}_{De}$, the number of links $De$ formed in a winning strategy where she builds a partial-star strategy is at most equal to the number of links $De$ formed in a winning strategy where she builds a minimal

<footnote n="15">¹⁵Typically majority would require strictly greater than half, $\#\mathcal{N}(1, \mathbf{v}) \ge \lfloor n/2 \rfloor + 1$. But, the results presented in this section would be qualitatively the same for this case as well.</footnote>
quasi-core. In particular, there is no link between the agents in $\mathcal{I}_{De}$ in a winning strategy based on a partial-star, while $De$ forms at least one such link in a winning strategy based on a minimal-quasi-core network. It follows that there are two possible strategies for $De$: either build the empty network and influence $\lceil n/2 \rceil$ agents, or build the cheapest partial-star network that allows her to get $\lceil n/2 \rceil$ agents who vote 1. Since $De$ chooses the less costly strategy, her least cost strategy incorporating these two possibilities is given by

$$ \min \left\{ \lceil n/2 \rceil c_{De}, \min_{x \in \llbracket 1, \lceil n/2 \rceil - 1 \rceil} \left( x c_{De} + \left( \lceil n/2 \rceil - x + 1 \right) c_L \right) \right\}. $$

The above arguments are summarized in the following proposition given without proof. In fact, it is sufficient to observe that $De$ has no incentive to influence more than one agent when she forms links, due to the linearity of the costs.

**Proposition 6** Suppose the payoff functions of players $De$ and $Ad$ are given by Equations (12) and (13) respectively. An optimal strategy is independent of the value of $\alpha$ and of $c_{Ad}$. Further,

1. if $\frac{c_L}{c_{De}} > \left(1 - \frac{1}{\lceil n/2 \rceil}\right)$, then in her optimal strategy $De$ forms no links and influences exactly $\lceil n/2 \rceil$ agents;

2. if $\frac{c_L}{c_{De}} < \left(1 - \frac{1}{\lceil n/2 \rceil}\right)$, then in her optimal strategy $De$ forms $\lceil n/2 \rceil$ links and influences exactly 1 agent. The resulting network is a partial-star; and

3. if $\frac{c_L}{c_{De}} = \left(1 - \frac{1}{\lceil n/2 \rceil}\right)$, then the two strategies listed above are equilibria.

The strategy where $De$ builds the partial-star where it influences the center implies that peripheral agents have only one neighbor with 1 as initial opinion. Therefore, in contrast to the benchmark model, $De$ shapes the network according to her costs $c_L$ and $c_{De}$, without taking into account the costs for influencing agents incurred by $Ad$, or the value $\alpha$.

## 4.3 Adversary is a Better Influencer than Designer

In this section, we assume that when both players $De$ and $Ad$ exert influence on agent $i$, the adversary is the one with the better influencing technology, i.e., $\theta_i = 0$. In order to simplify the presentation, we assume that $n$ is even.<fnref n="16" /> Formally, the initial opinion of each agent $i$ is now given by

$$ \theta_i = \begin{cases} 1 & \text{if } i \in \mathcal{I}_{De} \setminus \mathcal{I}_{Ad} \\ 0 & \text{if } i \in \mathcal{I}_{Ad} \\ \emptyset & \text{if } i \notin \mathcal{I}_{De} \cup \mathcal{I}_{Ad} \end{cases} $$

<footnote n="16">¹⁶The results obtained when $n$ is odd are qualitatively the same, except that there exist conditions where as part of her optimal strategies player $De$ chooses $\#\mathcal{I}_{De} = n - 1$.</footnote>
To present the results, additional definitions of networks and strategies are required. A k-regular network *g* is a network where every *i* ∈ *N* has exactly *k* links. We illustrate a 4-regular network in Figure 7 (a).

<figure><img src="image_9.png" /><figcaption>Figure 7: Specific Strategies of De</figcaption></figure>

**Definition 4** In a (*a*, *b*, *Y*)-groups-regular network, *N* is partitioned into two subsets: *Y* and *N* \ *Y*. Moreover, when *a* × *Y* is even, we have

(R1) For every $i \in \mathcal{Y}$, $\sum_{j \in \mathcal{Y}} A_{i,j}(g) = a$,

(R2) For every $i \in \mathcal{N} \setminus \mathcal{Y}$, $\sum_{j \in \mathcal{Y}} A_{i,j}(g) = b$, and $\sum_{j \notin \mathcal{Y}} A_{i,j}(g) = 0$.

When $a \times \mathcal{H}\mathcal{Y}$ is odd, conditions provided in (R1) and (R2) hold except that there is a unique agent $i \in \mathcal{Y}$ for whom we have $\sum_{j \in \mathcal{Y}} A_{i,j}(g) = a + 1$.

Let *g* be a network that satisfies (R1) and (R2) where *a* × *Y* is even. (R1) implies that *g*[*Y*] is an *a*-regular network, and (R2) implies that every agent in *N* \ *Y* has formed *b* links with agents in *Y* and no links with other agents in *N*\*Y. In Figure 7 (b) we illustrate a (2, 3, ⌈3, 7⌋)-group-regular network where every agent in *Y* = ⌈3, 7⌋ is colored white. Clearly, each agent in *Y*, is linked to two other agents in *Y*. Moreover, each agent in *N* \ *Y*, colored black, has three links all with agents in *Y*. In Figure 7 (c), we present the same type of strategy when *a* × *Y* is odd, where player 7 ∈ *Y* has 4 links with other members of *Y*.

In this section we focus on two specific strategies for *De*. First, in an *a*-regular network *strategy*, *De* builds an *a*-regular networks and influences all agents. Second, in a (*a*, *b*, *Y*)-groups-regular network *strategy*, *De* builds a (*a*, *b*, *Y*)-groups-regular network and influences all agents in *Y*.
Since $Ad$ is now a better influencer than $De$, he chooses a (minimal) number of agents to influence so that for one agent, say $i$, $v_i(\theta_i^F) = 0$. When $k_{Ad}$ is sufficiently high, there is no strategy in which $De$ can get all the agents to vote 1. This is the case, for example, when $k_{Ad} = n$. We begin our analysis by examining the conditions concerning the minimum number of agents $De$ must influence to achieve a unanimous vote for 1, relative to the number of agents $Ad$ has an incentive to influence. Let $\eta = \lfloor \frac{\alpha(k_{Ad}-1)}{\alpha-\frac{1}{2}} \rfloor$.

**Proposition 7** *Suppose that payoff functions of players De and Ad are respectively given by Equations (3) and (4) and $n$ is even.*

1. Suppose that $(1 - \alpha)k_{Ad} < 1/2$. If $n \ge \lceil 2\alpha k_{Ad} \rceil + 1$, then $\#\mathcal{I}_{De}^{\min} = \lceil 2\alpha k_{Ad} \rceil + 1$. Otherwise, there is no winning strategy for De.

2. Suppose that $(1 - \alpha)k_{Ad} > 1/2$. If $n \ge \eta$, then $\#\mathcal{I}_{De}^{\min} = \eta + 1$. Otherwise, there is no winning strategy for De.

3. When $(1 - \alpha)k_{Ad} = 1/2$, then the previous two results hold.

We now provide an intuition for this result. First, recall that $Ad$ wants to obtain $v_i(\theta_i^F) = 0$ for either $i \in \mathcal{I}_{De}$, or for $i \in \mathcal{N} \setminus \mathcal{I}_{De}$. Second, $Ad$ has two possible strategies: either he influences both agent $i$ and some of his neighbors, or he only influences some neighbors of $i$. The threshold given in Proposition 7 follows from straightforward computations given the previous strategies that $Ad$ can use.

In the proposition below, we provide the candidate strategies for being optimal. Some additional properties of $C(\#E(g), \#\mathcal{I}_{De})$ are needed to characterize optimal strategies. Obviously, we restrict our attention to cases where $De$ has an incentive to influence some agents (and possibly form links). Clearly, the complete influence-empty network strategy cannot be optimal for $De$, since $Ad$ can always influence one agent, say $i$, and obtain $v_i(\theta_i^F) = 1$.

**Proposition 8** *Suppose that the cost function is convex in each of its two arguments, and $n$ is even.*

1. Suppose that $\frac{1}{2} < (1 - \alpha)k_{Ad} < \alpha$. If $De$ has a winning strategy, then the strategies' candidate for being optimal are: $(\eta, 2k_{Ad}, \mathcal{I}_{De})$-groups-regular network strategies where $\#\mathcal{I}_{De} \in [\#\mathcal{I}_{De}^{\min}, n-1]$, or $\eta$-regular network strategies.

2. Suppose that $(1 - \alpha)k_{Ad} < \frac{1}{2}$. If $De$ has a winning strategy, then the strategies' candidate for being optimal are: $([2\alpha k_{Ad}], 2k_{Ad}, \mathcal{I}_{De})$-groups-regular network strategies where $\#\mathcal{I}_{De} \in [\#\mathcal{I}_{De}^{\min}, n-1]$, or $\lceil 2\alpha k_{Ad} \rceil$-regular network strategies.
3. Suppose that $(1 - \alpha)k_{Ad} > \alpha$. If De has a winning strategy, then the only optimal candidate strategies are: $(\eta, \eta, \mathcal{I}_{De}^{\min})$-groups-regular network strategies.

Moreover, when $(1 - \alpha)k_{Ad} = \frac{1}{2}$, points 1. and 2. hold, and when $(1 - \alpha)k_{Ad} = \alpha$ points 2. and 3. hold.

In the above proposition, it is interesting to note that there are different group regular network strategies that are candidates to be optimal for $De$ in the first two points, depending on the value of $\mathcal{H}\mathcal{I}_{De}$. The number of agents influenced by $De$ differs in these different strategies. These possibilities arise from the fact that, in these strategies, the number of neighbors of $i \in \mathcal{I}_{De}$ $De$ must influence to get $v_i(\theta_i^F) = 1$ is less than the number of neighbors of $j \in \mathcal{N} \setminus \mathcal{I}_{De}$ $De$ must influence to get $v_j(\theta_j^F) = 1$. Consequently, the fewer agents $De$ influences, the more links she has to create. Each of these additional links involves an agent in $\mathcal{I}_{De}$ and an agent in $\mathcal{N} \setminus \mathcal{I}_{De}$, and allows $De$ to prevent agents in $\mathcal{N} \setminus \mathcal{I}_{De}$ from voting for 1.

# 5 Concluding Remarks

In this paper, we examine a situation in which a player can both establish the pattern of interactions between agents and influence them. We study how this player should act when faced with an opponent who intends to counter influence the agents. This type of situation occurs in many social situations where a player, the designer, has the ability to create links between agents by forming committees, working groups, and so on. More specifically, we have assumed that the two players interact in a “zero-sum” type game where the designer wins *if and only if* she obtains the vote of all the agents. We have provided the optimal strategies for the designer to obtain a unanimous vote for 1, given that creating links and influencing agents are costly activities. These optimal strategies depend on these costs. We then explore the possibility that unplanned links may occur with some probability, and provide a condition that allows us to preserve the results obtained in the benchmark model.

In the extension section of the paper, we relax the main assumptions. First, we assume that agents interact multiple times before voting. We show that the designer's optimal strategy is less costly in this case since the designer can use the network to persuade everyone due to the repeated interactions. In addition, the architectures of the networks she builds are very different from that of the benchmark model. In particular, these networks allow the designer to achieve unanimity among agents by influencing only a single agent. Note that the process of achieving unanimity can often be lengthy. Second, we assume that the designer only needs the consent of a majority of agents to win the zero-sum game, rather than unanimity as in
our benchmark model. Not surprisingly, we find that the designer's optimal strategy requires fewer resources. We also find that the designer's optimal strategy does not depend on the cost of influencing the adversary's agents in this context. Furthermore, the designer builds networks that are qualitatively close to the benchmark model. Finally, we explore a situation where the adversary is a better influencer than the designer. We establish that the designer can only win the zero-sum game if she can overcome the number of attacks of her opponent by forming links and influencing agents. Moreover, the designer's optimal strategies are very different from those in the benchmark model. In particular, there are situations where the designer needs to influence all agents and form links between them in order to avoid the diffusion of opinion in favor of the adversary. The extension section shows that the results are significantly affected by which the player is the most effective influencer, i.e., who has the best influencing technology. This finding has important implications for public policy. Thus, in the context of Example 1, if the police (the adversary) have a greater ability to influence and threaten a sufficient number of the criminal organization's members, then the criminal organization's ability to control the pattern of interactions of its members may not be sufficient to secure their consent/loyalty. In other words, the fact that the designer is not the best influencer is not always compensated for by his ability to shape the network, which may require specific public policies.

## References

[1] D. ACEMOGLU, A. MALEKIAN, AND A. OZDAGLAR, *Network security and contagion*, Journal of Economic Theory, 166 (2016), pp. 536–585.

[2] D. ACEMOGLU, A. OZDAGLAR, AND J. SIDERIUS, *A model of online misinformation*, The Review of Economic Studies, accepted, (2023).

[3] J. H. ALDRICH, *Why parties?*, American Politics & Political Economy S., University of Chicago Press, Chicago, IL, Jan. 1996.

[4] M. BACCARA AND H. BAR-ISAAC, *How to Organize Crime*, The Review of Economic Studies, 75 (2008), pp. 1039–1067.

[5] M. BARBER AND N. MCCARTY, *Causes and consequences of polarization*, in Political Negotiation: A Handbook, Mansbridge, Jane, and Cathie Jo Martin, editors. Brookings Institution Press, 2016, pp. 37–90.

[6] M. BATTAGLINI, V. L. SCIABOLAZZA, AND E. PATACCHINI, *Abstentions and social networks in congress*, The Journal of Politics, 85 (2023), pp. 581–592.
[7] F. BLOCH, G. DEMANGE, AND R. KRANTON, *Rumors and social networks*, International Economic Review, 59 (2018), pp. 421–448.

[8] C. BRAVARD, L. CHAROIN, AND C. TOUATI, *Optimal design and defense of networks under link attacks*, Journal of Mathematical Economics, 68 (2016), pp. 62–79.

[9] C. BRAVARD, J. DURIEU, S. SARANGI, AND S. SÉMIRAT, *False information from near and far*, Games and Economic Behavior, 137 (2023), pp. 152–174.

[10] A. CABRALES, P. GOTTARDI, AND F. VEGA-REDONDO, *Risk Sharing and Contagion in Networks*, The Review of Financial Studies, 30 (2017), pp. 3086–3127.

[11] L. COHEN AND C. J. MALLOY, *Friends in high places*, American Economic Journal: Economic Policy, 6 (2014), pp. 63–91.

[12] M. DZIUBIŃSKI AND S. GOYAL, *Network design and defence*, Games and Economic Behavior, 79 (2013), pp. 30–43.

[13] M. K. DZIUBIŃSKI AND S. GOYAL, *How do you defend a network?*, Theoretical Economics, 12 (2017).

[14] B. GOLUB AND M. O. JACKSON, *Naïve learning in social networks and the wisdom of crowds*, American Economic Journal: Microeconomics, 2 (2010), pp. 112–49.

[15] S. GOYAL AND A. VIGIER, *Attack, defence, and contagion in networks*, The Review of Economic Studies, 81 (2014), pp. 1518–1542.

[16] M. GRABISCH, A. MANDEL, A. RUSINOWSKA, AND E. TANIMURA, *Strategic influence in social networks*, Mathematics of Operations Research, 43 (2018), pp. 29–50.

[17] H. HALLER AND B. HOYER, *The common enemy effect under strategic network formation and disruption*, Journal of Economic Behavior & Organization, 162 (2019), pp. 146–163.

[18] M. O. JACKSON AND L. YARIV, *Diffusion of behavior and equilibrium properties in network games*, The American Economic Review, 97 (2007), pp. 92–98.

[19] K. D. JAEGHER AND B. HOYER, *Collective action and the common enemy effect*, Defense and Peace Economics, 27 (2016), pp. 644–664.

[20] K. PEARSON, *Party Discipline in the U.S. House of Representatives*, AnnHarbor: University of Michigan Press, 2015.

[21] D. W. ROHDE, *Parties and Leaders in the Postreform House*, American Politics & Political Economy S., University of Chicago Press, Chicago, IL, 2 ed., June 1991.
# Appendix A. Model Analysis

## A.1. Existence of $(q, \mathcal{Y})$-MQC Network

To show the existence of a $(q, \mathcal{Y})$-MQC network for every $q \le 1$, it is sufficient to establish that the set of $(q, \mathcal{Y})$-quasi-core-periphery networks is non-empty. Indeed, since this set is finite, it admits at least one minimal element with regard to the number of links. Since $q \le 1$, a $(1, \mathcal{Y})$-MQC is a $(q, \mathcal{Y})$-quasi-core-periphery network. The existence of $(1, \mathcal{Y})$-MQC implies that the set of $(q, \mathcal{Y})$-MQC networks is non-empty.

Let us construct a process that leads to a $(1, \mathcal{Y})$-MQC network $g$. We build network $g$ as follows:

1. Start with the empty network.

2. While $\#E(g[\mathcal{Y}]) = \frac{1}{2} \sum_{i,j \in \mathcal{Y}} A_{i,j}(g)$ is such that $\#E(g[\mathcal{Y}]) < \left\lceil \frac{n-\#\mathcal{Y}}{2} \right\rceil$, take two unlinked agents $i, j \in \mathcal{Y}$ such that $\#N_i(g), \#N_j(g) \in \min_{\ell \in \mathcal{Y}} \{\#N_\ell(g)\}$, do $i, j \in E(g)$. When $\#E(g[\mathcal{Y}]) = \left\lceil \frac{n-\#\mathcal{Y}}{2} \right\rceil$ go to 3.

3. While there exists $j \in \mathcal{N} \setminus \mathcal{Y}$, with $N_j(g) = \emptyset$, take $i \in \mathcal{Y}$ with $\sum_{\ell \in \mathcal{Y}} A_{i,\ell}(g) \ge \sum_{\ell \in \mathcal{N} \setminus \mathcal{Y}} A_{i,\ell}(g) + 1$, do $i, j \in E(g)$. Stop.

## A.2. Optimal Strategy of $D_e$

In order to present the proof of Proposition 1, we introduce two lemmas.

**Lemma 2** Suppose that payoff functions of players $D_e$ and $A_d$ are respectively given by Equations (3) and (4). Let $(g, \mathcal{I}_{D_e})$ be a winning strategy. For every $i \in \mathcal{I}_{D_e}$, we have $\#(N_i(g) \cap \mathcal{I}_{D_e}) \ge \kappa k_{B1}$, with $k_{B1} = k_{B1}(i, g)$.

**Proof** The condition is obvious for isolated agents in $\mathcal{I}_{D_e}$. Consider a non-isolated agent $i \in \mathcal{I}_{D_e}$. A winning strategy requires that $\theta_i^F = 1$. By Equation (2), this is true when $1/2 \le (1-\alpha) + \alpha \bar{\Theta}_i = 1 - \alpha + \alpha \frac{\#(N_i(g) \cap \mathcal{I}_{D_e})}{\#(N_i(g) \cap \mathcal{I}_{D_e}) + k_{B1}}$ for every $i \in \mathcal{N}$. Hence, $(\alpha - \frac{1}{2}) k_{B1} \le \frac{1}{2} \#(N_i(g) \cap \mathcal{I}_{D_e})$ which leads to the conclusion. $\square$

**Lemma 3** Suppose that payoff functions of players $D_e$ and $A_d$ are respectively given by Equations (3) and (4). Let $(g, \mathcal{I}_{D_e})$ belong to a minimal winning strategy. If $i \in \mathcal{N} \setminus \mathcal{I}_{D_e}$, then $N_i(g) = \{j\}$, with $j \in \mathcal{I}_{D_e}$.
**Proof** Suppose that $(g, \mathcal{I}_{De})$ is a minimal winning strategy. First, if $i \in \mathcal{N} \setminus \mathcal{I}_{De}$, then $i$ is not isolated. Otherwise, $Ad$ chooses to influence agent $i$, and the strategy is not a winning one, a contradiction. Second, we show that if $i, j \in \mathcal{N} \setminus \mathcal{I}_{De}$, then $A_{i,j}(g) = 1$. It is clear that links between agents $i, j \in \mathcal{N} \setminus \mathcal{I}_{De}$ cannot allow $De$ to save links between agents in $\mathcal{I}_{De}$ and agents in $\mathcal{N} \setminus \mathcal{I}_{De}$. Consequently, $De$ has no incentive to form links between agents $i$ and $j$ in $\mathcal{N} \setminus \mathcal{I}_{De}$. Similarly, if $i \in \mathcal{N} \setminus \mathcal{I}_{De}$ has a unique neighbor who is influenced by $De$, then $\theta_i^F = 1$. Again, an additional link between $i$ and another agent in $\mathcal{I}_{De}$ is useless and costly and thus not formed in a minimal winning strategy. □

**Proof of Proposition 1** First, we establish that $\#(\mathcal{N}_i(g) \cap \mathcal{I}_{De}) \le \lfloor \frac{n}{2} \rfloor$ for every $i \in \mathcal{I}_{De}$. To introduce a contradiction, suppose that there exists $i \in \mathcal{N}$ such that $\#(\mathcal{N}_i(g) \cap \mathcal{I}_{De}) \ge \lfloor \frac{n}{2} \rfloor + 1$. Then, $\#(\mathcal{N}_i(g) \cap \mathcal{I}_{De}) \ge \lfloor \frac{\#\mathcal{N}_i(g)}{2} \rfloor + 1 \ge \frac{\#\mathcal{N}_i(g)+2}{2}$. We have $2\#(\mathcal{N}_i(g) \cap \mathcal{I}_{De}) \ge \#\mathcal{N}_i(g) + 2 \Rightarrow \#(\mathcal{N}_i(g) \cap \mathcal{I}_{De}) \ge \#\mathcal{N}_i(g) - \#(\mathcal{N}_i(g) \cap \mathcal{I}_{De}) + 2 \Rightarrow \#\mathcal{N}_i^1(g) \ge \#\mathcal{N}_i^0(g) + 2 \Rightarrow \#\mathcal{N}_i^1(g) \ge \lfloor \kappa\#\mathcal{N}_i^0(g) \rfloor + 2$. Consequently, if $\#(\mathcal{N}_i(g) \cap \mathcal{I}_{De}) \ge \lfloor \frac{n}{2} \rfloor + 1$, then it is possible for $De$ to decrease $C(\#E(g), \#\mathcal{I}_{De})$ by removing a link and obtain a winning network, a contradiction. Second, we establish that a strategy is optimal if and only if it is a solution of Program (1). Note that an optimal strategy for $De$ is a minimal winning strategy. We divide the proof into two parts.

1. We establish that an optimal strategy $(g^*, \mathcal{I}_{De}^*)$ is a solution of the program. We know that an optimal strategy $(g^*, \mathcal{I}_{De}^*)$ for $De$ has to satisfy the two necessary conditions given in Lemmas 2 and 3, i.e., (Cons. 1) and (Cons. 2). Moreover, an optimal strategy has to minimize the cost incurred by $De$. The result follows.

2. We show that a solution of the program $(g^*, \mathcal{I}_{De}^*)$ is an optimal strategy. Suppose that the solution of the program is not an optimal strategy for $De$. Then, there exists a winning strategy $(g, \mathcal{I}_{De})$ less costly than $(g^*, \mathcal{I}_{De}^*)$. Such a pair $(g, \mathcal{I}_{De})$ has to violate one of the two constraints, a contradiction by Lemmas 2 and 3. □

We now introduce a lemma needed for the proof of Proposition 2.

**Lemma 4** Let

$$ \bar{x} = \arg\min_{x \in [1, \#\mathcal{N}]} \left\{ x \left\lfloor \frac{x-1}{\kappa} \right\rfloor \ge n - x \right\}. \quad (14) $$

Then, $\bar{x} = \lceil \sqrt{\kappa n} \rceil$ or $\bar{x} = \lceil \sqrt{\kappa n} \rceil + 1$.

**Proof** Consider the real valued function $f: x \mapsto x \lfloor \frac{x-1}{\kappa} \rfloor - (n-x)$. We seek $\bar{x}/in\mathcal{N}$, the minimal value such that $f(\bar{x}) \ge 0$. Let $w = \sqrt{\kappa n}$. Then, $w \lfloor \frac{w-1}{\kappa} \rfloor = \sqrt{\kappa n} \lfloor \frac{\sqrt{\kappa n}-1}{\kappa} \rfloor \le \sqrt{\kappa n} (\frac{\sqrt{\kappa n}}{\kappa} - 1) = n - \sqrt{\kappa n} = n - w$ and thus $f(w) \le 0$. Let $y = \sqrt{\kappa n} + 1$. Then $y \lfloor \frac{y-1}{\kappa} \rfloor =$
(√κn + 1) ⌊√κn/κ⌋ > (√κn + 1) (√κn/κ − 1) = n + √κn/κ − √κn − 1 = n + √κn/κ − y > n − y.
Thus, f(y) > 0. Since f is strictly increasing any value x ≥ y satisfies f(x) ≥ 0. Similarly,
any value x < w satisfies f(x) < 0. The conclusion follows from the fact that x̄ is the smallest
integer for which f is non-negative.
□

**Proof of Proposition 2** In a winning strategy, and so in an optimal strategy, there is at least one agent in $\mathcal{I}_{De}$. By Proposition 1, an optimal strategy satisfies (Cons. 1) and (Cons. 2). Since for every $i \in \mathcal{N}$, $k_{B1}(i,g) = \min\{k_{Ad}, \#\mathcal{N}_i(g) \setminus \mathcal{I}_{De}\}$ two cases can occur.

1. Consider an optimal strategy where $\#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g)) \le k_{Ad}$ for every $i \in \mathcal{I}_{De}$. Then, from (Cons. 1), we have $\#\mathcal{N}_i^1(g) \ge \kappa k_{B1}$. Thus, $\#\mathcal{I}_{De} - 1 \ge \#\mathcal{N}_i^1(g) \ge \kappa \#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g))$. Hence, $\frac{\#\mathcal{I}_{De}-1}{\kappa} \ge \#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g))$ and finally $\left\lfloor \frac{\#\mathcal{I}_{De}-1}{\kappa} \right\rfloor \ge \#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g))$ since the right-hand side is an integer. Summing over all agents in $\mathcal{I}_{De}$, we obtain that $\#\mathcal{I}_{De} \left\lfloor \frac{\#\mathcal{I}_{De}-1}{\kappa} \right\rfloor \ge \sum_{i \in \mathcal{I}_{De}} \#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g))$. Next, from (Cons. 2), we have $n - \#\mathcal{I}_{De} = \sum_{i \in \mathcal{I}_{De}} \#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g))$ and thus necessarily $\#\mathcal{I}_{De} \left\lfloor \frac{\#\mathcal{I}_{De}-1}{\kappa} \right\rfloor \ge n - \#\mathcal{I}_{De}$. By definition $\bar{x}$ is the minimum integer that satisfies the above inequality. From Appendix A.1, a winning strategy with $\#\mathcal{I}_{De} = \bar{x}$ agents exists: it is a $(\kappa, \mathcal{I}_{De})$-influence-MQC network strategy.

2. There exists $i \in \mathcal{I}_{De}$ such that $\#(\mathcal{N}_i(g)\setminus\mathcal{N}_i^1(g)) > k_{Ad}$. Since $\#\mathcal{N}_i^1(g) \ge \kappa k_{B1} = \kappa k_{Ad}$, necessarily $\#\mathcal{I}_{De} \ge \kappa k_{Ad} + 1$. Consider a partial-star-network with the center being influenced by $De$ as well as $\lceil \kappa k_{Ad} \rceil$ peripheral agents. It is a winning strategy satisfying the minimal number of influenced agents. It is possible to construct it if and only if $n \ge \kappa \lceil k_{Ad} \rceil + 1$.

□

**Proof of Proposition 3** First, we deal with the number of links between agents in $\mathcal{I}_{De}$. Two cases can occur.

1. Consider a minimal winning strategy where $\#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g)) \le k_{Ad}$ for every $i \in \mathcal{I}_{De}$. From (Cons. 1), we have $\#\mathcal{N}_i^1(g) \ge \kappa k_{B1}$ for $i \in \mathcal{I}_{De}$. Thus, $\#\mathcal{N}_i^1(g) \ge \kappa \#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g))$. By summing over all agents in $\mathcal{I}_{De}$, we have $\sum_{i \in \mathcal{I}_{De}} \#\mathcal{N}_i^1(g) \ge \kappa \sum_{i \in \mathcal{I}_{De}} (\#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g)))$. Note that $\sum_{i \in \mathcal{I}_{De}} \#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g))$ represents the total number of links joining agents in $\mathcal{I}_{De}$ to agents in $\mathcal{N} \setminus \mathcal{I}_{De}$. Thus, by (Cons. 2), $\sum_{i \in \mathcal{I}_{De}} (\#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g))) = n - \#\mathcal{I}_{De}$. Therefore, the number of links in $g[\mathcal{I}_{De}]$ is at least $\left\lfloor \frac{\kappa(n - \#\mathcal{I}_{De})}{2} \right\rfloor$.
2. Consider a minimal winning strategy where there is $i \in \mathcal{I}_{De}$ such that $\#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g)) > k_{Ad}$. By Proposition 1, we have $\#\mathcal{N}_i^1(g) \le \lfloor \frac{n}{2} \rfloor$. Moreover, since $\#\mathcal{N}_i^1(g) \ge \kappa k_{B1} = \kappa k_{Ad}$, $g[\mathcal{I}_{De}]$ contains at least $\lceil \kappa k_{Ad} \rceil$ links involving agent $i$.

From (Cons. 2), the number of links joining agents in $\mathcal{I}_{De}$ to agents in $\mathcal{N} \setminus \mathcal{I}_{De}$ is exactly $n - \#\mathcal{I}_{De}$ in a minimal winning strategy. The result follows. $\square$

**Proof of Theorem 1** Recall that an optimal strategy is a winning strategy where $De$ cannot remove a link without forming additional links given the set of agents she influences. Consider a winning strategy such that $\#\mathcal{I}_{De} = n$. Then, the unique winning strategy is the complete influence-empty network. When $\#\mathcal{I}_{De} < n$, there are two possibilities:

1. Consider strategies where $\#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g)) \le k_{Ad}$ for every $i \in \mathcal{I}_{De}$. We establish that $(\kappa, \mathcal{I}_{De})$-influence-MQC network strategies with $\#\mathcal{I}_{De} \ge \#\mathcal{I}_{De}^{\min}$ are optimal. First, they are winning strategies since they satisfy (Cons. 1), (Cons. 2), and Proposition 2. Second, the number of links in $(\kappa, \mathcal{I}_{De})$-influence-MQC network strategies satisfies the bound given in the proof of Proposition 3 part 1.

2. Consider strategies where there is $i \in \mathcal{I}_{De}$ such that $\#(\mathcal{N}_i(g) \setminus \mathcal{N}_i^1(g)) > k_{Ad}$. We establish that $(p, \mathcal{I}_{De})$-influence-partial-star strategies, with $\#\mathcal{I}_{De} \ge \#\mathcal{I}_{De}^{\min}$ and $p \ge \lceil \kappa k_{Ad} \rceil$ are optimal. First, they are winning strategies since they satisfy (Cons. 1), (Cons. 2), and Proposition 2. Moreover, the number of links in $(p, \mathcal{I}_{De})$-influence-partial-star strategies satisfies the bound given in the proof of Proposition 3 part 2.

<figure><img src="image_10.png" /></figure>

## Appendix A.3. Possibility of Interactions between Non-linked Agents

**Proof of Proposition 4** Let $\mathbb{P}^W(g)$ be the probability to obtain a winning network from $g$, and $\mathbb{P}_i^W(g)$ be the probability that agent $i$ satisfies (Cons. 1 & 2) after some links have been formed by Nature. Note that $\mathbb{P}^W(g) = \prod_{i \in \mathcal{N}} \mathbb{P}_i^W(g)$ since every agent has to satisfy (Cons. 1 & 2) in a winning network.

First, we provide a lower bound for the expected payoff associated with a network, say $g^{mw}$, which is a minimal winning network before Nature forms links. We have $\mathbb{P}^W(g^{mw}) = \prod_{i \in \mathcal{N}} \mathbb{P}_i^W(g^{mw}) \ge \prod_{i \in \mathcal{N}} (1-\omega)^n = n(1-\omega)^n \ge (1-\omega)^{n^2} = ((1-\omega)^n)^2 \ge (1-n\omega)^2 \ge (1-\frac{c_L}{4})^2$. The first inequality follows the fact that if Nature does not form any links, then the realization of $g^{mw}$ is a winning network. The third and the last inequalities follow the assumption that $\omega \le \frac{c_L}{4n}$ and the fact that $\frac{c_L}{4n} \le \frac{1}{n}$. We conclude that $\mathbb{P}^W(g^{mw}) \ge 1 - 2\frac{c_L}{4} = 1 - \frac{c_L}{2}$.
We now establish that $\mathcal{D}_e$ has no incentive to build a non-minimal winning network, $g^w$, instead of $g^{mw}$. Recall that the set $\mathcal{I}_{\mathcal{D}_e}$ is given. The difference between the expected payoff of $g^w$ and $g^{mw}$ is bounded by: $1 - \#E(g^w)c_L - (1 - \frac{c_L}{2} - c_L\#E(g^{mw})) = (\frac{1}{2} - (\#E(g^w) - \#E(g^{mw})))c_L < 0$ since $\#E(g^w) - \#E(g^{mw}) \ge 1$.

Finally, we establish that $\mathcal{D}_e$ has no incentive to build a network, say $g^l$, which is non-winning before Nature forms links. For every agent $i \in \mathcal{N}$ for which (Cons. 1 & 2) do not hold in $g^l$, Nature has to form at least $b_i$ links in order to obtain agent $i$ satisfies (Cons. 1 & 2) in a winning network $g^w$. Let $M(\ell)$ be the minimal set of links that allows $g^l$ to be a winning network, i.e., there is no set of links with lower cardinality that allows to obtain a winning network. Clearly, $m(\ell) = \#M(\ell) \ge 1$. Similarly, let $S(\ell)$ be the set of agents that are involved in links in $M(\ell)$. We have $\mathbb{P}^W(g^l) \le \sum_{k=b_i}^B \binom{B}{k} \omega^k$, with $i \in S_l$ and where $B = \#\mathcal{I}_{\mathcal{D}_e} - \#\mathcal{N}_i^1(g^l)$. Note that $\binom{B}{k} \omega^k = B\omega \frac{(B-1)\omega}{2} \dots \frac{(B-k)\omega}{k} \le (B\omega)^k$. Moreover, $\sum_{k=b_i}^B (B\omega)^k = (B\omega)^{b_i} \frac{(1-(B\omega)^{B+1-b_i})}{1-B\omega} \le \frac{(B\omega)^{b_i}}{1-B\omega} \le \frac{B\omega}{1-B\omega}$ since $b_i \ge 1$ and $B\omega < 1$. Since $\omega < \frac{c_L}{4n}$ and $B < n$, $\frac{B\omega}{1-B\omega} < \frac{B\frac{c_L}{4n}}{1-B\frac{c_L}{4n}} \le \frac{nc_L}{4n-nc_L} < \frac{c_L}{2}$. We conclude that $\mathbb{P}^W(g^l) \le \frac{c_L}{2}$. We now compute the difference between the minimal expected payoff of $\mathcal{D}_e$ with $g^{mw}$ and the maximal one with $g^l$: $1 - \frac{c_L}{2} - \#E(g^{mw})c_L - (\frac{c_L}{2} - (\#E(g^{mw}) - m(\ell)))c_L > 1 - c_L - (\frac{n(n-1)}{2} - 1)c_L = 1 - \frac{n(n-1)}{2}c_L \ge 0$.

# Appendix B. Extensions

## Appendix B.1. Reach Unanimity in Several Periods

**Proof of Proposition 5** We prove successively, the two parts of the proposition.

1. Clearly, $\mathcal{D}_e$ cannot obtain that all agents vote 1 at the end of the process if she does not influence at least one agent. Indeed, at $t=0$, for every $\theta_i \in \{0, \emptyset\}$, and $v_i^0(\theta_i) \in \{0, \emptyset\}$. By Equation (11), if at $t-1$, for every $i \in \mathcal{N}$, $v_i^{t-1}(\theta_i^{t-1}) \in \{0, \emptyset\}$, then $\theta_i^t \in \{0, \emptyset\}$ for every $i \in \mathcal{N}$. By Equation (10), it follows that $v_i^t(\theta_i^t) \in \{0, \emptyset\}$ for every $i \in \mathcal{N}$. Consequently, $\mathcal{N}(1, v) = \emptyset \ne \mathcal{N}$.

2. (a) Suppose that $\mathcal{D}_e$ influences one agent and $g$ is not connected. Then, network $g$ contains at least two distinct components. The previous reasoning can be repeated for agents within the component where no agents have been influenced by $\mathcal{D}_e$ for obtaining a contradiction. Consequently, $g$ is connected, i.e., it contains at least $n-1$ links. It is sufficient to show that if $\mathcal{D}_e$ influences only one agent, say $i$, and
builds an acyclic connected network, then for every finite $T$, we have $N(1, v) \neq N$. Recall that $k_{Ad} = n$, so it is profitable for $Ad$ to target each agent to ensure that some of them do not vote 1 at $T$. Therefore, De's strategy must prevent this specific strategy of $Ad$ from leading to a situation where some agents do not vote 1 in a finite period. When $Ad$ influences all agents, we have $v_i^t \in \{0, 1\}$ for every $t \le T$. To establish a contradiction, suppose there exists a finite period $T$ such that $N(1, v) = N$. Then, at period $t \le T$, there are two agents $j^t$ and $k^t$ linked in $g$ who vote 1. Since $j^t$ and $k^t$ are linked in an acyclic network, there is a unique path between $i$ and $j^t$ and a unique path between $i$ and $k^t$. Moreover, $d(i, j^t; g)$ is even *if and only if* $d(i, k^t; g)$ is odd. Since $g$ is an acyclic connected network, there are two distinct agents $j^{t-1}$ and $k^{t-1}$ respectively neighbors of $j^t$ and $k^t$ such that $v_{j^{t-1}} = v_{k^{t-1}} = 1$. Clearly, $d(i, j^{t-1}; g)$ is even *if and only if* $d(i, k^{t-1}; g)$ is odd. By reiterating this process, any period $\tau$ where there are two agents $j^\tau$ and $k^\tau$ such that $v_{j^\tau} = v_{k^\tau} = 1$, with $d(i, j^\tau; g)$ is even *if and only if* $d(i, k^\tau; g)$ is odd, requires that at period $\tau - 1$, there are two agents $j^{\tau-1}$ and $k^{\tau-1}$ such that $v_{j^{\tau-1}} = v_{k^{\tau-1}} = 1$, with $d(i, j^{\tau-1}; g)$ is even *if and only if* $d(i, k^{\tau-1}; g)$ is odd. This process stops at $t = 0$ where such agents do not exist, a contradiction.

(b) Suppose that $De$ builds a $i_1$-triangle network and influences agent $i_1$. As in the previous point, we consider that $Ad$ influences all the agents. At period 1, we have $V_i^1(g; 1) \ge V_i^0(g; 1)$ for $i \in \{i_1, i_2, i_3\}$. Consequently, at period $t \ge 2$, $V_i^1(g; t) \ge V_i^0(g; t)$, and $v_i^t = 1$ for $i \in \{i_1, i_2, i_3\}$. Next, by construction of the triangle network, for agent at distance one of agent $i_1$, $\ell_1 \in N \setminus \{2, 3\}$, we have $V_{\ell_1}^1(g; t) \ge V_{\ell_1}^0(g; t)$, for $t \ge 2$ and $v_{\ell_1}^t = 1$ for $t \ge 3$. By reiterating this argument for agent $\ell_d$ at distance $d$ of agent $i_1$, we have $V_{\ell_d}^1(g; t) \ge V_{\ell_d}^0(g; t)$, for $t \ge d+1$ and $v_{\ell_d}^t = 1$ for $t \ge d+2$. Since the population of agents is finite and the network $g$ is connected, the distance between agent 1 and any other agent in the set $N$ is also finite. We conclude that the process that leads all agents to vote 1 is finite. $\square$

**Appendix B.2. Ad Is the Stronger Influencer**

We establish Propositions 7 and 8. First we begin with a lemma. Let $N_i(g, I_{De})$ be the set of neighbors of agent $i$ who are influenced by $De$. Recall that $\eta = \lfloor \frac{\alpha(k_{Ad}-1)}{\alpha-\frac{1}{2}} \rfloor$.
**Lemma 5** Suppose that payoff functions of players De and Ad are respectively given by Equations (3) and (4) and n is even. Let $\mathcal{N}_i(g, \mathcal{I}_{De})$ be optimal for De.

1. Suppose that $(1 - \alpha)k_{Ad} \le \frac{1}{2}$. If $\sharp\mathcal{I}_{De} \ge \lceil 2\alpha k_{Ad} \rceil + 1$, then

$$ \sharp\mathcal{N}_i(g, \mathcal{I}_{De}) = \begin{cases} \lceil 2\alpha k_{Ad} \rceil & \text{if } i \in \mathcal{I}_{De}, \\ 2k_{Ad} & \text{otherwise.} \end{cases} $$

If $\sharp\mathcal{I}_{De} < \lceil 2\alpha k_{Ad} \rceil + 1$, then $\sharp\mathcal{N}_i(g, \mathcal{I}_{De}) = \emptyset$.

2. Suppose that $\frac{1}{2} < (1 - \alpha)k_{Ad} \le \alpha$. If $\sharp\mathcal{I}_{De} \ge \eta + 1$, then

$$ \sharp\mathcal{N}_i(g, \mathcal{I}_{De}) = \begin{cases} \eta & \text{if } i \in \mathcal{I}_{De}, \\ 2k_{Ad} & \text{otherwise.} \end{cases} $$

If $\sharp\mathcal{I}_{De} < \eta + 1$, then $\mathcal{N}_i(g, \mathcal{I}_{De}) = \emptyset$.

3. Suppose that $(1 - \alpha)k_{Ad} > \alpha$. If $\sharp\mathcal{I}_{De} \ge \eta + 1$, then

$$ \sharp\mathcal{N}_i(g, \mathcal{I}_{De}) = \eta, \text{ for every } i \in \mathcal{N}. $$

If $\sharp\mathcal{I}_{De} < \eta + 1$, then $\mathcal{N}_i(g, \mathcal{I}_{De}) = \emptyset$.

**Proof** Note that if $g$ is non-empty and $\mathcal{I}_{De} \ne \emptyset$, then for every $i \in \mathcal{N}$, $\sharp\mathcal{N}_i(g, \mathcal{I}_{De}) > k_{Ad}$, otherwise $De$ obtains a strictly negative payoff. $Ad$ has two possibilities concerning the agents he influences when he wants to obtain $v_i(\theta_i^F) = 0$: either (i) he influences only the neighbors of agent $i$, or (ii) he influences both agent $i$ and his neighbors. We present successively the case where $Ad$ wants to obtain $v_i(\theta_i^F) = 0$ for $i \in \mathcal{I}_{De}$, and then for $i \notin \mathcal{I}_{De}$.

(a) Suppose that $Ad$ wants to obtain $v_i(\theta_i^F) = 0$ for $i \in \mathcal{I}_{De}$. (i) When $Ad$ influences only the neighbors of agent $i$, $De$ has to ensure that the following inequality holds: $1 - \alpha + \alpha \frac{\sharp\mathcal{N}_i(g, \mathcal{I}_{De}) - k_{Ad}}{\sharp\mathcal{N}_i(g, \mathcal{I}_{De})} \ge 1/2$. It follows that $\sharp\mathcal{N}_i(g, \mathcal{I}_{De}) \ge 2\alpha k_{Ad}$. (ii) When $Ad$ influences agent $i$ and his neighbors, $De$ has to ensure that the following inequality holds: $\frac{\alpha}{\sharp\mathcal{N}_i(g, \mathcal{I}_{De})} (\sharp\mathcal{N}_i(g, \mathcal{I}_{De}) - k_{Ad} + 1) \ge 1/2$, that is $\sharp\mathcal{N}_i(g, \mathcal{I}_{De}) \ge \frac{\alpha(k_{Ad} - 1)}{\alpha - 1/2}$. Consequently, $v_i(\theta_i^F) = 1 \Leftrightarrow \sharp\mathcal{N}_i(g, \mathcal{I}_{De}) \ge \max\{\eta, 2\alpha k_{Ad}\}$. We have $\eta \ge 2\alpha k_{Ad} \Leftrightarrow (1 - \alpha)k_{Ad} \ge \frac{1}{2}$. It follows that

$$ v_i(\theta_i^F) = 1 \Leftrightarrow \left[ (1 - \alpha)k_{Ad} \le \frac{1}{2} \text{ and } \sharp\mathcal{N}_i(g, \mathcal{I}_{De}) \ge 2\alpha k_{Ad} \right]. $$

(b) Suppose that $Ad$ wants to obtain $v_i(\theta_i^F) = 0$ for $i \notin \mathcal{I}_{De}$. (i) When $Ad$ influences only the neighbors of agent $i$, $De$ has to ensure that the following inequality holds:
$\frac{\#\mathcal{N}_i(g, \mathcal{I}_{De}) - k_{Ad}}{\#\mathcal{N}_i(g, \mathcal{I}_{De})} \geq 1/2$, that is $\#\mathcal{N}_i(g, \mathcal{I}_{De}) \geq 2k_{Ad}$. (ii) When $Ad$ influences both $i$ and his neighbors inequality $\alpha \frac{\#\mathcal{N}_i(g, \mathcal{I}_{De}) - k_{Ad} + 1}{\#\mathcal{N}_i(g, \mathcal{I}_{De})} \geq 1/2$ holds, that is $\#\mathcal{N}_i(g, \mathcal{I}_{De}) \geq \eta$. We have $\eta \geq 2k_{Ad} \Leftrightarrow (1 - \alpha)k_{Ad} \geq \alpha$. It follows that

$$v_i(\theta_i^F) = 1 \Leftrightarrow [(1 - \alpha)k_{Ad} \geq \alpha \text{ and } \mathcal{N}_i(g, \mathcal{I}_{De}) \geq 2k_{Ad}].$$

Because $\alpha \in (1/2, 1]$, we have to examine three intervals for completing the analysis.

1. Suppose $(1 - \alpha)k_{Ad} \leq \frac{1}{2}$. Then necessarily inequality $\#\mathcal{N}_i(g, \mathcal{I}_{De}) \geq 2\alpha k_{Ad}$ holds when $Ad$ influences $i \in \mathcal{I}_{De}$ and inequality $\#\mathcal{N}_i(g, \mathcal{I}_{De}) \geq 2k_{Ad}$ holds when $Ad$ influences $i \notin \mathcal{I}_{De}$. $De$ has to choose the lowest number of neighbors of $i$ which satisfies the previous inequalities:

$$\#\mathcal{N}_i(g, \mathcal{I}_{De}) = \begin{cases} \lceil 2\alpha k_{Ad} \rceil & \text{if } i \in \mathcal{I}_{De}, \\ 2k_{Ad} & \text{otherwise.} \end{cases} \qquad (15)$$

Note that when $(1 - \alpha)k_{Ad} \leq \frac{1}{2}$, $\lceil 2\alpha k_{Ad} \rceil + 1 \geq 2k_{Ad}$. If $\#\mathcal{I}_{De} \geq \lceil 2\alpha k_{Ad} \rceil + 1$, then (15) holds. Otherwise, $De$ cannot satisfy the necessary condition: $\#\mathcal{N}_i(g, \mathcal{I}_{De}) \geq \lceil 2\alpha k_{Ad} \rceil$ for $i \in \mathcal{I}_{De}$.

2. Suppose $\frac{1}{2} \leq (1 - \alpha)k_{Ad} \leq \alpha$. Then necessarily inequality $\#\mathcal{N}_i(g, \mathcal{I}_{De}) \geq \eta$ holds when $Ad$ influences $i \in \mathcal{I}_{De}$ and $\#\mathcal{N}_i(g, \mathcal{I}_{De}) \geq 2k_{Ad}$ holds when $Ad$ influences $i \notin \mathcal{I}_{De}$. $De$ has to choose the lowest number of neighbors of $i$ which satisfies the previous inequalities:

$$\#\mathcal{N}_i(g, \mathcal{I}_{De}) = \begin{cases} \eta & \text{if } i \in \mathcal{I}_{De}, \\ 2k_{Ad} & \text{otherwise.} \end{cases} \qquad (16)$$

Note that when $(1 - \alpha)k_{Ad} \geq \frac{1}{2}$, $\eta + 1 \geq 2k_{Ad}$. If $\#\mathcal{I}_{De} \geq \eta + 1$, then (16) holds. Otherwise, $De$ cannot satisfy the following necessary condition: $\#\mathcal{N}_i(g, \mathcal{I}_{De}) \geq \eta$ for $i \in \mathcal{I}_{De}$.

3. Suppose $(1 - \alpha)k_{Ad} > \alpha$. Then necessarily inequality $\#\mathcal{N}_i(g, \mathcal{I}_{De}) \geq \eta$ holds when $Ad$ influences $i \in \mathcal{I}_{De}$ or when $Ad$ influences $i \notin \mathcal{I}_{De}$. $De$ has to choose the lowest number of neighbors which satisfies the previous inequality:

$$\#\mathcal{N}_i(g, \mathcal{I}_{De}) = \eta. \qquad (17)$$

If $\#\mathcal{I}_{De} \geq \eta + 1$, then (17) holds. Otherwise, $De$ cannot satisfy $\#\mathcal{N}_i(g, \mathcal{I}_{De}) = \eta$ for $i \in \mathcal{I}_{De}$.
☐

**Proof of Proposition 7** The proof is straightforward from Lemma 5. Indeed for every value of $k_{Ad}$, Lemma 5 provides a necessary condition for the value of $\#\mathcal{I}_{De}^{\min}$:

1. If $(1 - \alpha)k_{Ad} \le \frac{1}{2}$, then there is a winning strategy if $\#\mathcal{I}_{De}^{\min} = \lceil 2\alpha k_{Ad} \rceil + 1$;

2. if $\frac{1}{2} < (1 - \alpha)k_{Ad} \le \alpha$, then $\#\mathcal{I}_{De}^{\min} = \eta + 1$;

3. if $(1 - \alpha)k_{Ad} > \alpha$, then $\#\mathcal{I}_{De}^{\min} = \eta + 1$.

☐

**Proof of Proposition 8** Due to Proposition 7, we know the minimal size of $\#\mathcal{I}_{De}$ for a winning strategy, $\#\mathcal{I}_{De}^{\min}$. It follows that because of the convexity in each of its two arguments of the cost function, in a winning strategy, $\#\mathcal{I}_{De} \in [[\#\mathcal{I}_{De}^{\min}, n]]$. Moreover, by Lemma 5, we know conditions that a winning strategy has to satisfy. Clearly, when $(1 - \alpha)k_{Ad} \le \frac{1}{2}$, $(\lceil 2\alpha k_{Ad} \rceil, 2k_{Ad}, \#\mathcal{I}_{De})$-groups-regular network strategies, with $\#\mathcal{I}_{De} \in [[\#\mathcal{I}_{De}^{\min}, n - 1]]$, and $\lceil 2\alpha k_{Ad} \rceil$-regular network strategies allow to satisfy conditions given in Lemma 5 and minimize the number of links given the size of $\mathcal{I}_{De}$. Similarly, by using Lemma 5, we obtain the two other parts of the proposition. Note that the only two types of strategies candidate for being optimal are $(\eta, \eta, \mathcal{I}_{De})$-groups-regular network strategy where $\#\mathcal{I}_{De} \in [[\#\mathcal{I}_{De}^{\min}, n - 1]]$, and $\eta$-regular network strategies. Obviously, the number of links in all these networks is the same, since the degree of each agent in each of these networks is $\eta$. Consequently, only $(\eta, \eta, \mathcal{I}_{De}^{\min})$-groups-regular network strategies are optimal for $De$ since the number of agents influenced by $De$ is minimal.

☐