Pairwise Diffusion of Preference Rankings in Social Networks

1 Introduction

The development of models of opinion diffusion in a networked society is important for many reasons: such models enable us to obtain better predictions of electoral results, to maximise the effect of marketing campaigns, or to advance our understanding of the cognitive processes behind social influence. Social scientists have been the first to propose models of belief and opinion diffusion and their simple linear models have been deeply influential [de Groot, 1974; Lehrer and Wagner, 1981]. More complex models developed later on have borrowed heavily from related work in physics and biology [see, e.g., Jackson and Yariv, 2011].

In most of this work, individual opinions are modelled as real numbers or binary views on a given issue. For instance, models initially defined for the study of epidemics have been applied to the propagation of beliefs, by interpreting the likelihood of having a disease as an agent's degree of belief in some proposition. However, opinions can be complex objects that cannot always be accurately modelled by a single number, and this is particularly true for preferences. Indeed, the representation of preferences is a major research topic in Artificial Intelligence in its own right [see, e.g., Rossi et al.,

Edith Elkind

University of Oxford United Kingdom elkind@cs.ox.ac.uk

Umberto Grandi

University of Toulouse France umberto.grandi@irit.fr

2011]. In this paper, we therefore ask how to model the diffusion of structured preference information across a network.

Our starting point is the intuition that agents update their preferences by aggregating the views of the agents they trust. We model this trust relationship by means of a (directed) social network, where each agent trusts her influencers in the network. Furthermore, following standard conventions in voting theory [e.g., Taylor, 2005] we model preferences as linear orders over a set of alternatives. Preferences spread over the network by means of individual agents repeatedly reconsidering pairwise comparisons: an agent picks a pair of alternatives that are ranked one after the other in her preference order, and then compares her opinion on that pair to that of her influencers. If the agent's opinion differs from that of a majority of her influencers, then the pair is swapped. We call this process pairwise preference diffusion, and we study both its synchronous version, in which all agents make these updates simultaneously, and an asynchronous one, where only one agent at a time performs an update.

Our model extends that of Farnoud et al. [2013] who study iterated voting with agents updating their preferences on pairs of alternatives so as to agree with the overall majority. Their work can thus be viewed as a preference diffusion process on a complete network, where each agent is influenced by all members of the system. Our approach generalises their model to arbitrary social networks. We also draw inspiration from a recent line of work in multiagent systems, which studies diffusion processes based on complex representations of individual opinions, grounded in research on belief merging [Schwind et al., 2015] and judgement aggregation [Grandi et al., 2015]. A little further afield, related work modelling individually held points of view as numerical values includes the seminal contributions of Clifford and Sudbury [1973] and Holley and Liggett [1975], as well as more recent studies of linear threshold models [Kempe et al., 2003; 2005] and refinements of the classic voter model [Raghavan et al., 2007; Kearns and Tan, 2008; Hung et al., 2013].

In this paper we identify conditions for a process of preference diffusion in our model to terminate, and we seek to characterise the profiles of preferences the process converges to in case of termination. Our results indicate that outcomes of a diffusion process depend both on the structure of the graph representing the social network and on the properties of the initial profile of preferences. After a review of basic definitions in Section 2, we formally introduce our model in Section 3. Section 4 presents our results on termination, Section 5 those on convergence, and Section 6 concludes. Some proofs are omitted due to space constraints.

2 Preliminaries

Let A be a finite set of alternatives and N = ¶1↪ ▷ ▷ ▷ ↪ n♦ a finite set of agents. The preferences of agents over alternatives are recorded in a preference profile ≻ = (≻1↪ ▷ ▷ ▷ ↪ ≻n), where each ≻i ✓ A ⇥ A is a (strict) linear order over A representing the preferences of agent i. For two distinct alternatives a↪ b 2 A we write a ≻i b if (a↪ b) 2 ≻i, and a 6≻i b if (a↪ b) ◁2 ≻i. Thus, a ≻i b signifies that agent i prefers alternative a to alternative b.

Furthermore, for a 6= b, we let ab denote the unordered pair ¶a↪ b♦. A pair ab is adjacent in ≻i if there is no c 2 A with a ≻i c ≻i b or b ≻i c ≻i a. We will make frequent, often implicit, use of the following folklore result (for a proof, see e.g., the paper of Elkind et al. [2009]).

