Exploiting social influence in networks

Nora, Vladyslav; Winter, Eyal Article Exploiting social influence in networks Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Nora, Vladyslav; Winter, Eyal (2024) : Exploiting social influence in networks, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 19, Iss. 1, pp. 1-27, https://doi.org/10.3982/TE5068 This Version is available at: https://hdl.handle.net/10419/296452 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Theoretical Economics 19 (2024), 1–27 1555-7561/20240001 Exploiting social influence in networks Vladyslav Nora Department of Economics, Nazarbayev University Eyal Winter Department of Economics, Lancaster University and Department of Economics, and the Federmann Center for the Study of Rationality, The Hebrew University We study binary action network games with strategic complementarities. An agent acts if the aggregate social influence of her friends exceeds a transfer levied on the agent by a principal. The principal seeks to maximize her revenue while inducing everyone to act in a unique equilibrium. We characterize optimal transfers showing that agents who are more popular than their friends receive preferential treatment. Our main result is that under mild conditions complete coreperiphery networks deliver the highest revenue to the principal. Furthermore, we show that the revenue is higher in networks where links are allocated unequally across agents. Hence, the principal benefits from creating “influentials” by linking well-connected hubs to less popular periphery. Keywords. Social networks, unique implementation, strategic complementarities, split graphs. JEL classification. C72, D82. 1. Introduction The spread of behaviors on social networks is often mediated by external forces exemplified by firms or social media platforms. Using various incentive mechanisms, they are trying to get individuals to purchase products or adopt behaviors at maximal revenue or minimal cost. When decisions are strategic complements, such mechanisms typically induce multiple equilibria, and hence are prone to coordination failures. In this paper, we study how external forces can exploit social influence to overcome coordination failures and which networks are the most accommodating to such efforts. We use a canonical model of a social network, where nodes represent individuals (agents), and edges represent links (friendships). An individual decides whether to take an action such as buying a product or voting for a candidate. Acting creates a positive Vladyslav Nora: [email protected] Eyal Winter: [email protected] We are grateful to Francis Bloch, Andrea Galeotti, Sanjeev Goyal, Sergiu Hart, Matt Jackson, Marek Weretka, and seminar audience at OfCom UK, FCC, KSE, Hebrew University, University of Hamburg, VEST, and the participants of the conference on Game Theoretic and Behavioral Economic Insights on Social Media for their insightful comments that helped to improve the paper. Eyal Winter wishes to acknowledge financial support from the ESRC through a research grant ECA7674. ©2024 The Authors. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE5068 2Nora and Winter Theoretical Economics 19 (2024) externality on her friends who took the action as well, encouraging them to act. A novel feature of our model is the degree-dependent network effects: individuals with many friends are less influenced by any one of them compared to their less popular peers. An agent acts if the aggregate influence of her friends exceeds a transfer levied on her by a principal. A set of transfers, or a mechanism, induces a binary action network game. We study mechanisms that maximize the principal’s revenue while inducing everyone to act in a unique equilibrium, i.e., optimal mechanisms. The requirement of uniqueness is a cornerstone of our analysis that captures the concern that the principal cannot coordinate agents to act in accordance with her preferred equilibrium. Indeed, experiments show that such an equilibrium tends to unravel (Devetag and Ortmann (2007)), which makes focusing on it unjustified in environments where the principal cannot shape individual beliefs, as is arguably the case in real world social networks. Our model speaks to applications of strategic complementarities in networks. One example is a firm selling a network good. The principal is a firm who posts an individual price, and a transfer represents the price net of an intrinsic value of the good. Another example is when the principal is a social media platform willing to incentivize its users to adopt a new online application, such as a messenger, by providing a subsidy to each adopting user. A transfer is given by an adoption cost net of the subsidy. In this case, the platform minimizes the sum of subsidies, which is equivalent to maximizing the sum of the transfers. Such campaigns often start with significant persuasive efforts to recruit community leaders as early adopters with the intention that their public visibility will induce others to adopt as well. As we shall see, this feature of the incentive mechanism arises from our analysis of the model. Our first result characterizes an optimal mechanism. Such a mechanism induces a cascade of iterative elimination of dominated strategies, leading to the outcome where everyone acts. But more importantly, the result highlights the role of relative rather than absolute degree centrality in networks. We show that being more popular than your friends guarantees preferential treatment from the principal. Such individuals pay lower transfers (or receive higher subsidies) than the rest and take the role of network leaders, allowing the principal to exploit their influence by raising transfers of their friends, who expect leaders to act and are willing to pay these higher transfers. We apply our characterization of optimal mechanisms to study the properties of networks that make achieving coordination easier for the principal. Put differently, we are interested in networks that guarantee higher revenue. Our motivation is twofold. First, the principal might have some control over the network. For example, the newsfeed algorithm of Facebook partially determines how active a link between users is. If the majority of user i’s posts are hidden from user jand vice versa, then a nominal link would be rather inactive. Likewise, by means of friends suggestions, the platform influences the likelihood of new links emerging. Second, an interested party might want to compare exogenously given networks. For instance, to predict the commercial success of a new network product a firm must consider its associated network. Whether the product is a messenger or a specialized editing software determines the structural properties of a relevant network, and hence the product’s profitability. Theoretical Economics 19 (2024) Exploiting social influence in networks 3 Our main result is that under mild conditions complete core-periphery networks guarantee the highest revenue, and hence allow for the most effective coordination. In these networks, the nodes are partitioned into two subsets, core and periphery. Every core node is connected to all nodes, and hence is a star, while every periphery node is connected only to stars. One implication of this result is that core-periphery structures ubiquitous in real life social networks are vulnerable to manipulation by external forces. To gain further insights into the interplay between the revenue and a network structure, we first show that one network always delivers a higher revenue than another if it has more links with a small-degree agent as at least one of the endpoints. The reason is that small-degree agents are more susceptible to social influence and the principal can exploit it by charging them higher transfers. For networks with the same degree sequence, this implies that the revenue is always higher in a more disassortative network where connections tend to be between small- and high-degree agents. We also characterize networks that deliver the lowest revenue or, equivalently, require the most resources to induce action. We show that for a given number of links, these networks have as many isolated agents as possible, while other agents are tightly connected to each other. Finally, we discuss several extensions that include heterogeneous social influence and show that many insights from the original model continue to hold. 1.1 Related literature The paper builds on a vast literature that studies how locally interacting individuals coordinate their actions (Contagion (2000), Jackson and Yariv (2007), Sadler (2020a)). These papers consider games where players face a simple choice of whether to adopt some behavior or not, and study how adoption levels and dynamics relate to characteristics of social interaction networks. Using the binary action framework of this literature, we explore two novel questions: what are the optimal mechanisms for solving coordination problems and which networks are more susceptible to manipulation by external forces? Our analysis of influence mechanisms contributes to the literature on pricing and influence in networks.1 Candogan, Bimpikis, and Ozdaglar (2012), Bloch and Querou (2013), and Fainmesser and Galeotti (2016) consider price-discriminating firms selling network goods and explore how prices and welfare depend on network characteristics. They assume a unique equilibrium, and hence no coordination problems among consumers. Belhaj and Deroïan (2019) study bilateral contracting in networks aimed at increasing the sum of agents’ effort, and focus on equilibria that maximize the principal’s objective. Computer science papers investigate the algorithmic aspects of pricing in networks (Hartline, Mirrokni, and Sundararajan (2008), Arthur, Motwani, Sharma, and 1See Bloch (2016) for a comprehensive survey. An extensive literature on targeting and interventions in networks uses distinct modeling approaches. Ballester, Calvó-Armengol, and Zenou (2006)studies “key” players whose removal induces the greatest change in equilibrium aggregate action; Talamàs and Tamuz (2017) and Galeotti, Golub, and Goyal (2020) consider welfare-maximizing interventions; Bimpikis, Ozdaglar, and Yildiz (2016), Vohra (2020), and Sadler (2020b) consider influencing agents who update their beliefs in a DeGroot fashion. 4Nora and Winter Theoretical Economics 19 (2024) Xu (2009)) and influence maximization (Kempe, Kleinberg, and Tardos (2003)).2Unlike the above papers, we explicitly address coordination problems, adopting the unique implementation approach currently unexplored in the network literature.3 Several network formation models speak to the empirical ubiquity of core-periphery networks. Hojman and Szeidl (2008) derive periphery-sponsored stars as a unique equilibrium of a network formation game where individuals benefit from indirect connections, while Galeotti and Goyal (2010) show that core-periphery networks arise as a consequence of strategic information acquisition and network formation. Belhaj, Bervoets, and Deroïan (2016) show that such networks maximize welfare when agents choose an effort level in a game of strategic complements. Our paper is complementary to this literature highlighting an unexplored property of core-periphery networks.4 The unique implementation approach was pioneered by Segal (1999,2003), who develops a general contracting model, and Winter (2004), who explores incentives provision in organizations. Babaioff, Feldman, Nisan, and Winter (2012), Bernstein and Winter (2012), Halac, Kremer, and Winter (2020), and Halac, Lipnowski, and Rappoport (2021) are prominent papers in this vein. We contribute to this literature by incorporating local externalities captured by a social network. The paper is organized as follows. We begin with the model and an example in Section 2.InSection3, we characterize optimal mechanisms. In Section 4, we compare revenue across networks, while in Section 5we characterize optimal networks. In Section 6, we discuss robustness of our results. All proofs are presented in the Appendix. 2. Model 2.1 Setup There are nindividuals (agents) indexed by i=1, 2, ,n. Each individual idecides whether to act (xi=1), or not (xi=0). Individuals interact through a social network, represented by an undirected graph with a symmetric adjacency matrix G,wheregij =1 if and only if iand jare connected (friends) and gij =0 otherwise; by convention gii =0. We let didenote the number of friends of i, i.e., di=jgij . Individuals are prone to social influence that affects their incentives to take the action; they are encouraged to act when more of their friends do. Specifically, given a network Gandanactionprofilex−i= (x1,,xi−1,xi+1,,xn), we normalize the payoff of individual ifrom abstaining, xi= 0, to zero, i.e., Ui(0, x−i,G)=0, and let the payoff from taking the action, xi=1, be Ui(1, x−i,G)=f(di) j gij xj−ti.(1) 2Atypicalproblemistofindknodes such that if these nodes act, eventually the highest number of other nodes also choose to act. By contrast, we look for a profile of thresholds such that in the unique equilibrium everyone acts and the sum of the thresholds is maximal. 3The literature on network goods uses adoption-contingent prices (Weyl (2010), Masaki (2013)), whereas we study bilateral contracting where transfers are not contingent on actions of others. 4Other notable examples are Bala and Goyal (2000), Goyal and Joshi (2003), Goyal, Van Der Leij, and Moraga-González (2006), König, Tessone, and Zenou (2014), Hiller (2017), and Herskovic and Ramos (2020). Theoretical Economics 19 (2024) Exploiting social influence in networks 5 The term jgij xjis the number of friends of iwhochoosetoact,andf(di)>0captures a social influence exerted on iby each such friend. Hence, the payoff from acting is linearly increasing in the number of friends who act. We call fasocial influence function, and assume that it is nonincreasing in the number of friends of an individual, i.e., f(m)≥ f(m+1)for m≥1. The assumption reflects the idea that someone with more friends is swayed less by each one of them. The term ti≥0 can be viewed as a threshold; an individual chooses to act when her aggregate social benefit from acting, f(di)jgij xj, exceeds her threshold ti. Because f(di)>0, the resulting simultaneous move game with complete information has strategic complementarities, and, typically, there are multiple equilibria. 2.2 External influence Consider the principal who influences individuals by choosing their thresholds. Specifically, we interpret a threshold tias a transfer from individual ito the principal. An influence mechanism is a profile of transfers, i.e., a vector t=(t1,,tn). Because the game between the agents might have multiple equilibrium outcomes, we require that the principal chooses the transfers to induce a unique equilibrium where all agents act. Formally, an influence mechanism tis incentive-inducing (INI) if x=(1, ,1)is a unique Nash equilibrium of the simultaneous move game induced by t. Clearly, such influence mechanisms exist because the principal can make acting a dominant strategy for each agent iby offering ti=0. Moreover, if tis INI, then so is each t<t. However, the principal also wants to maximize the revenue while inducing action. Influence mechanism tis optimal if it has the highest revenue among all INI mechanisms, i.e., ti≥t ifor each INI mechanism5t. The maximal revenue that the principal can achieve while incentivizing all agents to act depends on a social network. Networks that deliver a higher revenue are more attractive to the principal. A network is optimal if its optimal influence mechanism has the highest revenue across all networks. In the remainder of this section, we present an example based on a social influence function naturally arising in certain settings. We use the example to illustrate the construction of optimal influence mechanisms and compare the revenue across networks. Example 1. Consider the case where individuals directly care about a proportion and an absolute number of friends who take the action.6Then the social influence of each such friend on agent iis given by f(di)=α+1 di , 5Note, however, that a set of INI mechanisms is not closed, so an optimal INI mechanism may not exist. Let I∈Rnbe a set of INI mechanisms and ¯ I∈Rnbe its closure. Formally, we say that influence mechanism t∗is optimal if t∗∈arg maxt∈¯ Iti. Hence, although our optimal mechanism t∗may admit multiple equilibria, for every ε>0 there exists an INI mechanisms trevenue from which is only εsmaller, i.e., t∗ i−ε=t i. 6The examples of such situations studied in the literature include models of social comparison (Ghiglino and Goyal (2010)) and conformity (Liu, Patacchini, and Zenou (2014)). For example, Ghiglino and Goyal (2010) discuss two situations, when local aggregate action matters and when local average matters, and provide justification for each case. Both cases are subsumed by our model. 6Nora and Winter Theoretical Economics 19 (2024) Figure 1. Comparing the principal’s revenues across networks. where α≥0 is a constant part of the social influence from an acting friend. When αis small an individual cares mostly about the relative proportion of acting friends, whose number becomes important as αgrows. We begin by illustrating the construction of optimal influence mechanisms in each of the networks in Figure 1and then compare the corresponding revenues. To begin, note that, in any network, the principal must induce at least one of the agents to act even when no one else does (otherwise there will be an equilibrium in which no one acts). Hence, the transfer of one of the agents must be at most zero. Now consider a complete network in panel (a). All agents are symmetric in the network and, therefore, we can let agent 1 pay t1=0. Moreover, one of the remaining agents must pay at most α+1/3; otherwise there is an equilibrium where only agent 1 acts. Again, by symmetry we can let t2=α+1/3. Similarly, to induce one of the two remaining agents to act when both 1 and 2 act, the principal must ask for a transfer of at most 2α+2/3. Let t3=2α+2/3. Finally, agent 4 must pay at most t4=3α+1. In fact, this is an optimal influence mechanism for the complete network with the revenue of 6α+2. Next, consider a line network in panel (b). In an optimal influence mechanism, we let t1=0 to induce agent 1 to act when no one else does. Now to induce 2 to act when only 1 does we let t2=α+1/2. Furthermore, to induce 3 and 4 to act when 1 and 2 do, we let t3=t4=α+1. The corresponding revenue is 3α+5/2. Finally, a star network in panel (c) has an optimal influence mechanism where t1=0andt2=t3=t4=α+1. Note that agent 2 can pay more than in the line network because all her friends now act. The revenue is 3α+3. Two observations are in order. First, note that the principal achieves a higher revenue in the star network than in the line network, regardless of the influence function f. We revisit the example in Section 4, where we introduce and characterize a dominance order on networks with respect to the principal’s revenue. Second, the principal obtains a higher revenue in the complete network if α>1/3, and in the star network if α<1/3. Both graphs belong to a general class of core-periphery networks. In Section 5,weprove our main result that an optimal network is indeed a core-periphery. We also show that the above social influence function results in a “bang bang” solution, where generically either a star or a complete network is optimal. ♦ Theoretical Economics 19 (2024) Exploiting social influence in networks 7 3. Optimal influence mechanisms We begin our investigation by characterizing optimal influence mechanisms for any network. We show that individuals who have more connections than their friends have are asked to pay lower transfers. This allows the principal to exploit their influence by extracting surplus from their friends. Fix a network G. We generalize the construction of the optimal influence mechanisms given in Example 1. We say, an influence mechanism tis tight if it is INI and there does not exist another INI influence mechanism tsuch that for some iwe have ti<t  i and tj=t jfor all j= i.Inwords,iftis tight, then we cannot increase the transfer of any single agent without violating the requirement of the uniqueness of equilibrium where all agents choose to act. Clearly, an optimal influence mechanism is tight. It turns out that there is surjection between a set of permutations of agents and a set of tight influence mechanisms.7 Lemma 1. An influence mechanism t=(t1,,tn)is tight if and only if there exists a permutation πsuch that for all i, ti=f(di) j:π(j)<π(i) gij ,(2) where π(i)denotes a place of iin the permutation π. Given a permutation of agents, we can use (2) to construct a tight influence mechanism. In this mechanism, every agent transfers to the principal the social benefit obtained from her friends that are earlier in the corresponding permutation. Notice that despite the fact that in equilibrium everyone acts, in a tight influence mechanism the principal does not extract the entire social benefit from each agent. For instance, in Example 1a permutation that corresponds to the constructed optimal influence mechanism in a complete network is (1, 2, 3, 4). Here, the transfer of agent 2 is equal to her social benefit from agent 1 acting, i.e., α+1/3. However, her equilibrium social benefit from acting is 3α+1, and so she is left with a surplus of 2α+2/3. Intuitively, a permutation represents an order in which agents iteratively eliminate dominated strategies. Indeed, in any incentive-inducing influence mechanism, there must exist an agent who acts regardless of other agents’ decisions. That is, acting is her dominant strategy. This agent appears first in the permutation, and so her transfer is given by her social benefit when no one else acts, namely zero. Similarly, there must exist one agent for whom acting is a dominant strategy conditional on the first agent acting (otherwise we would have an equilibrium where all agents but the first one stays still). This agent is placed second in the permutation, and pays just as much as is her social benefit given that the first agent is acting, and so on. Hence, for each incentive-inducing mechanism we can inductively construct a corresponding permutation of agents. Given the above lemma, finding an optimal mechanism reduces to a simpler problem of maximizing over permutations. For any permutation π, the revenue in the corre- 7All the proofs are deferred to the Appendix. 8Nora and Winter Theoretical Economics 19 (2024) sponding tight influence mechanism t=(t1,,tn)is  i ti= i f(di) j:π(j)<π(i) gij = ij:π(j)<π(i) gij f(di),(3) where the last line follows from rearranging the summation. Each link in a network contributes a single term to (3). Specifically, consider a link between iand j.Ifπ(j)<π (i), then the link contributes f(di)to (3), and if π(j)>π (i), then the link contributes f(dj). Because fis nonincreasing, the contribution of a link between iand jsuch that di>d j is maximal when π(i)<π (j). Moreover, the contribution depends only on the relative positions of iand jin the permutation, and not on the entire permutation. Call a permutation πof agents nonincreasing if among any two connected agents the one with a strictly higher degree appears earlier in the permutation, i.e., for all agents iand jsuch that gij =1anddi>d j,wehaveπ(i)<π (j). Clearly, the contribution of each link is maximal in every nonincreasing permutation and for a link between iand jit is given by max{f(di),f(dj)}. Hence, we obtain a characterization of an optimal influence mechanism. Proposition 1. Fix a network G. An influence mechanism t=(t1,,tn)is optimal if it is induced by a nonincreasing permutation, i.e., there exists a nonincreasing permutation πof agents such that tis given by (2). Moreover, the revenue in an optimal influence mechanism is given by R(G)= i<j gij maxf(di),f(dj).(4) Intuitively, the principal arranges agents according to their resilience to social influence from others. Well-connected individuals are more resilient in a sense that their incentives to a act increase less when a friend chooses to act compared to their less connected peers. Hence, it is better for the principal to persuade them directly by offering lower transfers, and instead exploit their social influence on their less connected, and hence more easily influenced friends, who are asked to pay higher transfers. This means placing high-degree agents earlier in a permutation. Notice that this is in contrast to arranging agents according to how influential they are. For example, consider a star network in panel (c) of Figure 1. In a case of a constant social influence function f(di)=α, all agents are equally resilient (everyone is influenced in the same way when a friend chooses to act), but agent 1 is clearly the most influential. However, the revenue is the same in each permutation. One interesting observation about the principal’s revenue (4)isthatitisdecomposable as the sum of revenues generated by individual links determined only by the “local” properties of a network, namely agents’ degrees. This means that changing a network structure in one place does not affect the values of remote links. Another observation is that whereas the equilibrium surplus generated by a link between iand jis f(di)+f(dj), Theoretical Economics 19 (2024) Exploiting social influence in networks 15 Figure 4. Networks Gand Gare resilient, while network G is not. section with a glimpse of an opposite question—what are the networks that deliver the lowest revenue? Strategic complementarity implies that an empty network is trivially such a network, and hence we shall fix the number of links. We say a network with E links is resilient if its optimal influence mechanism has the lowest revenue across all networks with Elinks. Note that if f(di)=α, then every network is resilient. Proposition 5. Suppose that fis strictly decreasing and Assumption 2holds. If there exists an integer ssuch that E=s 2, then a resilient network consists of a clique of sagents and n−sisolated agents.16 If there exists an integer ssuch that s 2<E<s+1 2,thena resilient network consists of a connected component of s+1agents and n−s−1isolated agents. Panels (a) and (b) in Figure 4illustrate resilient networks with 6 and 8 links and 6 nodes. When E=s 2for some s, the result pins down a unique network, whereas it provides only a partial characterization when s 2<E<s+1 2for some s. For example, one can show that a network in panel (c) is not resilient under our assumptions. In a resilient network, all the social influence is concentrated inside a tightly interconnected group, and it has as many as possible isolated agents who pay zero transfers. We prove the result by showing that if we could reallocate all the links from the smallest degree agent to others, thus isolating this agent, then we would decrease the revenue. One way to grasp the intuition is to consider a greedy algorithm to construct a network with Elinks, analogous to the algorithm in Section 4. Begin with an empty network. At each step, connect two highest degree agents and terminate when out of links. Thus, at each step the algorithm minimizes the value of a newly created link. When E=s 2for some s, the algorithm generates a clique of sagents as in the proposition above.17 6. Concluding remarks In this section, we briefly discuss the robustness of our results. So far, we assumed that an influence exerted by an agent varies across her friends—popular individuals are influenced less than others. Alternatively, a strength of influence may depend on the characteristics of the influencer and the same individual may be influenced differently by every friend. More generally, agents can be heterogeneous with respect to both, their 16These networks are called the dominant group architecture by Goyal and Joshi (2003). 17Note that the algorithm fails to produce a resilient network if s 2<E<s+1 2. 16 Nora and Winter Theoretical Economics 19 (2024) susceptibility to the influence from others, as well the influence they have on others. Some of our main insights extend to these environments. Given a network Gandanactionprofilex−i=(x1,xi−1,xi+1,,xn),weletthe payoff of individual ifrom taking the action be given by Ui(1, x−i,G)= j gij wij xj−ti,(6) and the payoff from abstaining be Ui(0, x−i,G)=0. Thus, an agent iis influenced by an agent jaccording to a weight wij >0. Apart from the heterogeneous influences represented by a matrix (wij )i,j,themodelisasinSection2. Whereas it is straightforward to confirm that the result analogous to Lemma 1holds, the general model is no longer tractable.18 Instead we discuss several interesting special cases. •Degree-dependent susceptibility:wij =f(di)for each iand jand fis nonincreasing. This is our benchmark model from Section 2. •Degree-dependent influence:wij =f(dj)for each iand jand fis nonincreasing. The interpretation is that an agent splits her effort between influencing each of her friends, and hence someone with more friends will influence each of them less. Optimal mechanisms are obtained from nondecreasing permutations of agents, i.e., permutations where among the two connected agents the one with a strictly higher degree appears later in a permutation. Moreover, the revenue is the same as in the benchmark model (provided the same network and f). Hence, our optimal network result holds.19 •Exogenous influence:wij =ωjfor each iand j. Individuals are heterogeneous with respect to their influence on others, but the level of influence is exogenous. We can interpret it as stemming from public credentials, such as those of political or religious leaders. Because agents can be ordered with respect to their level of influence, an optimal mechanism is characterized by permutations where the influential agents appear earlier. It is clear that in a model where social influence is independent of degree, complete networks are trivially optimal. Appendix Proof of Lemma 1. Given a permutation π,lettbe a corresponding influence mechanism defined by (2). We shall show that tis tight. First, we show that tis INI. Note 18The general model does not admit a characterization of optimal mechanisms analogous to Proposition 1. For example, a natural conjecture would be to order agents with respect to the “influence index” Wi=jgij wji. One can check that the conjecture fails in an example with 3 agents where g12 =g23 =1, g13 =0 and w12 =w31 =1, w21 =w13 =3. Whereas 1 is the most influential, it is optimal to put 3 at the first place in the permutation. 19If fis nondecreasing, then an optimal influence mechanism in a model with degree-dependent susceptibility (influence) is obtained from a nondecreasing (nonincreasing) permutation of agents. Moreover, in both cases an optimal network is complete because there is no trade-off between introducing new connections and diluting the influence of the existing friends. Theoretical Economics 19 (2024) Exploiting social influence in networks 17 that tiis sufficient to induce ito act given that all agents preceding iin πact, no matter what the other agents do. Thus, an agent on the first place in the permutation, π−1(1), acts no matter what the others do. By induction suppose that for k=1, ,n−1agents π−1(1),,π−1(k)act. Then an agent π−1(k+1)also acts. Hence, each agent acts and tis INI. Second, we show that increasing a transfer of any single agent creates an equilibrium where some of the agents do not act. For agent j,let Fj=i|∃j1,,jmsuch that gjj1=gj1j2=···=gjmi=1 and π(j)<π (j1)<···<π (jm)<π (i). If we increase the transfer of agent π−1(n), then she would strictly prefer not to act. Moreover, she strictly prefers not to act if any of her friends do not act. By induction suppose that for k=1, ,n−1, each agent π−1(k+1),,π−1(n)strictly prefers not to act if all her friends following her in πand at least one of her friends preceding her in πdoes not act. If we increase the transfer of agent π−1(k), then there would exist an equilibrium where agent π−1(k)and all agents in Fπ−1(k)do not act, while everyone else does. Therefore, tis tight. Given a tight t, we construct a permutation πsuch that tis given by (2). First, there must exist an agent a1such that ta1=0, otherwise there would exist an equilibrium where no one acts. Let π(a1)=1 and proceed to inductively define π. Suppose that for k=1, ,n−1, each of the agents a1,,akacts if agents with a lower index than theirs act, and correspondingly π(ai)=iand tai≤f(dai)i−1 j=1gaij for i=1, ,k.Then there exists an agent ak+1who weakly prefers to act when a1,,akact and others do not. Otherwise, there would exist an equilibrium where a1,,akact and others do not, contradicting that tis INI. Hence, we must have tak+1≤f(dak+1) k  i=1 gak+1ai.(7) Let π(ak+1)=k+1. If at any step of the induction argument there are several such agents, then pick the one with the lowest index. Moreover, suppose that for k=1, ,n and some agent akwe have that (7) holds with a strict inequality. But then tcannot be tight because by slightly increasing tak, we can increase the revenue while keeping the mechanism INI. Thus, we have established a surjection from a set of permutations to a set of tight influence mechanisms. Proof of Proposition 2. First, we will need the following standard result (Abel’s lemma). Let a1,,an,b1,,bnbe real numbers. Set Ak=k j=1aj.Then n  k=1 akbk= n−1  k=1 Ak(bk−bk+1)+Anbn.(8) 18 Nora and Winter Theoretical Economics 19 (2024) Also,notethatwecanrewrite(4)as R(G)= k lG(k)f(k).(9) Now suppose that k j=1lG(j)≥k j=1lG(j)for each k=1, 2, . We shall show that G dominates G, i.e., R(G)≥R(G)for each nonincreasing f. Using (9), this is equivalent to k[lG(k)−lG(k)]f(k)≥0 for each nonincreasing f.By(8), we get ˆ d  k=1lG(k)−lG(k)f(k)= ˆ d−1  k=1 Akf(k)−f(k+1)+Aˆ df(ˆ d), where Ak=k i=1[lG(i)−lG(i+1)],and ˆ dis the highest degree among the nodes in Gand G. The above expression is nonnegative for each nonincreasing f, because by assumption, Ak≥0 for each k=1, 2,  Suppose that Gdominates G. For the sake of contradiction, suppose that there exists a positive integer ¯ ksuch that ¯ k j=1lG(j)<¯ k j=1lG(j).Takefsuch that f(k)= f(k+1)for each k= ¯ k,andf(¯ k)>f(¯ k+1).Thenwehave ˆ d  k=1lG(k)−lG(k)f(k)=A¯ kf(¯ k)−f(¯ k+1). However, by assumption A¯ k<0, and we obtain the desired contradiction. Proof of Corollary 1. Suppose Gdominates G.Fixh=1, 2, .Notethat h  k=1 lG(k)=E−Hh(G), (10) where Eis the total number of links, which is the same in both networks. Thus, by dominance we have E−Hh(G)≥E−Hh(G), implying that Hh(G)≤Hh(G).LetDh be the sum of degrees of agents with a degree weakly lower than h,whichisalsothe same in both networks. Note that Dh=2Lh(G)+E−Lh(G)−Hh(G) =2LhG+E−LhG−HhG. Combining it with the above, we get Lh(G)≤Lh(G). Finally, if Gis more disassortative than G,thenfrom(10) it immediately follows that Gdominates G. Proof of Corollary 2. For brevity, we consider only the case where there exists an integer ssuch that E=1 2s(s−1)+s(n−s), i.e., the algorithm generates a complete core periphery with sstars. Note that a complete core periphery with sstars maximizes the number of links in a network given that there are n−sagents with degree less than or Theoretical Economics 19 (2024) Exploiting social influence in networks 19 equal to s. Moreover, the maximal number of links is increasing in s.Nowforthesakeof contradiction suppose that a core periphery with sstarsisdominatedbyG, and hence the number of links in Gmust be greater or equal to E. Then by Proposition 2there exists d<n−1suchthatLd(G)+Md(G)>s (n−s)and Ls(G)+Ms(G)≥s(n−s).Let nd(G)denote the number of nodes in Gwith degree higher than d.Fromtheabove,we get nd(G)<s. Hence, the number of links in Gmust be less than E, a contradiction. Proof of Proposition 3 We prove the result with help of four lemmas. Fix an optimal network G. Without loss of generality, assume that if gij =1anddi>d j,theni<j, and hence the identity permutation, id, is nonincreasing and induces an optimal influence mechanism. Let Ni denote a set of friends of agent i, i.e., Ni={j|gij =1}. For a permutation πand an agent i,letNπ,− i⊆Nidenoteasubsetofi’s friends who follow iin permutation π, i.e., Nπ,− i={j|gij =1andπ(j)>π (i)}. We say that agents in Nπ,− iare influenced by i.Let dπ,− i=|Nπ,− i|and dπ,+ i=|Ni\Nπ,− i|.Wecallagentiasink if Nπ,− i=∅. Lemma 2. Fix four different agents i,j,x,andysuch that max{dx,dy}<min{di,dj}.If gix =gjy =1, then either giy =1,orgjx =1,orboth. Proof. For the sake of contradiction, suppose that giy =gjx =0. Consider replacing a link between jand yby a link between iand y. Since the benefits of the two links are the same, the corresponding change in the revenue is given by the change in the cost of a link, given by did,+ if(di)+did,+ jf(dj)−did,+ if(di+1)−did,+ jf(dj−1). Similarly, the change in the revenue from replacing a link between iand xby a link between jand xis did,+ if(di)+did,+ jf(dj)−did,+ if(di−1)−did,+ jf(dj+1). Because Gis optimal, each replacement must weakly decrease the revenue: did,+ if(di)−f(di+1)−did,+ jf(dj−1)−f(dj)≤0, did,+ jf(dj)−f(dj+1)−did,+ if(di−1)−f(di)≤0. Combining the inequalities, we get f(dj)−f(dj+1) f(di−1)−f(di)≤did,+ i did,+ j ≤f(dj−1)−f(dj) f(di)−f(di+1). (11) By convexity, we have f(dj)−f(dj+1)≤f(dj−1)−f(dj), f(di)−f(di+1)≤f(di−1)−f(di), 20 Nora and Winter Theoretical Economics 19 (2024) with equality only when the right-hand sides are zero. Clearly, if at least one right-hand side is not zero, then (11) is inconsistent. Hence, one of the two replacements must strictly decrease total revenue. Alternatively, if both RHSs are zero, then the cost of adding a link between iand yand a link between jand xon top of the existing links is zero, and hence it strictly increases the revenue. Lemma 3. There exists a nonincreasing permutation πof agents such that Nπ,− π−1(1)⊇Nπ,− π−1(2)⊇···⊇Nπ,− π−1(n). (12) Proof. We shall construct a permutation πby inductively defining a permutation πk for 1 ≤k≤nand letting π=πn.Apermutationπkwill satisfy three properties: (i) πk is nonincreasing, (ii) Nπk,− π−1 k(1)⊇Nπk,− π−1 k(2)⊇···⊇Nπk,− π−1 k(k), and (iii) π−1 k(l)=lfor l>k.Begin with an identity permutation id, letting π1=π2=id. Indeed, because agent 1 is the highest degree agent she has zero cost of a link, and thus must be connected to each node, implying that Nid,− 1⊇Nid,− 2. For the induction step, suppose that for 1 ≤k<n there is a permutation πksatisfying the three properties above. We construct a permutation πk+1. Suppose that π−1 k(k)=x. First, we show that either Nπk,− x⊇Nπk,− k+1 or Nπk,− x⊆Nπk,− k+1. For the sake of contradiction, suppose there exist iand jsuch that i∈Nπk,− x,i/∈Nπk,− k+1and j∈Nπk,− k+1,j/∈Nπk,− x.Ifi= k+1, then by Lemma 2we have either gxj =1, or g(k+1)i=1, or both, a contradiction. So, suppose that i=k+1. By the induction assumption, Nπk,− x⊆Nπk,− π−1 k(l)for each l<k, and hence each node that follows and is connected to xis also connected to each node before xin πk.Hence,k+1must have strictly more friends preceding it in πkthan x, i.e., dπk,+ k+1>d πk,+ x.Moreover,ithas a weakly lower degree than xbecause πkis nonincreasing. Now consider replacing a link between k+1andjby a link between xand j. It follows that the revenue must increase because the benefit accrued to jis the same but the cost of a link is lower for xthan for k+1. Therefore, if i=k+1, then Nπk,− x⊇Nπk,− k+1, a contradiction. Thus, we have established that either Nπk,− x⊇Nπk,− k+1or Nπk,− x⊆Nπk,− k+1.NowifNπk,− x⊇Nπk,− k+1, then let πk+1=πk. On the other hand, if Nπk,− x⊆Nπk,− k+1, then define πk+1in the following way. Move xone position further in the permutation, i.e., let π−1 k+1(k+1)=x. Then, by the same argument as above either Nπk,− π−1 k(k−1)⊇Nπk,− k+1or Nπk,− π−1 k(k−1)⊆Nπk,− k+1.If Nπk,− π−1 k(k−1)⊇Nπk,− k+1,thenletπ−1 k+1(k)=k+1, and π−1 k+1(l)=π−1 k(l)for l= k,k+1. On the other hand, suppose that Nπk,− π−1 k(k−1)⊆Nπk,− k+1and π−1 k(k−1)=z.Then,bythesame argument as above, zis not connected to k+1. Now let π−1 k+1(k)=z, and if Nπk,− π−1 k(k−2)⊇ Nπk,− k+1,thenletπ−1 k+1(k−1)=k+1, and π−1 k+1(l)=π−1 k(l)for l= k−1, k,k+1. Continue moving k+1 to the top of the permutation in this way until a set of agents influenced by it is nested in the set of agents influenced by an agent preceding it in πk.Eachstep of the above procedure is well-defined, and in the end, it produces a permutation πk+1 satisfying the properties. Iterating the procedure yields πn, and finally letting π=πnwe obtain the required permutation. Theoretical Economics 19 (2024) Exploiting social influence in networks 21 Lemma 4. If k≤m,then(k+1)f(m+1)−kf (m)is: (i) nonincreasing in k,givenm,and (ii) nondecreasing in m,givenk≥n/2. Proof. Part (i) follows from fbeing a nonincreasing function. To prove (ii) note that by strong convexity, for n/2≤k≤mwe have f(m)−f(m+1)≥f(m+1)−f(m+2)1+1 k. Rewriting, we get f(m+1)−f(m+2)(k+1)≤kf (m)−kf (m+1), (k+1)f(m+1)−kf (m)≤(k+1)f(m+2)−kf (m+1). Lemma 5. Fix a nonincreasing πand agents iand jsuch that di=dj=m,dπ,+ i=dπ,+ j= k.If2k<m,thengij =1. Proof. For the sake of contradiction, suppose that gij =0. Consider the change in the revenue due to adding a link between iand j: kf (m+1)+(k+1)f(m+1)   After adding a link −2kf (m)   Before adding a link . Rewriting, we find that a new link increases the revenue if f(m+1)−2kf(m)−f(m+1)>0. By Assumption 1,wehave f(m+1)−2kf(m)−f(m+1)≥f(m+1)−2k mf(m+1). Hence, the revenue increases when 2k<m, contradicting the optimality of G. Now we are ready to prove Proposition 3. Proof of Proposition 3. Take a nonincreasing permutation πsatisfying (12), and let π−1(k)=skfor k=1, ,n. We show that each nonsink is connected to each sink. First, we show that each sink is connected to the same set of nonsinks. For the sake of contradiction, suppose that xand yare two sinks and nonsink sjconnects to xbut not to y.Thenby(12) each sksuch that k≤jconnects to xand each slsuch that l≥jdoes not connect to y. Hence, there are strictly fewer agents connected to ythan to x, i.e., dx>d y.Moreover,by(12) it follows that each agent connected to yalso connects to x. Then take all agents connected to xand not to y. Removing the links from these agents to xmust decrease the revenue. But then adding the links from these agents to ycreates 22 Nora and Winter Theoretical Economics 19 (2024) the same benefit as adding them to x, but has a lower cost by convexity. Hence, each agent connected to xmust also connect to y, a contradiction. Second, notice that there cannot exist a nonempty set of nonsinks not connected to sinks because the last such agent in πmust be herself a sink. It remains to show that all nonsinks are connected. Let skbe the last nonsink in sequence (s1,s2,,sn). First, we show that sk−1connects to sk. For the sake of contradiction, suppose not. Then Nπ,− sk−1=Nπ,− skand x∈Nπ,− sk−1if and only if xis a sink. Suppose, first, that dsk−1<d sk. Thenbyanargumentsimilartotheabove,thereexists sj,j<k−1, such that sk−1/∈Nπ,− sjand sk∈Nπ,− sj. Take all such agents. By symmetry, adding links between these agents and sk−1reduces the total revenue, because the costs are lower and the benefit is the same as when adding links between these nodes and sk. It follows that sk−1and skare symmetric. Now by Lemma 5,sk−1must be connected to skif dπ,+ sk<d π,− sk,wheredπ,− skis also the number of sinks. Instead suppose that dπ,+ sk−1=dπ,+ sk≥dπ,− sk−1=dπ,− sk.Then dπ,+ sk+dπ,− sk≤n−2, 2dπ,− sk≤n−2, dπ,− sk≤n/2−1, where the second inequality follows from dπ,+ sk≥dπ,− sk. Hence, there are weakly fewer sinks than n/2−1 and, therefore, the in-degree of each sink must be strictly greater than n/2 because it is connected to each nonsink. Take any sink x, and consider the benefit created by a link between sk−1and x.Itisgivenbyd+ xf(dx)−(d+ x−1)f(dx−1). We compare this benefit to the one created by instead connecting sk−1to sk,givenby (d+ sk+1)f(dsk+1)−d+ skf(dsh).Wehave d+ sk+1f(dsk+1)−d+ skf(dsh)>d+ x+1f(dsk+1)−d+ xf(dsh), >d+ x+1f(dx+1)−d+ xf(dx), where the first inequality follows because xconnects to each nonsink, and skis at least not connected with sk−1,andsowehaved+ sk<d + x, and the second inequality follows from Lemma 4because d+ x>n/2anddsk≥dx. Therefore, it is profitable to add a link between sk−1and skinstead of a link between sk−1and x,andthussk−1and skmust be connected. Finally, suppose that nonsink sjand sj+1are not connected, and all nonsinks after j+1 connect to the following nonsinks. The argument above applies, and hence the two nonsinks must be connected. Remaining proofs Proof of Corollary 3. By Proposition 3, an optimal network is a complete core periphery. The revenue in such a network with sstars is s(s−1) 2f(n−1)+(n−s)sf (s). (13) Theoretical Economics 19 (2024) Exploiting social influence in networks 23 Substituting the expression for f, we get a quadratic As2+Bs +n,whereA=1 2(n−1)−α 2 and B=α(n−1 2)−2n−1 2(n−1).Ifα< 1 n−1, then the function is convex and the maximum is achieved either when s=1ors=n−1. Substituting the values, we find that s=1, in other words a star, is optimal. If α> 1 n−1, then the function is concave and is maximized at s∗=− B 2A. Some algebra reveals that s∗is constant in αand is equal to n−1 2.Thus,the maximum in integer values is achieved when s=nor s=n−1, both cases corresponding to a complete network. Finally, when α=1 n−1, then the revenue is independent of s. Proof of Proposition 4.Letfbe flatter than h.Fors=2, 3, ,n−1, we have f(s)=1− s−1  i=1f(i)−f(i+1). Let δs=f(s)−h(s)for s=1, 2, ,n−1.Fromtheabove,weget δs= s−1  i=1h(i)−h(i+1)−f(i)−f(i+1), where each term is positive by assumption. Thus, δs≥0 and is nondecreasing. For f,letGs fdenote the revenue in a complete core periphery with sstars given by (13). We show that Gs f−Gs his nondecreasing in s.Wehave Gs f−Gs h−Gs+1 f−Gs+1 h=s(s−1) 2δn−1+(n−s)sδs −···− (s+1)s 2δn−1−(n−s−1)(s+1)δs+1 =−sδn−1+(n−s)sδs−(n−s−1)(s+1)δs+1 ≤−sδn−1+(n−s)sδs−(n−s−1)(s+1)δs =−sδn−1+(2s−n+1)δs ≤−sδs+(2s−n+1)δs =(s−n+1)δs ≤0. The first two inequalities follow from δsbeing nondecreasing. Finally, fix s∗(h)and consider moving from hto f. From the above, it follows that the revenue in a complete core periphery with s∗(h)stars increases weakly more than in any complete core periphery with fewer stars. Hence, a complete core periphery with fewer stars cannot be optimal under f. Proof of Proposition 5. Suppose that Gis a resilient network with Elinks. Let ibe an agent with the smallest positive degree and Cbe a subset of agents with positive degrees, excluding i. It suffices to show that |C| 2<E. For the sake of contradiction, suppose that E≤|C| 2, and so it is possible to isolate iby sequentially deleting an existing 24 Nora and Winter Theoretical Economics 19 (2024) link between each pair iand j, and replacing it by a link between some pair in C.Consider a link reallocation procedure. At step t,letGtbe the current network and (dt i)n i=1 be the degrees of agents in Gt. At each step t≥1, we conduct one of the two types of link reallocation: 1. If there exists j,k∈Csuch that gt−1 ij =1andgt−1 jk =0, then let gt ij =0, gt jk =1, and gt xy =gt−1 xy for each pair x,ydifferent from i,jor j,k. 2. If there exists j∈Csuch that gt−1 ij =1, but does not exist k∈Csuch that gt−1 jk =0, then take any pair m,l∈Csuch that gt−1 ml =0andletgt ij =0, gt ml =1, and gt xy =gt−1 xy for each pair x,ydifferent from i,jor m,l. The procedure first exhausts all reallocations of type (1) and then of type (2). Initialize at G=G0and terminate if dt−1 i=0. Consider type (1) reallocation at step t. A value of a link between jand kin Gtcannot exceed the value of a link between jand iin G, because type (1) reallocations do not decrease the degrees of agents in C,andthusmin{dt−1 j,dt−1 k}≥di. Moreover, the revenue generated by each other link in Gt−1does not increase in Gtbecause we have increased k’s degree. Consider type (2) reallocation at step t. A value of a link between mand lin Gtcannot exceed the value of a link between jand iin G. Indeed, as mentioned before, type (1) reallocations do not decrease the degrees of agents in C, and type (2) reallocations can decrease a degree only of agents adjacent to i. However, type (2) reallocation decreases the degree of jand increases the degrees of mand l. First, we evaluate the increase in the revenue due to the decrease in j’s degree. Note that agents connected to i in Gt−1have the highest degree in Gt−1equal to |C|.LetSt−1be a set of such agents. Because the degree of jdecreases by one, the revenue generated by each of |St−1|−1 links between agents in St−1\jand jincreases by f(|C|−1)−f(|C|), while the revenue from each other link adjacent to jdoes not change because jremains the highest degree agent in Gt. Hence,wehaveatotalincreaseintherevenueof(|S|−1)[f(|C|−1)−f(|C|)]. Second, we evaluate the decrease in the revenue due to the increases in the degrees of mand l. Consider the revenue generated by each of 2|St−1|links between mand land each h∈St−1. It must decrease by at least f(|C|−2)−f(|C|−1)by convexity, because the highest degree of mand lin Gt−1is |C|−2. Hence, the revenue decreases by at least 2|S|[f(|C|−2)−f(|C|−1)]. Thus, the net change in the revenue after reallocation (2) at step tis negative because 2|S|f|C|−2−f|C|−1>|S|−1f|C|−1−f|C|, by convexity. Therefore, it follows that after each reallocation the total value that links between agents in Ccontribute to the revenue decreases. When the procedure terminates at step T, the value of each reallocated link is not higher in GTthan in G.Therefore, the revenue in GTis not higher than in G.Thus,|C| 2<E. References Arthur, David, Rajeev Motwani, Aneesh Sharma, and Ying Xu (2009), “Pricing strategies for viral marketing on social networks. ArXiv e-prints.” [4]