# Iterating influence between players in a social network

Michel Grabisch, Agnieszka Rusinowska

► To cite this version:

Michel Grabisch, Agnieszka Rusinowska. Iterating influence between players in a social network. 2010. halshs-00543840

HAL Id: halshs-00543840

https://shs.hal.science/halshs-00543840

Submitted on 6 Dec 2010

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

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

Iterating influence between players in a social network

Michel GRABISCH, Agnieszka RUSINOWSKA

2010.89

<figure><img src="image_4.png" /></figure>
# Iterating influence between players in a social network*

MICHEL GRABISCH and AGNIESZKA RUSINOWSKA

paris School of Economics
Université Paris I Panthéon-Sorbonne
106-112 Bd de l'Hôpital, 75647 Paris, France
Phone: 0033 144 078 285, Fax: 0033 144 078 301
michel.grabisch@univ-paris1.fr
agnieszka.rusinowska@univ-paris1.fr

**Abstract.** We generalize a yes-no model of influence in a social network with a single step of mutual influence to a framework with iterated influence. Each agent makes an acceptance-rejection decision and has an inclination to say either ‘yes’ or ‘no’. Due to influence by others, an agent’s decision may be different from his original inclination. Such a transformation from the inclinations to the decisions is represented by an influence function. We analyze the decision process in which the mutual influence does not stop after one step but iterates. Any classical influence function can be coded by a stochastic matrix, and a generalization leads to stochastic influence functions. We apply Markov chains theory to the analysis of stochastic binary influence functions. We deliver a general analysis of the convergence of an influence function and then study the convergence of particular influence functions. This model is compared with the Asavathiratham model of influence. We also investigate models based on aggregation functions. In this context, we give a complete description of terminal classes, and show that the only terminal states are the consensus states if all players are weakly essential.

**JEL Classification:** C7, D7

**Keywords:** social network, influence, stochastic influence function, convergence, terminal class, Markov chains, aggregation function

**Corresponding author:** Michel Grabisch

## 1 Introduction

The concepts of interaction and influence on networks are studied in several scientific fields, e.g., in psychology, sociology, economics, mathematics. In the game-theoretical literature, one-step models of influence appeared already more than fifty years ago. For a short survey of cooperative and noncooperative approaches to influence, see, e.g., Grabisch and Rusinowska (2010d). Although the contribution of the one-step interaction models to the analysis of influence issues is significant, it is very important to study dynamic aspects of influence, since in real-life situations we frequently face the iteration of influence. An overview of dynamic models of imitation and social influence is provided, e.g., in Jackson (2008); see also Golub and Jackson (2010).

The present paper deals with iteration of an influence model originally introduced as a one-step influence framework. Before focusing on the model in question, first we survey the literature on dynamic models of interaction and influence.

<footnote>* This research project is supported by the National Agency for Research (Agence Nationale de la Recherche), Reference: ANR-09-BLAN-0321-01.</footnote>
## 1.1 Literature on dynamic models of interaction and influence

One of the leading models of opinion formation has been introduced by DeGroot (1974). In his model, individuals in a society start with initial opinions on a subject. The interaction patterns are described by a stochastic matrix whose entry on row *j* and column *k* represents the weight 'that agent *j* places on the current belief of agent *k* in forming *j*'s belief for the next period'. The beliefs are updated over time. Results in Markov chain theory are easily adapted to the model. Several works in the network literature deal with the DeGroot model and its variations. In particular, Jackson (2008) and Golub and Jackson (2010) examine a model, in which agents communicate in a social network and update their beliefs by repeatedly taking weighted averages of their neighbors' opinions. One of the issues in the DeGroot framework that these authors deal with concerns necessary and sufficient conditions for convergence of the social influence matrix and reaching a consensus; see additionally Berger (1981). Jackson (2008) also examines the speed of convergence of beliefs, and Golub and Jackson (2010) analyze in the context of the DeGroot model whether consensus beliefs are "correct", i.e., whether the beliefs converge to the right probability, expectation, etc. The authors consider a sequence of societies, where each society is strongly connected and convergent, and described by its updating matrix. In each social network of the sequence, the belief of each player converges to the consensus limit belief. There is a true state of nature, and the sequence of networks is wise if the consensus limit belief converges in probability to the true state as the number of societies grows.

Several other generalizations of the DeGroot model can be found in the literature, e.g., models in which the updating of beliefs can vary in time and circumstances; see e.g. DeMarzo et al. (2003), Krause (2000), Lorenz (2005), Friedkin and Johnsen (1990, 1997). In particular, in the model of information transmission and opinion formation by DeMarzo et al. (2003), the agents in a network try to estimate some unknown parameter, which allows updating to vary over time, i.e., an agent may place more or less weight on his own belief over time. The authors study the case of multidimensional opinions, in which each agent has a vector of beliefs. They show that, in fact, the individuals' opinions can often be well approximated by a one-dimensional line, where an agent's position on the line determines his position on all issues. Friedkin and Johnsen (1990, 1997) study a similar framework, in which social attitudes depend on the attitudes of neighbors and evolve over time. In their model, agents start with initial attitudes and then mix in some of their neighbors' recent attitudes with their starting attitudes.

Also other works in sociology related to influence are worth mentioning, e.g., the eigenvector-like notions of centrality and prestige (Katz (1953), Bonacich (1987), Bonacich and Lloyd (2001)), and models of social influence and persuasion by French (1956) and Harary (1959); see also Wasserman and Faust (1994). A sociological model of interactions on networks is also presented in Conlisk (1976); see also Conlisk (1978, 1992) and Lehoczky (1980). Conlisk introduces the interactive Markov chain, in which every entry in a state vector at each time represents the fraction of the population with some attribute. The matrix depends on the current state vector, i.e., the current social structure is taken into account for evolution in sociological dynamics. In Granovetter (1978) threshold models of collective behavior are discussed. These are models in which agents have two alternatives and the costs and benefits of each depend on how many other agents choose which alternative. The author focuses on the effect of the individual thresholds
(i.e., the proportion or number of others that make their decision before a given agent) on the collective behavior, discusses an equilibrium in a process occurring over time and the stability of equilibrium outcomes.

A certain model of influence is studied in Asavathiratham (2000); see also Asavathiratham et al. (2001) and Koster et al. (2010) for related works. The model consists of a network of nodes, each with a status evolving over time. The evolution of the status is according to an internal Markov chain, but transition probabilities depend not only on the current status of the node, but also on the statuses of the neighboring nodes.

Another work on interaction is presented in Hu and Shapley (2003b,a), where authors apply the command structure of Shapley (1994) to model players' interaction relations by simple games. For each player, boss sets and approval sets are introduced, and based on these sets, a simple game called the command game for a player is built. In Hu and Shapley (2003a) the authors introduce an authority distribution over an organization and the (stochastic) power transition matrix, in which an entry in row *j* and column *k* is interpreted as agent *j*'s “power” transfered to *k*. The authority equilibrium equation is defined. In Hu and Shapley (2003a) multi-step commands are considered, where commands can be implemented through command channels.

There is also a numerous literature on social learning, in particular, in the context of social networks; see e.g. Banerjee (1992), Ellison (1993), Ellison and Fudenberg (1993, 1995), Bala and Goyal (1998, 2001), Gale and Kariv (2003), Celen and Kariv (2004), Banerjee and Fudenberg (2004). In general, in social learning models agents observe choices over time and update their beliefs accordingly, which is different from the model analyzed in our paper, where the choices depend on the influence of others.

## 1.2 The present paper

The present paper deals with a framework of influence introduced in Hoede and Bakker (1982) and studied extensively, e.g., in Grabisch and Rusinowska (2009, 2010a,b,c). We consider a social network in which agents (players) may *influence* each others when making decisions. Each agent has an *inclination* to choose one of the actions, but due to influence by others, the *decision* of the agent may be different from his original inclination. Such a transformation from the agents' inclinations to their decisions is represented by an *influence function*. The functions considered so far in our works were deterministic. Moreover, the framework analyzed in the related papers was a decision process after a single step of mutual influence. However, in many real decision processes, the mutual influence does not stop necessarily after one step but may iterate.

The aim of this paper is therefore to refine the model of influence in question and to investigate its generalization in which the influence between players iterates. Any classical influence function can be coded by a stochastic matrix, and an obvious generalization leads to *stochastic influence functions*. We apply Markov chain theory to the analysis of stochastic binary influence functions. Apart from a general analysis of the convergence, we also study the convergence of particular influence functions whose deterministic versions are introduced in Grabisch and Rusinowska (2010a) (majority influence function, guru function, mass psychology function). Moreover, the Confucian example, analyzed, e.g., in Grabisch and Rusinowska (2009, 2010b) as a one-step influence model, is reconsidered in the dynamic framework.
Despite the existence of numerous works on influence, our dynamic model is different from the ones mentioned in Section 1.1. In particular, in our model rows and columns of a stochastic matrix do not correspond to agents, but to a set of ‘yes’-agents. Hence, we consider as a first achievement of our paper the proposition of such a general framework, together with a precise analysis of convergence.

In the second part of the paper, we describe briefly the model of influence introduced in Asavathiratham (2000), where influence is in some sense linear, and show that it can be put into our framework of influence. Moreover, a generalization of this idea gives rise to the wide class of models based on aggregation functions: roughly speaking, the opinion of each agent is obtained as an aggregation (not necessarily linear) of the opinion of the others. It turns out that all examples given in the paper are particular cases of this model. We give a complete description of terminal states and classes in this framework, and give a simple sufficient condition for which the only terminal states are the consensus states. This is the second (and main) achievement of the paper.

The rest of the paper is structured as follows. In Section 2 we briefly present selected basic concepts on directed graphs and Markov chains. Section 3 concerns the point of departure for this research, that is, our one-step model of influence. In Section 4 we investigate the dynamic process of influence in the framework. In Sections 5 and 6 the convergence of several influence functions is studied. In Section 7 we compare our dynamic influence model with the model of influence introduced by Asavathiratham (2000). Section 8 concerns models based on aggregation functions. Section 9 contains some concluding remarks.

## 2 Basic notions on directed graphs and Markov chains

In this section we summarize the basic material on Markov chains needed for our purpose. We refer the reader to standard textbooks, e.g., Seneta (1973), Horn and Johnson (1985), Meyer (2000)) for more details.

We denote vectors by lower-case boldface letters and matrices by upper-case boldface letters, with entries in the corresponding lower case letters. **1** and **0** denote all-ones and all-zeros column vectors of length *n*, respectively.

