You pick up your iPhone while waiting in line at a coffee shop. You google a not-so-famous actor, get linked to a Wikipedia entry listing his recent movies and popular YouTube clips of several of them. You check out user reviews on Amazon and pick one, download that movie on BitTorrent or stream that in Netflix. But suddenly the WiFi logo on your phone is gone and you're on 3G. Video quality starts to degrade, but you don't know if it's the server getting crowded or the Internet is congested somewhere. In any case, it costs you $10 per Gigabyte, and you decide to stop watching the movie, and instead multitask between sending tweets and calling your friend on Skype, while songs stream from iCloud to your phone. You're happy with the call quality, but get a little irritated when you see there're no new followers on Twitter. You may wonder how they all kind of work, and why sometimes they don't. Take a look at the list of 20 questions below. Each question is selected not just for its relevance to our daily lives, but also for the core concepts in the field of networking illustrated by its answers. This course is about formulating and answering these 20 questions. All the features of this course are available for free. It does not offer a certificate upon completion.
Voting
Loading...
From the course by Princeton University
Networks: Friends, Money, and Bytes
79 ratings
From the lesson
Why Does Wikipedia Even Work?
In this lecture, we focus on the concepts of crowdsourcing and consensus formation, which are two of the mechanisms allowing Wikipedia to be both a scalable and (reasonably) accurate encyclopedia. In particular, we will look at different voting systems, which are ways of determining consensus from a collection of individual preferences.
Meet the Instructors
Mung ChiangProfessor
Electrical Engineering
Christopher BrintonLecturer
Electrical Engineering
Voting is a very important mechanism to understand
interactions within the crowd or a network of people.
It is a important mechanism to reach a consensus a bonding resolution among
a group of individuals, out of conflicting configuration of opinions
is clearly used in many scenarios.
And Wikipedia is rarely actually explicitly used, as we mentioned.
But still we can view extension of the basic voting model as a underlying
model of how people react to rough consensus formation there.
It is explicitly used in many political system.
Some variant of that is used in jury, Process,
some of that is used in talents show.
And the list can go on.
Now compared to some of the others consensus formations we have already seen,
voting is different.
It is different from presenting a rank order list for
each person to individually evaluate as in Netflix' similar situation.
It is different from using pricing as a way to coordinate people's actions.
For example, ad space auction by Google or
congestion control in the internet that we'll see later.
It is also different from ranking objects, for
example ranking webs pages through page ranking google or
ranking products based on aggregation of rating on Amazon.
Now, voting is so important that we will go through
a tiny tip of this big iceberg in the next 30 minutes or so.
And later in Lecture 20 we'll also talk about fairness systematically.
Voting and fairness theory are the two pillars in the so
called Social Choice Theory that's extensively studied
in economics, in politics, in philosophy and so on.
And some of our study will be based on very famous results
on the impossibilities of axiomatic systems.
But first let's start with something very intuitive, something that we must have all
encountered, it's a simple basic voting system.
There are a lot of variants that one can imagine but
this is America's starting point where we have the following input to the system.
It is a collection of voting inputs called preference profiles for each voter.
And let's say there are N voters.
They can rank order M candidates.
The candidates could be real people running for
election or they could be just different choices.
Options that one need to choose from.
So I got N voters and M candidates.
Each voter would rank these M candidates.
So we've got a rank order list per person.
And you've got another one for another voter.
The collection of all these lists is called the preference profile.
The output to the voting system is a single list called the voting outcome.
So they go through this voting system, and then out comes one single list.
We're going to require that these list be complete.
Meaning that all M candidates need to show up in the list for
both of each the input and output lists.
In many practical cases that is that doesn't have to be, for
example in the rough consensus formation processes in Wikipedia,
a lot of times of the committee members or the editors may not have a complete list.
They may say, well they have three choices and I just want to make sure
choice A is higher than choice B, I don't care where choice C might be.
Whether its right here or right below there.
And in certain voting systems you have so
many candidates that it's impossible to ask people to completely rank them.
You just say tell me whose the number one you really want?
And then, I'll work with that information.
So clearly incomplete input will make the theory richer, but
we'll not have time to cover that.
We'll also, for sake of logical consistency, require that
each of the inputs and the output list must be transitive.
Later in about two lectures time,
we'll also look at transitive property in a graph.
That's very different from this one.
It's unrelated.
This transitive property says that if you rank A to B better than B,
AB I took out of the M candidates and we write that as A bigger than B
and following the same notation if you also think that B is better than C then
these two statements logically must imply A is ranked higher than C in your list.
This is just to ensure logical self consistency.
Otherwise, you're ready run into a cyclic situation,
if A is better that B, B is better than C and if C is better than A,
then, this is a self inconsistent set of input or output.
So we say that, if A is better than B,
B is better than C, it must imply A is better than C.
Alright, having said what are the inputs and outputs of a voting system,
you have to realise that any voting system try to compress information.
There will be a loss of information.
Otherwise, it will be too good to be true.
You start with N list and you end up with one list.
Of course, this one list cannot be reverse engineered to give you the analysis.
Something must be lost in the process.
The question is, can we still maintain something useful?
But the most commonly encountered voting system is perhaps called the plurality or
majority voting, okay.
It simply says the following.
I'm going to count the number of voters or put a candidate J in the first position.
Okay, look at all the list and say,
how many put candidate J in the first position?
Say 10 out of 20 voters.
For J, and then what about K, what about the other candidates?
And then I simply pick the number one candidate in the output
list as the one with the highest number of voters who put it on the first position.
Then I say the second position, this is the first position.
The second position in the output list would be the one with the second highest
number of voters who put it on the top of their list.
Okay, that's assuming there's no ties,
otherwise we have to think of some way to break the tie.
And this is the majority voting that we encounter in many situations.
There's also the mirror image of that called Kemeny voting system.
Which says that we'll count how many least liked vote a candidate
receives than instead of looking at how many people put you on the top
you look at how many people put you on the bottom for example.
For example 3 out of 20 voters put candidate J at the bottom of their lists.
Then our rank order in the descending, in the ascending
order of the number of people could put you at the bottom of their list.
Okay, that will be so-called Kemeny rule.
Either way, this is a special case of plurality voting.
It sounds pretty intuitive, but as we'll see,
it can be problematic and lead to counter-intuitive results.
A second clause is called positional voting, in fact,
it is a generalization of plurality voting.
Positional voting in general says that if you give me a list of candidates, okay?
Let’s say Alice and Chris and Bob, and
then I'll assign a certain score to each candidate for this list based on position.
For example the score could be if I list on the top I give you a score of 1 and
then everybody else get a score of 0.
And then I tally the score received by each candidate across all the votes.
For example, another votes could be CBA, and
another vote could be ABC.
Then I see that A received a total score of two.
Okay, so one plus one is two.
C receives a score of one, and B receives a score of zero.
And therefore A is ranked the best, followed by C, followed by B.
As you can see,
this actually realized the special case of plurality of majority voting.
But in general,
the positional voting system doesn't have to assign 1 to the top and 0 to the rest.
In fact, one other way is to say, I'll
assign M- 1 points to the top, and M- 2 points to the second one.
And then eventually,
I'll get to the bottom of the list, then I'll assign a score of zero.
Why don't we assign M, M-1 all the way down to 1?
Well because since we require each input list to be complete,
so all the candidates will show up in each list somewhere.
So the fact that it shows up at the bottom of the list really does not carry any
information.
Maybe this voter really hates this candidate,
but still it would be somewhere, say the bottom of the list.
So the bottom we say you are there possibly just because
it needs to be a complete list.
So I will give you a score of 0, and
therefore the top one receives a score of M-1.
So in this case A would get a score of 2, C gets a score of 1,
B gets a score of 0 for this input list.
Then I add up the score you get from all the input lists and
then that give me a number and
then once I get M numbers then I can rank order the M candidates.
This is what's called Borda count.
Borda is a French mathematician that started
the rigorous study of voting system.
Now, you may wonder why is voting sometimes difficult.
Perhaps this is because we're trying to compare too many candidates, okay?
When M equals 3 or more, it becomes very difficult.
Why?
Because if M were just 2, and then it's easy, if there are only two candidates,
Alice and Bob, okay?
Then for whatever method you use,
we can give a exact comparison between the two for each input.
Okay, then I can use a single scalar to represent that comparison.
Then I got N scalars from N voters, and comparing scalars is fine.
In other words, it boils down to the following.
On the real line comparing two points is always easy because
there is a full order whereas on the 2D or higher dimensional plane comparing two
points is difficult like can you say this point is bigger than this point or not?
Well it's bigger in one dimension and smaller on the other dimension.
So if there are only two candidates comparison becomes a scalar operation.
And therefore, ranking becomes easy.
But since pairwise comparison's easy, let's just only do pairwise comparison.
Okay, we'll just look at all the possible pairwise comparisons.
For example, you have the three candidates I'll look at A B comparison A C comparison
and B C comparison.
All three possible pairs.
Okay.
And if pairwise comparison between AB sets A is better than B, we'll write it down.
And if pairwise comparison says A is better than C, good, and between B and C,
B better than C.
Then, we have only one logical conclusion.
A is better than B is better than C.
That's the output of system except sometimes we are running into a problem
which we can easily identify right away.
Maybe A is better than B.
Okay, written with this arrow pointing from A to B.
And B pairwise comparison's better than C.
And C pairwise comparison is better than A.
Then that would be a problem.
Say well, is it really that easy to generate such a problematic situation?
It's actually very easy.
For example, I've got three voters and three candidates.
The first voter says, A is better than B, B is better than C.
The second voter says, B is better than C, C is better than A.
The third one says, C is better than A, A is better than B.
Alright, let's do pairwise comparison between A, B.
Well, A is better than B.
B is better than A, A is better than B.
So, A is better than B, there are two votes.
B is better than A, only one vote.
So, A is better than B wins.
All right.
So, we're just doing a majority count of the pairwise comparison.
What about AC comparison?
Well, A is better than C, but now C is better than A and C is better than A.
So C is better than A receives 2 instead of 1 vote, and
therefore C is better than A.
Now at this point
just by transitivity requirement you say we better have the following result.
C is better than A is based on A is better than B.
We really need C to be better than B, otherwise we'll be in trouble.
Well let's see, let's compare B and C.
And do we get C better than B?
B is better than C, B is better than C, C is better than A.
B is better than C actually gets two votes, so B is better than C,
not the other way around, and now we're in trouble.
Because A is better than B, B is better than C, C is better than A.
Each of the three input is transitive, yet the output is cyclic.
This highlights the problem with so-called Condorcet voting
named after another French mathematician right
after Borda who further extended the rigorous study of voting systems.
So pairwise comparison makes each compression easy but
the over all voting output maybe cyclic as this simple example illustrates.
So in the next video segment,
we will look at another case where we see not only is Condorcet voting problematic,
but all voting systems might have some problematic issues.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2019 Coursera Inc. All rights reserved.