Lemma 1. Let ≻ and ≻0 be two distinct linear orders on A. Then ≻ and ≻0 must disagree on at least one pair of alternatives that are adjacent in ≻.

We introduce some further notation. In case ab is an adjacent pair in ≻i, let swap(≻i↪ ab) be the linear order resulting from swapping alternatives a and b in ≻i. For instance, if a ≻i b ≻i c and ≻0i = swap(≻i↪ bc), then a ≻0i c ≻0i b. If R is a binary relation on A and a↪ b 2 A, the restriction R↾ab of R on ab is defined as R↾ab = R \ ¶(a↪ b)↪ (b↪ a)♦. If ≻ is a linear order, then ≻↾ab is always a singleton, and if R is asymmetric, then R↾ab is either a singleton or the empty set.

We restrict attention to graphs without self-loops, i.e., we assume (i↪ i) 62 E for all i 2 N. 1 Some of our results apply to specific classes of graphs: directed acyclic graphs (DAGs), the complete graph E = ¶(N ⇥N) ∩ ¶(i↪ i) : i 2 N♦, and simple cycles E = ¶(1↪ 2)↪ (2↪ 3)↪ ▷ ▷ ▷ ↪ (n↪ 1)♦.

Agents are connected by an influence network represented by a directed graph E ✓ N ⇥N. An edge from j to i signifies that agent i is influenced by agent j. We let Inf (i) = ¶j 2 N : (j↪ i) 2 E♦ denote the set of influencers of agent i. We often refer to agents in N as the nodes of the influence network E. A node i such that Inf (i) = ; is called a source, and SE denotes the set of all sources of network E.

3 The Model

In this section, we introduce our model and formally establish some of its basic properties.

3.1 Pairwise Preference Diffusion

Our diffusion model is based on the familiar majority rule. If ≻ is a preference profile and C ✓ N a subset of agents, the (strict) majority relation with respect to C is defined by

1 Thus, we assume that agents do not influence themselves. This simplifies exposition and does not significantly affect our results.

Next, we define the basic update function underlying our diffusion process. Let ≻ be a preference profile, i 2 N, and a↪ b 2 A. The function PPD ("pairwise preference diffusion") is defined as

Thus, a ≻C b if a strict majority of agents in C prefer a to b. Majority relations are asymmetric (a ≻C b implies b 6≻C a), but, in contrast to linear orders, they may have ties and cycles. In the case of a majority tie, i.e., ♣¶i2C : a ≻i b♦♣ = ♣C♣◁2, we have ≻C↾ab = ;. This can only happen if ♣C♣ is even.

Let now turn : N ! 2N ∩ ¶;♦ be a turn function, indicating which individuals in N are updating their preferences at each point in time, and let pair be a randomised procedure that, given a voter in N, outputs a pair of alternatives sampled from A ⇥ A uniformly at random. Starting from a preference profile ≻0 , pairwise preference diffusion (PPD) is the following discrete-time iterative process:

Given a profile, an agent i, and a pair of alternatives ab, the PPD update swaps a and b in ≻i if ab is adjacent in ≻i and a majority of i's influencers disagrees with i on ab. In case of a tie, i.e., when ≻Inf (i)↾ab = ;, i's preferences remain unchanged. 2 Note that PPD takes a profile as its (first) input, but returns only a single preference relation. Nevertheless, we will often speak of the new profile obtained as a result of an update. This is the profile that results from≻ by replacing ≻i with PPD(≻↪ i↪ ab).

An update from≻t to ≻t+1 is called effective if at least one agent performs a swap, i.e., if ≻t+1 6= ≻t . We define two diffusion processes. Under synchronous PPD the turn function is such that turn(t) = N for all t 2 N, i.e., at every step all agents sample (possibly different) pairs of alternatives and update accordingly. Under asynchronous PPD the turn function selects only one agent uniformly at random at every time point t 2 N, i.e., one agent at a time samples a pair of alternatives and updates accordingly. See Figure 1 for an example.

3.2 Termination and Convergence

Both synchronous and asynchronous PPD are discrete-time dynamical processes, and a natural question is whether they terminate. A preference profile ≻ is called stable for E if PPD(≻t ↪ i↪ ab) = ≻ti for all i 2 N and a↪ b 2 A. Note that this definition of stability is independent of the turn function and thus not specific to either synchronous or asynchronous diffusion. Let P[X] denote the probability of event X under PPD. We can now define asymptotic termination.

