6CCS3AIN – Week 9 – Part B
1 / 17
Motivation
Motivational Example
v2
v4
t=0
v1
v3
v5
• Consider a graph such as the one above.
• Nodes in this graph represent agents.
• Colour of nodes represent their current opinion. (it may change over time!)
• Edges represent what other agents a node sees.
• Their goal: to reach consensus. (i.e., all agents with same colour)
Idea They can learn from their
6CCS3AIN – Week 9 – Part B 2 / 17
Motivational Example
v2
v4
t=1
v1
v3
v5
• Consider a graph such as the one above.
• Nodes in this graph represent agents.
• Colour of nodes represent their current opinion. (it may change over time!)
• Edges represent what other agents a node sees.
• Their goal: to reach consensus. (i.e., all agents with same colour)
Idea They can learn from their neighbours
6CCS3AIN – Week 9 – Part B 3 / 17
Motivational Example
v2
v4
t=2
v1
v3
v5
• Consider a graph such as the one above.
• Nodes in this graph represent agents.
• Colour of nodes represent their current opinion. (it may change over time!)
• Edges represent which other agents a node sees.
• Their goal: to reach consensus. (i.e., all agents with same colour)
Idea They can learn from their neighbours over
6CCS3AIN – Week 9 – Part B 4 / 17
Motivational Example
v2
v4
t=3
v1
v3
v5
• Consider a graph such as the one above.
• Nodes in this graph represent agents.
• Colour of nodes represent their current opinion. (it may change over time!)
• Edges represent what other agents a node sees.
• Their goal: to reach consensus. (i.e., all agents with same colour)
Idea They can learn from their neighbours over time.
6CCS3AIN – Week 9 – Part B 5 / 17
Motivational Example
v2
v4
t=0
v1
v3
v5
• There are many algorithms that can be considered in this case. Today, we are focusing on the following, usually called voter model.
• The process happens in rounds, or time-steps, denoted by t.
• At each round t, each agent v selects one of its neighbours u uniformly at
random.
• Then, v adopts u’s colours for next round.
To avoid ambiguity, we consider that they all change at the same time at the end of round t.
6CCS3AIN – Week 9 – Part B 6 / 17
Some Notation
• First we assume there is a time variable t ∈ T that represent rounds. In our case, T is the set of non-negative integers 0, 1, . . . .
• We have an undirected connected graph G = (V, E).
• An edge (v, u) indicates that v sees u and u sees v.
• The number of neighbours of v is denoted by deg(v).
• A set of colours or opinions X. (in our example, X = {b, r})
• For each time t ∈ T, the current state of the process is described by a function St :V →X.
• We are interested in the consensus states. When, for a given t, we have St(v) = b for all v ∈ V, we say St = blue. Analogously for red, we have St = red.
• In these cases, we say the processes ends, and we denote this by saying that Send = blue, or Send = red.
6CCS3AIN – Week 9 – Part B 7 / 17
Examples of update rules
v2
v4
t=0
6CCS3AIN – Week 9 – Part B
8 / 17
v1
v3
v5
1) What is P r(S1(v1) = r)?
2) What is P r(S1(v4) = b)?
3) What is P r(S1(v5) = r)?
4) What is P r(S1 = blue)?
5) What is P r(S1 = red)?
Questions
• Is consensus stable? I.e., once consensus is reached, will it be maintained indefinitely? In other words,
St0 =blue ⇒ St =blue,forallt>t0?
• Can the process ever get stuck and never find a consensus state? (exercise!)
• Imagine you are not an agent in this process, but you have the power to flip the colour of an agent before anyone makes a decision in a given round. Which agent is the most influential, i.e., the best choice?
• And our key point:
same for red.
Question Given an initial configuration S0, what is the probability that the game ends in blue consensus (same for red)?
6CCS3AIN – Week 9 – Part B 9 / 17
Probabilities of Consensus
v2
v4
t=0
v1
v3
v5
• What counts for an opinion’s advantage?
Option (1) The number of nodes of a given colour.
6CCS3AIN – Week 9 – Part B
10 / 17
Probabilities of Consensus
v2
v4
t=0
v1
v3
v5
• What counts for an opinion’s advantage?
Option (1) The number of nodes of a given colour.
#
Option (2) The sum of degrees of nodes with a given colour.
6CCS3AIN – Week 9 – Part B
11 / 17
Probabilities of Consensus
v2
v4
t=0
v1
v3
v5
• What counts for an opinion’s advantage?
Option (1) The number of nodes of a given colour.
#
Option (2) The sum of degrees of nodes with a given colour.
6CCS3AIN – Week 9 – Part B
12 / 17
Probabilities of Consensus
v2
v4
t=0
v1
v3
v5
• What counts for an opinion’s advantage?
(proof in extra material!)
Theorem Let G = (V, E) be a graph that do not allow deadlocks in a voter model process, i.e., a consensus is reached with probability 1. Given an initial configuration S0 = s, the probability of blue winning is given by
Pr(Send =blue|S0 =s)= analogously for red.
v∈V,s(v)=b
deg(v) 2|E |
6CCS3AIN – Week 9 – Part B
13 / 17
Probabilities of Consensus – Example
v2
v4
t=0
v1
v3
v5
• We apply the theorem to the example above.
Pr(Send =blue|S0 =s)= 4+3+2 = 9 ≈64%
14 14
Pr(Send =red|S0 =s)= 2+3 = 5 ≈36% 14 14
6CCS3AIN – Week 9 – Part B
14 / 17
Some easy and not so easy follow up questions
• Can we say something about the expected time this will take to converge to consensus? (see Hassin and Peleg, 2001 and subsequent work)
• What happens if the graph is not undirected but instead a directed graph with weighted edges? (see Linear Voting Model Cooper and Rivera, 2016)
• We consider that, in this case, the weight of the edge (v,u) represents the probability that v copies colours of u in a given round.
• What is there is some sort of bias toward a colour? For example, if when an agent has a blue and a red neighbour, they may have a higher chance of choosing, say, colour blue. (see )
Why not implement this yourself and check if our probabilities check out? Once you are there, make sure to calculate how many rounds it takes on average.
6CCS3AIN – Week 9 – Part B 15 / 17
6CCS3AIN – Week 9 – Part B
16 / 17
The End
Some references
[Cooper and Rivera, 2016] Cooper, C. and Rivera, N. (2016). The Linear Voting Model: Consensus and Duality.
[Hassin and Peleg, 2001] Hassin, Y. and Peleg, D. (2001). Distributed probabilistic polling and applications to proportionate agreement. Information and Computation, 171(2):248–268.
6CCS3AIN – Week 9 – Part B 17 / 17