Suppose there is a rural village, with a large supply of gold, high up in the mountains somewhere. People from all over the world travel to the village in order to try and become a villager as they hope to gain their share of the gold. The rules for becoming a villager are simple: all existing villagers must vote and unanimously agree that you should be allowed into the village. This is clearly quite a tough task, so the villagers are kind enough to vote more than once over your admittance. In fact, they will keep voting until they all agree, either to let you in or deny your entry.

We call such a situation where everyone comes to the same opinion a consensus. As an example look at the two pictures below. We can imagine each village as a dot, supposing that villagers who vote "Yes" on your application to join and red and villagers who vote "No" are blue. We will suppose that a line between two dots (villagers) means that they are neighbors. (The reason for adding such information should become clear shortly.) On the left we can see a collection of opinions that do not form a consensus as there are "Yes" and "No" dots. On the right, we can see a successful consensus as the opinion of all the villagers is "Yes".

Let us now imagine that there is a villager who is perhaps a bit bored (and greedy) and has decided to set up a shop that lets people bet on the outcome of traveller's applications. Since they wish to make as much gold as possible it is necessary for them to be able to predict the outcome of these applications accurately so that they can set the correct odds. To this end they have enlisted the help of a mathematician. Which, dear reader, we will suppose is you.

The villager, wishing to help you, has provided you with a picture quite like the one on the left above. It gives you the initial opinions of all of the villagers and tells you which villagers are neighbors with one another. Mathematically, we call such a picture a graph. It is a collection of vertices (the dots representing the villagers) and edges (the lines representing the fact that two villagers are neighbors). Technically this is not how graphs are defined, as it is not always convenient to draw pictures of the graphs we want to study, but it will be good enough for our purposes to think of them like this.

Our next problem is to decided how a villager's neighbors should influence them. We want to pick some type of rule that mirrors how people behave in the real world. Pause for a moment and try of think of some possible rules (there is no one right answer)

Some Possible Rules:

It is possible to come up with different practical justifications for each of these rules. The majority rule reflects the idea of "wisdom of crowds" which encapsulates the fact that the average opinion of a group can be much more accurate than an individual expert opinion. Meanwhile, it is unlikely that people speak to all of their neighbors or friends everyday so it also makes sense to pick a smaller sample which more accurately reflects how many opinions from people we know that we encounter on a daily basis.

It is also possible, in fact quite likely, you came up with some different rules that aren't listed above. Try and think briefly about how you would justify them.

As mathematicians we are not necessarily too interested in the specifics of these behavioural considerations. However, it is quite remarkable how these simple rules can successfully model complex human behaviour when applied to graphs. Indeed, we use the term graph dynamics to describe the area of mathematical research that studies how rules like these behave on different graphs. Therefore, if we wished to give our present investigation a proper title, we could say that we are studying majority dynamics on the village graph. Where, we could have substituted in any of the other rules for majority and the village graph is exactly the graph we have been considering where villagers are vertices and edges correspond to neighbors.

A Sure Thing

Let us now return to our bookmaking villager. Using your ideas about dynamics on the village graph they have employed a programmer who has been running some simulations which predict when an application will be accepted. Whilst these simulations are bringing them a reasonable profit they are very expensive to compute and aren't always reliable. Keen to make even more gold, they now want you to improve your predictions so that from the initial graph you are able to guarantee whether or not application will be accepted, no simulations needed. 

It is worth thinking about what guaranteed means in this context. Since we are assuming villagers behave randomly it is impossible ever to get a precise guarantee on what exactly a particular villager's final opinion will be. However, we only care about which consensus is reached which somehow seems easier to predict. 

It turns it is possible to say for certain types of village graph which consensus will be reached with high probability. This means that if our village were to get really large (i.e. the number of villagers tends towards infinity) our prediction would be correct with probability 1, that is to say it would be certain to happen.

Some less sure things...

Let's again consider the graph we have just been studying but this time under the pull voting protocol. Since, pull voting is a very simple procedure (every vertex just randomly picks one neighbor and adopts their opinion) we will consider in more detail how to predict whether or not an application will be accepted. 