2 According to the definitions of Farnoud et al. [2013], an adjacent pair ab with a≻i b is swapped if and only if ♣¶i2N : b≻ia♦♣ > ♣¶i2N : a≻ib♦♣. If Inf (i) = N ∩ ¶i♦, the latter is equivalent to b ≻Inf (i) a. Thus, the setting of Farnoud et al. [2013] exactly corresponds to our setting for the special case of a complete graph.

Definition 2. We say that PPD asymptotically terminates on a class of graphs E ✓ 2N 2 if for each graph E 2 E and for each profile of initial preferences ≻0 we have

It will be useful to view PPD as a simple Markov chain, in which the states are all possible preference profiles, and PPD updates define transitions from one state to another. That is, in the case of asynchronous PPD, it is possible to move from state ≻ to a state ≻0 if and only if there exists an agent i and a pair ab such that ≻0i = PPD(≻↪ i↪ ab) and ≻0j = ≻j for all agents j 6= i. For synchronous PPD, we require that for each agent i there is a (possibly different) pair aibi such that ≻0i = PPD(≻↪ i↪ aibi). Transitions between distinct states correspond to effective PPD updates, and absorbing states, i.e., states without effective PPD updates, correspond to stable profiles. In Section 4 we will use the fact that PPD asymptotically terminates if and only if the respective Markov chain is absorbing, i.e., from each state there exists a sequence of PPD updates leading to a stable state [see, e.g., Kemeny and Snell, 1976].

We now define a second, stronger notion of termination.

Definition 3. We say that PPD universally terminates on a class of graphs E if for each graph E 2 E and each preference profile ≻ on E there does not exist an infinite sequence of effective PPD updates starting from ≻.

Intuitively, Definition 3 says that, as long as we keep moving, we are guaranteed to reach a stable state, irrespective of the random choices made by turn and pair. Clearly, universal termination implies asymptotic termination. Next, we establish some further connections between the two concepts.

Lemma 4. If ♣A♣ > 3, then every sequence of asynchronous updates is also a sequence of synchronous updates.

Proof. We show that any asynchronous update can be simulated with a synchronous update. Let ab be the pair that is being swapped during the asynchronous update in ≻i. For each agent j 6= i, we choose a pair that is nonadjacent in ≻j (which is possible since ♣A♣ > 3), and we keep ab as the selected pair for i. Now we have ≻t+1 i = PPD(≻t ↪ i↪ ab) and ≻t+1 j = ≻tj for all j 6= i.

As a direct consequence of Lemma 4, we have the following.

Proposition 5. Let ♣A♣ > 3. If synchronous PPD universally terminates on graph E, then so does asynchronous PPD. If asynchronous PPD asymptotically terminates on E, then so does synchronous PPD.

Proof. Universal termination requires the absence of infinite sequences of effective PPD updates. The claim regarding universal termination thus follows immediately from Lemma 4. Asymptotic termination requires, for every profile ≻, the presence of a sequence of PPD updates from ≻ to a stable state. Lemma 4 thus also establishes the claim regarding asymptotic termination.

We will now introduce further terminology to characterise the profiles encountered at termination. Let a termination profile for ≻0 be a stable profile that is reachable from ≻0 . We say that (asynchronous or synchronous) PPD converges to a unique profile for ≻0 if it terminates when starting from≻0 and all termination profiles for ≻0 coincide. We say that PPD converges to consensus for ≻0 if it terminates when starting from≻0 and all termination profiles ≻⇤ are unanimous, i.e., ≻⇤i = ≻⇤j for all i↪ j 2 N. Observe that we do not require all termination profiles to be equal, thereby allowing for convergence to different consensus profiles.

4 Termination Results

In this section, we investigate how the structure of the influence network affects the termination of PPD.

4.1 Universal Termination

Universal termination is a very strong property, and we show that it can only be obtained by heavily restricting the class of graphs. As noted in Footnote 2, in the special case where the influence network E is a complete graph (without self-loops), our model coincides with the setting of Farnoud et al. [2013], who (implicitly) prove the following.

Proposition 6 (Farnoud et al., 2013). Asynchronous PPD universally terminates on complete graphs.

Simple examples, such as that of two connected agents with opposing preferences a ≻1 b and b ≻2 a, are sufficient to show that synchronous PPD does not universally terminate on complete graphs. However, if we restrict attention to acyclic networks (DAGs), we obtain universal termination for both synchronous and asynchronous PPD.

