0:00

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.

Â 0:52

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.

Â 2:38

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.

Â 4:55

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

Â 5:29

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.

Â 6:19

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.

Â 7:21

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.

Â 8:04

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.

Â 8:54

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.

Â 10:47

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.

Â 13:29

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.

Â 14:02

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.

Â 15:01

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.

Â