Hi folks this is Matt. And so we're talking a little bit about social choice theory now. And I'll introduce you to voting schemes and social choice functions. And in terms of the overall idea, what we're looking at now is we're looking at a setting where a societies making decisions. And we've got a bunch of different individuals who have preferences and that we want to aggregate those, right? So we've got a set of voters, a set of people. They have to make a decision and we want to take into account the preferences of the different individuals. So we're looking at a setting where we have a set of outcomes or a set of alternatives, so something we're going to choose over. So it could be a set of political candidates. It could be that we're trying to choose a set of new members for a society, that we're trying to decide on a new tax rate for a government. We've got a whole series of different questions, and there's possible outcomes that are there. And the people, the voters, the agents, the people in the society have preferences over these outcomes. So in this setting we're going to look at, for now, people are going to have preferences. They'll be able to tell you this is my favorite outcome, this is my second favorite, my third, my fourth, and so forth. And what a social choice function is going to do is take the preferences of the individuals and as a function of those tell us which outcome are we going to choose. So it's going to be a mapping from profiles of preferences to a particular outcome. And generally what we're going to be interested in is sort of which ones, which of these social choice functions would we like to have. Now in the course we're going to eventually have to talk about incentives. Because people, in a setting where we're voting for a bunch of candidates, it might be that I actually, and you ask me which one is my favorite candidate, I might not tell you truthfully which is my favorite candidate. I might vote for somebody else if I think my candidate has no chance of winning the election. So, people might try and manipulate the voting scheme by changing how they represent their preferences. They'll say, okay actually I would like to vote for this person, not for this other person. So, we'll have to very carefully think about how the mapping from preferences into alternatives eventually is achieved. But for now what we are going to do is we are just going to look at the function itself and say okay, if society, there's a whole set of ways in which these things can be mapped. And then later we will ask which ones can actually be achieved or how they can be achieved or so forth. Okay. So given is a set of preferences or outcomes. Sorry, outcomes or alternatives. So that's going to be set O. And people are going to have preferences over these. And we are going to represent these in a very simple form. Generally the agents are going to have strict preferences over these things. We will eliminate indifferences that will make our life easier. So that's going to be represented by these relationship which is going to be generally linear orders. So we're look at situations where people are not in-different. So they'll be having linear order or what's known as a total order over the alternative. So, they can tell you which is my favorite, which is my second favorite, and so forth. So, given a finite set, I can just list them in order. And so a linear order, the set of linear orders will be denoted by L and there's going to be the binary relations which are total and transitive. What does that mean? That means if you look at any two alternatives, any two outcomes a and b that are not equal to each other. Then either a is prefered to b, or b is prefered to a, but not both. So, it means first of all I can tell you which of the two I prefer, and I'm not indifferent. Okay, so one part about a linear order is it's going to be a strict ordering, I'm never going to be indifferent, and for any two alternatives I can always make a comparison. I can't say I don't know, I'm not sure, I'm not undecided. All these voters are decided they can tell you exactly how they rank everything, and, preferences are going to be strict. They're also going to be transitive. So if I like A better than B, and B better than C, then I'd better like A better than C, okay. So we've got a nice transitive ordering, that's going to be a linear, orders total, and transitive. Sometimes we will also be working with non-strict preferences. So, it could be that someone is indifferent. So, then we will allow for transitivity and completeness you can make a comparison between a and b. So, a could be weakly prefered to b, b weakly referred to a. And you could have both relationships holding at the same time, which means you're actually indifferent. So sometimes it'll be better to work with non-strict relationships. And in fact, when we're thinking about how society decides on a relationship, it might mean, it might be that everybody in society has a strict ranking, but then society as a whole ends up with a weak ordering. So we'll offer for non-strict preferences as well. Okay, so those are going to be preferences. Those are the object that we're going to assume people have, and then based on those we try to make a choice for the society. Okay, so that the formal model then in terms of the way that will work through social choice functions. We've got a finite set of individuals, a finite set of outcomes O, and we'll consider the linear orders on the outcomes the set L. And also the non-strict version. So social choice function is going to be a function that maps from the set of preferences, weak preferences into outcomes. So if you tell me what everybody thinks in this society in terms of their rankings, I'll pick an outcome. So social choice function tells you as a function of what people believe in terms of their preferences of different outcomes. What's the outcome we're going to choose? A social welfare function or a social welfare ordering is going to be the same kind of object except, that instead of just picking an outcome, what it's going to do is actually, say, give you a full ranking of outcomes. So society is going to rank outcomes, and that's different than just picking an outcome. So it might be that we've got three outcomes, A, B, C, and we ask people what they're preferences are over these things, and we're going to pick one of them. So we just need to make a choice for who's going to br our president. Alternatively we might actually want society to be able to rank these objects. Okay, so often when you look at rankings of organizations like rankings of universities or rankings of schools, we'll take a whole series of different people, say here's my ranking and then we aggregate those up and say okay, here's an overall ranking. And there might be ties, okay. So we might have people express their preferences or their rankings and then society might end up saying here's society's rankings. Okay, and that's different so sometimes we're picking outcomes and sometimes we are picking a ranking. Okay, so what are some examples of these things? The most basic and most widely used is what's known as plurality rule. What's plurality rule? That's just picking the outcome that is most preferred by the most people. So everybody just gets one vote they get to express it and generally if we'll assume that people are truthful we assume that they express who's their favorite. And then the social choice function just picks the outcome that is most preferred by most people. So that's known as plurality. Cumulative voting, that's another interesting voting role. You give people multiple votes so you get a set of votes and you can give your votes to different candidates. So if there's four different candidates, I can assign several votes to the first, two to my most preferred and then one each say to might second and third, and then we'll count up and find who has the most votes. So now I've got multiple votes I can express. Approval voting is another interesting voting rule. And that's one where you can basically just express whichever outcomes you like and not express which ones you don't like. So this is often used in say, electing new members to a club or electing new members to a society, something like that, so, like a hall of fame. You can list which candidates you think should be included, and then give zeros basically to the ones you don't think should be included. So you just vote for the ones you think should be included, not for the ones you don't. And then there's some method of counting up, and either picking just one, if we just want kind of one candidate, or picking several if we're going to pick memberships or some threshold. It's less known as approval voting. So, these are different methods of making choices, and they're going to have different properties. A set of other voting schemes, based on more kinds of information ranking. Plurality with elimination. So, what's known often as instant run off, or single transferable vote, or transferable voting goes by a series of different names. And in that case, what one does is you actually express your whole preference ordering. And so you first, we count everybody's favorite outcome. So, think everybody voting for their favorite outcome. And if some outcome has a majority, it wins. So if somebody gets more that 50% of all the votes then it wins. But if nobody has a majority; so if we have say three or four outcomes, it could be that we have some candidates that are tied or some no candidate got more than majority. And so what we do then is look at the outcome with the fewest votes and eliminate it. Okay, so you knock out the one that has the fewest votes. You may need a tie-breaking procedure if there's two that have the fewest votes. So knock the one with the fewest votes out and then revote. So now we've only got a subset of the candidates left, everybody expresses their favorite out of this. If somebody has a majority, that's the winner, if not, knock another one out, okay and so forth. And actually there are rules, there's variations on this. The French presidential election works this way, where you first vote, and if nobody wins enough votes in the first round, there's a runoff among a subset of candidates. There's a number of systems that work this way. Okay. Another one is very interesting and widely used. What's known as Borda Rule, Borda Count. How do we pick outcomes under this? In this case, you get to give your ranking. And so you're assigning a single number to each outcome and so generally, suppose I have a ranking of I like a better than b better than c better than d. If we had four different possible outcomes, what I would give is I get to give a score of three to my preferred, 2 to my second preferred 1, 0, and so my most preferred gets three votes, this gets 2, 1 and 0. And now when we look across different individuals we add them all up. Right? So somebody else has d, b, a, c. Somebody else has b, c, a, d etcetera. Right? So in this case, d gets 3, 2, 1, 0. B gets 3, 2, 1, 0. So, b gets three votes here, two votes here, two votes here. B is going to have seven votes overall, and so forth. So Borda count will get numbers for each one of these things, then we'll count up this total number of numbers, and the winner is the one with the most, the highest score. And this is actually going to produce a social welfare ordering, right? It's going to tell us what's which outcomes are in first place, which ones are in second place and so forth. So it's actually going to rank all the outcomes. And so Borda count gives us an overall ranking and actually this is used in a lot of sports evaluations. So in the U.S. for ranking basketball teams or football teams and different pools. A series of different situations where you're trying to rank alternatives, you can give votes and then aggregate those up and produce a ranking. Another one that's very interesting, successive elimination. You order the alternatives, and then you first have a vote over the first two. Do we prefer a or b? The winner of that, gets matched against c. The winner of that, gets matched against d. The winner of that get's matched against e, and so forth. So you order the alternatives, do a pairwise vote and then do this. This actually works often in legislatures where we could imagine that there was a bill introduced then somebody amended the bill, then somebody put out an amendment to the amendment. And what we would is first vote whether we do the amendment to the amendment or just keep the amendment. And then the winner of that gets put up against the bill. Do we want that versus the bill? And then finally we ask bill, no bill. So that's voting by successive elimination and is often used in many legislative processes. So you can see there's many different ways of voting and choosing alternatives. And these are all going to have different properties, and that's what makes this area so interesting. If just not a simple way to do things there's many different ways to do things. They are each going to have plusses and minuses and so they could be trade offs involved. The one important concept that we'll be talking about little bit in the future is what's known as Condorcet consistency. And the Marquis de Condorcet defined this centuries ago. And the idea here is looking for a candidate that's preferred, that beats every other one in a pairwise majority. So if you look, if we've got a versus b, a's preferred to b by majority. If we look at a versus a, a's preferred to c by a majority. In a to d. So if a beats every other alternative, it has a majority of votes versus all other ones, then that's known as a Condorcet winner. Okay? So, it's something which majority prefers to any other alternative. And when those exist, then we'll say that a rule is Condorcet consistent if a social choice function picks a Condorcet winner when there is one. Okay? So that's a nice property that's sometimes desired of a rule. And there can be a cycle. So for instance, if we had three alternatives, person one likes a, b, c, person two likes b, c, a, person three likes c, a, b. Now you can see here, a is prefered to b by a majority. Two people prefer a over b. B is preferred to c by a majority, but c is also preferred to a by a majority. So, we get a cycle here where we end up with majority rule. We have a beating b, but b beating c and c beating a. So, we can begin to see that there's going to be problems with voting rules, in terms of making sure that everything is, Coherent in terms of the way this society is going to end up making a choice. And Condorcet Cycles are going to be an important part of that. It's nice if we have a Condorcet winner, but they don't always exist. So the next thing we'll be talking about is some of the properties of voting rules in more detail and then some more general results on these things.