Proposition 7. Synchronous PPD universally terminates on DAGs.

The proof of Proposition 7 uses a potential function argument similar to that used by Farnoud et al. [2013]. Proposition 7 is tight, because-as we have seen already-synchronous PPD does not even terminate universally on a simple cycle with just two alternatives. Combining Proposition 7 with Proposition 5 we directly obtain the following result.

Corollary 8. Asynchronous PPD universally terminates on DAGs.

4.2 Asymptotic Termination

We now prove an asymptotic termination result for arbitrary networks. We need the following definition.

Definition 9. Let ≻0 be a preference profile and E an influence network. The pair (≻0 ↪E) satisfies the linear local majority property (LLM) if for all profiles ≻ reachable from ≻0 and for all i 2 N the relation ≻Inf (i) is a linear order.

Thus, we require the influence exercised over any agent in the network after any update sequence to be based on a linear order. Profiles satisfying domain restrictions such as those studied in Section 5.1 satisfy LLM on any network.

Theorem 10. Let ≻0 denote the initial preference profile. For ♣A♣ = 2, asynchronous PPD asymptotically terminates on any graph E. For ♣A♣ > 3, asynchronous PPD asymptotically terminates on E when (≻0 ↪ E) satisfies LLM.

Proof sketch. For A = ¶a↪ b♦, we define a two-phase process inspired by an idea of Chierichetti et al. [2013]. In the first phase, we consider all agents i with b ≻i a and a ≻Inf (i) b, and we perform a PPD update on them. We iterate this process until all remaining agents with b ≻i a agree with their influencers. In the second phase, we consider agents j with a ≻j b, and we iteratively update all those that disagree with a majority of their influencers. We claim that this process is guaranteed to reach a stable profile. To see this, let ≻0 and ≻00 denote the profile after the first and after the second phase, respectively. We show that ≻00 is stable.

Now let ♣A♣ > 3, and assume that (≻0 ↪E) satisfies LLM. Fix an arbitrary enumeration p1↪ ▷ ▷ ▷ ↪ p♣A♣(♣A♣-1)◁2 of all unordered pairs of alternatives in A and consider the pairs in this order. Say the first pair is p1 = ab. For this pair, we execute a generalised variant of the two-phase process defined above: In the first phase, we consider all agents i with b ≻i a and a ≻Inf (i) b, and we repeatedly perform PPD updates on agent i until ≻i is identical to ≻Inf (i) (we "copy" the entire relation ≻Inf (i) to agent i). We can do this because ≻Inf (i) is guaranteed to be a linear order by the LLM property. In particular, agent i prefers a to b after such an update. We iterate this process until all remaining agents with b ≻i a agree with their influencers on ab. In the second phase, we consider agents j with a ≻j b and iteratively copy the linear order ≻Inf (j) to agent j whenever b ≻Inf (j) a.

Assume for contradiction that there is an agent i such that ≻00 Inf (i) 6✓ ≻00 i . We distinguish two cases. If a ≻00 i b (and thus b ≻00 Inf (i) a), then ≻i would have been updated at the end of the second phase, a contradiction. If, on the other hand, b ≻00 i a (and thus a ≻00 Inf (i) b), then at every time step during the second phase a majority of i's influencers preferred a to b. Consequently, at the end of the first phase we already had b ≻0i a and a ≻0Inf (i) b. But then ≻i would have been updated to a ≻i b, a contradiction. This proves that ≻00 is stable.

After completing this two-phase process for p1 = ab, we execute the two-phase process for p2, then for p3, and so on. We claim that, after all pairs have been considered, we have reached a stable profile. Say that a pair xy is stable if ≻i↾xy = ≻Inf (i)↾xy for every agent i, and unstable otherwise. If all pairs are stable, the profile itself is stable (but note that the converse does not hold, since there may be unstable pairs in a stable profile, notably non-adjacent ones).

Now let xy be an arbitrary pair. After the two-phase process has completed for xy, we know (by the argument for ♣A♣ = 2) that xy is stable. It remains to show that executing the two-phase process for subsequent pairs does not make xy unstable. But this is true simply because, once a pair is stable, no sequence of asynchronous PPD updates will lead to an agent performing an xy swap. Indeed, suppose that xy is stable and assume for contradiction that there is a sequence of PPD updates that swaps xy for some agent. Let t be the first time that happens, and let i be the agent whose preferences are swapped at time t. The swap can only be caused by some agent in Inf (i) having swapped xy at an earlier time t0 < t, contradicting the minimality of t. Therefore, at the end of the process all pairs are stable and so is the profile.

Proposition 5 implies asymptotic termination of synchronous PPD under the same conditions.

It is not clear whether Theorem 10 remains true when LLM is not satisfied. We leave this as an open problem for future work. A useful corollary of Theorem 10 concerns simple cycles, where LLM trivially holds.

Corollary 11. Asynchronous PPD asymptotically terminates on the class of simple cycles.

Asynchronous PPD does not universally terminate on simple cycles. To see this, take two alternatives a and b, and let all agents on a simple cycle of length n > 3 have preference a ≻i b except for one agent who prefers b to a. This situation allows for an infinite sequence of effective PPD updates, with the preference of the outlier moving around the cycle.

5 Convergence Results

In this section we study the properties of termination profiles. We consider two graph classes: directed acyclic graphs (Section 5.1) and simple cycles (Section 5.2).

Recall that when the influence network is complete, our model is equivalent to the one studied by Farnoud et al. [2013]. They show that, if n is odd, PPD converges to consensus if and only if the majority relation ≻N is acyclic [Farnoud et al., 2013, Theorem 8]. It is straightforward to check that acyclicity of ≻N is neither necessary nor sufficient for convergence to consensus if the network is incomplete (see Figure 2). We first consider DAGs.

5.1 Directed Acyclic Graphs (DAGs)

For an acyclic network E, the sources SE play an important role because their preferences never change. We now study the influence that the preferences of the sources have on the termination profile. In particular, we consider the case where the preferences of the sources are in some sense "aligned," and study whether at termination this will be reflected across the whole network. Such results are important when the diffusion process precedes the aggregation of individual preferences into a collective preference ordering, e.g., when taking a collective decision in an election. We identify conditions under which the asynchronous PPD diffusion process on a DAG with aligned sources leads to termination profiles that can be safely aggregated. 3

The idea of aligned preferences can be formalised by restricting the set of preference relations that can co-occur in a profile, i.e., imposing a domain restriction. A very wellknown example of a domain restriction is single-peakedness. A profile ≻ = (≻1↪ ▷ ▷ ▷ ↪ ≻n) is single-peaked if there exists a linear order / on A, called the axis, such that, for each i 2 N, a / b / c implies that b ≻i a or b ≻i c. Single-peaked preference profiles have many desirable properties. For instance, it is well known that the majority relation ≻N is acyclic (and thus gives rise to weak Condorcet winners) whenever preferences are single-peaked [Black, 1948]. Other well-known restricted domains are those of single-crossing preferences [Mirrlees, 1971; Roberts, 1977] and value-restricted preferences [Sen, 1966; Sen and Pattanaik, 1969] (we omit the definitions due to space constraints; see, e.g., [Gaertner, 2009]); a further (trivial) example is full consensus.

Now, it is straightforward to observe that if the sources form a consensus, i.e., if ≻i = ≻j for all i↪ j 2 SE, then PPD converges to consensus. What we want to show next is that more complex domain restrictions such as single-peakedness similarly spread to the whole network whenever they hold at the source nodes. A simple example shows that this is not possible if there can be majority ties among the influencers of a node (see Figure 3). For this reason, we need to assume that no majority ties occur during the PPD process. This assumption is formalised in the no-tie property.

Definition 12. Let ≻0 be a preference profile and E an influence network. The pair (≻0 ↪E) satisfies the no-tie property if, for all profiles ≻ reachable from ≻0 and for all i 2 N, ≻Inf (i) does not have ties, i.e., ≻Inf (i)↾ab 6= ; for all a 6= b.

The no-tie property generalises a common assumption in social choice theory-that of assuming that the number of a ≻3 c ≻3 b decision-makers is odd-and can be regarded as natural when considering large enough networks.

3 This argument has been used in the literature on deliberative democracy to suggest that deliberation can be an effective process to obtain an "aggregatable" preference profile [see, e.g., Miller, 1992; Knight and Johnson, 1994; Dryzek and List, 2004].

Figure 3: A stable profile ≻ showing that single-peakedness is not propagated when there are ties in ≻Inf (i). Profile ≻ is not single-peaked, even though ≻♣SE is.

Using this assumption, we will show that PPD propagates a number of domain restrictions, including, in particular, single-peakedness, single-crossingness, and valuerestrictedness, to the whole network. We now define three properties a domain restriction may possess.

