{'fraction_non_alphanumeric': 0.03537982597157366, 'fraction_numerical': 0.007821072239659088, 'mean_word_length': 4.6061082898219015, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Maximizing the Spread of Stable Influence: Leveraging Norm-driven Moral-Motivation for Green Behavior Change in Networks

In an effort to understand why individuals choose to participate in personally-expensive pro-environmental behaviors, environmental and behavioral economists have examined a moral-motivation model in which the decision to adopt a pro-environmental behavior depends on the society-wide market share of that behavior. An increasing body of practical research on adoption of pro-environmental behavior emphasizes the importance of encouragement from local social contacts and messaging about locally-embraced norms: we respond by extending the moral-motivation model to a social networks setting. We obtain a new decision rule: an individual adopts a pro-environmental behavior if he or she observes a certain threshold of adoption within their local social neighborhood. This gives rise to a concurrent update process which describes adoption of a pro-environmental behavior spreading through a network. The original moral-motivation model corresponds to the special case of our network version in a complete graph. By improving convergence results, we formulate modest-size Integer Programs that accurately (but not efficiently) find minimum-size sets of nodes that convert the entire network, or alternately that maximize long-term adoption in the network given a limited number of nodes which may be temporarily converted. Issues of stability in determining long-term adoption are key. We give hardness of approximation results for these optimization problems. We demonstrate that there exist classes of networks which qualitatively have severely different behavior than the non-networked version, and provide preliminary computational results in in modestly-sized highly-clustered small-world networks related to the famous small-world networks of Watts and Strogatz.


Introduction
Moral-motivation in Environmental and Behavioral Economics. Voluntary participation in personallyexpensive pro-environmental behaviors (like opting-in to pay a higher rate for electricity that is partially supplied by renewable sources like solar and wind) appears illogical under classic economic models. Nevertheless, this option is offered by electric utilities in many parts of the United States, and some members of the public opt to pay the higher rates [19]. While the adoption of some pro-environmental behaviors (like curbside recycling) may be actively encouraged by peer-observation (and corresponding fear of social dis-utility for not conforming-a phenomenon studied under the term "social sanctioning"), adoption of minimally-observable pro-environmental behaviors led environmental and behavioral economists to explore models that include utility derived from "moral motivation." See [19], [21]. These models posit that individuals experience utility when they feel that they are acting in accordance with a virtuous norm. In particular, the moral-motivation model proposes that this utility benefit is non-decreasing in the percentage of adoption society-wide.
Colloquially, we might describe the moral-motivation model as follows: if an individual perceives a personally-expensive (in terms of time, money, etc.) green behavior to be a normal part of good citizenship, then she can effectively be compensated for spending money or time engaging in the green behavior by the satisfaction of being a good citizen. A natural policy question then arises [19]: for settings where moralmotivation applies, how can we best motivate many individuals to adopt green behavior?
The Importance of a Local View. In [19], Nyborg, Howarth and Brekke relax the assumption that individuals have perfect knowledge of society-wide adoption rates, but individuals remain essentially symmetric: knowledge is impacted by stochastic noise, but every member of the society sees the same noisy picture of society-wide adoption rates. In strong contrast, recent studies on attitudes and adoption of emerging greentechnologies and green behavior highlight the importance of normative encouragement from local social contacts and messaging about locally-embraced norms of behavior.
In a qualitative study on consumer attitudes from the Institute of Transportation Studies at U.C. Davis, entitled "Interpersonal influence within car buyer's social networks: applying five perspectives to plug-in hybrid vehicle drivers," Axsen and Kurani [2] examine several frameworks that aim to understand how positive views of plug-in hybrid electric vehicles (PHEVs) are shaped. Eleven families test-drove PHEVs for a 4-6 week period; their perceptions of the usefulness and convenience of the technology and their interactions with social contacts were tracked. Axsen and Kurani highlight "the existence of supportive prosocietal values within the household's social network," as one of three key factors that contribute to a high valuation of the benefits of PHEVs at the end of the trial. This factor is important even when individuals have a technical understanding of the environmental benefits of PHEVs. Axsen and Kurani conclude, "...integrating concepts from contagion, conformity, and reflexivity...this paper points to the importance of: disseminating functional awareness of such technologies, stimulating interpersonal discussion of prosocietal benefits, and marketing to a social network rather than only the individual car buyer." [2] Geographic proximity may also contribute to the local (and thus, spatially heterogeneous) nature of norms about green behavior participation. In a study from the Journal of Consumer Research, entitled, "A Room with a Viewpoint: Using Social Norms to Motivate Environmental Conservation in Hotels," Goldstein, Cialdini and Griskevicius [13] conduct a sizable controlled experiment on how different norm-based messages impact the reuse of towels by hotel guests. Switching from a standard door-hanger message about saving the environment to a message about other hotel guests reusing towels at a high rate resulted in a 26% jump in towel reuse. Replacing a message of the later type with a message that other hotel guests in the same room reused towels at a high rate resulted in a further 15% jump in towel reuse. Goldstein, et al. describe their observations as the activation of a desire to conform to provincial norms: they warn that attempts to market pro-environmental behaviors by appealing to broader demographic categories (e.g. to women) may waste valuable opportunities.
In describing the "environmental morale," of individuals, Frey and Stutzer [11] summarize the "core results" of laboratory experiments on when individuals will provide for the common good despite personal costs. Three of seven such results emphasize the importance of repeated contact with the same people (including face-to-face contact) in determining when individuals will be willing to cooperate.
Our Extension: Network Moral Motivation. Strong empirical evidence suggests that people infer prevailing pro-environmental norms based on the behavior of the people they encounter and engage with, and these norms are adopted in response to both internal motivation and social pressure. We respond by extending the moral-motivation model from [19] to networks in which individual behavior depends on the percentage of adoption among neighbors in the network. Each individual in the network has a threshold: if the percentage of their neighbors that adopt a green behavior is above the threshold, they also adopt the green behavior (this decision rule corresponds to the egoistic benefit of conforming to a virtuous green norm overcoming the other costs associated with that behavior). Our work contributes to the growing exploration in the economic literature of how studied models may be extended to network settings (for example, the extensions of many game-theoretic notions to networks, as in [12] and [3], the latter of which specifically focuses on evaluating how each player-based on network position-impacts the equilibrium outcome). 1 The decision rule described above gives rise to green behavior spreading through the network via a spread mechanism highly similar to the recently-studied notion of complex contagion spreading through a network in the mathematical sociology literature (see the work of Centola et al. [6], [7]). The main modeling difference is that, following the extensive body of work on extending game theory to networks, our model allows each individual to update their adoption status in every time step (decisions to update are concurrent). We also focus on different questions. The work in sociology uses simulation to ask questions about what network properties best propagate a new behavior that arises in a random neighborhood of the network. In contrast, we are interested in planning questions in which a specific social network exists: how can knowledge of this network inform the design of targeted campaigns to spread and normalize proenvironmental behaviors?
The (non-network) moral-motivation model creates a framework with important implications for policies that aim to encourage pro-environmental behavior. In particular, the findings in [19] predict that temporary periods of financial subsidy can cause migration from an equilibrium in which no members of the society adopt the pro-environmental behavior to an equilibrium in which a high percentage of the society adopts the behavior. Once this favorable equilibrium is reached, the society accrues additional environmental benefits associated with widespread pro-environmental behavior. The idea is that a temporary financial subsidy is implemented (so that adopting the pro-environmental behavior gives a utility gain regardless of adoption rates) until some critical level of society-wide adoption is reached. Once the critical level of adoption is reached, the egoistic utility benefit of conforming to the widely-adopted pro-environmental norm is sufficient to guarantee convergence to a high-adoption equilibrium. Without the adoption-percentage-driven moralmotivation benefit, classical models predict that when temporary subsidies are removed, participation in the pro-environmental behavior will disappear.
In parallel with this original work on moral-motivation, we focus on on the policy/planning question in networks where individuals have access to adoption information only among their neighbors. How can understanding moral-motivation in networks allow planners to leverage the boom in emerging information about social networks to create temporary targeted subsidies, or targeted public education campaigns, that normalize pro-environmental behavior? As in the non-network moral-motivation model the goal is to convert the society to a stable "virtuous equilibrium" characterized by high levels of pro-environmental behavior. Stability of this equilibrium after the temporary subsidy lapses again must be enforced by the moral-motivation of individuals, however, in the network setting the issue of stability has become much more complex. Suppose that a particular member of the network is an adopter when the subsidy is in place, but when it lapses, an insufficient number of their neighbors are adopters to convince them to adopt due to moral-motivation alone: when they switch to non-adoption, each of their neighbors will also recompute whether participating in the green behavior gives positive net utility, etc. Effectively, at the end of an intervention period, participation in pro-environmental behavior may be eroded by cascades that domino through the network. The potential for such erosion has been described qualitatively by those interested in persistence of sustainability-oriented policies: "Regulations and economic incentives play an important role in encouraging changes in behavior, but although these may change practices.... Without changes in social norms, people often revert to the old ways when incentives end or regulations are no longer enforced, and so long-term protection may be compromised."-Jules Pretty, 2003, Science [20] To choose a good set of individuals to temporarily subsidize, we must characterize the long-term effect of subsidy. This effect depends on a spatially-heterogeneous pattern of adoption that evolves according to the local update rules we have described above. A technical contribution of this work is proving that the evolving pattern of adoption converges (almost), and rather quickly. There is one notion of temporary subsidy for which the evolution of the process can be cleanly divided into a phase in which adoption is growing and a second phase in which it is eroding. In this setting it is straightforward to prove a bound on convergence time that is linear in the number of individuals in the network. For another natural notion of temporary subsidy in which adoption and erosion of adoption proceed simultaneously, the situation is more complicated. Here we extend results of Goles from the early 80s on the convergence of general threshold automata [14]. Proving a lemma on the monotonicity of the threshold-based updating rule over the adoption vector 2 , and describing a key function in a more intuitive way, we give a convergence bound that is better by a factor of 2 regardless of the network, and that is a arbitrarily-small fraction of the bound from [14] when the average degree is constant and the number of members of the network is large. 3 Significantly, we give an upper bound on the convergence time that is a small linear multiple of the number of edges (or links) in the network (regardless of the degree distribution of nodes in the network). 4 Connections to notions of seeding influence in Computer Science. The spread and "optimal seeding" of influence has been studied extensively in the theoretical computer science literature for spread mechanisms where a single infected contact is enough to cause conversion (see, for example, the canonical work of Kempe, Kleinberg and Tardos [15] that has been cited over 1,400 times). This model has attracted great interest in both academic and industry research communities for its connections to viral marketing; as the body of observable data on how purchases and product valuations flow through networks expands, companies with products to sell and e-advertising space to allocate are eager to learn as much as possible about how to market in this new landscape. Analogously, as Axsen and Kurani suggest, we seek to explore how green behaviors may be marketed: what is fundamentally new about our work is addressing the influence maximization question with a strong notion of local thresholds, and with an emphasis on long term stability of adoption (both considerations essential to an honest extension of the moral-motivation model). 5 Implications for Cost/Benefit Analysis. The moral-motivation model in [19] offers a theoretical foundation compatible with temporary subsidy policies that have already been implemented in practice, and that appear to be succeeding in establishing stable participation in personally-costly pro-environmental behaviors. A motivating example in [19] is a subsidy structure adopted in Oslo, Norway where greener winter-traction tires were subsidized until a fixed level of the population was using the green option, then the subsidy was removed. Prior to subsidy, studded tires were strongly preferred despite the availability of green alternatives: this had resulted in particulate air pollution from road-surface abrasion. The use of studded tires vs. greener traction tires is not visually obvious, so effects of social-sanctioning seem likely to be small. When the subsidy was removed green adoption decreased only slightly, and then seemed to remain stable: the dramatic drop-off classical arguments would predict based on the strong pre-subsidy preference for studded tires was not observed. Further, why would policymakers adopt a plan of this form? The choice of such a subsidy structure seems to indicate that policymakers may already believe that using temporary subsidies to reach high levels of green adoption can have effects beyond the term of the subsidy.
That temporary subsidy may be able to enforce a permanent change in behavior expands the range of policy settings in which subsidy is a rational approach. Subsidy is generally rational when the cost of providing the subsidy annually is outweighed by the benefits that result from the resulting behavior change annually. But if temporary subsidy can be used to cause a permanent shift in behavior, then the cost of imposing the temporary subsidy for some number of years should now be weighed against all benefits accrued during the term of the subsidy and in the future due to the behavior change that results from the temporary subsidy (discounted appropriately). In particular, in settings where moral-motivation is in play, the size of investments in subsidy policies and public education campaigns that are "rational" may be much larger than when the future-benefit of permanent behavior change is ignored.
Environmental economics is deeply concerned with appropriately valuing investments in environmentallysound practices: if the benefits of these investments are under-valued (which may happen frequently in attempts to apply classical metrics for evaluating investment returns created to describe much simpler products), or the estimates of their costs are inflated, societies risk making highly-inefficient choices about allocation of resources.
This paper points out that if decision rules applied by individuals rely on local information, then the level of investment required to reach a virtuous equilibrium may be much less than predicted by the non-network model. There exist classes of networks where taking advantage of the network structure can significantly 5 We note that a few results on a related theme of reversible threshold processes exist in the mathematics literature, but the focus there is on characterizing extremely special classes of networks that exhibit certain properties (for example, that they can be completely converted by a set of a particular size given a particular uniform threshold, etc.) not on optimization of influence within a given network. For example, see [8] or [1]. The discrete math literature has also considered a problem of when iterative local computation in networks (specifically, agreeing with the majority of one's neighbors) will converge to the majority opinion; the focus there is on characterizing a specialized set of networks in which convergence to a homogeneous state that reflects the majority of the initial adoption vector is guaranteed [17]. Again, this work is strongly divorced from our planning perspective. reduce the number of individuals that must be subsidized to reach the high-adoption equilibrium. Thus, the cost to reach the virtuous equilibrium could be much lower than is predicted by the non-network model. As environmental and behavioral economists and sociologists work to understand why individuals adopt pro-environmental behaviors and the body of observable data about social networks continues to explode, leveraging network characteristics in considering the costs and benefits of encouraging behavior change could critically impact cost-benefit analyses used to evaluate important policies.
Model Richness: The emergence of heterogeneous equilibria. In addition to providing an encouraging message about the potential for moral-motivation to act as an ally in stabilizing green equilibria, our network model allows for long-term heterogeneous outcomes in behavioral adoption that are intuitively satisfying in their realism.
Exploring similar issues, the statistical mechanics literature has considered spread mechanisms in random networks where individuals are influenced by trends in adoption among their neighbors; if a highpercentage of their neighbors adopt a behavior, they are very likely to adopt it, etc (e.g. [24], [16]). The widely-studied version in [24] relies on a combination of a mathematically-convenient update rule that individuals periodically choose a random neighbor to emulate, and the assumption that these neighbors are always, in some sense, a representative sample of the society. The process defined gives a random walk which must eventually converge to an adoption pattern that is totally homogeneous: either the entire society participates or no one participates. This model behavior feels suspiciously simplistic, and insights based on such an approach feel brittle (for example, the finding that adding a single intransigent individual to a network-who will never alter their opinion-will unfailingly steer the entire society to their opinion [24]). Concerned with this simplistic equilibrium behavior, recent work of Centola [5] does manage to produce partial-adoption equilibria by assuming a secondary adoption threshold above which the sign of the benefits of adoption becomes negative. Such an assumption seems highly unnatural for describing norm spread.
Similarly, the traditional moral-motivation model from [19] can result in partial-adoption equilibria (that is, a society-wide fraction of adoption that is strictly greater than 0 but strictly less than 1) only by making some individuals more immune to moral-motivation than others: that is, non-adopters are evenly mixed throughout the population, and are precisely those individuals that don't respond to the pressure to conform to norms at modest rates of society-wide adoption.
Our network model, on the other hand, allows stable adoption patterns that are not homogeneous without relying on the moral callousness of all non-adopters: stable pockets of non-adoption may easily occur when certain portions of the network mainly talk to themselves and not to other portions of the network in which adoption is higher. This speaks to the flavor of the famous work of Nowak and May [18] on evolutionary games where introducing a network structure to repeated game play gives rise to persistent spatial heterogeneity. Anecdotal observations of the heterogeneous behavioral norms and locally-normalized values in our society also seem to recommend models of norm formation that are capable of producing a rich set of heterogeneous equilibria.
Observability of Behavior and Diversity of Local Influences. Egoistic moral-utility benefits associated with conforming to locally-embraced green norms could also help to stabilize observable pro-environmental behaviors (like curbside recycling, avoiding littering, purchase of fuel-efficient vehicles, use of public transportation, etc). Further, many anecdotes offered to illustrate social sanctioning have a strong local flavor ("your neighbor judges you for not recycling", etc). If dis-utility experienced by non-adopters is nondecreasing in the fraction of local adoption (a reasonable-seeming hypothesis) then incorporating this effect does not change the form of the function we analyze in the following sections.

The Moral-Motivation Model: Extending to Networks
We first describe the basic moral-motivation model studied in [19], then explain an equivalent thresholdbased decision rule, then extend this decision rule to a network.
In [19], each individual i has a function f i (p) ≥ 0 of the fraction of society-wide adoption p that describes the moral utility benefit they receive for adopting the green behavior. This is a non-decreasing function. 6 See Figure 1 below. The individual may also experience a small environmental-quality benefit β as a result of their green behavior choice (this is specified to be additive in [19]). The sum of these benefits is weighed against the individual cost of adopting the green behavior c. This small environmental benefit β from i adopting is also accrued by all other members of the society. The focus in [19] is to understand behaviors where both • f i (0) + β < c : if no other members of society adopt the green behavior, then individual i will not adopt the green behavior.
• For at least some individuals f i (1) + β > c : at a high rate of adoption at least some individuals will adopt even if they ar not directly subsidized to do so.
A temporary intervention (like a subsidy of value s for adopting green behavior), can be introduced so that Thus, an individual will adopt the green behavior during the subsidy period. At the time the subsidy is removed there is some society-wide adoption rate p : if f i (p ) + β > c then i will continue to engage in the green behavior. Otherwise, i will stop engaging in the green behavior. When the subsidy is discontinued, individuals will repeatedly perform updates based on this decision-rule: some erosion of adoption rate may occur.
In [19], dynamics are studied for the case of uniform f i (·) under the assumption that individuals update in a random order. These assumptions give a system that conforms to replicator dynamics: the convergence rate is proportional to the net benefit associated with adoption. The replicator-dynamics convergence analysis in [19] relies critically on the assumption that, under any current level of adoption, the personal benefit of adoption is identical for every individual.

Moral-Motivation in Networks.
We define an extended model that applies the local decision rule from [19] to each individual in a network.
• Input: A network (or "graph") consisting of nodes and edges, G = (V, E). Each node in V is in one of two states: Green or Brown. We associate the Green state with value 1, and the Brown state with value 0.
Each node i has a critical susceptibility fraction α i . 7 This fraction is the minimal percentage of the neighbors of i that must be Green before i will adopt the green behavior (without being subsidized), namely: Notice that given G and α i , we can immediately obtain a cardinality threshold, b i , for adoption. Let δ(i) denote the set of i's neighbors in G. Then b i = |δ(i)|α i is the minimum number of green neighbors that will ensure i adopts when no subsidy occurs.
• Dynamics: for each time step t, every node i checks how many of his neighbors are Green. If more than b i neighbors of i are Green, i is set to Green in time step t + 1. Otherwise, i is set to Brown in time step t + 1. This update process iterates, giving a binary adoption vector x(t) ∈ {0, 1} |V | that evolves deterministically in time. 8 Figure 2: Adoption in a local neighborhood determines behavior in the next time step. Green adoption in the present time step is indicated by thick green circles. To decide adoption in the next time step, each node checks the percentage of adoption within his set of neighbors. For example, the boxed node will adopt in the next time step if he has threshold α ≤ 0.6.
• Space of Actions: Choose a set of nodes to temporarily subsidize (these nodes will be Green regardless of their neighbors behavior until the subsidy is removed).
• Goal: When the subsidy is removed, the long-term behavior of the adoption vector exhibits a high fraction of green behavior.
In networks, stability of adoption depends on spatial distribution. An important difference between the traditional moral-motivation model and our network version is in the ease of describing the long-term conversion achieved by subsidizing a particular set of nodes. In the traditional model, if the individuals have uniform threshold (α i is constant) the stability of conversion can be determined exactly by whether or not the critical level of adoption has been exceeded during the term of the subsidy. In the network model describing the long-term stability of a subsidy strategy must also consider the spatial distribution of the adopting nodes. A pattern of adoption and the configuration of network connections will together either maintain a high level of green behavior or allow green adoption to slowly erode. This added complexity makes description of the long-term effects of a temporary subsidy significantly more challenging.
Natural notions of temporary subsidy in the network model: • temporary (temp): The planner chooses a set of nodes to subsidize continuously until growth in green adoption stops, then the subsidy is removed.
• fixed-duration (fd): The planner chooses a set of nodes to subsidize for d consecutive time steps, then the subsidy is removed.
When d ≥ |V | we will show that fixed-duration is a special case of temporary. We list these models separately since we will prove much stronger results in the temporary case. For each of these notions of temporary subsidy there are two natural planning problems to consider: What is the smallest number of nodes that can be subsidized to convert the entire network 9 permanently to Green behavior? We consider both tempMCC and fdMCC. 10 Problem 2: Budgeted Maximum Conversion (BMC) Given budget of k nodes to subsidize, what is the maximum percentage of the network that can be permanently converted to Green behavior? We consider both tempBMC and fdBMC.

Summary of Results on Stability, Convergence, and Hardness
For all 4 problem variants, we formulate time-indexed Integer Programs that compute the precise optimal set of seeds for stable green adoption. The correctness of these optimal seed sets depends critically on several theorems we prove about convergence of the evolving adoption vectors (convergence from an arbitrary initial adoption state). For the case of temporary subsidy (temp) we show convergence to a single stable adoption vector. For fixed-duration (fd) subsidy we show convergence to a 2-cycle (in which two adoption vectors -that may be identical-alternate). Further, we prove upper bounds on the number of time steps the adoption vector (which evolves in the exponentially large space {0, 1} |V | ) requires to converge. In the worst case this upper bound is linear in the number of connections (edges) in the network (or equivalently, quadratic in the number of individuals in the network). These upper bounds determine the number of variables in our IP formulations. Applying fast off-the-shelf solvers then allows practically-efficient measurement of optimal seed sets provided that the network (and its resulting IP) is not too large.
Our method of computing optimal sets is not efficient in a rigorous sense 11 (currently, no rigorouslyefficient method for solving general Integer Programs is known). In fact, we prove that no efficient methods to find optimal seed sets exist 12 by reductions from Set Cover and Maximum Coverage Models studied in the computer science theory literature. Further, a significant notion in computer science theory is that beyond proving that an optimal solution for a problem cannot be found by any efficient algorithm, a class of problems may be proved hard to approximate. This formalizes the idea that the class of problems cannot even be solved approximately by an efficient algorithm. Consider a class of problems for which all feasible solutions for any input instance have non-negative value. The following is a widely-embraced definition in the literature (see [23]): 1. An algorithm is a β-approximation if, for every input instance, the algorithm produces in polynomial-time a feasible solution of value at least β times the optimal possible value given the input.
For example, for a maximization problem, an efficient algorithm that always solves a problem perfectly is called a 1-approximation, an efficient algorithm that always returns a solution of value at least 1/2 the optimal value is a (1/2)-approximation, etc. For a minimization problem, an efficient algorithm that always solves a problem perfectly is called a 1-approximation, an efficient algorithm that always returns a solution of cost at most twice the optimal cost is called a (2)-approximation, etc.
The following table summarizes our results on the convergence states, upper bounds on maximum convergence times, and hardness of approximation for the four problem variants.
Results on Stability, Convergence, and Hardness: temporary (temp) fixed-duration (fd) Min-Cost converges to: stable adoption vector converges to: stable adoption vector In the more general fixed-duration subsidy model we give an upperbound on convergence time that is linear in the number of connections (edges) in the network. We note that the average degree in social networks is often bounded by a constant: for such networks all upper bounds given are linear in the number of individuals in the network. We also note that considering a network which is a simple line shows that the best possible upper bound that could exist on adoption vector convergence time is |V |: for social networks, at most a constant factor improvement could be given in the upper bounds we prove. The formal statement of these results and their proofs are included in the appendix.
For Min-cost Complete Conversion, we prove that no efficient algorithm is a O(ln(|V |))-approximation. This is by reduction from the Set Cover problem (shown to be Ω(ln(|V |))-hard to approximate in the work of Feige [9]). For Budgeted Maximum Conversion, we prove that no efficient algorithms achieves more than a (1 − 1 e ) fraction of the optimal value. This is by reduction from the Maximum-Coverage Problem. The details of these reductions can be found in the appendix. These rather daunting hardness results for network Moral-Motivation point out that the well-studied "Linear Threshold Model" of Kempe, Kleinberg, and Tardos (a tangent to the main results from [15]) in the CS theory literature represents an very special case of threshold-based transmission. Kempe, et al. employ a very specialized assumption on the form of uncertainty in threshold values to establish the property of submodularity; this property results in the success of certain approaches to solution construction. Unfortunately, these approaches can fail dramatically for even slight variations on the form of uncertainty.

Contrasts with non-network Moral-motivation
In [19] the authors describe a number of properties of the original moral motivation model. First note that our model generalizes the original moral-motivation model: the non-network model corresponds exactly to the special case of our model where G is a complete graph. 13 How much can the properties of the model vary when the graph is not complete (that is, in our network moral-motivation model)? The answer is that the properties may be dramatically different.
Original Moral-motivation (complete graph G = K |V | ): 1. The long-term adoption rate resulting from a subsidy depends only on the number of individuals subsidized.

2.
When α i is uniform, achieving 100%-adoption requires subsidizing the criticalsusceptibility fraction (α i ) of the entire society. a

3.
When α i is uniform, there are two stable equilibrium: no adoption and 100%-adoption.
Heterogeneous stable equilibria can be obtained only when α i is not uniform.
Network Moral-motivation (general G): 1. The long-term adoption rate resulting from a subsidy depends strongly on its spatial placement in the network.
2. There exist networks with uniform α i in which 100%-adoption can be achieved by subsidizing a vanishingly-small percentage of the critical susceptibility fraction of society.
3. Networks may have many stable heterogeneous equilibria in addition to 2 homogeneous equilibria, even when α i is uniform.

4.
Even when a subsidy set S can achieve 100%-adoption, almost every subsidy set of the size |S| can fail to do so (sometimes miserably).
To make the above statements precise, we demonstrate classes of networks where the properties associated with network moral-motivation depart strongly from the original version. We examine asymptotic classes of examples to illustrate the severity of the departure possible. Later, in Section 5, these extreme departures for pathological networks motivate our exploration of the magnitude of departures for graphs that have been studied as proxies for social networks.
Theorem 3.1. (Moral-motivation in Networks) Two subsidy sets of the same size may have widelydifferent long-term adoption rates. This is true even when the α i are uniform.   • Given any > 0 there exists a network which can be converted to 100% adoption by a set S but where a randomly-selected set of size |S| fails to achieve 100% adoption with probability at least 1 − . This is true even when the α i are required to be uniform.
• When the α i are allowed to be non-uniform, given an additional parameter γ > 0, there exists a network where some subsidy set S gives 100%-adoption, but the expected adoption resulting from a random |S|-size set is < γ.
To prove these theorems we introduce several classes of networks.  Figure 3: Class 1: Resulting cardinality thresholds (b i ) are marked. Subsidizing any single node in the triangle for at least 3 time steps results in 100%adoption, but subsidizing any single node not in the triangle (for any number of time steps) will result in long term adoption strictly less 50%.
Class 1: G is composed of a triangle on three nodes, with two "legs" each containing n nodes (where the first such node in each leg is a common node from the triangle). Let α i = 1/2 for all i ∈ V . See Figure 3.
• Proof of Theorem 3.1: As explained in Figure 3, two subsidy sets of size 1 have widely-different long-term adoption rates for Class 1 (which has uniform α).
• Proof of Theorem 3.2: Regardless of the value of n, a network in Class 1 can be converted to 100% adoption by subsidizing any single node in the triangle for at least three time steps. A network of Class 1 has 2n + 1 nodes. Thus, for any > 0, we can choose n sufficiently large so that 1 < (2n + 1) 1 2 = |V |α. We obtain an infinite class of examples (for n ≥ n ) which satisfy Theorem 3.2.
• Proof of Theorem 3.4 (first half): For a network in Class 1 there are three possible subsidy sets of size 1 which result in 100% adoption if subsidy is maintained for three timesteps. There are 2n − 2 sets of size 1 that result in strictly less than 50% adoption (regardless of how long the subsidy is maintained). Thus, while 100% adoption is achievable by subsidizing a single node, for any > 0, there exists sufficiently large n so that the probability of randomly selecting a single node that achieves 100% adoption is 3/(2n + 1) < .
Class 2: G is composed of a triangle on three nodes, with n "legs" of length 3 attached to a common node of the triangle (the first node of each such leg is the common node in the triangle). All nodes of degree 1 or 2 have α i = 1/2. The node of degree n + 2 has α = 2/(n + 2). See Figure 3 below.  Thus, while 100% adoption is achievable by subsidizing a single node, for any γ > 0, there exists sufficiently large n so that the expected adoption rate achieved by selecting a random set of size 1 is strictly less than γ.

Formulating Integer Programs
In this section we apply our results on convergence states and times to write down Integer Programs that perfectly calculate the optimal set of individuals (nodes) to subsidize. Let δ(i) denote the set of neighbors of i in G. Recall the problem variants from Section 2.
We wish to minimize q subject to the following constraints. First, the number of nodes that are chosen for subsidy is at most q: During the period of the subsidy, a node i is allowed to be an adopter only if either it is subsidized, or if at least b i of its neighbors are adopters during the previous time step. Due to the integrality of the Adoption and Subsidy variables this condition is enforced precisely by the following inequality: From the proof of Lemma 7.2 in the appendix, assuming that the subsidy is maintained for |V | time steps and is then removed gives the same behavior as if subsidy is removed immediately after the first step in which no 0 to 1 conversions occur (that is, assuming subsidy is maintained for |V | time steps perfectly emulates the conditions we defined for temporary subsidy). After the period of subsidy ends, a node i is allowed to be an adopter only if at least b i of its neighbors are adopters during the previous time step: From Lemma 7.3 in the appendix, imposing the above condition for |V | time steps after subsidy is removed ensures that the process will have converged to a stable adoption vector. Forcing the adoption variables for the final time step to 1 ensures we only consider solutions which result in 100% adoption. This is enforced by requiring that for all i ∈ V : x i,2|V | ≥ 1 Combining these constraints we obtain the following IP that computes the smallest subsidy set which permanently converts the entire network.
A technical note: a sequence of adoption variables that constitute a feasible solution for the IP may not perfectly match the evolving adoption vector of the process. In particular, a set of adoption variables may "lag" the true adoption vector: the process effectively turns on (from 0 to 1) a node as soon as possible, while we only require that the IP not turn on (from 0 to 1) a node if it is not justified in doing so (the second and third sets of constraints ensure this). This discrepancy might seem disconcerting for a moment; we might worry that the IP could gain some advantage by lagging the process, and thus produce a subsidy solution that is apparently the best but in fact performs badly with respect to the true adoption-evolution process. The answer to this concern is Theorem 7.1 from the appendix on the monotonicity of the process: when our goal is enlarging the set of adopters, there is never an advantage in delaying turning a node from 0 to 1. The formulation of the IPs for the other 3 problem variants is highly similar (though the form of the constraint sets for the fixed-duration cases depend on the case-specific convergence bounds we prove in the appendix). The three other model formulations (tempBMC, fdMCC, fdBMC) are included in the appendix.

Intransigent Individuals, Weighted Neighbors, Differential Costs of Subsidy
Intransigence: The model can describe intransigent individuals by letting the cardinality threshold, b i , exceed the degree of the node, |δ(i)|. This threatens to make our Min-cost Complete Conversion Problems infeasible: intransigent individuals will clearly violate the constraint that they be adopters in the final time step. By doing a simple iterative search in the network, it is easy (and efficient) to identify a set of nodes that are explicitly intransigent or implicitly intransigent (they are intransigent once all explicitly intransigent nodes are removed from the network, or once other implicitly intransigent nodes are removied, etc). This gives a network of intransigence: the planner can never hope to influence these nodes to adopt without direct indefinite subsidy. Removing the final time step constraint for nodes in this network of intransigence gives a variation of Min-budget Complete Conversion in which we can compute the minimum-size subsidy set that permanently converts all nodes which are not in the network of intransigence.
Weighted Neighbors: Suppose that the adoption of some set of is neighbors is more important to i than the adoption of other sets of is neighbors. We might model this by weighting each neighboring adoption status (0 or 1) by a scalar before comparing to a threshold b i . In particular, when symmetric weights are used to describe homophily of individuals (how alike a pair of individuals are) and weights are chosen from the set of integers {1, 2, ..., k} for some constant k, nearly all our results go through immediately (with somewhat diluted, but still linear, upperbounds on convergence time for the fixed duration case). We mention this in reference to recent work in the mathematical sociology literature on how homophily appears to contribute substantially to increased rates of healthy-behavior transmission in social networks. [4] Differential Costs of Subsidy: None of our convergence or monotonicity results require the cost of subsidizing nodes to be uniform. Trivial alteration of the Integer Programs specified allows perfect computation in the non-uniform case.

Computational Results
The integer programs introduced can be solved for modestly-sized networks using off-the-shelf integerprogramming solvers (we use CPLEX to solve models formulated in the AMPL language). A large space of questions might be explored using these tools. We defer more extensive computational exploration to a later study, and concentrate here on preliminary computational observations related to the asymptotic results in Section 3. Networks that look like social networks. Social Networks are generally characterized by high levels of local density (or high "clustering coefficient" 14 ) in combination with low average shortest-path length between randomly-selected pairs [22]. The canonical work of Watts and Strogatz [22] demonstrated that starting from uniform lattices (rings and square lattices), random "rewiring" of even a small percentage of the edges quickly gives rise to networks with these properties (qualitatively, even a very small percentage of random long ties results in a small-world). Similar rewiring schemes have been used widely in the sociology literature to create test networks to examine the spread of complex contagion (see [6] and [7]).
In this section we describe computational observations for classes of networks with these properties that are composed of dense local communities, which are linked via a random rewiring procedure. Then we computationally investigate analogs of Theorem 3.2 and Theorem 3.4 for these networks.

Dense Local Communities
Random Smaller-world Increasing randomness p=1 p=0 Figure 5: Randomly-rewired clusters. A random-rewiring scheme analogous to that in [22] interpolates between dense local communities (small complete graphs) and a random network. Above, we start with 5 complete graphs each containing 6 nodes. For each edge in the graph we "rewire" it with probability p: the edge is removed from the graph and replaced by a randomly-chosen edge between one of its endpoints and a random node from any community. We do this procedure for every edge in the leftmost figure, eliminating rare duplicate edges when they appear. When p=0 no edges are rewired: this gives the leftmost figure. As p increases, some local ties are replaced by longer random ties, reducing the average path-length between pairs, but maintaining fairly high clustering coefficient. When p=1 the procedure will give a random graph with low clustering coefficient, very low average path length (and closely-preserved average degree).

What percentage of subsidy can convert the whole network?
In Theorem 3.2 we saw that for some highly-pathological classes of networks (with uniform threshold α = 1/2), subsidizing a vanishing fraction of the critical percentage of the network (a vanishing fraction of αn) would be sufficient to convert the entire network to adoption.
Question: Is there a very small subsidy set that converts the entire network for networks that look like real social networks?
Our observations for the rewired-cluster graphs of size 30 (as described in Figure 5) indicate that for a range of p values, giving rise to a range of (clustering coefficient, average path length) pairs, and a range of α values, the optimal size of a set that converts the entire network is less than 1 2 αn. See Figure 6 for a graphical summary over a range of (p, α)-pairs.
When we require that complete adoption in the network is obtained quickly the size of subsidy required increases, but only becomes larger than αn when we insist that complete adoption be reached after only 14 Following [22], the clustering coefficient is defined as follows. For each node v in the graph, look at its set of immediate neighbors (not including itself). Let kv denote the size of this set. The largest number of edges that could exist between two members of this set is kv(kv − 1)/2. Let Cv denote the fraction of these possible edges that actually exist. The clustering coefficient of the graph is the average of Cv over all nodes v.  Figure 6: Smaller subsidies suffice to reach 100% adoption: Unless we require that total adoption be reached very quickly, targeted subsidy of at most 1 2 αn nodes appears to suffice in this parameter range. Each row of the figure shows three runs for a fixed rewiring probability p in the 30-node graph described in Figure 5 (with the clustering coefficient C and average path length L listed for each run at left) for varying values of the threshold level α. one time step of subsidy. Qualitatively, if local-norm spreading is given time to operate, the percentage of subsidy required to reach 100% adoption decreases substantially from what is predicted by the non-network Moral-motivation model of [19].

How much does network-position-based targeting help?
If we had no specific knowledge about the social network, we might optimistically hope that a randomlyplaced subsidy in the network would perform reasonably well compared to the best-targeted subsidy of the same size. Qualitatively, we are hoping that the information deficit (lack of knowledge of the network) is not too costly in terms of the long-term adoption we are able to establish with our subsidy campaign. When thresholds are small, randomly-selected sets of the same size as the optimal seeding set result in 100% long-term adoption. As thresholds increase, the average adoption resulting from a randomly-selected set decreases (though notably, this quantity has high variance, and some randomly-selected sets do result in 100%-adoption). This observation appears to hold for a range of rewiring probabilities, p: for each p the figure shows three randomly-rewired clusters of size 30. For each randomly-rewired cluster, over a range thresholds, the performance of 10 randomly-selected seed sets (of size identical to the optimal seed set for total adoption) is observed.
In Theorem 3.4 we saw that for certain classes of specialized networks, even when a small set exists that converts the entire network, a randomly-selected set of the same size could result in very low expected long-term adoption. Qualitatively, this means that in certain classes of networks, careful targeting gives substantial gains in long-term adoption.
Question: For networks that look like real social networks, if k targeted subsidies are sufficient to convert the entire network, how much adoption results from a randomly-selected k-set?
In Figure 7 we observe that when thresholds are very small, randomly-selected sets perform similarly to the optimal seeding set. However, as thresholds increase (corresponding to when the percentage of local-adoption must be higher in order to surpass the personal cost of the green-behavior) we observe that randomly-located subsidies are substantially less effective on average. That is, the importance of targeting appears to increase as thresholds increase. We note that some randomly-selected sets do perform very well in terms of long-term adoption, though we suspect that how often this happens may be influenced by the number of initial clusters (in this case 5) and the size of the optimal seeding sets (which are relatively small in the examples we observe). For the parameter range we examine though, small sets that result in high long-term adoption do not appear to be highly-rare. We note that the heuristic strategy of randomly selecting many sets of small size and choosing a good one does require knowledge of the social network.
Notice in Figure 7 that the performance of the randomly-selected sets often corresponds to multiples of 6: this is due to green-behavior stabilizing in several local communities but not being able to spread through the rewired ties into the remaining communities.
Comment: We consistently observed that for a fixed network, solve times were much slower for large values of α (where "large" is above 1/2).

Conclusion
To explore how the spread of pro-environmental behaviors can be best encouraged in social networks, we extend the Moral-motivation model from [19] to networks. The green behaviors we are interested in spread in a very different way from disease or information, and motivate a complex optimization problem. To examine natural planning questions about seeding the spread of green-norms, we create a practical computational tool that relies on new results we prove on stability and convergence of an evolving spatially-heterogeneous vector of adoption. For specialized classes of networks, targeting subsidy based on the social network and adoption thresholds yields huge gains over strategies that specify only the size of the subsidized set.
Our computational experiments in networks which replicate the high clustering and small-world path lengths characteristic of real social networks indicate that milder, but still substantial, advantages may be gained by careful subsidy targeting. Targeting subsidies based on knowledge of social-network structure could result in more long-term green adoption, or in substantial reduction in the costs of stabilizing widespread participation in pro-environmental behaviors. The subsidy size required to establish stable societywide adoption is predicted to be much smaller than under the non-network model (at most half the size for the modest examples we explore). Further, in networks that resemble real social networks, the relative advantage of social-network-based targeting appears to increase as thresholds increase. For green behaviors where moral motivation applies, good information about social-network structure and targeted subsidy based on this information may increase the benefits and reduce the costs of subsidy and public education campaigns that aim to establish long-term participation in environmentally-friendly behaviors. A rigorous understanding of the local-norm-driven nature of marketing green adoption could critically impact the future cost/benefit calculations that inform public investment aimed at achieving sustainable practices.
We have just scratched the surface of the computational exploration that is possible with the IP tool we have introduced here. A study on the properties of sets of high-influence with respect to the thresholdbased spread mechanism described here is underway; we expect significant departures from the qualitative properties of sets of high influence under information-spread mechanisms. There are also a number of natural questions on the robustness of seeding strategies to noisy specification of the network, and how stability of high-green-adoption equilibria is threatened by evolving network structure, increasing personal costs of green behaviors, etc.

Appendix: Theoretical Results on Monotonicity and Convergence
In this section we establish several theorems about the Moral-motivation model in networks that will be required in our Integer-Program formulations. A prime issue in the formulation is the convergence time and convergence states of an adoption vector: how many time steps of the update process are necessary in order to describe the long-term adoption rate?
For adoption vector x(t) ∈ {0, 1} |V | , let A x(t) denote the set of indices i for which x i (t) = 1.  The analysis in this section is relatively simple because the growth of adoption (updates from 0 to 1) and erosion of adoption (updates from 1 to 0) are divided cleanly into separate phases. The growth phase occurs while the subsidy is maintained, and the erosion phase begins in the first time step in which subsidy is removed. We explain below. We start with a trivial but useful observation. Suppose that the subsidy is either maintained indefinitely, or has already been removed. If there is a series of 2 time steps in which the adoption vector is unchanged, then it will never change in the future. That is, if x(t) = x(t + 1), then for all T ≥ t, we have x(t) = x(T ).
Lemma 7.2. (Growth Phase) For any set of nodes S ∈ V : if S is subsidized from time 0 until the first time-step g in which no new adoptions occur, then g is at most |V |. Further, if subsidy of S is maintained indefinitely after g (and no additional nodes are subsidized), no new adoptions occur after g.
Proof: While subsidy of S is maintained there is no back-migration from 1 to 0 (recursively, all nodes that convinced any node to adopt are still adopters themselves while the subsidy is maintained). If there is a single step g with no new node adoptions, growth of adoption must be over since the next new adoption that occurs, say in time step q, will be based on adoption vector x(g − 1) just as x(g) was: since x(g) has no new adopters, x(q) will have no new adopters (contradicting the choice of time step q as the next in which a new adoption happens). Thus, since at least one node newly adopts in each time step (starting from time 0), and no back-migration occurs while subsidy of S is maintained, after at most |V | timesteps adoption has stopped increasing. .  − 1), then all future updates will be from 1 to 0, and the adoption vector will converge to a stable adoption vector within |V | time steps.
Proof: Since x(r) = x(r − 1), no future updates from 0 to 1 will occur (as argued in the proof of the previous lemma). In particular, let S denote the set of all non-adopters at time r: all nodes in S will have value 0 in all future time steps. Setting b i = max{δ(i) − b i , 0}: view the process of erosion as a subsidy at nodes in S (to encourage converting to 0) which is maintained indefinitely and spreading via the network moral-motivation model with thresholds b i . The evolving adoption vector that results is exactly identical to the evolution of the adoption vector for the original process. Applying the previous Lemma gives that a time step with no new 1 to 0 updates will occur within |V | time-steps, and that after that time step the adoption vector will never change. .
As a direct consequence of these two lemmas, we obtain: Theorem 7.4. (Convergence for tempMCC, tempBMC, and fd with d ≥ |V |) Consider a subsidy that is maintained for |V | time steps (or until growth in new adoptions stops), and is then removed. A total of 2|V | time steps is sufficient for the adoption vector to converge to a stable equilibrium.  Figure 8: (An alternating cycle of length 2 with average adoption 50%) Here α is uniformly 1/2. Suppose that the planner can subsidize one node for one time step. Subsidizing a node of degree 1 gives long term adoption 0. Subsidizing the central node in time step 1: in time step 2, the central node looks at its neighbors status from time step 1 and thus stops adopting, while each degree-1 node sees that the central node adopted in time step 1 and so adopts in time step 2. In time step 3: each degree-1 node sees that the central node did not adopt in time step 2 and thus decides not to adopt in time step 3, while the central node sees at least 2 neighbors adopted in time step 2 and so adopts in time step 3. Thus, adoption in time step 3 is identical to adoption in time step 1. Since updates are deterministic, the adoption vector is in a cycle of length 2: every odd time step has only the central node adopting, every even time step has all nodes except the central node adopting. Thus, the optimal average adoption is 50%.
It is not immediately clear that a meaningful concept of long-term behavior exists if the adoption vector does not converge. In the example in Figure 7.2, an average rate can be computed because we notice that adoption has entered a small cycle (of length 2), but suppose that this does not happen. Perhaps the adoption vector enters an exponentially-long cycle, or no cycle at all. This would endanger our scheme to optimize the adoption rate with a small Integer Program: the objective function might have exponentially-many terms. Fortunately, the example in Figure 7.2 is in essence as bad as possible: we can always capture the longterm average adoption as an average over two consecutive adoption vectors (provided we wait a sufficient number of time steps before computing this quantity).
Theorem 7.5. (Convergence for fdMCC, fdBMC) If subsidy is removed at time step d, then within 2|E|+ |V | time steps the evolving adoption vector will converge to a cycle of length at most 2.
Next, we explain the proof of this theorem, which requires the proof of a number of intermediate lemmas.
The update rule of our network Moral-Motivation Model is a special case of the general threshold-based update rule Goles analyzed in [14]. We follow Goles analysis closely, but by exploiting the monotonicity of our restricted case, and emphasizing a more combinatorial description of a key function, we give significantly tighter results for our model. Further, we state an explicit bound that is linear in the size of the edge set of the network regardless of degree distribution (whereas [14] states explicit bounds only for uniform-degree networks).
In the following proof we will use the fact (from [14]) that for a set of specified integer cardinality thresholds (our model as described until now) denoted b i for i ∈ V , replacing b i with b i − 0.5 for all i gives an identical update procedure. 15 Thus, without loss of generality, we will assume all thresholds are half-integer. Lemma 7.6. (Adoption enters a cycle [14]) Suppose the subsidy is removed at time d, and the adoption vector evolves according to the update rule. There exists a c with the property that x(t) = x(t + c) = x(t + 2c) = ... and that x(t) is not equal to any of x(t + 1), x(t + 2), ..., x(t + c − 1) for all t above some Transient Time T . Proof: The space of possible adoption vectors, {0, 1} |V | , is finite. Thus, at some time step an adoption vector y must be repeated, and since the update process is deterministic, the behavior from that point forward will be identical to the evolution after the first occurrence of y, giving a cycle. .
We'll define and analyze a special function E(x(t)). In contrast to the analysis in [14], we describe E(x(t)) in terms of the update process in the network. To do this we introduce the idea of sightings. Given an adoption vector y ∈ {0, 1} |V | , we say that node i sights each of its neighbors which is 1 according to y. 16 The expression for E(x(t)) will include two terms related to sightings.
Sightings Necessary to get x(t): If x(t) occurs during our updating process, we can give a bound on how many sightings must have happened in the graph at time t − 1: if i is 1 at t, it must have sighted at least b i neighbors which were 1. Thus, throughout the graph at least sightings must have happened at t − 1. This counts accurately: b i is included exactly when x i (t) is 1.
Sightings wasted in turning on x(t + 1): The adoption vector x(t) produces the next state x(t + 1): each node i that is 1 in x(t + 1) saw at least b i sightings in x(t), but i may also have sighted some extra neighbors at 1 beyond the b i that were required. We say these sightings were wasted in turning on x(t+1). Let A i denote the ith row of the adjacency matrix for G. 17 The number of sightings that were wasted at node i is A i x(t) − b i . So, summing over i: = (Sightings wasted in turning on x(t + 1)) This counts the correct quantity because A i x(t) − b i is included in the sum exactly when x i (t + 1) = 1.
Proof: The proof of this lemma is largely from [14]: we include the details for completeness and because they are critical to explaining the subsequent improvements we make.
In the algebra above: first we make a combined term for all sightings at t by nodes which are 1 at t + 1, next we switch the order of summation: sightings by 1s from t + 1 at x(t) are the same as sightings by 1s from t at x(t + 1) (which is alternately true from A a symmetric matrix), then simply combine terms.
The righthand side sums the following term over all nodes i: If i has the same state in x(t + 2) and x(t) then the term for i has value 0. If x i (t + 2) = 1 and x i (t) = 0: These facts follow from the half-integrality of the b i . In both cases where x i (t + 2) = x i (t), the term for node i contributes at least 1/2 to the value of E(x(t)) − E(x(t + 1)). Since we assumed we are not in a 2-cycle yet (aka that x(t) = x(t + 2)) there must be at least one i that contributes value 1/2.
We can now prove that the evolving adoption vector will converge to a cycle of length at most 2.
Since x(t) = x(t + c), we also have that E(x(t)) = E(x(t + c)). This gives a contradiction. Thus c ≤ 2.
We have already shown in Lemma 7.7 that E(x(t)) decreases in every time step unless the process has converged to its final 2-cycle, so bounding the range of E(x(t)) will give an upper bound on the transient time of the process. This is our general strategy, but to give an improved upper bound, we use the monotonicity of our process (Lemma 7.1) to show that unless the process is already very close to a 2-cycle, the decrease in E(x(t)) is twice as large per time step as specified by Lemma 7.7: Lemma 7.8. Unless the evolving adoption vector is within 2|V | time-steps of entering a 2-cycle, at least 2 nodes i have x i (t) = x i (t + 2), so that E(x(t + 1)) + 1 ≤ E(x(t)).
Proof: Suppose that x(t + 2) differs from x(t) in only one position. We'll show that the adoption vector enters a 2-cycle within 2|V | time steps. Let N x(t) denote the subset of V corresponding to nodes that are at 1 in x(t). Suppose that x i (t + 2) = 1 and x i (t) = 0, and for all other j, x j (t + 2) = x j (t). By definition, N x(t) ⊆ N x(t+2) . We use monotonicity to reason about the set of adopters in following time steps.
Consider N x(t+1) : it results from sightings at N x(t) . Since N x(t) ⊆ N x(t+2) , all sightings at N x(t) happen at N x(t+2) . Thus, N x(t+3) is a superset of N x(t+1) : any node that decided to adopt based on x(t) will certainly adopt based on x(t + 2). By the same rationale, N x(t+5) , etc. This argument holds iteratively. To make this more clear, write the set of adopters in a z-pattern using N x(t) ⇒ N x(t+1) to denote that the set of adopters at time t + 1 results from the set of adopters at time t: · · · · · · · · · Now, add the subset relationships: Since the update process is deterministic, if any of these ⊆ relationships is not proper then the adoption vector has entered a 2-cycle. That is, if N x(t+k) = N x(t+k+2) , then it also must be the case that N x(t+k+1) = N x(t+k+3) , so that for all time steps after t+k the adoption vector alternates between x(t+k) and x(t+k+1). The maximum number of time steps that could elapse before a ⊆ relationship is forced to be non-proper is 2|V |: since all the subsets must be proper, at least one node is in (N x(t+k+2) \N x(t+k) ) for all k. The longest path that could ever be achieved is if N x(t) is the empty set and N x(t+2|V |) is the entire set V . After this many time steps it must be the case that N x(t+k+2) = N x(t+k) : the adoption vector has entered a 2-cycle within 2|V | time steps.
A symmetric argument (with opposite direction of ⊆ relationships) establishes the case where x i (t + 2) = 0 and x i (t) = 1, and for all other j, x j (t + 2) = x j (t). We have established that if x(t + 2) differs from x(t) in only one position the adoption vector will enter a 2-cycle within 2|V | time steps. Equivalently, if the adoption vector is more than 2|V | time steps from entering a 2-cycle, then it must be that if x(t + 2) differs from x(t) in strictly more than 1 position. Thus, evaluating the final expression from the proof of Lemma 7.7: Lemma 7.9. The range of values that E(x(t)) can achieve is ≤ 2|E|.
Recall the definition of E(x(t)): E(x(t)) = (Sightings Necessary to get x(t))-(Sightings wasted in turning on x(t + 1)) From our definitions of necessary and wasted sightings, the first term is always positive (or 0) and the second term is always negative (or 0). Letting the first term be as large as possible, and the second term be as small as possible, we obtain an upper bound on E(x(t)) of |V | i=1 b i (every node in |V | makes the necessary sightings for it to adopt).
An obvious lower bound on E(x(t)) assumes the first term is 0 and makes the second term as large in magnitude as possible (as many wasted sightings as possible at every node): Thus the range of E(x(t)) is at most .
Proof: (Convergence time claimed in Theorem 7.5) We start from the end of the subsidy period. The range of E(x(t)) is at most 2|E| from Lemma 7.9. At most 2|V | steps can decrease E(x(t)) by only 1/2. Every other step must have size at least 1. Thus, there are at most (2|V | + (2|E| − |V |)/1) = 2|E| + |V | time steps after the subsidy is removed before the adoption vector enters a 2-cycle. .
Consider the Set Cover Problem defined as follows. Let S denote a set of elements {1, 2, ..., n}. Let F denote a group of subsets of S which we will denote J 1 , J 2 , ..., J |F | . The objective is to specify the smallest set of indices I so that ∪ i∈I J i = S. Given an instance of the Set Cover Problem, construct an instance of Min-cost Complete Conversion as follows. Construct a graph with three sets of nodes: for each subset J i introduce a subset node called n J i , and for each element q introduce an element node called n q . If element q is in subset J i then add the edge (n q , n J i ) to the graph. Finally, each element node n q has a unique dummy copy called n q and the edge (n q , n q ) is in the graph. See the figure below.  For every element node, let α nq = 1/(|F | + 1). For every subset node, let α n J i = 1 + for some small > 0, and for every dummy node let α n q = 1.
Notice that subset nodes will adopt only when they are directly subsidized. Thus, all element nodes that will ever adopt (for any reason) will do so by the end of the third time step at latest. If any single neighbor of an element node adopts, the element node will also adopt. If an element node and its dummy node are both adopters when subsidy is removed, they will both be permanent adopters.
Given a black-box to solve Min-cost Complete Conversion: we get the smallest set to subsidize that converts all element and dummy nodes permanently after a subsidy of duration d. 18 Call this current optimal subsidy set O. We explain how to find a subsidy set consisting only of subset nodes which has size |O| and converts all element and dummy nodes permanently (within the same duration of subsidy).
Suppose that O contains a dummy node n q . Then the updated set (O ∪ n q )\n q has size at most |O| and converts all element and dummy nodes permanently after a subsidy of duration d. Notice that if |(O ∪ n q )\n q | < |O|, this would contradict the optimality of O. Repeat until all dummy nodes have been removed from O.
Suppose that the updated O contains an element node n q . Since O is the smallest set that permanently converts all element nodes, some subset node that is a neighbor of n q must not be in O (otherwise removing n q from O gives a smaller subsidy set that converts all element and dummy nodes within duration d). Let n J k denote such an unsubsidized neighbor. The alternate subsidy set (O ∪ n J k )\n q has size |O| and converts all element and dummy nodes permanently within duration d. Repeat until all element nodes have been removed from O. Now we have a set of |O| subset nodes that permanently converts all element and dummy nodes. By our construction, this means that the set of subset indices corresponding to our subsidy set has resulting union equal to the entire set of elements S (since an element node adopts precisely when a subset node that is its neighbor is subsidized). Thus, we have a solution of size |O| for the set cover instance.
For the original set cover instance, suppose that a strictly smaller solution for the set cover instance exists. Then subsidizing the corresponding set of subset nodes in our constructed Min-cost Complete Conversion instance would give a subsidy set that permanently converts all element and dummy nodes for any subsidy of length at least 3 time steps (all element nodes would be converted in the second time step, all dummy nodes in the third time step), but has size < |O|. This contradicts the optimality of O for the constructed instance.
Thus, a black-box for Min-cost complete conversion gives a polynomial-time algorithm to solve the set cover instance exactly. Thus Min-cost Complete Conversion (for arbitrary d ≥ 3) inherits Ω(ln(|V |))hardness from the Set Cover Problem (this hardness holds unless NP has slightly superpolynomial time algorithms, see [9] for details).
Consider the Budgeted Maximum-coverage Problem defined as follows. Let S denote a set of elements {1, 2, ..., n}. Let F denote a group of subsets of S which we will denote J 1 , J 2 , ..., J |F | . Given a budget k, the objective is to specify a set of k indices I so that the cardinality of the following union is maximized: Proof. The graph constructed is identical to the previous case. We make the additional observation that for subsidy duration of at least 3 the permanent adoption status of an element node and its dummy are identical (either both are adopters or neither adopts).
Given a black-box to solve Budgeted Maximum Conversion: we get a size-k subsidy set that converts the maximum possible number of (element, dummy)-pairs of nodes permanently after a subsidy of duration d. Call the number of pairs converted h. As in the case above we can produce a subsidy set of the same size which permanently converts an identical set of (element, dummy)-pairs but is composed only of subset nodes. Now we have a set of k subset nodes that permanently converts h (element, dummy)-pairs. By our construction, this means that the set of subset indices corresponding to our subsidy set has resulting union of cardinality h (since an element node adopts precisely when a subset node that is its neighbor is subsidized). Thus, we have a solution of size k with union containing h members of S for the budgeted maximumcoverage instance.
For the original budgeted maximum-coverage instance, suppose that some other solution of size at most k has union of cardinality strictly greater than h. Then subsidizing the corresponding set of subset nodes in our constructed budgeted maximum-conversion instance would give a subsidy set of size at most k which permanently converts strictly more than h (element, dummy)-pairs for any subsidy of length at least 3 time steps (the element nodes of each such pair would be converted in the second time step, the dummy nodes of each such pair in the third time step). This contradicts the optimality of O for the constructed instance.
Thus, a black-box for budgeted maximum conversion gives a polynomial-time algorithm to solve the budgeted maximum coverage instance exactly. Thus budgeted maximum conversion (for arbitrary d ≥ 3) inherits (1 − 1/e)-hardness from the Budgeted Maximum Coverage Problem (this hardness holds unless P=NP, see [9] for details). x it = 1 if node i adopts at time t 0 otherwise The number of nodes chosen for subsidy is at most the given budget k. During the period of the subsidy, a node i is allowed to be an adopter only if either it is subsidized, or if at least b i of its neighbors are adopters during the previous time step. As explained for tempMCC, assuming subsidy is maintained for |V | time steps perfectly emulates the conditions we defined for temporary subsidy. After the period of subsidy ends, a node i is allowed to be an adopter only if at least b i of its neighbors are adopters during the previous time step. As explained for tempMCC, imposing these conditions for |V | time steps ensures that the process will have converged to a stable adoption vector: counting the adopters in the final time step gives the number of long term adopters (precisely the quantity we seek to maximize). For given budget, k, the following IP computes the largest set of long term adopters that can be achieved by the strategy of subsidizing k nodes until growth in adoption has stopped, and then removing all subsidy.

fixed-duration Min-cost Complete Conversion (fdMCC)
Decision Variables: • (Subsidy Variables) for i ∈ V : y i = 1 if node i is subsidized from time step 0 to d 0 otherwise • (Adoption Variables) for i ∈ V, t ∈ {0, 1, 2, ..., (d + 2|E| + |V |)}: x it = 1 if node i adopts at time t 0 otherwise • (Subsidy Size) a dummy variable q describes the size of the subsidized set.
Minimize q subject to the following constraints. The number of nodes chosen for subsidy is at most q. During the period of the subsidy of d time steps, a node i is allowed to be an adopter only if either it is subsidized, or if at least b i of its neighbors are adopters during the previous time step. After the period of subsidy ends, a node i is allowed to be an adopter only if at least b i of its neighbors are adopters during the previous time step. From Theorem 7.5, imposing these conditions for 2|E| + |V | time steps ensures that the process will have converged to a 2-cycle. Forcing the adoption variables for the final time 2 time steps ensures we only consider solutions which result in 100% adoption. For given subsidy duration d, the following IP computes the smallest subsidy set which, when subsidized until growth in adoption stops, permanently converts the entire network.

fixed-duration Budgeted Maximum Conversion (fdBMC)
Decision Variables: • (Subsidy Variables) for i ∈ V : y i = 1 if node i is subsidized from time step 0 to d 0 otherwise • (Adoption Variables) for i ∈ V, t ∈ {0, 1, 2, ..., (d + 2|E| + |V |)}: x it = 1 if node i adopts at time t 0 otherwise The number of nodes chosen for subsidy is at most the given budget k. During the period of the subsidy of d time steps, a node i is allowed to be an adopter only if either it is subsidized, or if at least b i of its neighbors are adopters during the previous time step. After the period of subsidy ends, a node i is allowed to be an adopter only if at least b i of its neighbors are adopters during the previous time step. From Theorem 7.5, imposing these conditions for 2|E| + |V | time steps ensures that the process will have converged to a 2-cycle. Thus, averaging the adoption variables for the final time 2 time steps gives the rate of long term average adoption (the quantity we wish to maximize). For given subsidy duration d, and budget k, the following IP computes the subsidy set which gives the highest long term average adoption rate.