Our main tool for this will be a theorem (aka a mathematical fact) which was proved by Hassin and Peleg in 1999 [1]. It tells us that for pull voting on any (non-bipartite) graph the probability that an opinion becomes a consensus is proportional to the number of neighbors of vertices which held that opinion initially. More precisely,

Where the  ∑ means we add up the number of neighbors for each villager which meets the condition given. What all of this means if that for villager graphs where every villager knows roughly the same number of people (as is the case in the graph that we have been looking at) we can just look at the proportion of "Yes" votes in the graph initially to decide how likely it is for the application to be accepted. Therefore, the probability of the application being accepted in the graph is about 12/15 as we have 12 "Yes" votes and 15 villagers overall. 

It is worth highlighting the distinction between pull voting and the other two protocols we have been looking at. For majority and two-sample dynamics on nearly all (reasonable) choices of voter graph if 99% of the villagers initially want to vote "Yes" then the application will be accepted with high probability. However, we have just seen that for pull voting such a situation cannot happen as there is always a non negligible chance of the minority opinion winning.

Fortunately, our villagers behavior seems to model majority dynamics and so our bookmaking villager is able to predict the results of application with high probability. Unfortunately for them, word of your mathematical ideas has spread and now all of their customers are using the same strategies! As a result of all this, the villagers are now in competition to devise more and more complex strategies for predicting the outcome of applications. 

There is in fact lots we still don't know about graph dynamics. For example, it is an open question to determine how sparse you can make a graph (that is how much you can reduce the number of edges) and still have majority dynamics reach a consensus. Problems in mathematics are often given more attention when many people care about what the solution is. So, if this example has piqued your interest I highly encourage you to read more about graph dynamics and potentially try and analyse (or simulate) the behavior of different dynamics on different network structures.

Applications (outside of the village)

Whilst we have mainly been concerned with a (slightly) silly example here it is worth mentioning that the field of graph dynamics can have very important applications. As a more serious example it is used to understand the concept of information aggregation. That is, how a network can "learn" information over time. During the 1930s a bad drought in the US led to the creation of hybrid corn which offered yields which were up to 20% better than the varieties in use before. As soon as the early 1940s they became the dominant crop. Farmers adoption of the new corn was largely driven by their own experiences and the opinions of their neighbors. 

Consider now a different event in the US: the Great Recession of the 2000s. The main cause of the recession is largely agreed to be the housing bubble. In the years after economists have made the case that one of the main factors driving investors' actions in the housing market was the investment behavior of other investors. This created a herd mentality where all investors adopted similar behaviors. 

It is hopefully clear that in both situations the factors affecting individuals decisions were similar and yet in one case a correct consensus was reached and in the other an incorrect one. One of the reasons for this difference can be put down to the different structures of the networks. Farmers live largely in small communities and interact only with their local neighbors whereas investors pay attention a much wider range of sources.

This difference in network structure is what enabled information aggregation in one case and the failure to do so in another.

(This example was taken from the excellent paper by Feldman, Immorlica, Lucier and Weinberg [2])

A Final Note

If you have made it this far I can only hope you have enjoyed learning a little bit about a fascinating and very practical area of mathematics. Whilst I have not detailed the actual research over the summer (it mainly involved looking at [2] and a very similar paper and trying to extend their results) I have aimed to give an intuition based introduction to social dynamics on random graphs and provide some motivation as to why it is worth studying! 

The only thing I have left to say is an enormous thank you to my supervisor Debsoumya Chakraborti who provided me with a high level of support throughout the summer and was always there to help me with whatever challenges I was facing.

References

[1] Yehuda Hassin and David Peleg. Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248–268, 2001.

[2] Michal Feldman, Nicole Immorlica, Brendan Lucier, and S. Matthew Weinberg. Reaching Consensus via Non-Bayesian Asynchronous Learning in Social Networks. In Klaus Jansen, Jos´e Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014), volume 28 of Leibniz International Proceedngs in Informatics (LIPIcs), pages 192–208, Dagstuhl, Germany, 2014. Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik.