\section*{6. For APPLICANTS IN $\left\{ \begin{array} { l } \text { COMPUTER SCIENCE } \\ \text { MATHEMATICS \& COMPUTER SCIENCE } \\ \text { COMPUTER SCIENCE \& PHILOSOPHY } \end{array} \right\}$ ONLY.}
This question is about influencer networks. An influencer network consists of $n$ influencers denoted by circles, and arrows between them. Throughout this question, each influencer holds one of two opinions, represented by either a - or a □ in the circle. We say that an influencer $A$ follows influencer $B$ if there is an arrow from $B$ to $A$; this indicates that $B$ has ability to influence $A$.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{e7ecf335-c72f-44dd-a0ab-7a3c25c56ae5-24_228_378_890_584}
\captionsetup{labelformat=empty}
\caption{Figure 1}
\end{center}
\end{figure}

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{e7ecf335-c72f-44dd-a0ab-7a3c25c56ae5-24_216_368_895_1037}
\captionsetup{labelformat=empty}
\caption{Figure 2}
\end{center}
\end{figure}

The example in Figure 1 above shows a network with $A$ and $B$ following each other, $B$ and $C$ following each other, and $C$ also following $A$. In this example, initially $B$ and $C$ have opinion □ , while $A$ has opinion $\triangle$. An influencer will change their mind according to the strict majority rule, that is, they change their opinion if strictly more than half of the influencers they are following have an opinion different from theirs. Opinions in an influence network change in rounds. In each round, each influencer will look at the influencers they are following and simultaneously change their opinion at the end of the round according to the strict majority rule. In the above network, after one round, $A$ changes their opinion because the only influencer they are following, $B$, has a differing opinion, and the network becomes as shown in Figure 2 above.

An influencer network with an initial set of opinions is stable if no influencer changes their opinion, and a network (with initial opinions) is eventually stable if after a finite number of rounds it becomes stable. The network in the above example is eventually stable as it becomes stable after one round.\\
(i) A network of three influencers (without opinions) is shown below. Is this influencer network eventually stable regardless of the initial opinions of the influencers $A$, $B$ and $C$ ? Justify your answer.\\
\includegraphics[max width=\textwidth, alt={}, center]{e7ecf335-c72f-44dd-a0ab-7a3c25c56ae5-24_209_366_2215_861}\\
(ii) Another network of influencers (without opinions) is shown below. Is this influencer network eventually stable regardless of the initial opinions of the influencers? Justify your answer.

\begin{figure}[h]
\begin{center}
  \includegraphics[alt={},max width=\textwidth]{e7ecf335-c72f-44dd-a0ab-7a3c25c56ae5-25_366_698_370_703}
\captionsetup{labelformat=empty}
\caption{( $\triangle ) A$}
\end{center}
\end{figure}

(iii) A partial network of influencers (without opinions for $B _ { 1 } , \ldots , B _ { 8 }$ ) is shown below. You can add at most six additional influencers, assign any opinion of your choice to the new influencers, and add any arrows to the network to describe follower relationships. Design a network that is eventually stable regardless of initial opinions, and has the property that when it becomes stable $A$ has opinion □ if and only if each of $B _ { 1 } , B _ { 2 } , \ldots , B _ { 8 }$ had opinion □ at the start. Justify your answer.

\begin{figure}[h]
\begin{center}
\captionsetup{labelformat=empty}
\caption{( $\triangle ) A$}
  \includegraphics[alt={},max width=\textwidth]{e7ecf335-c72f-44dd-a0ab-7a3c25c56ae5-25_129_766_1347_662}
\end{center}
\end{figure}

(iv) You are given two influencer networks, $N _ { 1 }$ and $N _ { 2 }$, with disjoint sets of influencers shown below. Both are eventually stable. Suppose one of the influencers from network $N _ { 2 }$ follows the influencer $X$ from the network $N _ { 1 }$. Is the resulting network guaranteed to be eventually stable? Justify your answer.\\
\includegraphics[max width=\textwidth, alt={}, center]{e7ecf335-c72f-44dd-a0ab-7a3c25c56ae5-25_113_166_1818_575}\\
\includegraphics[max width=\textwidth, alt={}, center]{e7ecf335-c72f-44dd-a0ab-7a3c25c56ae5-25_214_465_1813_1064}\\
(v) (a) Given a network with $n$ influencers, where the arrows are fixed, but you are allowed to assign opinions ( $\triangle$ or $\square$ ) to each influencer, how many possible assignments of opinions is possible?\\
(b) Given an influencer network and an initial assignment of opinions, explain how you would determine whether the influencer network is eventually stable. Justify your answer.

This page has been intentionally left blank