Let $X = \{x_1, \dots, x_m\}$ be a finite set of states. We consider the $m \times m$ transition matrix $\mathbf{P} = [p_{ij}]_{i,j=1,\dots,m}$, where $p_{ij}$ is the probability that the next state $s(t+1)$ is $x_j$ knowing that the current state $s(t)$ is $x_i$, i.e., $p_{ij} = \text{Prob}(s(t+1) = x_j | s(t) = x_i)$. This matrix is row-stochastic. Let us consider now the row-vector $\mathbf{z}(t) := [z_i]_{i=1,\dots,m}$ of probabilities of each state at time $t$, i.e., $z_i := \text{Prob}(s(t) = x_i)$. We know from Markov chain theory that

$$ \mathbf{z}(t) = \mathbf{z}(t-1)\mathbf{P} = \dots = \mathbf{z}(0)\mathbf{P}^t. \quad (1) $$

To $\mathbf{P}$ we associate its transition directed graph (digraph) $\Gamma$, whose set of nodes is the set of states $X$, and there is a directed edge from $x_i$ to $x_j$ if and only if $p_{ij} > 0$ (then we say that $x_j$ is a successor of $x_i$). A path in $\Gamma$ is a sequence of nodes $x_{j_1}, \dots, x_{j_k}$ such that $x_{j_{i+1}}$ is a successor of $x_{j_i}$ for $l = 1, \dots, k-1$. A cycle is a path for which the first and last nodes coincide, and its length is the number of edges. A (strongly) connected component (called more simply a class) is any subset $S$ of nodes such that there is a path from any node to any other node of $S$, and which is maximal for this property (note that a single node can
be a class). If the graph has only one class (which is then $X$), then the matrix is said to be irreducible. A class is transient if there is an edge going outside it, otherwise the class is said to be recurrent or terminal. The set of all classes $C_1, \dots, C_k$ forms a partition of $X$. A terminal class $C$ is said to be periodic of period $p$ if the greatest common divisor of the length of all cycles in $C$ is $p$. If $p = 1$, we say that the class is aperiodic. When the matrix is irreducible, if its (unique) class is aperiodic, we say that the matrix is aperiodic too. Usually, aperiodic (and therefore irreducible) matrices are called ergodic.

We turn to the study of convergence. We say that $\mathbf{P}$ is convergent if $\lim_{t \to \infty} \mathbf{z}\mathbf{P}^t$ exists for all vectors $\mathbf{z}$ (equivalently, if for any initial vectors $\mathbf{z}(0)$, the limit $\lim_{t \to \infty} \mathbf{z}(t)$ exists. The following situations can happen:

(i) If there is a single aperiodic terminal class (obviously, this is the case for ergodic matrices), the process terminates in this class, and the probability vector $\mathbf{z}^\infty := \lim_{t \to \infty} \mathbf{z}(t)$ of the states in this class is given by solving the eigenvector equation $\mathbf{z}^\infty = \mathbf{z}^\infty \tilde{\mathbf{P}}$, where $\tilde{\mathbf{P}}$ is the submatrix of $\mathbf{P}$ corresponding to the states in the terminal class.

(ii) If the terminal class is periodic of period $p$, $\lim_{t \to \infty} \mathbf{z}(t)$ does not exist. The terminal class $C$ can be partitioned into $p$ subclasses $C_1, \dots, C_p$, so that if at time $t$ the system is in a state in $C_k$, then at time $t+1$ it will be in a state in $C_{k+1}$. However, its Cesaro limit $\lim_{t \to \infty} \frac{1}{t}(\mathbf{z}(1) + \mathbf{z}(2) + \dots + \mathbf{z}(t))$ exists, and is found as above.

(iii) If there are several terminal classes, the process terminates in one of them with some probability which can be computed as follows. First we replace each terminal class by a single terminal state. Then we order the states such that states $x_1, \dots, x_k$ of transient classes are listed first, and then come the terminal states $x_{k+1}, \dots, x_m$. Then the matrix $\mathbf{P}$ takes the following form:

$$ \mathbf{P} = \left[ \frac{\mathbf{Q}|\mathbf{R}}{\mathbf{0}|\mathbf{I}} \right] $$

where the $k \times k$ submatrix $\mathbf{Q}$ gives the probabilities of transition among transient states, the $k \times (m-k)$ matrix $\mathbf{R}$ gives the probabilities of transition from transient states to terminal classes, and $\mathbf{I}$ is the identity matrix of size $m-k$. Let us denote by $\mathbf{\Pi}$ the $k \times (m-k)$ matrix giving the probabilities of reaching one of terminal states from one of the transient states. Then one can prove that

$$ \mathbf{\Pi} = (\mathbf{I} - \mathbf{Q})^{-1}\mathbf{R}, \qquad (2) $$

where $\mathbf{I}$ is now the identity matrix of size $k$.

### 3 The one-step model of influence

We consider a social network with the set of agents (players) denoted by $N := \{1, \dots, n\}$. Each player $j \in N$ has to make a certain acceptance-rejection decision, and he has an inclination (original opinion) $i_j$ to say either ‘yes’ (denoted by +1) or ‘no’ (denoted by -1). An inclination vector denoted by $\mathbf{i}$ is an $n$-vector consisting of ones and minus ones and indicating inclinations of the agents. Let $I := \{-1, +1\}^n$ be the set of all inclination vectors.

It is assumed that agents may influence each others, and due to the influences in the network, the final decision of an agent may be different from his original inclination. In
other words, each inclination vector $\mathbf{i} \in I$ is transformed into a *decision vector* (final opinion after influence) $B(\mathbf{i})$, where $B: I \to I$, $\mathbf{i} \mapsto B(\mathbf{i})$, is the *influence function*. The decision vector $B(\mathbf{i})$ is an $n$-vector consisting of ones and minus ones and indicating the decisions made by all agents. The coordinates of $B(\mathbf{i})$ are denoted by $(B(\mathbf{i}))_j$, $j \in N$.

For convenience, $(1, 1, \dots, 1) \in I$ is denoted by $1_N$, and $(-1, -1, \dots, -1) \in I$ by $-1_N$.

In the paper, we use frequently the equivalent set notation, i.e., by $S \subseteq N$ we denote the set of agents with the inclination to say ‘yes’. Similarly, if $\mathbf{i}$ corresponds to $S$, we denote $B(\mathbf{i})$ by $B(S)$, and $B(S) \subseteq N$ is the set of agents whose decision is ‘yes’. Hence, an influence function can also be seen as a mapping from $2^N$ to $2^N$.

Consequently, any classical influence function $B$ can be coded by a $2^n \times 2^n$ row-stochastic matrix $\mathbf{B} = [b_{S,T}]_{S,T \subseteq N}$ with entries

$$b_{S,T} := \begin{cases} 1, & \text{if } B(S) = T \\ 0, & \text{otherwise} \end{cases}.$$

In other words, for a set $S$ of the yes-inclined agents, if after one step of influence represented by the matrix $\mathbf{B}$ all agents who decide ‘yes’ are the ones in a certain set $T$, then the entry of matrix $\mathbf{B}$ in row $S$ and column $T$ is 1, and the entry in row $S$ and any column different from $T$ is 0.

**Remark 1** In order to write the matrix, one needs to define an order on the subsets of $N$. We propose the binary order, which has the advantage to be recursively defined. Example for $n = 4$

$$[[[[\emptyset], 1], 2, 12], 3, 13, 23, 123], 4, 14, 24, 124, 34, 134, 234, 1234]].$$

An obvious generalization is to define $b_{S,T}$ as the probability that $B(S)$ is $T$, which gives a *stochastic influence function*. In other words, any stochastic influence function $B$ can be coded by a $2^n \times 2^n$ row-stochastic matrix $\mathbf{B} = [b_{S,T}]_{S,T \subseteq N}$ with

$$b_{S,T} := \text{Prob}(B(S) = T)$$

and $\sum_{T \subseteq N} b_{S,T} = 1$ for every $S \subseteq N$.

# 4 The dynamic process of influence

Next, we consider *iteration* of the model of influence recapitulated in Section 3: we suppose that the processus of influence does not stop after one step (e.g., there are several rounds in the discussion). Let us denote by $S(0)$ the set of players with inclination ‘yes’. After influence, the set of ‘yes’ players becomes $S(1) = B(S(0))$, and let us denote by $S(2), \dots, S(k), \dots$ the sequence of sets of ‘yes’ players after successive steps of influence. We make the following fundamental assumption: $S(k)$ *depends only on* $S(k-1)$ and *not on the whole history* $S(0), \dots, S(k-1)$. Moreover, the *influence mechanism does not change with time*. As a consequence, $S(2) = B(S(1)) = B(B(S(0))) =: B^{(2)}(S(0))$, and more generally $S(t) = B^{(t)}(S(0))$.

Switching to the matrix representation of an influence function, we see that $S(k)$ obeys a Markov chain whose set of states is $2^N$ (set of ‘yes’ voters), and $\mathbf{B}$ becomes the
transition matrix of the Markov chain.<fnref n="1" /> Each state $S$, i.e., vertex of the digraph $\Gamma(\mathbf{B})$ of the transition matrix, corresponds in our model to the set of 'yes' agents, and arrows from state $S$ to state $T$ denote a possible transition (with positive probability) from $S$ to $T$.

Let $\mathbf{x}(t)$ denote the probability distribution over the states at time $t \in \mathbb{N}$, i.e., $\mathbf{x}(t)$ is a $2^n$-dim row vector satisfying $\mathbf{x}1 = 1$. The Markovian assumption implies by (1) that $\mathbf{x}(t)$ evolves as follows:

$$ \mathbf{x}(t) = \mathbf{x}(t-1)\mathbf{B} = \mathbf{x}(t-2)\mathbf{B}^2 = \cdots = \mathbf{x}(0)\mathbf{B}^t, $$

where $\mathbf{x}(0)$ is the initial probability distribution.

Applying directly results from Section 2, we can describe the convergence of the process of influence. We summarize below the various situations, and give first a qualitative description, which can be easily obtained from the transition graph $\Gamma(\mathbf{B})$, and a quantitative description obtained from the transition matrix $\mathbf{B}$.

### Description of the convergence conditions from the graph (qualitative):

First, we compute all strongly connected components of the graph (classes), and distinguish between transient and terminal classes. Second, we check if terminal classes are periodic or aperiodic.

- If there is a single aperiodic terminal class, the process will converge in this class. If the class is reduced to a single state, it means that the process will end up in this state with probability 1. Otherwise, there is a limit vector of probabilities to be in the states of this class.

- If there are several terminal aperiodic classes, the process will converge into one of these classes with some probability depending on the initial state.

- If one of the terminal classes is periodic, there is no convergence, and the process will loop into this class.

### Description of the convergence conditions from the matrix (quantitative):

- There is always an eigenvalue of modulus 1 for $\mathbf{B}$. If 1 is an eigenvalue, its multiplicity indicates the number of aperiodic terminal classes.

- If the $d$-root of 1 is an eigenvalue, there is a periodic terminal class of period $d$.

- Assume there is a single terminal class, which is aperiodic (i.e., 1 is a single eigenvalue, and no other eigenvalue has modulus 1). Then the asymptotic probability distribution over states is the vector $\mathbf{x} := \lim_{t \to \infty} \mathbf{x}(t)$ which is a solution of

$$ \mathbf{xB} = \mathbf{x} $$

satisfying $\mathbf{x}1 = 1$. It is independent of the initial probability distribution $\mathbf{x}(0)$.

- Assume there is a single periodic terminal class. Then there is no asymptotic probability distribution over states, but the Cesaro limit $\mathbf{z} := \lim_{t \to \infty} \mathbf{z}(t)$, with

$$ \mathbf{z}(t) = \frac{1}{t}(\mathbf{x}(0) + \mathbf{x}(1) + \cdots + \mathbf{x}(t)) $$

exists and $\mathbf{z}$ is a solution of $\mathbf{zB} = \mathbf{z}$ with $\mathbf{z}1 = 1$.

<footnote n="1">¹ In principle, this is also possible for the discrete case: assuming $m$ actions for each player would lead to a $m^n \times m^n$ matrix. Nevertheless, in this paper we focus on the binary case.</footnote>
# 5 Convergence of selected influence functions

We start with a very simple 2-agent example, and then we iterate several influence functions whose deterministic versions have been introduced originally in the binary one-step model of influence; see Grabisch and Rusinowska (2009, 2010b,a).

## 5.1 Following or being independent?

Let us consider a married couple: husband (agent 1) and wife (agent 2) who have to make regularly their decisions on a certain household issue. They can form different kinds of networks that lead to different decision-making processes. One possibility for each of them is just to remain independent and to follow his or her own inclination, no matter what the inclination of the other side is. Another extreme possibility for making a decision is to follow always the inclination of the other side. In the first case, the decisions are modeled by the identity function $\text{Id}$, and in the second case by the follow function $\text{Fol}$, that are given by

$$ \text{Id}(\mathbf{i}) = \mathbf{i}, \quad \text{Fol}(i_1, i_2) = (i_2, i_1) \quad \text{for any } \mathbf{i} = (i_1, i_2) \in I. $$

The transition matrices are therefore

$$ \mathbf{Id} = \begin{array}{c} \emptyset \\ \begin{bmatrix} 0 & 1 & 2 & 12 \\ 1 & 1 & 1 & 12 \end{bmatrix} \\ \begin{array}{c} 1 \\ 2 \\ 12 \end{array} \end{array} \quad \mathbf{Fol} = \begin{array}{c} \emptyset \\ \begin{bmatrix} 0 & 1 & 2 & 12 \\ 1 & 1 & 1 & 12 \end{bmatrix} \\ \begin{array}{c} 1 \\ 2 \\ 12 \end{array} \end{array} $$

where each “blank” entry means zero. The corresponding graphs are given in Figure 1.

<figure><img src="image_5.png" /><figcaption>**Fig. 1.** The graphs of the identity function $\text{Id}$ (left) and the follow function $\text{Fol}$ (right) for $n = 2$</figcaption></figure>

For the identity case there are four terminal classes ($\emptyset$, 1, 2, and 12), so if both husband and wife are always independent, the convergence occurs immediately. On the other hand, if the couple tries to be “ideal” and each of the two always follows the another one, the graph has a periodic class: the follow function is not convergent.

Another possibility for the couple would be to form a network in which one of them is a *guru*. Such a function for an arbitrary number of agents is presented in the next subsection.

## 5.2 The guru function

It might happen that there is a special influential agent which is followed by everybody.
**Definition 2** Let $n \ge \eta > \lfloor \frac{n}{2} \rfloor$. The majority influence function $\text{Maj}^{[\eta]}$ is defined by

$$ \text{Maj}^{[\eta]}(S) := \begin{cases} N, & \text{if } |S| \ge \eta \\ \emptyset, & \text{if } |S| < \eta \end{cases}, \quad \forall S \subseteq N $$

where $|S|$ denotes the cardinality of $S$.

For instance, the majority function written as a matrix for $n = 3$ and $\eta = 2$ is given by

$$ \text{Maj}^{[2]} = \left[ \begin{array}{c|c} \emptyset & \begin{array}{c} 0 \\ 1 \\ 2 \\ 3 \\ 13 \\ 23 \\ 123 \end{array} \\ \begin{array}{c} 1 \\ 2 \\ 3 \\ 13 \\ 23 \\ 123 \end{array} & \begin{array}{c} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{array} \end{array} \right] $$

The associated graph of such a majority influence function is presented in Figure 3.

<figure><img src="image_6.png" /><figcaption>Fig. 3. The graph of the majority function $\text{Maj}^{[2]}$ for $n = 3$</figcaption></figure>

Obviously, $\emptyset$ and $123$ are terminal classes. Moreover, for the majority function in the general case, we have the following:

**Fact 2** Let $\text{Maj}^{[\eta]}$ be the majority influence function as given in Definition 2. If the initial state $S(0)$ is such that $|S(0)| < \eta$, then the process converges to $\emptyset$ with probability 1. Otherwise, it converges to $N$ with probability 1. The convergence already occurs at $t = 1$.

## 5.4 The stochastic mass psychology function

According to a mass psychology function, if there is a sufficiently high number of agents with inclination $x \in \{+1, -1\}$, then it will possibly influence agents with a $(-x)$ inclination, and some of them will decide $x$, while the others will not change. The majority function $\text{Maj}^{[\eta]}$ is of this type with $x = +1$.
**Definition 3** Let $n \ge \eta > \lfloor \frac{n}{2} \rfloor$, $x \in \{+1, -1\}$, and $\mathbf{i}^x := \{k \in N : i_k = x\}$ for any $\mathbf{i} \in I$. The mass psychology function $\textbf{Mass}^{[\eta]}$ satisfies

$$ \text{if } |\mathbf{i}^x| \ge \eta, \text{ then } (\textbf{Mass}^{[\eta]}(\mathbf{i}))^x \supseteq \mathbf{i}^x. $$

In particular, we can define the stochastic mass psychology function, where a subset of $(-x)$-inclined agents will decide $x$ with a certain probability. For instance, the stochastic mass psychology function (with uniform distribution) ($n = 3, \eta = 2$) is given by the following matrix:

$$ \textbf{Mass}^{[2]} = \begin{bmatrix} \emptyset & 1 & 2 & 12 & 3 & 13 & 23 & 123 \\ \emptyset & 1 & & & & & & \\ 1 & 0.5 & 0.5 & & & & & \\ 2 & 0.5 & 0.5 & & & & & \\ \mathbf{Mass}^{[2]} = 12 & & & 0.5 & & & 0.5 & \\ 3 & 0.5 & & & 0.5 & & & \\ 13 & & & & & 0.5 & 0.5 & \\ 23 & & & & & & 0.5 & 0.5 \\ 123 & & & & & & & 1 \end{bmatrix} $$

where again a “blank” entry means zero. The associated graph is given in Figure 4.

<figure><img src="image_7.png" /><figcaption>**Fig. 4.** The graph of the stochastic mass psychology function $\textbf{Mass}^{[2]}$ for $n = 3$</figcaption></figure>

Similarly, $\emptyset$ and 123 are terminal classes. For the stochastic mass psychology function in the general case, with $n > 3$ and $\eta > \lfloor \frac{n}{2} \rfloor$, we have the following:

**Fact 3** Let $\textbf{Mass}^{[\eta]}$ be the mass psychology function with $n > 3$ and $\eta > \lfloor \frac{n}{2} \rfloor$. If the initial state $S(0)$ satisfies $|S(0)| \ge \eta$, then it converges to $N$ with probability 1 (under some mild conditions on the transition matrix). If $|S(0)| \le n - \eta$, then it converges to $\emptyset$ with probability 1. In all other cases, nothing can be said in general.
# 6 The Confucian model

Let us consider the Confucian model of society; see Hu and Shapley (2003a) and Grabisch and Rusinowska (2009, 2010b). We analyze a small four-member society $N = \{1, 2, 3, 4\}$, which consists of the king = agent 1, the man = agent 2, the wife = agent 3, and the child = agent 4. The principles in the decision-making process of the society say that:

(i) The man follows the king;

(ii) The wife and the child follow the man;

(iii) The king should respect his people.

The principles (i) and (ii) give the following conditions for the Confucian influence function Conf.

**Definition 4** The Confucian influence function Conf satisfies

$$ (\text{Conf}(\mathbf{i}))_2 = i_1, \quad (\text{Conf}(\mathbf{i}))_3 = (\text{Conf}(\mathbf{i}))_4 = i_2 \quad \text{for all } \mathbf{i} \in I $$

or, in the set notation, for every $S \subseteq N$

$$ 1 \in S \Rightarrow 2 \in \text{Conf}(S), \quad 2 \in S \Rightarrow 3, 4 \in \text{Conf}(S). $$

Depending on the interpretation of the rule (iii), we consider several versions of the model that lead to different definitions of the king's decision.

(1) **1st version**: the king needs (for the YES decision) approval of all his people, including himself. Hence, the king's decision satisfies

$$ (\text{Conf}(1_N))_1 = +1 \quad \text{and} \quad (\text{Conf}(\mathbf{i}))_1 = -1 \quad \text{for every } \mathbf{i} \neq 1_N. \qquad (3) $$

The graph of this version of the Confucian function is given in Figure 5.

<figure><img src="image_8.png" /><figcaption>**Fig. 5.** The graph of the Confucian function Conf - 1st version</figcaption></figure>

Every node is a connected component. They are all transient classes, except $N$ and $\emptyset$ which are terminal. We have the following:
**Fact 4** Let Conf be the first version of the Confucian function as given by Definition 4 and equation (3). If the initial state is $N$, then $S(0) = N = S(t)$ for each $t \in \mathbb{N}$, and if $S(0)$ is different from $N$, then the process converges to $\emptyset$ in at most 3 steps.

(2) **2nd version:** the king needs (for the YES decision) a majority of his people ($\ge 2$). Additionally, his inclination must be also positive. The king's decision is then:

$$ (\mathrm{Conf}(i))_1 = +1 \quad \text{iff} \quad (i_1 = +1 \text{ and } |\{k \in N \setminus 1 : i_k = +1\}| \ge 2). \quad (4) $$

The graph is given in Figure 6.

<figure><img src="image_9.png" /><figcaption>**Fig. 6.** The graph of the Confucian function Conf - 2nd version</figcaption></figure>