Definition 13. Let D be a domain restriction.

• ÷ D is closed under subprofiles if, for each profile ≻ satisfying D and for each I ✓ N, the profile ≻♣I = (≻i)i2I satisfies D.
• ÷ D is closed under majority if, for each profile ≻ satisfying D and for each I ✓ N such that ≻I is a linear order, the profile ≻ [ ¶≻I ♦ = (≻1↪ ▷ ▷ ▷ ↪ ≻n↪ ≻I ) satisfies D. 4

We are now ready to show that these properties are sufficient to guarantee PPD propagation from the sources.

• ÷ D satisfies the Condorcet condition if, for each profile ≻ satisfying D, the majority relation ≻N is acyclic.

Proposition 14. Let D be a domain restriction that is closed under subprofiles, closed under majority, and satisfies the Condorcet condition. Let E be a DAG and let ≻0 be a profile such that (≻0 ↪E) satisfies the no-tie property. If ≻0 ↾SE satisfies D, then all profiles at termination satisfy D.

Proof. Let the depth of node i be the length of a longest path from a source to i (this number is finite, as E is a DAG). We proceed by induction on the depth of a node. Nodes of depth zero are sources, so for them our claim is immediate.

Now, consider some d > 0 and assume that our claim is true for profiles formed by preferences of agents in nodes of depth d - 1 or less; we will show that it holds for profiles formed by preferences of agents in nodes of depth d or less. Consider an agent i at depth d and assume that her influencers Inf (i) have stabilised. Note that each node in Inf (i) has depth at most d - 1. Since D is closed under subprofiles and because of the induction hypothesis, the profile ≻♣Inf (i) satisfies D. This in turn implies that the majority relation ≻Inf (i) is a linear order, because (1) D satisfies the Condorcet condition and (2) ≻Inf (i) does not have majority ties due to (≻0 ↪E) satisfying the no-tie property. Thus, Lemma 1 implies that agent i's preference relation will eventually stabilise to ≻Inf (i): as long as agent i disagrees with ≻Inf (i), she will have an adjacent pair she can update. Our claim now follows from the assumption that D is closed under majority.

4 Being closed under majority is a slightly more demanding requirement than the closedness property that is studied by Puppe and Slinko [2015] in the context of Condorcet domains.

The requirements of Proposition 14 are satisfied by the three aforementioned domain restrictions: single-peakedness (SP), single-crossingness (SC), and value-restrictedness (VR).

Corollary 15. Let D 2 ¶SP↪ SC ↪ VR♦. Consider a DAG E and a profile ≻0 such that (≻0 ↪E) satisfies the no-tie property. If ≻0 ↾SE satisfies D, then all profiles at termination satisfy D.

Proof sketch. According to Proposition 14, it suffices to show that all three domain restrictions satisfy the Condorcet condition and are closed under subprofiles and majority.

It is well known that SP, SC, and VR satisfy the Condorcet condition and are closed under subprofiles. The proof that SP is closed under majority can be found, e.g., in Moulin's textbook [Moulin, 2003, Exercise 4.6]. SC is closed under majority because the preferences of the median voter(s) agree with the majority relation (assuming the latter has no ties). Finally, we can show that VR is closed under majority by straightforward case analysis.

Recall that PPD universally terminates on a DAG. A consequence of the results shown above is that if the sources are aligned then PPD converges to a unique profile, which can be computed in polynomial time with a sequence of updates that stabilises each node in increasing order of their depth.

We conclude this discussion of the case of DAGs by stating a result that does not require the no-tie property. The following property is a strengthening of closedness under majority.

Definition 16. A domain restriction D is closed under majority influence if the following holds for all profiles ≻ satisfying D and for all I ✓ N. Let E⇤ be an influence network on ♣I♣ nodes, consisting of ♣I♣ - 1 sources that all influence the single non-source node. Assign the preferences in ≻♣I to the nodes in E⇤ in an arbitrary order. Consider the PPD process on E⇤ and let ≻sink denote the preferences of the non-source node at termination. Then, the profile ≻ [ ¶≻sink ♦ = (≻1↪ ▷ ▷ ▷ ↪ ≻n↪ ≻sink ) also satisfies D.

Whenever the majority relation with respect to the source nodes in E⇤ is a linear order, ≻sink coincides with this order and closedness under majority influence follows from closedness under majority (Definition 13). However, when there are majority ties (or even cycles), then closedness under majority influence is a stronger requirement.

The following result is analogous to Proposition 14, but instead of requiring the no-tie property, we need to start with a network in which the preferences of all nodes, not only those of the sources, satisfy the domain restriction.

Proposition 17. Let D be a restricted domain that satisfies the Condorcet condition and is closed under subprofiles and majority influence. Consider a DAG E and a profile ≻0 . If ≻0 satisfies D, then all profiles at termination satisfy D.

The proof of Proposition 17 is very similar to that of Proposition 14, with closedness under majority influence taking over the roles of closedness under majority and the no-tie property. Proposition 17 applies to single-peaked and to single-crossing preferences.

Lemma 18. SP and SC are closed under majority influence.

Corollary 19. Let D 2 ¶SP↪ SC♦ and let E be a DAG. If ≻0 satisfies D, then all profiles at termination satisfy D.

5.2 Simple Cycles

We now investigate termination profiles for the special case of simple cycles. Lemma 1 implies that, if E is a simple cycle, then all stable profiles (and thus all termination profiles) are unanimous. We are going to characterise the set of linear orders that can be reached as the group consensus.

Clearly, this set contains all linear orders that occur in the initial profile ≻0 , as we can simply "copy" preferences along an influence edge. Also observe that if ≻0 is unanimous on a pair ab, then this unanimity will be preserved throughout the PPD process. We show that, for up to three alternatives, all linear orders that respect such initial unanimities can be obtained at termination.

Proposition 20. For ♣A♣ 6 3, a simple cycle of arbitrary size can converge to any linear order that does not conflict with a unanimously accepted pair in ≻0 (and only to those).

Proof sketch. The claim clearly holds for ♣A♣ 6 2. For A = ¶a↪ b↪ c♦, suppose w.l.o.g. that our goal is to reach consensus on a ≻ b ≻ c. Clearly, this is impossible if one of the comparisons a ≻ b, a ≻ c, or b ≻ c is unanimously rejected. It remains to show that convergence to a ≻ b ≻ c is possible when none of the comparisons a ≻ b, b ≻ c, a ≻ c is unanimously rejected. Consider a greedy algorithm that repeatedly finds an agent i that disagrees with both a ≻ b ≻ c and her influencer on some pair in ¶ab↪ bc↪ ac♦ and updates i's preferences on that pair. This algorithm terminates after at most 3n updates; we show that it always results in consensus on a ≻ b ≻ c. To prove this, we assume for the sake of contradiction that the greedy algorithm gets stuck, and analyse what a "stuck" profile looks like. By enumerating all six possible preference orders an agent might have, we show that any stuck profile consists of the linear orders c ≻ a ≻ b and b ≻ c ≻ a, in an alternating pattern. Both orders have c ≻ a, and hence so do the initial preferences (since the greedy algorithm never reverses a ≻ c), contradicting our assumption that a ≻ c is not unanimously rejected.

While it seems likely that Proposition 20 generalises to more than three alternatives, the proof technique employed above is not applicable to ♣A♣ > 3. We leave this as an open problem.

6 Conclusions

We have introduced a novel model of opinion diffusion on a social network that is tailored to the representation of individual preferences as linear orders over a finite set of alternatives. When prompted to reflect on the relative ordering of a pair of alternatives adjacent in her current preference ranking, an agent will swap them if a majority of her influencers disagree with the current ordering. At what point in time an agent is prompted to do so depends on the diffusion process, which may be synchronous or asynchronous. We have analysed two notions of termination for such processes, universal and asymptotic termination, and we have characterised the profiles of collective preferences at the time of termination for two classes of networks, namely directed acyclic graphs and simple cycles.

Modelling social influence as aggregation of the opinions of an agent's influencers is a simple idea that opens up a number of interesting directions for future investigation. For instance, the field of voting theory provides a huge variety of aggregators that can be explored in this setting. Interesting questions include how to measure and compute the influence of a given agent, and how to efficiently infer properties of a system at the time of convergence when given its initial state.

Acknowledgments

This work has been partly supported by COST Action IC1205 on Computational Social Choice, the Labex CIMI project "Social Choice on Networks" (ANR-11-LABX-0040-CIMI), a Feodor Lynen research fellowship of the Alexander von Humboldt Foundation, and ERC-StG 639945 (ACCORD).