So in this video we're going to look at Arrow's Theorem, and prove it formally. So to begin, let's establish the notation that we'll use throughout this video. I'll let N be the set of agents. I'll let O be a finite set of outcomes, so these are the candidates that the agents are going to have preferences over. And the really important thing about O is going to be that there are at least three candidates. So Arrow's theorem is going to require that we have at least three candidates that we're voting over. I'm going to use L to denote the set of all possible strict preference orderings over O. So I'm going to be speaking here only about strict orderings. That means that agents don't have any ties in their preferences. In the end, Arrow's Theorem is going to end up telling us that any desirable social welfare function can't exist. Even if preferences are restricted to be strict. So this restriction to strictness, it is not going to be a limiting thing. It's actually going to be a string-thinning thing. We're going to end up seeing that we can't have good social welfare functions, even if preferences are stripped. I'm going to use this notation here to denote an element of the set, L to the n. So in other words, this is going to be a preference profile. A preference ordering one for every agent. And this is of course the input that our social welfare function takes. So recall that a social welfare function is a mapping from a preference profile, a set of preferences, one for every agent, to a single preference ordering which is the social welfare ordering. Going on, I'll denote with this symbol a preference, an ordering relation here subscripted by a w. The preference ordering that is actually output by the social welfare function. So as I just said, the social welfare function itself outputs an ordering. And this is going to be the ordering that gets output. Now when the input to w is ambiguous, I might actually have even more complicated notation here saying precisely which ordering it is. So in particular, this notation here is going to mean the preference ordering output by w when given the preference profile here as input. And I'm going to care about this particular when I sort of change around which preference ordering it is I talked about. Okay so now let me formally state the conditions that Arrow's theorem speaks about. The first is Pareto efficiency. So recall the idea of Pareto efficiency is that when everybody agrees on how two outcomes should be racked if it's a case that every agent thinks that a is better than b, then the social welfare function Is required also to output that a is better than b. And this is only the case when everybody is unanimous. If even one person feels differently, this doesn't restrict us at all. So formally I'll say that a social welfare function W is Pareto efficient if for any pair of outcomes O1 and O2 from the set of outcomes. If it's the case then for all agents I, outcome 1 is preferred to outcome 2 then it must be that the social welfare function also chooses O1 preferred to O2. so the next definition we need to set up errors and possibility theorem is the idea of independence of irrelevant alternatives. So intuitively the idea here is that we want to say that the social welfare function should decide the ordering between two outcomes, a and b based only on the relative rankings that all of the agents give to these two outcomes. So it should only be allowed to look at whether or not each individual agent puts a above or below b in order to decide whether a should go above or below b in the final ranking. And it should be true for every pair of outcomes. So let's look at how we say this formally. We'll say that a social welfare function W is independent of irrelevant alternatives if for any pair of outcomes, O1 and O2, and any pair of preference profiles, I'll call them pref prime and pref double prime, the following condition is true. So let's look at what this condition here says. This says, O1 is preferred by agent i in pref prime to O2 if and only if O1 is preferred by agent i in pref double prime to O2. So in other words, this is saying, when I extend it out to the for all i here, this is saying that all of the agents relatively rank O1 and O2 in the same way in both pref prime and pref double prime. In other words, if agent i likes O2 better than O1 in pref prime, it must also be. That agent I likes O2 better than O1 and pref, double pref. So the condition says that if this is true, then it must be that the social welfare function, when given pref prime as an input, makes the same relative ranking between O1 and O2. As it does when given pref double prime as an input. So again in words, what we're saying here is that the social welfare function's decision between O1 and O2 in these two different preference profiles has to be the same if the relative ranking that all the agents make between these two things is also the same in both of these two orderings. Finally, I'll define non-dictatorship as follows. I'll say that a social welfare function does not have a dictator if there does not exist some agent i for whom the following property is true for all outcomes O1 and O2. It's the case that if agent i likes O1 better than O2, then it must be that the social welfare function also likes O1 better than O2. So in other words, a dictator is somebody who simply determines the social welfare function. It's the social welfare function if it has a dictator is a function that just listens only to one of its inputs, ignores the preferences of everybody else and simply spits out the one preference ordering and that comes from the one dictatorial agent. Okay, having said all these definitions we're now ready to formally define errors there. So, what we can say is any social welfare function W, that is Pareto efficient and independent of irrelevant alternatives is dictatorial the way the proof works is as follows. So for the rest of this video I'm going to give you the proof of this theorem which I think is a really beautiful proof. Because we're able here to say something about a space of functions, a space of very complicated functions from set of orderings into orderings without knowing really what function we're talking about. We want to assume simply that our function is PE and IIA. It's Pareto efficient and independent of irrelevant alternatives. And we'll see that that assumption is enough to show that it must be dictatorial. Now to avoid sweeping this under the rug, let me again remind you that we've made the assumption that the number of outcomes is at least three. That's important for this proof. In a sense, really it's important because independence of irrelevant alternatives doesn't really mean anything in the case of only two agents. There can't be an irrelevant alternative if there are only two things to be compared. So we're going to need to make use of the fact there are at least three outcomes, as you'll see in the proof. So let's get started. So we're going to proceed in four steps. We're going to end up proving four intermediate claims which will eventually get us to the proof that this social welfare function, which we assume is both Pareto efficient and independent of irrelevant alternatives must also be their tutorial. So, first of all, here's what I want to claim. Sounds like a strange thing to claim but it will get us where we want to go. If every voter ranks some outcome be, either at the very top of his preferences or the very bottom of his preferences. Then it must be that the social welfare function also puts b either at the very top or at the very bottom. So let me draw kind of a picture of this. So think of these as being a bunch of preferences from all the different agents. And what I'm saying here is that each agent has to put b either at the top or the bottom. It doesn't matter which. But they have to put it either at the top or at the bottom. And what I want to claim is that the social welfare function then has to do the same thing. It either has to go here at the top or it has to go here at the bottom. So let's see why that would be true. So the way we're going to do this is we will consider so arbitrary preference profile that satisfies this condition. Every voter rank puts b either at the very top or the very bottom of their preferences. And let's assume for contradiction that the claim that we just made is not true. Instead that we don't have b here, but we've got it somewhere in the middle. Well, in that case there must be some a and some c, where a is higher up in the ordering for the social welfare function and c is lower down in the ordering. That's what it means to be in the middle. There has to be something about that and there has to be something below it. So let call those things a and c. Well, now let's modify our ordering. So that every voter moves c just above a and his preference ranking. So, all of these rankings, we haven't drawn it, but we have c's and a's in here somewhere because everybody is ranking all of the different order, all of the different outcomes in their orderings. So, let's modify whatever this ranking is by constraining being where c and a go. So let's imagine that a was in all of these different places and so on. Let's just move it so wherever c was before, let's just stick it right above a in the ordering and leave everything else unchanged and let's call that new ranking pref prime. So now we're going to start using these definitions that we've assumed about the preference ordering. So we know from independence of irrelevant alternatives that in order for this to change or for this to change, these two facts, which we've assumed are true here. The pairwise relationships between a and b and the pairwise relationship of b and c will after change some of the agents here. However notice the b occupies the position of all the voters. And that means that c can be moved above a moving from pref to pref prime without changing any of the pair wise relationships between c and b and between a and b. And thus we can conclude that in the preference profile for pref prime, it's also the case that these two things are true, right? We assume that those two things are true in pref for contradiction, and because nothing has changed we can use IAA to say that they must also be true for pref prime. And from transitivity we can just, the fact that we're getting a strict ordering here. We can also conclude, therefore, that a must be ranked above c in the social welfare function. However, look at the ordering that we've actually made here. Note, you will recall that we put c above a in every agent's prefenture. Wherever a was, we stuck c just above. Right? Well, recall that Pareto efficiency says that any time all of the agents feel exactly the same way about something, the social welfare function has to also feel that way. Here, all of the agents think that c is better than a. And so Pareto efficiency requires that we would have c above a here. But in fact we have the opposite that a is above c. So that gives us a contradiction. So what does this all tell us? What we've established is what we have up. That if every voter has some outcome b at an extremal point in his preference list, it most be that goes into an extremal point of the social welfare function as well. Well so far that sounds fine and it doesnt seem like that is big trouble lets keep going and see what happens. This is the crucial step now. So now I want to claim that there exist some special voter. And I'm going to give that voter a name. I'm going to call him n*, who is extremely pivotal and in the following sense, I want to say that he's able to change his vote at some preference profile so there exists a preference profile where if he changes his vote, he can move a given outcome b from being at the very bottom of the social ranking to the very top. So there exists at least some circumstance in which some person is able to make a really big difference to the social choice. He can move b from being the very least preferred thing to the very most preferred thing. Let's see why that would be true. Well, let's consider preference profile, pref in which every voter ranks b last and in which the voters preferences are other wise completely unconstrained. By Pareto efficiency it must be the W also rates b last. Because every pair wise relationship between b and something else has that something else being preferred to b and so b has to be at the very bottom of the social ranking. So now I want to basically let voters. So I have some ordering of the voters from 1 to n, and I'm going to let them successively modify. So let me draw this, so I've got all these different rankings here. From different voters and I've got some social welfare ranking here. So we start out with everything at the bottom. And we conclude from PE that b must be at the bottom here too. So then I say let me, one at at time, take a voter and take b off being at the bottom and put it up at the top, and let me see what happens. Now, when I do this there has to eventually be a change. It can't be that I do this for everybody and b never changes. Because once I've done it absolutely for everybody, and I've got b at the top all the way, Then Pareto efficiency again is going to constrain me and it's going to say b has to be at the top. So I know there has to be somebody who in making these movements causes something to change at some point. So I'm going to give the name and star to the first voter in this apparently, arbitrary order in the voters that I've got here, whose change causes something to become different. So I'm going to get the first guy to move b from the bottom to the top and I'm going to look at what happens here, and if nothing changes, I'm going to have the second guy do it. I'm going to keep working my way through until at some point b moves somewhere, something different happens, and then I'm going to say all right, I found my n*. That guy who made a difference is n*. So now let me give some names to preference orderings because I need them for the rest of the proof. So I'm going to denote by pref one. The profile just before n* moves b. And I'm going to denote by pref 2, the profile just after n* has moved b to the top. And let's note that in pref 1, we have b at the bottom in the social welfare ordering. So our social welfare ordering here has b at the bottom. And in pref 2, b is in some different place than it was before. And every voter ranks b at either the top or at the bottom. Right, so notice here we have b's at the top for everybody. Here we have b's at the bottom for everybody. And here again, we have b's at the top, and b's at the bottom. But what's changed is n*. So here's the one guy whose actually moved something. And by our argument in step one, both of these profiles have b in extremal positions and so it must be that the social welfare function also puts b in an extremal position. And because we've defined n* as the person who causes b to change. It must therefore be in this profile pref 2 that b is at the top. And notice that that means now that we've proven the thing we set out to prove that there exist some voter who is able to change his vote at some profile, at this profile, in order to move some outcome b from the bottom to the top. Okay. Let's get to step 3. So now, I want to reason about the same guy, n*. So recall n* has special power over outcome b in this very narrow way that there exist this one special profound that we constructed, pref 1 where he can move b from bottom to the top, well, now I want to reason about the same guy and I want to claim something that all of the sudden seems very strong and he's a dictator over any pair ac that doesn't involve b. What does that mean? It means that the social welfare function must make every decision between any pair ac where I’m using those variable mean just to denote anything that isn’t b. Simply by listening to what n* effects. So if n* likes c better than a, the social welfare function will as well and it just doesn't matter what anybody else thinks. So that's what we want to claim here. So how does this argument work? Well, so we're going to begin by choosing one of the two elements from the pair and let's call the one that we choose a. So now I'm going to construct a new preference profile, pref 3, which differs from pref 2 in two ways. First of all, I'm going to move a to the very top of n*'s preference ordering, leaving everything else unchanged. So I'm going to take a, wherever it was here and I'm going to move it up to the top. You'll notice by the way in these pictures, if you can read it, some of the variable names are bold and some of the variable names are not bold. The ones that are bold are things we've made explicit assumptions about and the things that are not bold are given for illustrations but we haven't actually assumed. So if you can make it out, you'll see here a is not bold because we haven't assumed anything about where it goes. And over here a becomes bold because now we've assumed that it goes to the top of n*'s ordering. All right, so anyway we're making two changes. So our first change is to move a to the top of n*'s ordering. And that means that for n*, a is most preferred, and a is preferred to b, which is preferred to c because a and b are both at the top. So wherever c is, it must be further down. And second, we're just going to arbitrarily scramble the relative rankings of a and c for all voters other than n* without changing the position of b which is always extremal. So, we're just going to kind of move around a and c and some kind of arbitrary way but we're going to make sure that we still leave b in the same place for everybody else that are always was. All right, so that's our preference profile pref 3. Now notice that in preference profile pref one we had that a was preferred socially to b. And the reason the we can conclude that is that we know that b was actually at the very bottom of this social ordering so everything was preferred to b and so a in particular it must have been preferred to b. Now when we compare pref 1 to pref 3, the relative rankings between a and b are the same for everybody because b is in the same extremal position for everybody except for n* who moves b. But we've then changed it to put a above b. And so It's the case that this guys over here have b above a in both cases. This guys have a above b in both cases and n* also has a above b in all cases because here we actually move a to be above b. So from this fact we can conclude that in pref 3 it must be that a get socially preferred to b. Because by independence of variety of alternatives the social choice between a and b can only depend on the relative rankings by the different agents. And we've just seen those relative rankings are the same in pref 1 and and in pref 3. Now we're going to say something similar comparing pref 2 and pref 3. So in pref 2, we had that b was socially preferred to c, because we know that in pref 2, b was at the very top of the social ordering. And so wherever c was, it was somewhere further down. And in a similar way to as what we argued before, the relative rankings between b and c are the same in pref 2 and pref 3. Let's see why that is. So we have for all the agents other than n* b is in the same extremal position in both cases. So wherever c is, it's ordering must be the same. And for n* things are a little bit different. n* used to have b in the very top position here. And here he has b in the second position, but the thing above it is a. So in both cases wherever c is, it's somewhere downstream. Because the relative rankings are the same in both places, it must be that the social ordering again is the same. So here we have that the social ordering says b is higher up than c. So here it must also be that b is higher up than c in the social welfare ranking. So, using these two facts that we've just established, and transitivity, we can draw the conclusion that the social welfare ordering must give us that a is preferred to c in pref 3. Okay. Well, why do we care about that? Well, let's construct one more preference profile. I promise this is the last one. Pref 4, by changing pref 3 in two ways. First of all, let's arbitrarily change the position of b in every voter's ordering, or keeping all of the other relative preferences the same. So we're going from pref 3 to pref 4 by taking b and just kind of sticking it somewhere else. And but we're not going to move it on any of the other relative or preference ordering. Secondly, we're going to move a to an arbitrary position in n stars ordering with the constraint that a is kept higher than c. So let's look at that. So here we have a at a really special place. Here we're just going to stick it further down to here. But we're going to make sure that it's still higher than where c is. And what I want you to observe now Is that all voters other than n* at this point have completely arbitrated preferences. Because the only things that we had assumed about those voters ever before was the position of the b's. Right? Those are the only things that we had bold in those figures because that all we assume. All these other stuff here is just completely arbitrary. Furthermore n* also has arbitrary preferences, except for the fact that a is preferred by n* to c. Now what do we do with pref 4, well in pref 3 and pref 4, all the agents have the same relative preferences between a and c right. So we've moved things all around, but we done it in a way that still has all of the agents in three and four, having the same preferences between a and c. And that, and we know in pref 3, the social welfare function has to rank a higher than c. So, by independence and with all the alternatives, it must be that the welfare function also ranks a above c in pref 4 But that's pretty interesting, because the only thing we've assumed about pref 4 is that a goes above c for n*. And that means that we've established the thing we wanted to establish, which is that n* is all by himself able to determine the relative ranking between a and c, regardless of what everybody else says. So that makes him a dictator over the pair a, c. Well, clearly I'm going to want eventually to say n* is a dictator over everything. Not just over a, c, but also over pairs a, b. Pairs that do involve b. So, this turns out actually to be very easy to show. So, let's consider some third outcome c. So, I'm claiming now that n* is a dictator over pairs a b. So let me think about some third outcome, c. Well by the argument that I already made in step 2, there is some voter, let's call him n** who is extremely pivotal for c, right? So I can make that same argument that I made before where c starts at the bottom for everyone and social ordering has it at the bottom, and then I started moving things to the top until something changes and eventually I can see that it changes there and whoever the guy is, whoever made a change, let's call that n**, and in principle maybe this is a different guy. There's nothing in step 2 that says it has to be the same person. It just says there's nothing special about b that made it the thing that had to move around. It would have worked for anything so it'd work for example for c. Well, now, I can use the argument in step three to say that this guy that we've just identified n** is a dictator over any pair, alpha beta, which doesn't involve c right, I'm just basically running through the arguments I had before but, renaming the variables. So, of course, a b is an example of such a pair alpha beta. Right, so by this argument there's somebody who's a dictator over the pair a b. So what I want to show is that that person is n*. I might worry that there are different dictators for different things. But notice that I've already observed that n* is able to affect the way that W relatively ranks a and b. For example, we saw this in the movement from the profile pref 1 to pref 2, right? When we had this profile where b was at the bottom. Whoops I'm doing that wrong, let me do that again. We had this ranking where b was at the top for a couple people, was at the bottom for n*. And for the bottom for other people. And then we move it up to the top. We saw that that caused the social welfare ordering to take b and move it from the bottom to the top. And that means that n* is able to affect the relative ranking between a and b, because wherever a is, it's somewhere in the middle here in the social ordering. And so the relative ranking between a and b got affected by what n* declared here, by this change that only n* made. And what I've now just argued is that there has to be some dictator over a b pairs. And so if n star was able to make any difference to a b pairs, he has to be that dictator. Because it's not possible to have both a dictator for a, b pairs and a different person, whoever makes a difference, to the a, b ranking. So that means that this n** and n* must be the same agent. And that means n* is a dictator over everything. N* is just a full dictator and that means no matter what social welfare function I have, if it's Pareto Efficient and if it's independent of a relevant alternatives, it has to be some dictatorial social welfare function. Which means the only freedom you have in such a social welfare function is the freedom to decide which person is the dictator. And if you have any other social welfare function which isn't the tutorial, then it must be that it's either not Pareto efficient or it's not independent of irrelevant alternatives, and that explains why we have voting systems that cause things like the number of votes Ralph Nader gets to effect who wins the election in Florida. That's a case of not being independent of irrelevant alternatives. And that's usually the axiom that we relax, because not being Pareto efficient would be really terrible. That means If everybody all agrees about something, sometimes the social welfare function would do something different anyway. That's something that we're usually not willing to tolerate. And so, the practical consequence of Arrow's theorem is that we end up having social welfare functions that are not independent of irrelevant alternatives.