We have then the following:

**Fact 5** Let Conf be the second version of the Confucian function as given by Definition 4 and equation (4). If the initial state is either 123, 124 or $N$, then the process terminates at $N$, otherwise the process converges to $\emptyset$ in at most 4 steps.

(3) **3rd version:** the king needs the approval of only one of his people, and his inclination must be positive. Hence, we get

$$ (\mathrm{Conf}(i))_1 = +1 \quad \text{iff} \quad (i_1 = +1 \text{ and } |\{k \in N \setminus 1 : i_k = +1\}| \ge 1). \quad (5) $$

The graph for this version is presented in Figure 7.

Similarly as in the previous cases, we get immediately the following:

**Fact 6** Let Conf be the third version of the Confucian function as given by Definition 4 and equation (5). If the initial state is 1 or it does not contain the king, then the process converges to $\emptyset$ in at most 3 steps. Otherwise, i.e., if the initial state contains the king (except the initial state 1), then the process converges to $N$ in at most 2 steps.

(4) **Stochastic case:** the king's decision is as follows:
<figure><img src="image_10.png" /><figcaption>Fig. 7. The graph of the Confucian function Conf - 3rd version</figcaption></figure>

- for the YES inclination, the king has a uniform distribution on all 3 previous cases;

- for the NO inclination, the king changes to YES if there is unanimity of his people (1/3), if there is a majority of his people (1/3) or he does not change (1/3).

Figure 8 presents the graph of this stochastic Confucian function. If the transition from $S$ to $T$ has a probability less than 1, we figure the value of this probability on the edge from $S$ to $T$.

<figure><img src="image_11.png" /><figcaption>Fig. 8. The graph of the stochastic Confucian function Conf - 4th version</figcaption></figure>

As before, the two terminal classes are $\emptyset$ and $N$ (consensus situations). The transient classes are 3, 4, 23, 24, {1, 2, 34}, 13, 14, 123, 124, and {12, 134, 234}. The reduced graph is given in Figure 9.
<figure><img src="image_12.png" /><figcaption>Fig. 9. The reduced graph of the stochastic Confucian function Conf</figcaption></figure>

Let us compute the probability of reaching the terminal classes starting from any transient state, using (2). Since we have only two terminal classes, it is enough to compute the probability of reaching, say $\emptyset$ from any state $S$, which we denote by $\pi_S$. Then the column vector $\pi := [\pi_S]_{S \in 2^N \setminus \{N, \emptyset\}}$ is solution of the system

$$ (I - Q)\pi = r $$

where $I$ is the $(2^n - 2)$-size identity matrix, $Q$ is the transition matrix for the $2^n - 2$ transient states (see coefficients on Fig. 8), and $r := [r_S]_{S \in 2^N \setminus \{N, \emptyset\}}$ gives the transition probabilities from transient states to terminal states

$$ r_3 = 1, \quad r_4 = 1, \quad r_{34} = \frac{2}{3}, \quad r_S = 0 \text{ otherwise.} $$

In summary,

$$
\begin{align*}
\pi_3 &= 1 \\
\pi_4 &= 1 \\
\pi_{13} - \frac{2}{3}\pi_2 - \frac{1}{3}\pi_{12} &= 0 \\
\pi_{14} - \frac{2}{3}\pi_2 - \frac{1}{3}\pi_{12} &= 0 \\
\pi_{23} - \frac{2}{3}\pi_{34} - \frac{1}{3}\pi_{134} &= 0 \\
\pi_{24} - \frac{2}{3}\pi_{34} - \frac{1}{3}\pi_{134} &= 0 \\
\pi_{123} - \frac{1}{3}\pi_{234} &= 0 \\
\pi_{124} - \frac{1}{3}\pi_{234} &= 0 \\
\pi_1 - \pi_2 &= 0 \\
\pi_2 - \pi_{34} &= 0 \\
\pi_{34} - \frac{1}{3}\pi_2 &= \frac{2}{3} \\
\pi_{12} - \frac{2}{3}\pi_{234} &= 0 \\
\pi_{134} - \frac{1}{3}\pi_2 - \frac{2}{3}\pi_{12} &= 0 \\
\pi_{234} - \frac{1}{3}\pi_{34} - \frac{2}{3}\pi_{134} &= 0
\end{align*}
$$

By solving this system, we get the following:
**Fact 7** Let Conf be the stochastic version of the Confucian function as defined above, at point (4). There are two terminal classes $\emptyset$ and $N$. Let $\pi_S$ denote the probability of reaching $\emptyset$ from transient state $S$. Then:

$$ \begin{aligned} \pi_1 &= \pi_2 = \pi_3 = \pi_4 = \pi_{34} = 1 \\ \pi_{12} &= \frac{10}{19}, \quad \pi_{13} = \pi_{14} = \frac{16}{19}, \quad \pi_{23} = \pi_{24} = \frac{17}{19} \\ \pi_{123} &= \pi_{124} = \frac{5}{19}, \quad \pi_{134} = \frac{13}{19}, \quad \pi_{234} = \frac{15}{19}. \end{aligned} $$

## 7 Comparison with the Asavathiratham model

We describe briefly the model proposed by Asavathiratham. There is a set $N$ of $n$ agents who must make a yes/no decision. There is an $n \times n$ row-stochastic matrix $D := [d_{ij}]_{i,j \in N}$, called the network influence matrix, whose term $d_{ij}$ expresses the weight of player $j$ in the opinion of $i$. Specifically, let $s(t)$ be an $n$-dim column vector which is 0-1 valued: $s_i(t) = 1$ (resp., 0) indicates that player $i$ says ‘yes’ (resp., ‘no’) at time $t$. Then at time $t+1$, the probability $x_i(t+1)$ that player $i$ says ‘yes’, for all $i \in N$, is given by

$$ \mathbf{x}(t+1) = \mathbf{D}\mathbf{s}(t). $$

Next, from $\mathbf{x}(t+1)$, one computes $\mathbf{s}(t+1) \in \{0, 1\}^n$, obtained as a random realization of $n$ independent Bernoulli random variables with probability $x_1(t), \dots, x_n(t)$.

Note that $\mathbf{x}(t)$ is not a probability vector. The model is similar to DeGroot's model, $D$ has the same meaning, however $\mathbf{x}(t)$ has a different meaning since in DeGroot's model, $x_i(t)$ is the opinion of player $i$, which is a real number in some interval.

Asavathiratham studies the convergence of his model, and among others rediscovers DeGroot's results. In particular, $\mathbf{x}(t)$ converges towards a consensus vector, i.e., each player has the same positive probability to say ‘yes’. From this, it is proved that only two situations can occur: either all players say ‘yes’, or all players say ‘no’ (in our terminology, there are two terminal states, $N$ and $\emptyset$).

This model has the advantage of simplicity: the influence is linear, and $D$ is much smaller than our matrix $B$. We will show that we can cast it into our framework, but this will put into light some difficulties to interpret the Asavathiratham model from a probabilistic point of view.

Let us first construct the matrix $B$. Suppose that at time $t$, players in the set $S \subseteq N$ say ‘yes’, and the others say ‘no’. Hence $\mathbf{s}(t) = \mathbf{1}_S$, where $\mathbf{1}_S$ is the column vector with components 1 for $i \in S$ and 0 otherwise. Computing $\mathbf{x}(t+1) = \mathbf{D}\mathbf{s}(t)$ gives the probability of each player to say ‘yes’ after one step of influence. Supposing the decision of players to be independent as it is supposed in the Asavathiratham model, it is then possible to compute the probability for every $T \subseteq N$ to be the set of ‘yes’ players at time $t+1$ (this is vector $\mathbf{s}(t+1)$), that is, in our terminology, the probability of each state. This gives the row $[b_{S,T}]_{T \subseteq N}$ of our matrix $B$. Formally:

$$ \begin{aligned} b_{S,T} &= \prod_{i \in T} x_i(t+1) \prod_{i \notin T} (1 - x_i(t+1)) \\ &= \prod_{i \in T} d_{S,i} \prod_{i \notin T} (1 - d_{S,i}), \quad \forall T \subseteq N \end{aligned} \quad (6) $$
with $d_{S,i} := \sum_{j \in S} d_{ij}$, or more compactly $\mathbf{d}_S = \mathbf{D} \mathbf{1}_S$. Taking all $S \subseteq N$ determines the matrix $\mathbf{B}$ entirely.

The next proposition shows that the two models are equivalent.

**Proposition 1** Assume $\mathbf{D}$ is given, and consider $\mathbf{B}$ constructed by (6). For any $\mathbf{s}(t) = \mathbf{1}_S$, the output $\mathbf{x}(t+1) = \mathbf{D}\mathbf{s}(t)$ can be recovered from $\mathbf{z}(t+1) = \mathbf{z}(t)\mathbf{B}$ with $\mathbf{z}(t) = \boldsymbol{\delta}_S$ by

$$x_i(t+1) = \sum_{S \ni i} z_S(t+1) \qquad (7)$$

where $\boldsymbol{\delta}_S$ is the $2^n$-dimensional row vector having all its components equal to 0, except the one corresponding to $S$, which is 1.

**Proof:** From $\mathbf{x}(t+1) = \mathbf{D}\mathbf{s}(t)$ we have $x_i(t+1) = d_{S,i}$. On the other hand, from $\mathbf{z}(t+1) = \boldsymbol{\delta}_S \mathbf{B}$ we have $z_T(t+1) = b_{S,T}$. Therefore,

$$\begin{aligned}
\sum_{T \ni i} z_T(t+1) &= \sum_{T \ni i} b_{S,T} = \sum_{T \ni i} \left( \prod_{j \in T} d_{S,j} \prod_{j \notin T} (1-d_{S,j}) \right) \\
&= d_{S,i} \left( \sum_{T \subseteq N \setminus i} \left( \prod_{j \in T} d_{S,j} \prod_{j \notin T} (1-d_{S,j}) \right) \right) \\
&= d_{S,i}.
\end{aligned}$$

The last equality follows from the fact that for any $p$ and real numbers $x_1, \dots, x_p$

$$1 = \prod_{i=1}^{p} ((1 - x_i) + x_i) = \sum_{S \subseteq \{1, \dots, p\}} \left( \prod_{i \in S} x_i \prod_{i \notin S} (1 - x_i) \right).$$

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

**Remark 2** The above result extends to the case where $\mathbf{s}(t) \in [0, 1]^n$ by linearity of $\mathbf{D}$ and $\mathbf{B}$. Indeed, any vector $\mathbf{x} \in [0, 1]^n$ can be decomposed into vectors $\mathbf{1}_S$:

