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.