$$\mathbf{x} = \sum_{S \subseteq N} \mathbf{1}_S \left( \prod_{i \in S} x_i \prod_{i \notin S} (1 - x_i) \right),$$

since for every $j \in N$, the $j$th component of the right-hand side is

$$\sum_{S \ni j} \left( \prod_{i \in S} x_i \prod_{i \notin S} (1 - x_i) \right) = x_j \left( \sum_{S \subseteq N \setminus j} \left( \prod_{i \in S} x_i \prod_{i \notin S} (1 - x_i) \right) \right) = x_j$$

proceeding as above. For $\mathbf{z}(t) \in [0, 1]^{2^n}$, the decomposition is trivial:

$$\mathbf{z}(t) = \sum_{S \subseteq N} z_S(t) \boldsymbol{\delta}_S.$$
**Remark 3** Although the formalism of the Asavathiratham model is simpler than ours, it is in fact more difficult to use. Once our matrix **B** is computed, we can compute directly **z**(t) from **z**(0) by **z**(0)****B**^t and study convergence. However, computing **x**(2) = **D****x**(1) = **D**^2**s**(0) with **s**(0) = **1**_S does not permit to compute directly the probability that T is the coalition of ‘yes’ voters by

$$ \mathrm{Prob}(T) = \prod_{i \in T} x_i(2) \prod_{i \notin T} (1 - x_i(2)) \qquad (8) $$

because one cannot see why the individual probabilities should still be independent at t = 2, taken for granted that they are at t = 1. In fact, the model is not clear from a probabilistic point of view because there is no clear meaning for “combining values which are considered as probabilities of individual to say yes”. A proper probabilistic setting should consider combination of random variables, but it does not seem that this model can be interpreted as a linear combination of n random variables, one for each player. Anyway, linear combinations of independent random variables are no more independent in general.

The next example illustrates the above proposition and remarks.

**Example 1** Let us consider a simplified Confucian model with only 3 players: the king (1), the man (2) and the wife (3). As before the man follows the king, the wife follows the man, and the king respects his people. This last rule is implemented as follows: the king takes the average probability to say ‘yes’, including himself. Hence, the model is easily put into the Asavathiratham framework: the matrix is simply

$$ \mathbf{D} = \begin{bmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} $$

Let us compute the matrix **B**:

$$
\begin{align*}
\mathbf{s}(t) = [1 \ 0 \ 0]^T &\rightarrow \mathbf{x}(t+1) = [\frac{1}{3} \ 1 \ 0]^T &\rightarrow b_{1,12} &= \frac{1}{3}, b_{1,2} = \frac{2}{3} \\
\mathbf{s}(t) = [0 \ 1 \ 0]^T &\rightarrow \mathbf{x}(t+1) = [\frac{1}{3} \ 0 \ 1]^T &\rightarrow b_{2,13} &= \frac{1}{3}, b_{2,3} = \frac{2}{3} \\
\mathbf{s}(t) = [0 \ 0 \ 1]^T &\rightarrow \mathbf{x}(t+1) = [\frac{1}{3} \ 0 \ 0]^T &\rightarrow b_{3,1} &= \frac{1}{3}, b_{3,\emptyset} = \frac{2}{3} \\
\mathbf{s}(t) = [1 \ 1 \ 0]^T &\rightarrow \mathbf{x}(t+1) = [\frac{2}{3} \ 1 \ 1]^T &\rightarrow b_{12,123} &= \frac{2}{3}, b_{12,23} = \frac{1}{3} \\
\mathbf{s}(t) = [1 \ 0 \ 1]^T &\rightarrow \mathbf{x}(t+1) = [\frac{2}{3} \ 1 \ 0]^T &\rightarrow b_{13,12} &= \frac{2}{3}, b_{13,2} = \frac{1}{3} \\
\mathbf{s}(t) = [0 \ 1 \ 1]^T &\rightarrow \mathbf{x}(t+1) = [\frac{2}{3} \ 0 \ 1]^T &\rightarrow b_{23,13} &= \frac{2}{3}, b_{23,3} = \frac{1}{3}
\end{align*}
$$
and $b_{0,0} = 1$, $b_{123,123} = 1$. Hence, the matrix is:

$$ \mathbf{B} = \begin{bmatrix} \emptyset & 1 & 2 & 12 & 3 & 13 & 23 & 123 \\ \emptyset & 1 & 2 & 1/3 & 1/3 & & & & \\ 1 & 2 & 2/3 & 1/3 & & & & & \\ 2 & 1/3 & 2/3 & 1/3 & & & & & \\ 1/3 & 1/3 & & 1/3 & 2/3 & & & & \\ 2/3 & 1/3 & & & 1/3 & 2/3 & & & \\ 1/3 & 2/3 & & & & 1/3 & 2/3 & & \\ 2/3 & 2/3 & & & & & 1 & & \\ 1 & & & & & & & 1 & \end{bmatrix} $$

Consider now $\mathbf{s}(0) = [1 \ 0 \ 0]^T$. Then $\mathbf{x}(1) = [\frac{1}{3} \ 1 \ 0]^T$ and $\mathbf{x}(2) = [\frac{4}{9} \ \frac{1}{3} \ 1]^T$. From $\mathbf{B}$ we have with $\mathbf{z}(0) = \boldsymbol{\delta}_{\{1\}}$:

$$ \begin{align*} z_{12}(1) &= \frac{1}{3}, & z_{2}(1) &= \frac{2}{3} \\ z_{3}(2) &= \frac{4}{9}, & z_{13}(2) &= \frac{2}{9}, & z_{23}(2) &= \frac{1}{9}, & z_{123}(2) &= \frac{2}{9}. \end{align*} $$

However, a computation of $\mathbf{z}(2)$ from $\mathbf{x}(2)$ by (8) gives:

$$ z_3(t+1) = \frac{10}{27}, \quad z_{13}(t+1) = \frac{8}{27}, \quad z_{23}(t+1) = \frac{5}{27}, \quad z_{123}(t+1) = \frac{4}{27}. $$

Observe that the computation of probabilities of states from $\mathbf{x}(2)$ is not correct. A correct computation should proceeds as follows: since from $\mathbf{x}(1)$ we know that states 12 and 2 can happen with probabilities 1/3 and 2/3 respectively, we compute $\mathbf{x}^{(12)}(2) := \mathbf{D}[1 \ 1 \ 0]^T$ and $\mathbf{x}^{(2)}(2) := \mathbf{D}[0 \ 1 \ 0]^T$:

$$ \mathbf{x}^{(12)}(2) = [\frac{2}{3} \ 1 \ 1]^T, \quad \mathbf{x}^{(2)}(2) = [\frac{1}{3} \ 0 \ 1]^T. $$

¿From $\mathbf{x}^{(12)}(2)$, we deduce that states 123 and 23 happen with probability 2/3 and 1/3 respectively, while from $\mathbf{x}^{(2)}(2)$ we deduce that states 13 and 3 happen with probability 1/3 and 2/3 respectively. Multiplying by the a priori probabilities gives the desired result.

One can also verify that $\mathbf{x}(1)$ can be recovered from $\mathbf{z}(1)$ by (7), and this remains true for $\mathbf{x}(2)$ and $\mathbf{z}(2)$ (Remark 2).

# 8 Models based on aggregation functions

The Asavathiratham model performs a convex combination of individual probabilities. This is a particular example of aggregation, but other ways of aggregating can be thought of.

**Example 2** Consider $N = \{1, 2, 3\}$ and the following way to aggregate probabilities:

- Agent 1 takes the minimum of all agents

- Agent 2 takes the maximum of agents 1 and 3

- Agent 3 takes the minimum of agents 1 and 2.
Despite the nonlinear character of this aggregation procedure, one can still apply our methodology. The matrix **B** can be obtained exactly as with the Asavathiratham model:

$$
\begin{align*}
\mathbf{s}(t) &= [1 \ 0 \ 0]^T \rightarrow \mathbf{x}(t+1) = [0 \ 1 \ 0]^T & \rightarrow & b_{1,2} = 1 \\
\mathbf{s}(t) &= [0 \ 1 \ 0]^T \rightarrow \mathbf{x}(t+1) = [0 \ 0 \ 0]^T & \rightarrow & b_{2,0} = 1 \\
\mathbf{s}(t) &= [0 \ 0 \ 1]^T \rightarrow \mathbf{x}(t+1) = [0 \ 1 \ 0]^T & \rightarrow & b_{3,2} = 1 \\
\mathbf{s}(t) &= [1 \ 1 \ 0]^T \rightarrow \mathbf{x}(t+1) = [0 \ 1 \ 1]^T & \rightarrow & b_{12,23} = 1 \\
\mathbf{s}(t) &= [1 \ 0 \ 1]^T \rightarrow \mathbf{x}(t+1) = [0 \ 1 \ 0]^T & \rightarrow & b_{13,2} = 2 \\
\mathbf{s}(t) &= [0 \ 1 \ 1]^T \rightarrow \mathbf{x}(t+1) = [0 \ 1 \ 1]^T & \rightarrow & b_{23,2} = 1.
\end{align*}
$$

¿From this, **z**(t) can be computed from any **z**(0), and convergence can be studied as
described in Section 4.

More generally,

**Definition 5** An *n*-place aggregation function is any mapping *A* : [0, 1]ⁿ → [0, 1] satisfying

(i) $A(0, \dots, 0) = 0$, $A(1, \dots, 1) = 1$ (boundary conditions)

(ii) If $\mathbf{x} \le \mathbf{x}'$ then $A(\mathbf{x}) \le A(\mathbf{x}')$ (nondecreasingness).

Aggregation functions are well-studied and there exist many families of them: all kinds
of means (geometric, harmonic, quasi-arithmetic) and their weighted version, weighted
ordered averages, any combination of minimum and maximum (lattice polynomials or
Sugeno integrals), Choquet integrals, triangular norms, copulas, etc. (see Grabisch et al.
(2009)).

To each player $i \in N$ let us associate an aggregation function $A_i$. Then from $\mathbf{s} = \mathbf{1}_S$, we compute $\mathbf{x} = (A_1(1_S), \dots, A_n(1_S))$, where $1_S := (\mathbf{1}_S)^T$. Considering as in the Asavathiratham model that $\mathbf{x}$ is a vector of independent probabilities of saying ‘yes’ for each player, we find that

$$
b_{S,T} = \prod_{i \in T} x_i \prod_{i \notin T} (1 - x_i), \quad \forall S, T \subseteq N,
$$

which determines **B**.

To show that the aggregation model is very general, we show below that all previous
examples can be casted into this framework.

**Example 3 (The Confucian model revisited)** The different versions of the Confucian model (Section 6) fits well to an aggregation model. We have in any case for the man, the wife and the child a projection:

$$
A_2(x_1, x_2, x_3, x_4) = x_1, \quad A_3(x_1, x_2, x_3, x_4) = A_4(x_1, x_2, x_3, x_4) = x_2.
$$

For versions 1, 2 and 3, any aggregation function $A_1$ satisfying respectively

(i) $A_1(1_S) = 0$ for all $S \neq N$ (1st version (unanimity))
(ii) $A_1(1_S) = 1$ for all $S \subseteq N$ s.t. $|S| > 2$ and $S \ni 1$, and $A_1(1_S) = 0$ otherwise (2nd version (majority))

(iii) $A_1(1_S) = 1$ for all $S \subseteq N$ s.t. $|S| > 1$ and $S \ni 1$, and $A_1(1_S) = 0$ otherwise (3d version)

is suitable. For the stochastic version, $A_1$ must have the following values:

<table><tr><td>S</td><td>1</td><td>2</td><td>3</td><td>4</td><td>12</td><td>13</td><td>14</td></tr><tr><td>A<sub>1</sub>(1<sub>S</sub>)</td><td>0</td><td>0</td><td>0</td><td>0</td><td>1/3</td><td>1/3</td><td>1/3</td></tr><tr><td>S</td><td>23</td><td>24</td><td>34</td><td>123</td><td>124</td><td>134</td><td>234</td></tr><tr><td>A<sub>1</sub>(1<sub>S</sub>)</td><td>1/3</td><td>1/3</td><td>1/3</td><td>2/3</td><td>2/3</td><td>2/3</td><td>2/3</td></tr></table>

**Example 4 (The other examples revisited)** It is easy to see that the identity, follow, guru and majority functions are particular cases of the aggregation model. This is also true to a large extent for the stochastic mass psychology function. For this, one has to specify for each $S \subseteq N$ the probabilities of transition. If the set $S$ of ‘yes’ players satisfies $|S| > \eta$, then there is some probability that players in $N \setminus S$ (‘no’ players) become ‘yes’ players (and similarly if $S$ is the set of ‘no’ players). Suppose that for each situation $(S \subseteq N, \varepsilon = \text{‘yes’} \text{ or ‘no’})$, the probability $p_i^{S,\varepsilon}$ that player $i \in N \setminus S$ changes his opinion is specified, and that players in $N \setminus S$ change independently their opinion. Then this is equivalent to an aggregation model defined as follows, for every $S \subseteq N$

$$A_i(1_S) = \begin{cases} 1, & \text{if } i \in S \text{ and } |S| \ge \eta \\ p_i^{S,yes}, & \text{if } i \in N \setminus S \text{ and } |S| \ge \eta \\ 0, & \text{if } i \in N \setminus S \text{ and } |N \setminus S| \ge \eta \\ p_i^{N \setminus S, no}, & \text{if } i \in S \text{ and } |N \setminus S| \ge \eta. \end{cases}$$

For example, the matrix given in Section 5.4 can be recovered as follows:

$A_1(1 \ 0 \ 0) = 0.5,$

$A_1(0 \ 1 \ 0) = 0,$

$A_1(0 \ 0 \ 1) = 0,$

$A_1(1 \ 1 \ 0) = 1,$

$A_1(1 \ 0 \ 1) = 1,$

$A_1(0 \ 1 \ 1) = 0.5,$

$A_2(1 \ 0 \ 0) = 0,$

$A_2(0 \ 1 \ 0) = 0.5,$

$A_2(0 \ 0 \ 1) = 0,$

$A_2(1 \ 1 \ 0) = 1,$

$A_2(1 \ 0 \ 1) = 0.5,$

$A_2(0 \ 1 \ 1) = 1,$

$A_3(1 \ 0 \ 0) = 0$

$A_3(0 \ 1 \ 0) = 0$

$A_3(0 \ 0 \ 1) = 0.5$

$A_3(1 \ 1 \ 0) = 0.5$

$A_3(1 \ 0 \ 1) = 1$

$A_3(0 \ 1 \ 1) = 1.$

Note that in our construction, we need to know the aggregation functions only for 0-1 vectors. One may wonder however how to choose a particular aggregation function whose values are known only for 0-1 vectors. This can be seen as an interpolation problem. A fundamental result in aggregation theory says that the most parsimonious (in number of points involved to perform the interpolation) piecewise linear interpolation is given by the Choquet integral (Grabisch et al., 2009, Ch. 5, Prop. 5.25).

We end this section by studying terminal states and classes. In almost all examples seen so far, the two consensus states $\emptyset$ and $N$ were the only terminal states. Obviously, this is not true in general, and it is difficult to draw some conclusion in general. The aggregation model permits however to be more conclusive. First we need the following definition.
**Definition 6** (i) A player *j* is weakly essential for aggregation function *A* if *A*(*1*<sub>{j}</sub>) > 0 and *A*(*1*<sub>{ij}</sub>) > *A*(*1*<sub>{i}</sub>) for all *i* ∈ *N*, *i* ≠ *j*.

(ii) A player *j* is essential for aggregation function *A* if for all *S* ⊆ *N* \ *j*, *A*(*1*<sub>*S*∪*j*</sub>) > *A*(*1*<sub>*S*</sub>).

Note that for any strictly increasing aggregation function, all players are essential (and therefore weakly essential), but the converse is false. For clarity, we begin by studying terminal states.

**Theorem 1** Suppose **B** is obtained from an aggregation model, with aggregation functions $A_1, \dots, A_n$. Then

(i) {$\emptyset$} and {$N$} are always terminal classes.

(ii) Coalition *S* is a terminal state if and only if

$$A_i(1_S) = 1 \quad \forall i \in S \text{ and } A_i(1_S) = 0 \text{ otherwise.}$$

(iii) There are no other terminal states than $\emptyset$ and $N$ if there is some $A_i$ for which all players are weakly essential.

**Proof:** Recall that a class or a state is terminal if there is no outgoing arrow in it.

(i) Since $A_i(1, \dots, 1) = 1$ for every aggregation function, when $s = 1_N$, we have $x = (A_1(1_N), \dots, A_n(1_N)) = (1, \dots, 1)$. Therefore the next state is $N$ with probability 1, and there cannot be any outgoing arrow from $N$. This proves that $N$ is a terminal state. Now from the property $A_i(0, \dots, 0) = 0$, we deduce similarly that $\emptyset$ is a terminal state.

(ii) Take any $S \neq N, \emptyset$. It is a terminal state if and only if $b_{S,S} = 1$ and consequently $b_{S,T} = 0$ for all $T \neq S$. This is equivalent to $(A_1(1_S), \dots, A_n(1_S)) = 1_S$, i.e., $A_i(1_S) = 1$ if $i \in S$ and 0 otherwise.

(iii) Suppose that all players are weakly essential in $A_i$, and consider some $j \neq i$. Then $A_i(1_{\{j\}}) > 0$, which by condition (ii) and nondecreasingness of $A_i$ implies that no state $S$ such that $i \notin S$ and $j \in S$ can be a terminal state. Since any $j \neq i$ is weakly essential in $A_i$, it turns out that only $\{i\}$ can be a terminal state. If $\{i\}$ is a terminal state then we must also have $A_i(1_{\{i\}}) = 1$. But this would imply that any $j \neq i$ is not weakly essential, a contradiction. ■

The converse of (iii) is false: if there are only $\emptyset$ and $N$ as terminal states, it does not imply that one of the aggregation functions is with all players being weakly essential: take for example the guru influence function where $A_i(x_1, \dots, x_n) = x_{\tilde{k}}$ for $i = 1, \dots, n$. Clearly, only the guru is weakly essential in $A_i$.

Note that the above theorem says nothing about terminal classes which are not reduced to singletons. For terminal classes in general, we have the following result.

**Theorem 2** Suppose **B** is obtained from an aggregation model, with aggregation functions $A_1, \dots, A_n$. Then

(i) Terminal classes are:

- either cycles $\{S_1, \dots, S_k\}$ of any length $2 \le k \le 2^n - 2$ (and therefore they are periodic of period $k$) with the condition that there is no $i, j \in \{1, \dots, k\}$ such that $S_i \subseteq S_j$ and $S_{i+1} \supseteq S_{j+1}$
- or they can only contain $2^k$ coalitions, for some $k \in \{0, 1, \dots, n-1\}$. Each such terminal class (except the case of a cycle of length 2) is a Boolean lattice $[S, S']$ with $S' \supseteq S$, $|S' \setminus S| = k$, i.e., the collection of all coalitions containing $S$ and contained in $S'$, and there is at least one set connected to all others and itself.

(ii) If there exists $A_i$ for which all players are weakly essential, then there are no other terminal classes than $\{\emptyset\}$ and $\{N\}$, except possibly cyclic classes. If in addition all players in $A_i$ are essential, then there are no cyclic classes.

(see proof in the appendix)

# 9 Conclusions

We summarize the findings of the paper in several points:

- We consider the influence mechanism to be stochastic in nature, rather than deterministic, as it was the case in our earlier works. Therefore, an influence function is best represented as a row-stochastic matrix. Remarkable examples of such functions are the mass psychology function and the Confucian model.

- Considering that influence may iterate, and making the assumption that the opinion of the agents at time $t$ depends only on the opinion of all agents at time $t-1$, the evolution of influence obeys a Markov chain, where states are coalitions of 'yes' players. Therefore, the convergence of the process of influence is dictated by the classical results on convergence of Markov chains. In particular, we can determine in which terminal state or class the process will end. As far as we know, no such model has been proposed in the literature before.

- Inspired by the linear model of influence proposed by Asavathiratham, which can be casted into our framework, we propose a model of influence based on aggregation functions. Here, the opinion of an agent is, roughly speaking, an aggregation (combination) of the opinion of the others. More precisely, the probability of agent $i$ to say 'yes' uniquely depends on who said 'yes' and who said 'no' at previous step of discussion. Any kind of aggregation can be used, provided it preserves unanimity (if all agents said 'yes' (resp., 'no'), then agent $i$ will say 'yes' (resp., 'no') with probability 1), and it is nondecreasing (the more agents said 'yes', the higher the probability). Therefore, the model is very general, and all examples of influence function given in the paper are particular cases of the aggregation model.

- For influence functions based on aggregation, we can give a complete description of terminal states and classes: the two consensus states $N$ and $\emptyset$ are always terminal states. Other terminal classes are necessarily cycles of any length or classes of $2^k$ coalitions, for some $k = 0, \dots, n-1$. If there is an aggregation function for which all players are weakly essential, the only possible terminal classes are the consensus states, or cycles. If in addition the players are essential, the process converges always to one of the consensus states.
Bibliography

C. Asavathiratham. *Influence model: a tractable representation of networked Markov chains*. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, 2000.

C. Asavathiratham, S. Roy, B. Lesieutre, and G. Verghese. The influence model. *IEEE Control Systems Magazine*, 21:52–64, 2001.

V. Bala and S. Goyal. Conformism and diversity under social learning. *Economic Theory*, 17:101–120, 2001.

V. Bala and S. Goyal. Learning from neighbours. *The Review of Economic Studies*, 65(3): 595–621, 1998.

A. V. Banerjee. A simple model of herd behavior. *Quarterly Journal of Economics*, 107(3):797–817, 1992.

A. V. Banerjee and D. Fudenberg. Word-of-mouth learning. *Games and Economic Behavior*, 46:1–22, 2004.

R. L. Berger. A necessary and sufficient condition for reaching a consensus using DeGroot's method. *Journal of the American Statistical Association*, 76:415–419, 1981.

P. B. Bonacich. Power and centrality: a family of measures. *American Journal of Sociology*, 92:1170–1182, 1987.

P. B. Bonacich and P. Lloyd. Eigenvector-like measures of centrality for asymmetric relations. *Social Networks*, 23(3):191–201, 2001.

B. Celen and S. Kariv. Distinguishing informational cascades from herd behavior in the laboratory. *American Economic Review*, 94(3):484–497, 2004.

J. Conlisk. Interactive Markov chains. *Journal of Mathematical Sociology*, 4:157–185, 1976.

J. Conlisk. A stability theorem for an interactive Markov chain. *Journal of Mathematical Sociology*, 6:163–168, 1978.

J. Conlisk. Stability and monotonicity for interactive Markov chains. *Journal of Mathematical Sociology*, 17:127–143, 1992.

M. H. DeGroot. Reaching a consensus. *Journal of the American Statistical Association*, 69:118–121, 1974.

P. DeMarzo, D. Vayanos, and J. Zwiebel. Persuasion bias, social influence, and unidimensional opinions. *Quarterly Journal of Economics*, 118:909–968, 2003.

G. Ellison. Learning, local interaction, and coordination. *Econometrica*, 61:1047–1072, 1993.

G. Ellison and D. Fudenberg. Rules of thumb for social learning. *Journal of Political Economy*, 101(4):612–643, 1993.

G. Ellison and D. Fudenberg. Word-of-mouth communication and social learning. *Journal of Political Economy*, 111(1):93–125, 1995.

J. French. A formal theory of social power. *Psychological Review*, 63(3):181–194, 1956.

N. E. Friedkin and E. C. Johnsen. Social influence and opinions. *Journal of Mathematical Sociology*, 15:193–206, 1990.

N. E. Friedkin and E. C. Johnsen. Social positions in influence networks. *Social Networks*, 19:209–222, 1997.

D. Gale and S. Kariv. Bayesian learning in social networks. *Games and Economic Behavior*, 45(2):329–346, 2003.
B. Golub and M. O. Jackson. Naïve learning in social networks and the wisdom of crowds. *American Economic Journal: Microeconomics*, 2(1):112–149, 2010.

M. Grabisch and A. Rusinowska. A model of influence in a social network. *Theory and Decision*, 69(1):69–96, 2010a.

M. Grabisch and A. Rusinowska. Measuring influence in command games. *Social Choice and Welfare*, 33:177–209, 2009.

M. Grabisch and A. Rusinowska. Influence functions, followers and command games. *Games and Economic Behavior*, 2010b. Forthcoming.

M. Grabisch and A. Rusinowska. A model of influence with an ordered set of possible actions. *Theory and Decision*, 69(4):635–656, 2010c.

M. Grabisch and A. Rusinowska. Different approaches to influence based on social networks and simple games. In A. van Deemen and A. Rusinowska, editors, *Collective Decision Making: Views from Social Choice and Game Theory*, Series Theory and Decision Library C, Volume 43, pages 185–209. Springer-Verlag Berlin Heidelberg, 2010d.

M. Grabisch, J.-L. Marichal, R. Mesiar, and E. Pap. *Aggregation Functions*. Number 127 in Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2009.

M. Granovetter. Threshold models of collective behavior. *American Journal of Sociology*, 83:1420–1443, 1978.

F. Harary. Status and contrast status. *Sociometry*, 22:23–43, 1959.

C. Hoede and R. Bakker. A theory of decisional power. *Journal of Mathematical Sociology*, 8:309–322, 1982.

R. A. Horn and C. R. Johnson. *Matrix Analysis*. Cambridge University Press, 1985.

X. Hu and L. S. Shapley. On authority distributions in organizations: equilibrium. *Games and Economic Behavior*, 45:132–152, 2003a.

X. Hu and L. S. Shapley. On authority distributions in organizations: controls. *Games and Economic Behavior*, 45:153–170, 2003b.

M. O. Jackson. *Social and Economic Networks*. Princeton University Press, 2008.

L. Katz. A new status index derived from sociometric analysis. *Psychometrika*, 18:39–43, 1953.

M. Koster, I. Lindner, and S. Napel. Voting power and social interaction. SING7 Conference, Palermo, July 7-9, 2010.

U. Krause. A discrete nonlinear and nonautonomous model of consensus formation. In S. Elaydi, G. Ladas, J. Popenda, and J. Rakowski, editors, *Communications in Difference Equations*. Amsterdam: Gordon and Breach, 2000.

J. P. Lehoczky. Approximations for interactive Markov chains in discrete and continuous time. *Journal of Mathematical Sociology*, 7:139–157, 1980.

J. Lorenz. A stabilization theorem for dynamics of continuous opinions. *Physica A*, 355: 217–223, 2005.

C. D. Meyer. *Matrix Analysis and Applied Linear Algebra*. Philadelphia: SIAM, 2000.

E. Seneta. *Non-negative Matrices*. New York: John Wiley and Sons, 1973.

L. S. Shapley. A Boolean model of organization authority based on the theory of simple games. Mimeo, 1994.

S. Wasserman and K. Faust. *Social Network Analysis: Methods and Applications*. Cambridge University Press, Cambridge, 1994.
A Proof of Theorem 2

(i) The proof of (i) goes in several steps.

1. We study the case of cycles. Consider $S_1, \dots, S_k$ with $2 \le k \le 2^n - 2$. We must have:

$$
\begin{align*}
(A_1(1_{S_1}), \dots, A_n(1_{S_1})) &= 1_{S_2} \\
(A_1(1_{S_2}), \dots, A_n(1_{S_2})) &= 1_{S_3} \\
\vdots &= \vdots \\
(A_1(1_{S_k}), \dots, A_n(1_{S_k})) &= 1_{S_1}
\end{align*}
$$

Suppose that the vectors $1_{S_1}, \dots, 1_{S_k}$ are incomparable (i.e., no relation of inclusion occurs among the $S_i$'s). Then no condition due to the nondecreasingness of the $A_i$'s applies, and therefore there is no contradiction among the above equations. Now, suppose there exists $S_i \subseteq S_j$, and $S_{i+1} \supseteq S_{j+1}$. Then nondecreasingness implies $(A_1(1_{S_i}), \dots, A_n(1_{S_i})) \le (A_1(1_{S_j}), \dots, A_n(1_{S_j}))$, but $1_{S_{i+1}} \ge 1_{S_{j+1}}$ with some strict inequality, a contradiction. It is not difficult to see that this is a necessary and sufficient condition.

2. We consider the case of classes formed of $2^k$ sets. The case $k=0$ is addressed in Theorem 1. The case $k>n-1$ cannot happen since $\emptyset$ and $N$ are always terminal states.

2.1. Let us show that terminal classes can be formed of two coalitions ($k=1$), say $S$ and $T$. The case of a cycle has been already studied. Consider then that there are loops on $S$ and/or $T$:

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

First, we establish the following useful fact:

CLAIM 1: Suppose that from initial state $S$, there are only two possible transitions to $T$ and $K$ (with possibly $T$ or $K = S$). Then $T \Delta K := (T \setminus K) \cup (K \setminus T)$ is a singleton.

*Proof of the claim:* From initial state $S$, the next state can be only $T$ or $K$. It means that the vector of probability of individuals $\mathbf{x} = (A_1(1_S), \dots, A_n(1_S))$ must contain only 1,0 and a single component $x \neq 0, 1$. Therefore, either $T = K \cup i$ or $T = K \setminus i$ for some $i$ (the index of component $x$).

Applying Claim 1 to our situation, we find that $T = S \cup i$ or $T = S \setminus i$. Due to the symmetry between $S$ and $T$, we may assume without loss of generality that $T = S \cup i$. Therefore for initial state $S$, we have $\mathbf{x} = (1_S, x_i, 0_{N \setminus (S \cup i)})$, i.e.,

$$
A_j(1_S) = 1 \text{ if } j \in S, \quad A_i(1_S) = x, \quad A_j(1_S) = 0 \text{ if } j \notin S \cup i,
$$

and $T$ and $S$ realize with probability $x$ and $1-x$ respectively. Now, if the initial state is $T$, by the same reasoning we deduce that

$$
A_j(1_{S \cup i}) = 1 \text{ if } j \in S, \quad A_i(1_{S \cup i}) = x', \quad A_j(1_{S \cup i}) = 0 \text{ if } j \notin S \cup i.
$$
Observe that the two conditions can be satisfied simultaneously, provided $x' \ge x$. Also, we cannot have $x = 0$ or $1$, nor $x' = 0$ or $1$, i.e., both loops must exist. Indeed, $x = 0$ (resp., $x' = 1$) means that there is no transition from $S$ to $T$ (resp., from $T$ to $S$), so $\{S, T\}$ does not form a class. So it remains only the possibility $x = 1$ and $x' = 0$, which is forbidden by the condition $x' \ge x$. In conclusion from Steps 1 and 2.1, the only possible configurations of classes of two coalitions are those given in Fig. 10.

<figure><img src="image_15.png" /><figcaption>**Fig. 10.** Terminal class with 2 coalitions: periodic case (left; $S, T \neq \emptyset$), aperiodic case (right)</figcaption></figure>

2.2. Let us study the case of a terminal class $C$ formed with 3 coalitions $S, T, K$. For any coalition in $C$, there is a possible transition to $S, T$ and $K$. However, it is not possible to have exactly 3 possible transitions: if the vector $\mathbf{x} = (A_1(1_S), \dots, A_n(1_S))$ has only one component $x$ different from 0,1, then exactly 2 transitions are possible, while 4 are possible when there are 2 components $x, y$ different from 0,1. Hence, in our case, $\mathbf{x}$ contains only one component $x \neq 0,1$, and therefore from any coalition in $C$, only two transitions among $S, T, K$ are possible. Note that this amounts to consider the 4 following situations, where 0, 1, 2 or 3 loops exist:

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

Let us examine the 1st configuration (no loop, periodic case). Applying Claim 1, we deduce that $T\Delta K = i$, $S\Delta K = j$ and $S\Delta T = k$. Without loss of generality, we may assume that $T = K \cup i$. Now, $i \neq j$. Indeed, if $S = K \cup j$, $i = j$ implies $S = T$. If $S = K \setminus j$, since $i \notin K$ and $j \in K$, we have $i \neq j$. Hence in any case $S\Delta T = \{i, j\}$, contradicting the fact that $S\Delta T = k$.

Let us examine the 2nd configuration (one loop). From Claim 1, we can only deduce that $S\Delta T = i$ and $S\Delta K = j$. Proceeding as above, one can check that $i \neq j$. Therefore, the triple $(S, T, K)$ can take the following forms: $(S, S \cup i, S \cup j)$, $(S, S \cup i, S \setminus j)$, $(S, S \setminus i, S \cup j)$ and $(S, S \setminus i, S \setminus j)$. Taking the first form, we have:

$$ \mathbf{s} = \mathbf{1}_S \text{ implies } \mathbf{x} = (A_1(1_S), \dots, A_n(1_S)) = (0 \cdots 0 \underbrace{1 \cdots 1}_{S} \underbrace{0 \cdots 0}_{i}) $$

$$ \mathbf{s} = \mathbf{1}_{S \cup i} \text{ implies } \mathbf{x} = (A_1(1_{S \cup i}), \dots, A_n(1_{S \cup i})) = (0 \cdots 0 \underbrace{1 \cdots 1}_{S} \underbrace{0}_{j} \underbrace{0 \cdots 0}_{i}). $$
By nondecreasingness of $A_i$, we must have $x = 0$, but then there is no transition from $S$ to $T$ and $\{S, T, K\}$ is no more a class. For the second form, we have:

$$ (A_1(1_S), \dots, A_n(1_S)) = (0 \cdots 0 \underbrace{1 \cdots 1}_{S \setminus j} \underbrace{1}_{j} \underbrace{x}_{i} 0 \cdots 0) \\ (A_1(1_{S \cup i}), \dots, A_n(1_{S \cup i})) = (0 \cdots 0 \underbrace{1 \cdots 1}_{S \setminus j} \underbrace{0}_{j} \underbrace{x'_{i}}_{j} 0 \cdots 0). $$

Again, nondecreasingness of $A_j$ implies that $x' = 1$, but then there is no transition from $T$ to $K$ and $\{S, T, K\}$ is no more a class. The two remaining cases are similar.

Let us examine the 3d configuration (2 loops). We see that from Claim 1, we can deduce $S\Delta T = i$ and $T\Delta K = j$. This is similar to the case of one loop. Finally, for the configuration with 3 loops, we can deduce from Claim 1 that $S\Delta T = i$, $T\Delta K = j$ and $K\Delta S = k$, which is exactly the same situation as with Configuration 1 (without loops).

2.3. We turn to the general case. First, we generalize Claim 1 as follows:

**CLAIM 2:** Suppose that from initial state $S$, there are exactly $2^k$ possible transitions to $S_1, \dots, S_{2^k}$ (supposed all distinct but $S$ may belong to the collection). Then $|S_i \Delta S_j| \le k$ for any $i, j = 1, \dots, 2^k$, and moreover, the collection $C := \{S_1, \dots, S_{2^k}\}$ necessarily forms a Boolean lattice, more precisely, considering w.l.o.g. that $S_1$ is the smallest set and $S_{2^k}$ the greatest set, we have $C = \{S_1 \cup K \mid K \subseteq S_{2^k} \setminus S_1\}$.

*Proof of the Claim:* The $2^k$ transitions can be obtained with a vector $\mathbf{x} = (A_1(1_s), \dots, A_n(1_s))$ containing only 0,1 and $k$ variables $x_1, \dots, x_k$ in $]0, 1[$. The set of all “1” determines the smallest set $S_1$, while the set of all “1” and $x_1, \dots, x_k$ determines the greatest one $S_{2^k}$. Clearly, all sets between $S_1$ and $S_{2^k}$ can realize.

2.3.1. Suppose that the class $C$ contains exactly $2^k$ coalitions $S_1, \dots, S_{2^k}$ and that in $C$ there is a set $S_i$ having a transition to all sets in $C$, including $S_i$ itself (if not, we are in the case treated in 2.3.2: there are more sets in the class than transitions on one set). From Claim 2, it follows that $C$ forms a Boolean lattice, say with least element $S_1$ and greatest element $S_{2^k}$. For all other sets $S_j, j \ne i$, we assume without loss of generality that there are also $2^k$ transitions, possibly with probability zero. We have the following set of equations:

$$ (A_1(1_{S_1}), \dots, A_n(1_{S_1})) = (0 \cdots 0 \underbrace{1 \cdots 1}_{S_1} \underbrace{x_1^1 x_2^1 \cdots x_k^1}_{S_{2^k} \setminus S_1}) \\ (A_1(1_{S_2}), \dots, A_n(1_{S_2})) = (0 \cdots 0 \underbrace{1 \cdots 1}_{S_1} \underbrace{x_1^2 x_2^2 \cdots x_k^2}_{S_{2^k} \setminus S_1}) \\ \vdots = \vdots \\ (A_1(1_{S_{2^k}}), \dots, A_n(1_{S_{2^k}})) = (0 \cdots 0 \underbrace{1 \cdots 1}_{S_1} \underbrace{x_1^{2^k} x_2^{2^k} \cdots x_k^{2^k}}_{S_{2^k} \setminus S_1}) $$

Observe that this system has no contradiction as soon as the $x_i^l$'s follow the inclusion relations of the sets in $C$ (for each $i = 1, \dots, k$, they must form the same Boolean lattice):
$S_j \subseteq S_l$ implies $x_i^j \le x_i^l$ for all $i = 1, \dots, k$. Observe also that in general we may have some of the $x_i^l$ equal to 0 or 1 (which correspond to suppression of some transitions) provided that the monotonicity relations among them are preserved, and that $C$ remains strongly connected.

2.3.2. Suppose that the class contains more sets than the maximal number of transitions on one set (this is the case if either the number of sets is not of the form $2^k$, or there are $2^k$ sets but all sets have at most $2^{k'}$ transitions with $k' < k$).

Let us consider that the maximal number of transitions in the class is $2^k$, and $S_j$ be a set having this number of transitions. Let us call $C$ the collection of $2^k$ sets connected to $S_j$. From Claim 2, it is a Boolean lattice of the form $[S, S \cup K]$, with $|K| = k$, and $S \subseteq S_j \subseteq S \cup K$. Since by hypothesis the class contains more than $2^k$ sets, let us call by $\mathcal{T}$ the collection of remaining sets. Since the class is strongly connected, there must be a set $S_i \in C$ which is connected to some set in $\mathcal{T}$, say $T_1$.

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

We have by definition of $S_i$ and $S_j$:

$$ (A_1(1_{S_j}), \dots, A_n(1_{S_j})) = (0 \cdots 0 \underbrace{1 \cdots 1}_{S} \underbrace{x_1^j \cdots x_k^j}_{K} 0 \cdots 0) $$

$$ (A_1(1_{S_i}), \dots, A_n(1_{S_i})) = (0 \cdots 0 \underbrace{1 \cdots 1}_{S} \underbrace{x_1^i \cdots 0 \cdots x_k^i}_{K} 0 \cdots z \cdots 0) $$

with $x_i^i, x_i^j > 0, l = 1, \dots, k$, with $z > 0$ being at some position $t$, with $t \in T_1 \setminus (S \cup K)$, and the zero in $K$ (say, $x_i^i = 0$) corresponding to some $r \in K$ (there are as many such $t, r$ as the cardinality of $T_1 \setminus (S \cup K)$).

Suppose that $S_i \subseteq S_j$. Then by nondecreasingness, we must have $z = 0$, which would delete the link from $S_i$ to $T_1$, a contradiction.

Suppose that $S_j \subseteq S_i$. Again by nondecreasingness, $x_i^j = 0$, which would delete the links from $S_j$ to any set in $C$ containing $r$. This contradicts the definition of $S_j$.

Suppose finally that $S_i$ and $S_j$ are incomparable. Observe that by nondecreasingness, all supersets of $S_i$, in particular $S \cup K$, must be connected to $T_1$ as $S_i$ is, i.e., the component $t$ in $(A_1(1_{S \cup K}), \dots, A_n(1_{S \cup K}))$ must be some $z' \ge z > 0$. But since the number of transitions is at most $2^k$, this must be at the expense of some component $x_i^{S \cup K}$ in $K$ to be 0. Since $S_j \subseteq S \cup K$, it follows from nondecreasingness that necessarily the component $x_i^j$ in $(A_1(1_{S_j}), \dots, A_n(1_{S_j}))$ must be zero too, contradicting the definition of $S_j$.

(ii) Let us examine first the case of terminal classes which are not cycles. By the above result, these classes have $2^k$ sets, with at most $2^k$ transitions for each set, this number being attained for at least one set. If $S, S \cup K$ are the smallest and largest sets of the
class, we know that for each $S'$ in the class the vector $\mathbf{x} = (A_1(1_{S'}), \dots, A_n(1_{S'}))$ has the form $(1_S, \underbrace{x_1 \cdots x_k}_{K}, 0 \cdots 0)$.

Suppose that all players in $A_i$ are weakly essential. Then for any $j \neq i$, $A_i(1_{\{j\}}) > 0$, therefore by nondecreasingness of $A_i$, $A_i(1_{S'}) > 0$ for all $S' \ni j$ and $S' \not\ni i$. Hence $S'$ cannot be the greatest element of a terminal class since the vector $\mathbf{x}$ would not have the right form. Since any $j \neq i$ is weakly essential, it turns out that only $\{i\}$ can be the greatest element of a terminal class, and we are back to the case $k=1$ (Theorem 1).

The above argument does not work for cyclic classes. For example, with $n=3$, $S = \{1,2\}$ and $S' = \{1,3\}$, the fact that $A_1$ or $A_2$ or $A_3$ has all weakly essential players does not contradict the fact that $\{S,S'\}$ is a cyclic terminal class. However, since terminal cyclic classes has always transitions with probability 1, if $S$ belongs to the class, $A_i(1_S)$ is either 0 or 1. Now $S$ cannot be $N$ nor $\emptyset$ since these are already terminal states. However, if all players in $A_i$ are essential we have $A_i(1_S) \neq 0,1$ for all $S \neq N, \emptyset$.