Arrow's Impossibility Theorem | Infinite Series

Viewers like you help make PBS (Thank you 😃) . Support your local PBS Member Station here: to.pbs.org/don...
The bizarre Arrow’s Impossibility Theorem, or Arrow’s Paradox, shows a counterintuitive relationship between fair voting procedures and dictatorships. Start your free trial with Squarespace at squarespace.com... and enter offer code “infinite” to get 10% off your first purchase.
Tweet at us! @pbsinfinite
Facebook: pbsinfinite series
Email us! pbsinfiniteseries [at] gmail [dot] com
Previous Episode
Voting Systems and the Condorcet Criterion
• Voting Systems and the...
Written and Hosted by Kelsey Houston-Edwards
Produced by Rusty Ward
Graphics by Ray Lux
Made by Kornhaber Brown (www.kornhaberbrown.com)
Additional Resources
Networks, Crowds and Markets:: www.cs.cornell...
Original Paper by Kenneth Arrow:: web.archive.or...
Different voting systems can produce radically different election results, so it’s important to ensure the voting system we’re using has certain properties - that it fairly represents the opinions of the electorates. The impressively counterintuitive Arrow’s Impossibility Theorem demonstrates that this is much harder than you might think.
Thanks: Ben Houston-Edwards and Iian Smythe
Comments answered by Kelsey:
Johan Richter
• Voting Systems and the...
Nat Tuck
• Voting Systems and the...

[@seanm7445]

I feel these videos would be even better without colourblindness.

[@eyescreamcake]

The Wikipedia article on Single transferable vote uses food emojis. :D

[@TalysAlankil]

I assume they chose colors because they thought it would be easier/less off-puting than the usual demonstration for this theorem, which involves representing each candidate by a letter. Because that looks like algebra and a lot of people LOATHE algebra (probably without any good reason beyond "my high school math teacher sucked")

[@pierrecurie]

She should have used simple shapes - square/circle/etc

[@skebess]

I like algebra, it's fun.

[@rachelzimet8310]

As with voting, there are problems with any system - some people have trouble seeing the difference between such shapes.

[@evanbelcher]

Supplementary explanation for anyone who might be feeling lost after watching: I think what they did a very bad job of is explaining where they got the ballots that they used. There was only one real set of "randomly generated" (made up) ballots. Everything else was determined from that. What they called "test cases" were not randomly generated. They were completely predetermined. They were an exhaustive list of permutations where some number of voters had purple first and the rest had purple last. The overall rankings of the test cases WERE made up. We knew that in the first test case when everyone rated purple last, purple would HAVE to be last (unanimity). Similarly, we knew that in the last test case, purple would HAVE to be first. Therefore, somewhere in the middle there, purple would have to switch from last to first. (This is of course assuming that they can't be anywhere in-between. They set this up as a homework assingment and said "figure that part out yourself" but given how essential it was to the proof, they REALLY should have explained it outright) But again, purple has to switch from last to first somewhere in the middle. In the video, we are told that the shift happens from round 2 to round 3. Again, this was made up. It could have just have easily been between any other rounds, it just would have implied a different voter as the dictator. This is what ensures that the proof is a general one. The "election results" that are presented right after this are also made up. Presumably, they were contrived to be convenient to use in the logical steps to follow. Just because it's convenient doesn't mean it's not a generalized proof, though. In this setup, voter 2 IS the dictator so any set of election results would ultimately show this conclusion. It just could be more difficult to prove with a different set of election results. From this, there's just a lot of logical inferences, all of which are difficult but valid. I had to listen to just about every sentence in the proof part of this video two times or more. The proof is all there, just not explained super clearly in my (and obviously a lot of other) opinions. Good luck!

[@MustSeto]

I also think they should have better explained how they made the modified ballots. For each voter other than the suspect, move the polarizing candidate into the same position they are in in the two test elections for that voter (don't move any other candidate). Then pick two candidates other than the polarizing candidate. Move the polarizing candidate anywhere between them on voter2's ballot (again, don't move any other candidate). In fact I think that for the "election results" they shouldn't have given anyone except voter2 explicit rankings to make it more obvious that voter2's rankings are the only ones that matter. They do mention that they leave things out too. For example, they say you can pick _any_ two candidates. You can't. Neither can be the polarizing candidate. Proving that the polarizing candidate must be the in same place in the final rankings as in the dictator's ballot takes a little more. Some might also wonder about a method where the polarizing candidate can switch between last and first _multiple times_, though that's pretty easy to prove this cannot pass IIA and Unanimity. Suppose a method does this. Use the pair of elections around the first switch as tests, then use an election where it switches back as the "election results" of another election. You can prove that if the method really passed IIA and Unanimity, it would have to give different results (the results of the dictator).

[@florencjaaarts7769]

This helped me a lot, thank you!

[@IFORBIDANYDATACOLLECTIONTOALL]

Exactly! Rigged just like the real thing

[@realtimestatic]

bro the homework to the watcher makes no sense to me. wtf is wrong with them

[@twistedsim]

We could vote for a voting system, then vote. But first, we need to vote on how to vote the voting system....

[@PaulZeroSolis]

And then we must vote the voted upon voting system in using the voted upon voting system's method of voting.

[@marmorealcandors]

And then we have fractals.

[@DrEhrfurchtgebietend]

This is actually the problem we are having in British Columbia right now

[@b43xoit]

Use all voting systems to vote on the voting system. Then if they produce different winners, discuss. If there are only two winners, have a runoff.

[@taylorford1689]

@@b43xoit But isn't that, in itself, a voting system? Who's going to vote on whetever that is good or bad?

[@DaBTEDI]

i dont understand voting with colors.. maybe you could use animals like lions... just saying

[@recklessroges]

iswydt CGPG

[@columbus8myhw]

("I see what you did there, C. G. P. Grey)

[@ahmedshaharyarejaz9886]

PBS doesn't get enough Thanks for their free content.

[@pierreabbat6157]

Let's say that the three candidates are red, green, and blue, and that green is the polarizing candidate. Suppose that, in some election, the outcome is R>G>B. By IIA, you can run the election on just red and green, and green loses. And you can run it on green and blue, with the same voters preferring green as before, and green wins. By unanimity, there are at least one voter who prefers red to blue, at least one voter who prefers green to blue (and also to red, since green is polarizing), and at least one voter who prefers red (and blue) to green. Switch the preferences of all voters who prefer red to blue so that they prefer blue to red, without affecting whether they rank green first or last. By unanimity, blue is now above red. But by IIA, red is still above green and green is still above blue. R>G>B>R>G>.... Contradiction.

[@nomanmcshmoo8640]

What I absolutely LOVE about Infinite Series is the incredibly esoteric topics that come up as compared to many of the pop-sci channels. I.S. is definitely one of PBS' best short format video series.

[@florencebacus6012]

Proof that a polarizing candidate must be ranked first or last: Suppose A is a polarizing candidate who is not ranked first, so that candidate B is ranked ahead of A. Let C be a third candidate. Our goal is to show that C is ranked ahead of A for any ballot. Consider a ballot which I will call Ballot 1. Since A is polarizing, for any given voter, this voter either prefers A over B and C (in the case that A is first), or she prefers B and C over A (if A is last). Equivalently, for every voter, A > C iff A > B, and A

[@WoodenHorst]

An easier argument that proofs it: You just need IIA, unanimity is not necessary. Let's say we have candidates A,B,C. If candidate A is polarising, that means comparing only B and A will look exactly the same as comparing C and A due to IIA. Wherever B is higher than A, C must also be higher than A and vice versa, because A is either first or last. That means in the overall ranking, either B and C are higher than A or both are lower. Since this holds for any number of candidates, A is either first or last.

[@eclipz905]

If you plan on further discussing desirable voting system qualities, please consider Bayesian Regret. It doesn't get much attention, but you could make a strong argument that regret is more important than any collection of the standard criteria.

[@antistone349]

Isn't regret minimized in a dictatorship? (Guarantees no one would have voted differently due to knowing others' votes.) That would seem to argue it is not BY ITSELF "more important than any collection of the standard criteria."

[@eclipz905]

Antistone I should have been more clear what I was meant. rangevoting.org/BayRegDum.html Bayesian Regret is a measurement of the dissatisfaction generated by a given voting system. This value is determined experimentally, using simulated elections. Each voter is assigned a satisfaction score (0-99) for each candidate. For each candidate, summing their satisfaction scores across all voters can provide a utility score. Voters then vote according to their preference (simulations can include honest voters, strategic voters, or any mix of the two). The election results are then tallied to produce a winner. The regret score for the election is determined by taking the difference between the highest utility score, and the utility score of the candidate that was actually elected. This process is performed millions of times with varying input data to determine the range of scores for each voting system. To answer your question: no, a dictatorship system does not result in low regret, because there is nothing stopping the dictator from electing a candidate with a very low utility score.

[@wrightn9]

How did we determine that purple switched from last in round 2 to first in round 3? I know that the challenge was that it had to be either last or first, but my question is: why did the switch happen in round 3.

[@MustSeto]

The idea is that we don't know the specifics of the voting method, but we do know some of its properties, which meant we knew the winner must have switched to Purple at some point. It could have been at any point, but for an example they made it switch there.

[@__-cx6lg]

Nicholas Wright It didnt; that was just an exampe. She could have just as easily said the switch happened in round n, where 1

[@jfb-]

It has to switch at some point, 2 was just an arbitrary example.

[@memoryerror]

But in round 3 purple is last not first?!?

[@MustSeto]

Purple was the winner of round three. 7:14

[@ceramicsky14]

That was a lot to take in. Definitely going to rewatch like five more times!

[@pbsinfiniteseries]

Agreed! There's a lot of steps, but luckily, they're individually pretty manageable. I also recommend checking out the book linked to in the description. It's the main resource I used for the proof.

[@TimJSwan]

If 15% if people vote for chocolate, 45% for vanilla and 55% for strawberry, you might think strawberry wins and chocolate loses. That's not the case. It's because plurality voting doesn't take into account enough information. The people who wanted vanilla might have had chocolate last time but greatly prefer it to strawberry and the same could be true for the people who wanted strawberry first. So, chocolate could beat out vanilla 55% to 45% and strawberry 60% to 40% with those same voters.

[@Airhornsman]

I think there's a mistake in the voting diagram at 6:30 - between rounds 4 & 5 voter 2 changes the order of R > G > B to G > B > R

[@earthbjornnahkaimurrao9542]

4:30 - wow plot twist. I was under the impression that Arrow's Impossibility Theorem applied to all voting systems. I am happy to learn that it doesn't and that the Cardinal Voting System may be superior to ranked voting systems.

[@Sui_Generis0]

Yeah read some sen(1970) but interpersonal comparison is debated

[@ivarangquist9184]

The problem with Cardinal Voting is that most of the time, you don't vote according to your opinion. You are being encouraged to polarize your ratings to the maximum, which basically makes it into a binary voting system (in lack of a better name)

[@Xx_BoogieBomber_xX]

@@ivarangquist9184 That's why Arrows said that he supports a cardinal voting system where people can only vote on a scale from 1 to 3 or 1 to 4

[@ccederlo]

​@@ivarangquist9184 thankfully, STAR Voting was invented in 2014 to mitigate that problem among others!

[@contingenceBoston]

In my unimportant opinion, the example ballots might be easier to follow if each color was accompanied by its own shape.

[@DrEhrfurchtgebietend]

Colour blind guy agrees

[@corcorandm]

So, for 1 Million dollars you'd get punched in the face? We all have our limits. I think my get punched in the face is more like -100,000

[@arthurbernardocoopi6540]

corcorandm The scale is not linear, i don't think you'd be happier winning 10million dollars for no reason than winning 5million dollars than, say winning 4million dollars over losing 1million, for no reason.

[@kandrc]

The scale changes with circumstances. When I was an undergraduate, I'd have taken $10 for it. As a graduate student with a nice fellowship, it would have been closer to $150. And today, with a high-paying career and a wife monitoring the bank account, I'd do it for $5.

[@Noah-fn5jq]

anything is legal if no charges are pressed. Personally I like to see it as would i rather pay someone 25$ or get punched in the face. By those standards punched in the face = -350.

[@Noah-fn5jq]

Yep. Many people would do that. Just call it a "social experiment" and you might get to get a tax break since it is work related... although that might make you susceptible to worker abuse lawsuits.

[@alobko1]

"You can focus on the important things like how to pack spheres in a 9 dimensional space" best Squarespace plug *ever*.

[@lawrencetchen]

Orange was definitely the polarizing color.

[@omarasad7439]

Please bring this channel back

[@pierrecurie]

I can break this theorem - everybody ties! (and is a winner and loser at the same time) 1) no dictator - nobody's opinion matters 2) IIA - no candidate matters 3) unanimity - if A is ranked higher than B by everyone, B cannot be ranked higher than A in the end

[@SmileyMPV]

Proof of challenge problem: Let A be a polarizing candidate and assume it is not ranked first or last. So there exist B,C such that B>A>C. We can swap B and C whenever B>C and get a new input. By unanimity, the new output has C>B. But by irrelevance of independent alternatives, the new output has B>A>C. This contradict the transitivity property of ordering. Therefore polarizing candidates must always be ranked first or last.

[@DerToasti]

please cover cardinal voting systems!

[@XepheroiX]

can you do a video on cardinal voting

[@michaelsommers2356]

You'll have to wait until they elect a new pope.

[@b43xoit]

@@treyforest1999, cardinal voting will defeat the two-party scam.

[@TheManxLoiner]

Challenge question: Let P be a polarising candidate. Suppose for contradiction that P is not in first and not in last. This means there are candidates A and B such that the group ranks A above P and P above B. Now imagine changing all the votes as follows: --If a voter preferred B over A, leave their vote unchanged. --If a voter preferred A over B, swap around the positions of A and B in their vote, leaving all their other preferences unchanged. Now observe that the voting system will continue to rank A above P: Changing individual preferences between A and B does not change individual preferences between A and P (because P is polarising), and so by Independence of Irrelevant Alternatives, A is still ranked above P. Similarly, the voting system will continue to rank P above B. Hence, A is ranked above B. But every voter prefers candidate B over candidate A, contradicting Unanimity.

[@cantorscat6185]

I proved the challenge problem using slightly different assumptions. Instead my assumptions are "independence of irrelevant solutions", and another property, which is that the ranking of a candidate may only be determined by the order of the votes, and not by which candidate the candidate is. We will assume candidate A is polarizing. If we only look at candidate A and candidate B, by independence of irrelevant solutions this should be enough to determine the ranking of A relative to B in the overall vote. A must be ranked < B, or > B. Example System (only looking at A and B): A B A B A B B A If we now add in the votes for one other candidate, who we will call candidate C, we will get something like this: Example System (only looking at A, B, and C): A C B A B C A C B C B A If we now only compare A and C (to determine the ranking between A and C) we get this: A C A C A C C A As you can see, this looks exactly like when we compared A and B. This is because A is a polarizing candidate, which means if any voter votes A > B for some candidate B. They must also have ranked A > every other candidate. Similarly if they ranked B < A for some candidate B, they must also have ranked every other candidate as < A. Because of the second assumption I made, C must be ranked the same way relative to A, as B was relative to A. This implies A must be ranked relative to B, the same way that A is ranked relative to any other voter. This means that if A > B, A must be > all other candidates in the overall vote, and will thus be placed first. Similarly if B > A, all other candidates must be > A, so A must be placed last in the vote. This means A is either > all other votes and first, or all other votes are > A and A is placed last. Interestingly enough, it also means that to determine if a polarizing candidate is placed first or last overall, you only need to compare that candidate to one other candidate.

[@TheRealTNorty]

This is a very nice proof. I think your assumption is right: the name of the candidate is irrelevant. I used a similar assumption when I wrote my proof. Your proof is much clearer than mine though. Good job.

[@TheManxLoiner]

I do not think the assumption is right. As far as I know, there is no (axiomatic) reason why the voting system would treat all candidates equally, in the same way a voting system does not axiomatically have to treat all voters equally (hence the reason for having a `non-dictorial' axiom).

[@billyrobertson3170]

Yeah a lot of people (including myself) seem to be making this assumption, so it's pretty natural to make I guess. I wonder if maybe there's a way to prove our assumption based on the axioms we've got... (Probably not though)

[@cantorscat6185]

I expect that there is a proof for when you assume "independence of irrelevant solutions" and "unanimity", but not the second assumption which I made (because I didn't use unanimity in my proof). I haven't had time to look into trying to prove it this way though, since I'm actually meant to be studying for my exams which start in half a week.

[@DaviddeKloet]

I can prove your extra assumption using unanimity. Let's start by assuming your assumption is not correct. In that case there must be candidates A and B that in the same position would have different outcomes. This means that there is a candidate C and a vote V (between A and C, not including B) such that A wins against C but if you replace A with B, B loses against C. Now in V, add B next to A where on every ballot, B is right above A. Because of unanimity, B must win against A in this new vote V'. Because A wins against C, B also wins against C in V'. But because of "independence of irrelevant solutions", if you now remove A from V', B must still win against C. But this contradicts our assumption that B would lose against C in the same position.

[@th_rtyf_re]

For the challenge lemma, the independence of irrelevant alternatives is all we need: For each candidate (named A) other than the polarizing candidate (named P), we can construct a corresponding sequence of 1's and 0's such that if the kth voter ranked A above P, the kth digit is a 1, and otherwise it's a 0. For example in the round 2 of the example (around 7:00), green is given the sequence 01111, with purple being the polarizing candidate. We find that blue and red also given this sequence: in fact, the sequences corresponding to *all* candidates other than P are the same because P is polarizing (and so the other candidates are always grouped together on one side or another of P). The independence of irrelevant alternatives implies that the relative ranking of A and P in the global ranking is only a function of their relative rankings on the individual ballots; that is, it's a function of A's corresponding binary sequence. Therefore, since all the sequences are the same, P's ranking relative to any other candidate (in the global ranking) is the same: thus P is either ranked first or last. ◼︎ I didn't use unanimity in this proof because the lemma actually holds for any voting system and its opposite, the "opposite" being the voting system that returns the opposite ranking that the original voting system would give. If one of these systems verifies the unanimity property, the other one doesn't, but they both put polarizing candidates first or last.

[@michaeldavies6159]

Challenge problem solution: Let P be a polarising candidate and suppose P is neither first nor last in the result. So there must be candidates A and B such that A > P > B in the result. Consider all possible relative positions of A, B, P a ballot might have: 1) P > A > B 2) P > B > A 3) A > B > P 4) B > A > P Take all the ballots with A > B (i.e. 1s and 3s) and swap A and B (so there are only 2s and 4s left over). None of the A > P and P > B rankings were removed so by IIA final result still has A > P and P > B, and hence A > B. But by unanimity the final result must have B > A, contradiction.

[@robharwood3538]

So glad you tackled this topic! Better voting systems could potentially solve a bazillion political problems we have right now, in the US and around the world.

[@DaviddeKloet]

Challenge problem: Proof by contradiction: Let's assume we have a voting V where A is a polarizing candidate but neither first nor last in the final result. We'll derive a contradiction from this. Because A is not first, there is candidate B winning against A. Because A is not last there is a candidate C losing against A. Now add a candidate X to V just above B on every ballot. Because of unanimity, X must win against B and therefore against A. Now remove all candidates other than X and A and call the results V1. Because of Independence of Irrelevant Alternatives, X also beats A in V1. Now, instead, add X to V just below C on every ballot. Because of unanimity, X must lose from C and therefore from A. Now remove all candidates other than X and A and call the results V2. Because of Independence of Irrelevant Alternatives, X also loses from A in V2. Because A is polarizing, on every ballot its position relative to every other candidate is the same and so V1 and V2 must be identical. So X can't lose from A in V1 and win against A in V2. And there is our contradiction. QED

[@joangalt6270]

But your "Candidate A" MUST be either first or last according to the theorem (and this is the only part that made sense to me). And it DOES make sense. Substitute Trump as the polarizing candidate. Trump PROVED the theorem because he WAS first (supported by his base, Conservatives, Red States) or he WAS last, NOT the preferred candidate for liberal voters, Blue States, etc. This is how we have this shitty man in the WH now - Trump was polarizing. But more people were against him than for him (allegedly) thus, he came in LAST. So your outlier situation cannot happen. The ONLY situation the scenario MIGHT have issues of validity is if TWO polarizing candidates run for office. What then? But, even in this case, one would still be first or last bc they can't BOTH be first AND last simultaneously! WHEW! IDK if that even makes any sense. When substituting Trump as the polarizing candidate, the theorem IS ALWAYS TRUE.

[@sabriath]

I wrote a method last time, but here's another one I've come up with: 1. choose 2 candidates, grade all ballots based on which candidate is greater. 2. Give 1 point to all ballots that correlate with the determination of which candidate is greater. 3. Repeat for all possible combinations 4. The ballot with the greatest points is the "dictator," their score is the only one that matters. ?

[@b43xoit]

Not sure I understand. But it appears to use ranking ballots, so must be subject to Arrow.

[@DrEhrfurchtgebietend]

This is why ordinal (rank) voting is dumb. Cardinal systems are superior in every way

[@Desperis00]

Here's a proof by induction on the number of candidates : First step : Two candidates, each is a polarizing candidate and each will be ranked first or last. General step : Suppose A is a polarizing candidate amongst n. By independance of irrelevant alternatives, we can remove one candidate, say B, without interfering with the overall ranking of the n-1 other candidates. By induction hypothesis, A is first or last in the result of the n-1 candidates voting. Now where does B stand in the actual voting ? the only problematic cases are when B is first and A second or when be is last and A second to last. Let's consider the first case (the second is identical) and let's change the ballots as follows. In every ballot , we move B to the least possible preffered option, without changing its position relative to A. Example : xxBxxA becomes xxxxBA and AxBxxx- becomes AxxxxB. Observe that nowany candidate but A is preffered to B by everyone but that the A vs B choice of anyone has been preserved. This is only possible because A is a polarizing candidate. According to the unanimity principle, B should now be ranked lower than any candidate but should still be ranked higher than A which is a contradiction. We discarded the two problematic cases and hence, A is ranked either first or last in the election.

[@Desperis00]

Okay, much easier but probably wrong : Suppose A is polarizing. Observe that all the ballots of A vs another candidate are identical and hence produce the same result. By the independance of irrelevant alternatives axiom, this result should be reflected in the election result. Hence A either beats anyone and is first or is beaten by anyone and is last. Now my trouble is that I don't seem to have used the unanimity axiom. And that's because I did not ! I instead used that the voting should be fair in the sense that applying a permutation to the candidates in the ballots applies the same permutation to the result. But that's not required in the original question Question : Does this fairness derives from unanimity or from unanimity+ IIA ?

[@trulyUnAssuming]

Let me adapt that a bit because I think the proof by contradiction is unnecessarily confusing in my opinion. But I like the proof. Here's a proof by induction on the number of candidates : First step : Two candidates, each is a polarizing candidate and each will be ranked first or last. General step : Suppose A is a polarizing candidate amongst n. By independence of irrelevant alternatives, we can remove one candidate, say B, without interfering with the overall ranking of the n-1 other candidates. By induction hypothesis, A is first or last in the result of the n-1 candidates voting. Case 1: B > A in the overall voting. Change the ballot as follows: In every ballot , we move B to the least preferred option, without changing its position relative to A. As A is a polarizing candidate it has to be either first which means that B is after A and can be moved to the last spot. Or A is last which means that B can be moved to the second last spot. Observe that now any candidate but A is preferred to B by everyone but that the A vs B choice of anyone has been preserved. According to the unanimity principle, B should now be ranked lower than any candidate but should still be ranked higher than A which means that A has to be ranked last. Case 2 A > B in the overall voting. Similar: Shift B up without jumping over A. Results in A ranked first.

[@DaviddeKloet]

Desperis, I wrote the proof that your "fairness" derives from unanimity on another thread: kzbin.info/www/bejne/d5m5g2qde7J-hMk&lc=z13lyxtxmom1tv51y23tzluompyzg5xkw.1498299129602777

[@JM-us3fr]

Your argument does not result in a contradiction if there is only 2 candidates since B does not need to be ranked lower than A. Obviously you already proved the case for n=2, so since you're doing it by induction it can be assumed that n>2, but you should probably mention this to make it more clear.

[@trulyUnAssuming]

+QED that is why I wanted to rewrite it. Because it wasn't quite correct but very easy to see that you can fix it.

[@rafael17264]

my brain has a lot fun while i watch this,but after some time it gets tired and makes a decision to pause for a little bit :D *that's a compliment

[@williamdaly422]

Yay! so glad you finally did one on Arrow's impossibility theorem! please do more on social choice theory and fair division

[@Nothing_serious]

William Daly I think they already did fair division.

[@williamdaly422]

Your Waifu Sucks ahhh yes! I can't believe I missed the rent division one, thanks for pointing that out!

[@TheManxLoiner]

Maybe in the future they'll do Cake Cutting algorithms!

[@SmileyMPV]

It's worth noting that the theorem needs there to be more than two parties. If there are only two parties, say brexit or no brexit, then a democracy does work.

[@KohuGaly]

No it doesn't solve anything, because then you have to vote on what level of brexit you want as a sequence of yes/no votes. You just arranged the voting into binomial tree in semi-arbitrary way. It's nearly identical to instant runoff.

[@AmosOfSynhome]

In your last video you stated that the pairwise comparison system that led to the Condorcet Paradox failed. But I would argue that it didn't. It revealed that there was no group preference.

[@justinlandis9666]

My attempt at the Challenge question, prove"If a voting system has Unanimity and Independence of Irrelevant Alternatives, then there must be a polarizing candidate who is ranked either first or last." We should start by assuming the voting system has both Unanimity and Independence of Irrelevant Alternatives. Unanimity implies that everyone who has voted will rank one color over another color. Lets call the color of preference "Color A" and the other color "Color B." Independence of Irrelevant Alternatives implies that changing the ranking of some color C will never change the relative ranking of Color A to Color B. Use Unanimity to find the most preferred color in the voting system. Since our voting system has unanimity we may search for the most preferred color. If Color A is the most preferred color, namely no other color is ranked higher pairwise to all other colors, then we are done and we found the polarizing candidate who is ranked only first. If not, then there must exist another color everyone prefers to A. Since A is always preferred to B this new color must also be preferred to B. Repeat this process until the most preferred color is found. We may use Unanimity to find the least preferred color in the similar way. We either say B is the least preferred color or there must be another color which is ranked under B. We have thus constructed an ordered ranking of colors with Unanimity. Stating that our voting system has Independence of Irrelevant Alternatives means that the relative ranking of two colors will stay the same if the third is adjusted. This implies that our original ordered ranking could have been something like this C>.....>A>B>......>D where C was the most preferred and D was the least preferred. However we can change the ranking of A to be such that A>C>......>B>......>D Where C is still greater than all previous pairwise combinations (specifically C>B>D) Given this fact, we know that there must always be a polarizing candidate who is either ranked first or last. In this case I suppose there is two polarizing candidates, one ranked first and one ranked last. Let me know what you think.

[@JohnLangleyAkaDigeratus]

Thank you SO MUCH, this is an excellent video!

[@sunriseinspector]

Good job of breaking the proof into parts and preparing us for what was coming. You are very good at your explanations and the parts that you leave for us to prove are well thought out and fun to try.

[@JM-us3fr]

I wonder if this is why so many civilizations start out with chiefs and kings; in pursuit of perfect fairness, you unintentionally create autocracy.

[@hughobyrne2588]

"Independence of irrelevant alternatives" reminds me of the psychological pricing trick that I've heard called "spoilers". I forget the particulars, but it goes something like this: At a movie theater, they sell three sizes of drink, small, medium (about the size of 2 smalls) and large (about 3 smalls). The prices are $1.00, $1.95 and $2.15, respectively. Now, the medium seems like a terrible choice - and virtually no-one chooses it - but the very existence of the medium size at that price, makes the large look like great value. The movie theater across the street has the same small size, and the same large size, at the same prices, but they don't sell as many large drinks because the "spoiler" medium size - the "irrelevant alternative" - makes a difference. This result is shown in real psychological tests, it's something that really happens in the world.

[@florencjaaarts7769]

I was so confused after watching this the first three times, but I rewatched it, thought about it, read more, wrote it out myself, and now it makes sense! Thank you!

[@johanrichter2695]

Another election-related topic of mathematical interest is apportionment/proportional representation. The methods discussed/used in the US for distributing seats in the House of Representatives among the states are often the same as those used in Europe to distribute seats among parties in party list-PR systems. There are some nice and surprising algorithms to do that, and some surprising paradoxes involing intuitively appealing methods. I suggest a video on that.

[@johanrichter2695]

It is perhaps worth noting one reason that Arrow focused on ranked voting systems was philosophical. He thought that we can't compare the intensity of preference between different people so the maximal information we can have is everone's list of preferences.

[@MustSeto]

But later in his life he changed his mind and said Score with "three or four classes" was probably best.

[@catStone92]

so we're doing cardinal voting next, right? this video made too much of a buildup for you guys to do otherwise :P

[@NathanTAK]

I get this paranoid feeling Arrow's Impossibility Theorem corresponds directly with Gödel's Incompleteness Theorems...

[@b43xoit]

I'm thinking, not so much.

[@buchweiz]

The challenge problem is mostly about working out mathematical notation to me. So let's say that we have input vectors x_j which represents how a voter "j" ranked all candidates by giving them numbers from 1 to n (the first coordinate x_1j encodes the rank given to the first candidate, x_2j encodes the rank given to the second and so on). Now for convenience let's pack all of these vectors together into a matrix [x_ij] and run it through a function f([x_ij])=y, where y is results of the elections and the final rank of a candidate "k" is y_k=f_k([x_ij])=f(x_11,...,x_ij,...x_nN) with N being the number of voters. Now let's translate conditions of unanimity and independence of irrelevant alternatives into this notation. Unanimity would be: if for every voter "j" candidate "m" has a lower rank than candidate "l" i.e. x_li>x_mi for every i, it means y_l>y_m. And independence means that for the result of a candidate "k" it is irrelevant, if we swap ranks of two other candidates for a specific voter or that f_k(x_li,x_mi)=f_k(x_mi, x_li) for every l,m≠k. I'm going to assume for simplicity that the polarizing candidate is candidate "1", i.e. x_1i= 1 or n for every i. Finally the proof goes as follows: first assume that every voter chooses x_1j=n, this automatically means from the condition of unanimity that y_1=n. The opposite (x_1j=1 for every j) by the same logic gives the result y_1=1, but first let's concentrate on y_1=n. If now any random voter "j" changes his mind about candidate "1", it means he must swap him with candidate he ranked first "l", since 1 is a polarizing candidate and can be either first or last (it also shouldn't undermine the generality of taking into account all possible voter choices since l and j are chosen completely arbitrarily at this point). So in this notation x_1j=1 and x_lj=n, but because of the independence condition f_k(x_1j,x_lj)=f_k(x_lj,x_1j) for every k, or in other words the rankings of all other candidates aside from "1" and "l" should remain unchanged. After the swap it's either that the candidate "1" is still the loser with rank n or now he has swapped places with candidate "l" and is now the winner. If the candidate "1" is still loosing we can continue the process with voters changing their opinions about him until the voter is found, whose change of hearts determines the result of the election, and we know this is guaranteed to happen due to the fact that, if all of voters rank the candidate 1 first, he's going to win.

[@TheManxLoiner]

Two errors in your reasoning: 1) Your translation of indep or irrel alternatives is not correct. This axiom says that relative rank of two particular candidates is only dependent on individuals' preferences of those two particular candidates. I do not know how to write that in your notation. What you say is that a candidates rank is unaffected if an individual changes their preference of two other candidates, which is not the same. 2) You only considered swaps which involve the polarising candidate 1 in your argument. However, you need to also consider swaps that involve two other candidates.

[@alexwang982]

On the Condorcet thumbnail the cycle is a mobius loop

[@rohansharma1250]

2 continuous videos on topics discussed by undefined behaviour!

[@TheLoneGnu]

Challenge problem solution: Lemma: If a voting system satisfies Unanimity (U) and Independence of irrelevant Alternatives (IIA). Then a polarizing candidate must be ranked first or last. Proof: We prove this by induction. When there are 2 or less candidates any candidate will either be ranked first or last, so the induction start is trivial. Assume the lemma to hold for n-1 candidates, and consider a voting result with n>2 candidates with a polarizing candidate p. Let c be a candidate that is not p. If we remove c from the ballot it will not change the fact that p is a polarizing candidate, and since there are then n-1 candidates (in this case) we know by the induction assumption that p will come out first or last. We are going to assume here that p comes out last in the election with c removed, the proof for when p come out first is simmilar. By IIA the final order of all the candidates that are not c will be the same as the order of them when c was removed - that means all we have to prove is that c is ranked higher (ranked before) p in the final rank. If we change the current casting of the votes such that all the voters that placed p first places c second, and the rest (the ones that placed p last - since p is polarizing) places c first - all of this without changing the order of the other candidates - then c will be placed before all candidates that are not p on all the ballots, and therefore by IIA and U c will end up before all the n-2>0 candidates that are niether c nor p, but since the relative position of these n-2 candidates and p will be unchanges, they will still end up before p. That is c is ranked higher than n-2 candidates (at least 1) that are all/is ranked higher than p thereby c is ranked higher than p. Notice now that if we swap back to the orriginal voting, the relative order of c and p will not change, so since c won over p before the swap, it will again after the swap. Thereby p will end up last. As mentioned before you can make a very similar argument for when p ends up first in the voting with n-1 candidates then p will end up first in the voting with n candidates, which concludes the induction step and thus the proof! QED.

[@Tracks777]

Awesome video

[@AmosOfSynhome]

Note that the pairwise comparisons system described at the start of the first video meets both unanimity and a weaker (but still pretty strong) version of Independence from irrelevant alternatives. Adding a candidate never reverses a group preference but can only turn a clear group preference into a paradox. So A>B can't be changed to B>A by the introduction of option C. Instead it can only be turned into an ABC cycle or paradox. If you, as I do, consider a paradox to be a tie then adding a candidate can turn A>B into A=B. The worst effect of the way other systems turn A>B into B>A by the introduction of C is how that leads to tactical voting which denies the system true data to analyze.

[@pivotman64]

What would happen if candidates were allowed to have the same ranking?

[@b43xoit]

Vast improvement.

[@WatchCuriousCat]

[Cries in colorblindness]

[@nickelmouse451]

The condition which holds that - if orange drops out of the race, that should not change if green is preferred to red in the overall ranking, is not Independence of Irrelevant Alternatives (IIA). Its is Sen's condition alpha. IIA holds that - whether or not x is preferred (or indifferent) to y in our social choice ranking should not depend on where any other candidate, z, falls within the individual preference rankings. This is not the same as condition alpha, which holds that - if x is preferred to y in candidate set S, then we remove some elements of S and end up with S’, x ought to be preferred to y in S’ so long as neither was removed.

[@GoldenKingStudio]

Some interpretations argue that using cardinal methods do not actually avoid Arrow's Impossibility Theorem because cardinal information from one person is not directly comparable to the information obtained from another person. Plus, the Gibbard-Satterthwaite theorem still applies, as well as various extensions and related theorems. This means that gaming the system will always be possible, making some people want to vote against their own actual preferences in order to obtain a more desirable result (which also applies to Ordinal Systems). Thus, a Cardinal System is not necessarily an obvious choice against an Ordinal System. Unless you only have one voter and/or one candidate, there will always be some way the system is flawed. Even a system as simple when there are two parties, there can be the chance of a tie if there are an even number of voters. Plus, not everyone in a population does vote, and so questions have to be raised as to what counts as a win. If only one person out of an arbitrarily large voting population decides to vote, then that person alone decides the election, against the wishes of who knows how many people.

[@b43xoit]

I'm not sure I can prove this or express it clearly, but I think that the answer to the objection about incomparability of cardinal information from one person to another is just to demand that the system accord each person the same amount of power over the outcome as every other person. This can be fairly reasonably tested for by asking whether for every possible vote in the system, its exact opposite would also be permitted. For example, if I support Stein and Bush and oppose Gore, and you support Gore and oppose Stein and Bush, then in Approval Voting your and my votes cancel, so we both have the same amount of power. If our votes don't cancel or one of us can't express it within the rules of the system, but the other can, then the system is giving one of us more power than it is giving the other.

[@halulife35]

im having some trouble understanding how purple is ranked first overall in round 3. i get that purple is polarizing, but in round 3 it's still ranked last 3 out of 5 times, which just doesn't appear sufficient enough to warrant first overall to me. round 4 is legit, i can totally see that. it just makes no sense lol at 11:00, the election results, green was ranked higher than blue 4 out of 5 times. i 100% fail to see how that means blue is greater than green. that makes no sense to me.

[@MustSeto]

They were supposing that the "mystery system" said Purple was the winner of round 3. They could have changed that supposition so that Purple didn't become the winner until round 4, and then voter 3 would have to be the dictator. That's the key here; the only things we know about the "mystery method" is that is passes Unanimity, IIA, and gives some specific results in test elections. Everything else necessarily follows from that. Think of it this way: The reason why it looks so weird is probably because you were assuming that the method is at least _trying_ to be "fair". But the whole point of this video is to show that this method _absolutely is not even trying to be fair, it's dictatorial through and through_ . It passes both Unanimity and IIA, so someone must be the dictator from the beginning and their ballot is the only one that matters, no matter what anyone else puts down.

[@fred315h]

I know right... I really want to understand it, but that part just bugs me.

[@MrRoyalChicken]

You don't know the voting system used in this election. the point is that in one of the states between everyone choosing purple last and everyone choosing purple first the election tips in purples favour. It's only an example that this happens in round three. It could have happened in round four or five but the following logic to show that that person is the dictator still stands. Concerning the ranking at 11:00, I'm pretty sure it's a mistake.

[@fred315h]

+Skyval_Ream That is a cyclical argument. If we are trying to show that an voting system is unfair, we can't start with it being unfair. Likewise, for their argument to be sound, they can't just make the results unfair and then say that it is so... I also don't care which voting round the change happened in. Their modified results have Green beting Purple, just like in vote round 3, yet they state the opposite. Regardless of which voter is "suppose" to become the dictator, the method of finding said dictator MUST be fair. Else you are creating false positives. Don't get me wrong, I want to understand this, but i can't.

[@cabb99]

Do you think you will be able to explain cardinal voting systems too? Or do you think it is too far off topic from the series? I was always curious about what is the best option to treat the non valid votes (people who don't give a complete information about their preferences)

[@TheTrueAdept]

There are cullinaries to Arrow's Impossibility Theorem that go with other voting systems. Basically, it ends to end-state that Arrow's Theorem ended up with.

[@tommyrosendahl7238]

Could you do a video on Gödel's incompleteness theorems? That would be amazingly interesting...

[@timbeaton5045]

I suspect it MAY just take more than one video! That may also be true, but unprovable within the system.

[@aresmars2003]

My Plurality Criterion says "A Condorcet winner who is also the plurality winner should never lose." With that requirement, top-two runoff passes, while IRV fails. In IRV, the plurality candidate may fall to 3rd place and be eliminated and never get a chance for a head-to-head comparison to his rivals. It's important because REAL WORLD voting includes compromise before the election, and so using a voting method with this criterion encourages voters to "agree to agree" before the election, and that prevents the threat of elections like 100 candidates and 100 voters where rational ranking is impossible. If you know "I have to be first or second most popular", weaker candidates may choose to endorse someone else before the election even occurs.

[@aresmars2003]

The 2017 Minneapolis Mayor election was interesting (with IRV or RCV): 5 strong candidates, and the plurality candidate won in the end, while the plurality-second candidate was eliminated after falling to 4th place. With a close race at 2nd,3rd,4th for elimination order, any of the top-4 candidates might have been the Condorcet candidate, but we'll never know. en.wikipedia.org/wiki/Minneapolis_mayoral_election,_2017

[@ForYourMath]

If we're going to be pedantic, then the challenge problem is wrong unless we define being ranked first and last to include ties. For example, what if we have two people voting for blue or red, and person 1 ranks blue above red, while person 2 ranks red above blue?

[@Noah-fn5jq]

Solution for challenge question: Proof by contradiction - assume the result is A>P>B where P is a polarizing candidate. Now, if we allow A to be an irrelevant variable, then for all voters that selected P to be in first place, due to independence of irrelevant variables, we can place A in first. This will cause the placement of P to now be last (due to the rule of a polarized candidate) and that causes all voters to think that B>P. Due to unanimity, this contradicts the result. Similar argument can be used to show that P>A. Please note that this argument can be used to show that P must be in both first AND last place at the same time within the results. Thus any election with more than two candidates cannot have both unanimity and independence of irrelevant variables while using this election type (even if there is only one voter)... sigh.

[@mohalobaidi]

can anyone explain whay purple above green at 10:41 😅

[@MustSeto]

Vote Test 3 is round 3 from earlier in the video. At the time, Kelsey supposed the mystery system said Purple was the winner in round 3, which means Purple was preferred to Green. Each of the modified ballots have the same relative rankings for Purple and Green. So, by IIA, Purple must be preferred to green with the modified ballots.

[@7lllll]

the arrow's theorem i know of splits unanimity into two parts. One part requires that there exists a set of votes that outputs any given outcome, and the other part requires that when one candidate's rank is increased by some voters and decreased by none, then that candidate's rank cannot fall. it feels like unanimity is simpler, but is there some mathematical advantage of stating it in this way instead?

[@AmosOfSynhome]

The pairwise system includes only one opportunity for tactical voting and that would be an attempt to create a paradox or cycle that includes your preferred candidate. But you would only be interested in doing so if your first choice candidate were likely to come second. But engineering a paradox with a single vote is very difficult because you can't vote for the entire paradox but only two sides of the cycle (engineering a more than three sided cycle would be even harder so I am assuming three sides). The third side of the cycle you have to vote against. So you would have to determine from polling results which side of the cycle is most easily turned and make certain your vote reinforces the cyclw on that side. But too many people tactically vote and they will turn another side undoing the cycle and potentially helping their least preferred candidate to win. Thus the system deters what little tactical voting is possible under it by making it very likely to backfire.

The dictatorship kinda happen in majority between as well, if you have a tie. The next vote will be the "dictator".

[@michaelreilly8490]

I didn't know you guys existed but now I can binge watch all of your videos I can almost say other than the smartest men alive or women I cannot stop laughing if y'all ever need employees I'm there

[@hvonwolfenstein2638]

You are brilliant and your videos are well made. Thanks to the entire team for such thoughtful content.

[@ImaginaryMdA]

Suppose we have pink be a polarizing color, (as it tends to be). Then for every other color we choose, getting rid of irrelevant alternatives produces the same 2 color election. If for voter A, pink was last, then no matter what color we compare it to, that other color will be always be ranked higher, and so on for every other voter. So if the election decides that pink is ranked higher than any given other color, it must rank pink higher than all other colors, due to the rule of irrelevant alternatives. Hence pink is first, if it wins any 2 color election, and last otherwise.

[@unvergebeneid]

Maybe it should be noted why independence of irrelevant alternatives matters: it's another way of saying that every voter should be able to express their true preference, without any strategic voting according to how they expect others to vote.

[@b43xoit]

No voting system eliminates the benefit of strategy, per the Gibbard-Satterthwaite theorem.

[@b43xoit]

But with Approval Voting, your best strategy is never to betray your favorite nor to elevate your most hated. And when two voters have opposite positions on all the candidates, their votes cancel. So that is some evidence that the system may be giving every vote equal power, thus removing any incentive to choose power over merit.

[@SendyTheEndless]

Can we even democracy?

[@eyescreamcake]

Only if we the whole voting system.

[@RobertAdoniasCostaGomes]

democracy isn't the same as election-based representative democracy... if we just randomly select people out of everybody, we possibly get the most accurate type of representative democracy possible...

[@eyescreamcake]

Only if you average it out over long periods of time. (But political opinion changes over such long periods of time, so no, random ballot is not really representative at all.) After all, the optimal strategy in a random ballot election is to write-in your own name...

[@RobertAdoniasCostaGomes]

well, if it is random, you wouldn't have to write a ballot, right? but I do agree on the point about statistical flops... I would just argue that random selection does not work in a republic, specially one as large as the US at the federal level... but, if no one has job stability in politics, then no one is boss and everybody rules, which is basically what a democracy is... one could discuss the need for a fixed president that gets elected, though I think this should be better suited for PBS Demos channel * subtle suggestion for a political sciences/sociology channel *

[@Sempoo]

We need weighted democracy - every voter has weighted vote, i.e. college professor will have higher weight than factory worker.

[@Markd315]

All of this is important academic information to know, but the thing I would urge in understanding arrow's impossibility theorem is to not let the perfect be the enemy of the good. Yes, it is impossible to design a perfect system, but IRV/STV, condorcet (when there is one) and even Borda count (which I really dislike) have desirable properties compared to pluralist voting, which discounts most preferences entirely.

[@FarFromZero]

In this video, starting at ~ 7:40, it is told that there is just one important voter, in this case it is "voter 2". No other voter matters, just "voter 2" is responsible for the final outcome. Some suggestions: 1. If you can only look at the vote of voter 2 and you have no idea about the votes of the other voters, can you still state that voter 2 is the ony important "dictator"? If you disagree, how can voter 2 be the only important voter, if he, at the same time, needs specific results from all other voters? 2. Just before the election give red shirts to the -death squad- voters who wanna put the polarizing person into first position and blue shirts to the voters who wanna put the polarizing person into last position. Yes, not a very secret election, also there should be no liars. But, if after this 51 people are wearing red shirts and 50 people blue shirts, who of the redshirts is the dictator? Such stuff is a formalisation of a lot of intuitively know unfairnesses of democratic systems. You can always create pathologic situations, in which democracy leads to never ending unfairness. In a group of three persons, two passionate anglers and one person who hates fishing, there will be fishing all night and day, if they do fully democratic decisions. In reality this doen's happen. Also, if there are important digital decisions with no compromises and almost a 50:50 decision, this is hard for the losing half. But don't take all this stuff to stigmatize democratic systems. While they are very bad, in the long run they are still the best you can get.

[@MustSeto]

If you're using the same "mystery method" as is in the video: 1. Yes. You only need to look at voter2's ballot to determine the final rankings, how everyone else votes is irrelevant. 2. Voter2. He might not be a redshirt though. No one said the method was majoritarian, in fact it's proven that it must be a dictatorship, which cannot be majoritarian.

[@hyporealisttsilaeropyh6175]

But it is possible to determine the absolute top every time if we don't need to produce a full ranking, right?

[@wootcrisp]

This video was very motivating. Thank you for doing such a good job.

[@mathematicalcoffee2750]

I love this show so much

[@radekhladik7895]

Only -1000000 for punching in the face? I would expect -infinity on this channel...

[@MackJCM]

The weekly problem is trivial given Arrow's Impossibility Theorem. If there is only one ballot, then the only polarizing candidates are ranked first and last respectively by this singular ballot. These candidates rank first and last in the dictatorial vote, respectively. If there is more than one ballot, then by Arrow's Impossibility Theorem, our assumptions are violated. Therefore in every case that we have those two properties, every polarizing candidate must rank first or last. QED.

[@TheManxLoiner]

In the video, we use this challenge problem to prove Arrow's Impossibility Theorem, so it would be cyclic reasoning to prove the problem using the Theorem. You need to answer the problem only using the two properties given.

[@MackJCM]

Okay, I've got it now: If there are one or two candidates the property holds trivially. Suppose there are at least three candidates A, B, and C, such that B is a polarizing candidate in the election, and our system's relative ranking order is A>B>C (that is, B is polarizing but not first or last). Every voter either ranks both A and C above B, or both of them below B. Now suppose that for this same system and election, the results are changed such that every voter who ranked A above C swaps the positions of those two candidates on their ballots. Then every voter will have ranked C above A. It follows from unanimity that C must beat A in the overall ranking. However, it follows from independence of irrelevant alternatives that B must continue to beat C, since the relative positions of B and C never changed on any ballot. As well, A must beat B. So we have that A>B>C must hold, and C>A must hold, a contradiction. It therefore can never be the case that a polarizing candidate is neither first nor last in a system with unanimity and independence of irrelevant alternatives.

[@MackJCM]

In short, if a polarizing candidate were in the middle somewhere, you could take the winner and loser of the election, and make every voter rank the loser over the winner with no other changes. Then unanimity means the previous loser beats the previous winner, but independence means neither can cross the polarizing candidate's position, so one of our properties is violated.

[@pedraumbass]

It's important to state that this only works if there are 3 or more candidates.

[@TheRealTNorty]

I believe I have a proof for the challenge problem, although it might be a little rough with the details. I might add more later to clarify. Proof: Let us assume that we have more than 3 candidates (if we had 2 candidates, then obviously any candidate will be first or last) and that the number of ballots is any arbitrary number. Let's represent the polarizing candidate by the letter P. We start by defining a "starting configuration". A starting configuration is a vote where all the ballots rank candidate P last while the other candidates can be ranked however. It is clear by unanimity that any starting configuration will lead to a group preference where P is last. Further, let's say we "flip a ballot" if we change one ballot with P ranked last to a ballot with P ranked first and everything else stays the same. So we are just shifting P to first on a single ballot. It is possible to reach any valid voting outcome by a finite number of moves from a starting configuration. Since any starting configuration ranks P last overall, we can prove the result by demonstrating that if we flip a ballot from any valid voting outcome (here "valid" means P is ranked first or last on each ballot) where P is first or last overall then the new outcome will again rank P first or last overall.* Suppose that we have valid voting outcome and P is ranked either first or last overall with at least one ballot ranking P last. Now we flip one of the ballots. Now we suppose that P is *not* first or last, and we show that this produces a contradiction. If P is not first or last, then there are candidates ranked overall lower or higher than P. Let us say candidate A is the one ranked just above P and candidate B is ranked just below P, i.e., B < P < A. We consider two scenarios: (1) remove all candidates from the ballots except P and A; and (2) remove all candidates from the ballots except P and B. By the independence of irrelevant alternatives, (1) should result in an overall ranking of P < A and (2) should result in an overall ranking of B < P. However, the ballots from (1) and (2) are exactly the same if we switch the labeling of A and B. This means that identical votes are resulting in different outcomes! This is a contradiction, so our assumption that P was not first or last must have been false. From our earlier reasoning, we have proved the result. * This is similar to a proof by induction.

[@Tehom1]

Nice proof! Just to add a clarification for a step I had to read twice: "However, the ballots from (1) and (2) are exactly the same if we switch the labeling of A and B" - and we know this because P is first or last on every ballot, and in both (1) and (2), we've removed all the other candidates. So every ballot, after the pair of removals (1) and (2), looks like either: (1) P

[@TheRealTNorty]

@Tehom Yes, that's right. I definitely was a bit vague there. Thank you for clarifying.

[@TheManxLoiner]

1) "However, the ballots from (1) and (2) are exactly the same if we switch the labeling of A and B." They are not exactly the same! You have switched A and B around! There is no (axiomatic) reason why a voting system should treat different candidates fairly. (Similarly, a voting system does not axiomatically have to treat different voters fairly, and hence the reason why you need to explicitly add the axiom `non-dictatorial'). You are very close to a solution though. You should re-jig the individuals' preferences of A and B to get a contradiction of unanimity. 2) I think your ideas on flipping individual votes is unnecessary to your argument - you make no reference to flips when discussing P, A and B. I think you only need to say everything from "Now we suppose P is not first or last..." onwards and you would still get your desired contradiction. Also, it doesn't matter to your argument that A and B are *exactly one* higher/lower than P. (Apologies if this feedback is unwelcome. I think that since you've made such a considerable effort that you'd appreciate constructive feedback).

[@Tehom1]

His point is that if A beats P under (1), then B must beat P under (2), and similarly if P beats A. This is true because under the irrelevance of independent alternatives, only the voters' rankings of A and P matter for determining whether A beats P, and under relabeling B has the same rankings. Yes, you're right that it doesn't matter than A and B are exactly one place higher/lower than P. It only matters that P is between them in the total ranking.

[@TheManxLoiner]

@Tehom. Consider the two following hypothetical votes: FIRST VOTE 1. A>B>C>D 2. C>A>B>D 3. D>B>C>A SECOND VOTE 1. C>A>B>D 2. C>A>D>B 3. D>C>B>A Irrelevance of Independent Alternatives (IIA) says that the relative Rank of A and B in the first vote should be the same as their relative rank in the second vote (because we have 1.A>B, 2.A>B and 3.B>A in both votes). It also says that the relative rank of C and D should be the same for the first vote and for the second vote (because we have C>D, C>D and D>C for both votes). Now the question is, does the relative rank of A and B have to be the same as the relative rank of C and D? My understanding (which may be wrong) is that IIA does not say that the relative rank of A and B has to match the relative rank of C and D. It is feasible that the system decides A>B while D>C. The reason I think is is as follows. Suppose I am wrong, so that IIA does say that relative rank of A and B does have to match the relative rank of C and D . Then you do not need Unanimity to deduce that a polarising candidate has to be first or last - you only need IIA. But I doubt they would ask a challenge question which had extra assumptions, because that would be quite mean!

[@vibhuvikramaditya4576]

You are wrong on one crucial point, The arrow impossibility theorem doesn't just apply to Ranked choice ordinal voting, Borda system which provides cardinal numbers based on ordinal collective preferences doesn't satisfy the independence from irrelevant alternatives, as the number of options and rank has direct implications for votes. The theorem is general in nature and applies to all voting systems

[@MustSeto]

Borda is still generally considered a ranked method, whether the ranks are technically used to assign points isn't really relevant to the theorem (they even talk about it in their previous video) A better example would be Score voting, which can't losslessly be encoded using ranks. Then whether it passes IIA or not depends on how you define it for rating-based systems. Generally, if you extend the concept of IIA in a way that preserves its spirit, Score passes it (and all the others) without becoming a dictatorship. But there are other ways to extend it where Score fails (and I think Arrow's theorem still technically applies), but then it's blatantly obvious that it's not desirable when defined that way.

[@brianpso]

Thanks a lot for making these last videos about voting. They opened my eyes to the reality of our voting systems, and CGP's recommendation was very welcome as well, since his videos gave a ton of insight on how to make a more fair voting system. 10/10.

[@isaacdarche7103]

The distinction between "Arrow's idealized world" and "the real world" (resp. Satterwhite et al) is spurious. Arrow shows that for 2 or more choices, social choice mechanisms cannot satisfy all necessary rationality criteria (the ideal world). If you relax the rationality criteria (the real world), rationality criteria are still not satisfied. So, the statement "Arrow's Theorem does not apply to the real world" is false.

[@arturomagidin5361]

The MathReviews review of Arrow's original paper makes an argument against the Independence of irrelevant alternatives: "The following simple example may illustrate the difficulty. Two individuals are ranking 100 alternatives. Suppose x and y are two alternatives and suppose the first individual ranks x first and y last, the second ranks y first and x second. It then seems reasonable that the social ordering should rank x above y. On the other hand if the first individual ranks x first and y second, while the second ranks y first and x last the same reasoning would rank y above x in the social ordering. However, the author's second condition requires that x must also be ranked above y in this second case, which seems to contradict common sense."

[@arturomagidin5361]

(Review was by D. Gale)

[@MustSeto]

More than show that IIA isn't desirable, I think this shows that ranked systems aren't desirable. If a person changes their preference from A>B>(500 others) to A>(500 others)>B, rank-based systems can't tell if it's because the person started hating B, or realized that the 500 others were better than B but hasn't actually changed how they feel about B. With Cardinal/Rating-based systems, that's made explicit. The Gibbard-Satterthwaite theorem says that no non-dictatorial system with more than 2 candidates is strategy-free. Unlike Arrow's theorem, Cardinal systems can't escape that one (though they can sort of escape weaker versions of it).

[@bezadesta6484]

really really good

[@edwardlau892]

Perhaps we can use mathematical induction on two fronts: For the number of candidates, and the number of voters. Hopefully we can do the easy thing for this challenge. To prove: For any voting system observing "Unanimity" and "Independence of Irrelevant Alternatives"(IoIA), a Polarizing Candidate must be ranked first or last in the overall ranking given we have X candidates and Y voters, where X and Y are any natural numbers. We have a smallest non-trivial case: Three candidates with odd number of voters. If we have a polarizing candidate in this case, there must be a majority that either want it to be the first or last, and it will end up the first or last respectively. To build the ladder, we assume for SOME natural numbers C and V, the statement to be proved is true for C candidates (one of them is polarizing) and V voters Then, we add one candidate to the mix. The new candidate would not have enough variable to outpolar the existing polarizing candidate if the majority want the polarizing candidate. Then, we add one voter to the mix. If the immigrant voter should tip the balance for the polarizing candidate, the new voter must vote against the overall rank, and therefore tipping the balance of the Unanimity, making the polarizing candidate switch to the opposite end of the ranking since the majority wants it to. ------- BTW, another alternative method is to consider TWO polarizing candidate in the same election, then both of them would sit in the two poles of the overall ranking as a result (There must be majority wanting the two polarizing candidates to sit on the two poles in specific order). We mess with one of them with other candidates, so that we have one polarizing candidate as intended. Due to IoIA, the intact polarizing candidate must not have its overall rank moved.

[@eli0damon]

I feel like there should be some close relationship between independence of irrelevant alternatives and preclusion of strategic voting. Is there one? And if so, what is it? Thanks.

[@MustSeto]

Well according to another theorem that even applies to cardinal system, no system is immune to strategy (unless it's dictatorial, or nondeterministic, etc.) (Gibbard-Satterthwaite theorem) But IIA failure can lead to strategy. Plurality's spoiler effect is an example of IIA failure, and it leads people to voting only for the front-runner they prefer, even if they still don't like them, instead of supporting someone they like more.

[@atrumluminarium]

I've actually thought about a similar problem a while ago (I know by this point I am probably late to the party and haven't seen the previous episode yet so here goes). Consider a vote where the voter is asked to compare candidates pairwise. That is, suppose there are candidates A, B, C, D,... (the ballot may get very long since it is essentially n choose 2), but for each pair the voter rates who is better from the two (or leave blank if equal). Then when the votes are collected, calculate the net directed weight in each comparison of all votes and construct a directed graph with weighted edges. populate the adjacency matrix with the weights, make it column-stochastic and find the eigenvector of the eigenvalue 1. Basically ripping off Google's page-rank method tbh. Granted it is very process intensive since elections may have 60+ candidates making the ballot ~1770+ lines long and working with a (60+)×(60+) matrix, but it's just a concept.

[@detectivejonesw]

dear Kelsey I would really love to see a video on how many possible games of chess there are. I understand this is an open problem but if you could give us some idea of the current thoughts on the problem and methods being used to solve it that would be super awesome Joe

[@BrunoJMR]

What makes voter 2 specifically the dictator? What are the conditions of the distribution for a specific voter to be the dictator? And is there any way to manipulate your way into dictatorship?

[@MustSeto]

It was because we supposed the "mysterious" method switched Purple to be 1st between 2 and 3; that's when voter 2 switched. In this case, if the "mystery" method also meets Unanimity and IIA, then the only method it could possibly be is one that considers voter 2 to be the dictator. They could have made it switch between other rounds. In which case a different voter would be responsible. That would be a "different" method but it would still be dictatorial. As long as you use the exact same method, that "same" voter will always be the dictator; whatever is on their ballot will be the final rankings, no matter what the other ballots say.

[@humbertoseghetto5218]

What about a "reverse" borda count? every candidate wins as many points as his rank (first candidare gets 1 point, second gets 2...) and the winner is the one with least points?

[@b43xoit]

Same outcome as Borda count, just using golf scores.

[@edelopo]

I have a question regarding what you mean by voting system. I would assume that in a voting system all voters are indistinguishable, meaning that if we permute the votes, the outcome would be the same. Therefore if all voters cast different votes and there is a dictator, permuting the votes may result in the dictator making a different vote, but the outcome should remain the same. How does this exactly work?

[@TheManxLoiner]

So in the definition of a voting system, I think we do not assume that voters are indistinguishable. Nor do we assume that the candidates are indistinguishable. In principle, it would be nice to have the permuting property you describe. However, no such voting system can exist, because you can have completely symmetric votes: 1. A>B>C 2. B>C>A 3. C>A>B

[@b43xoit]

@@TheManxLoiner, in all seriously proposed voting systems, permuting the ballots has no effect on the outcome.

[@annayosh]

To see that irrelevence of independent alternatives is probably something a 'desirable' voting system does not have, look at a situation where there are 3 candidates A, B and C, and 1/3 of the population prefers A>B>C, 1/3 prefers B>C>A and 1/3 prefers C>A>B. Suppose we have a system that has irrelevence of independent alternatives. It will give one of the three candidates first place. Let's assume this is candidate A (the situation is fully symmetrical, so a similar argument could be made for the other two candidates). Then because of irrelevence of independent alternatives, A should win a 1-on-1 against C as well. But in such a 1-on-1 2/3 vote C>A and 1/3 A>C, which is usually not how we want the result to come out.

[@MustSeto]

That's the Condorcet paradox. What does that have to do with IIA? Rather than IIA not being desirable, I think it's more like ranked systems aren't desirable. If a person changes their preference from A>B>(500 others) to A>(500 others)>B, rank-based systems can't tell if it's because the person started hating B, or realized that the 500 others were better than B but hasn't actually changed how they feel about B. It's because of this that IIA failure isn't universally desirable. If you're using a ranked system then IIA is a pointless criterion because you can't tell when it should hold and when it shouldn't. But with a Cardinal/Rating-based system, strengths of preference can be made more explicit. In Score voting, A and B's relative rankings depends only one the scores given to A and B (passes IIA). The only way to change A and B's relative ranking is to change the score of one or both of them.

[@feldar]

Shouldn't the Condorcet Criterion be that if a candidate wins a head-to-head election with *every* other candidate they should be the overall winner? If it's any overall winner then everyone could vote A-B-C and the criterion would say that B should win because they beat C, even though A clearly beat both B and C.

[@johnnypoker46]

"polarizing candidate" I wonder where we might find one of those?

[@rufatsadigov4375]

What about the property of unrestricted domain for proving the Arrow's theorem? Or only unanimity and IIA are enough to show dictatorship?

[@MustSeto]

I think they simplified some things for the video.

[@theultimatereductionist7592]

We proved Arrow's Theorem in graduate math class in 1992 at Rutgers University. I find nothing special or important about one of those axioms. The one that forbids candidate X from being group-ranked 1st place in spite of no voter ranking X 1st place. I see no particular reason why one "needs" or "should have" that assumption. As long as everybody agrees on the particular algorithm to generate a group ranking from individual voter rankings, there's no logical reason to rule out X being group ranked highest.

[@MustSeto]

Does that axiom have a name? I don't think it's part of Arrow's theorem, or at least it isn't necessary. It isn't in this video's proof, for example. There are rank-based methods where the winner isn't necessarily put first by anyone, most notably Condorcet methods, but that's not the reason they fail Arrow's theorem---it's because they fail IIA, which I'm pretty sure is different.

[@thomasgregory4871]

This 'dictator' thing is a fallacy. I don't know if there is already a name for it, but I call it the "Last Point Fallacy". This is where extra weight/emphasis is given to the final point scored in a game. For instance, a basketball game is down to the last fraction of a second. The score is Team A has 90 points and Team B has 89 points. Player #14 from Team B shoots and scores as time expires. The fallacy is to say that Player #14 "won the game". It is a fallacy because saying that Player #14 won the game negates the previous 89 points scored. The statement "Player #14 won the game" would only be true if the score was 1-0 at the final shot. Technically still a fallacy since basketball is a team sport therefore no single player could "win the game", but I hope you get my point. In the case of voting, saying that one voter decided the outcome (in this case the 'Dictator') is a post hoc rationalization for the eventual outcome. It's like saying that there is a specific raindrop that caused a flood or the dam to break. Or in the case of 3+3+3+1=10, that 1 is the 'dictator' that resulted in 10. Also, wouldn't the example in the video be an example of the Gambler's Fallacy? Since no candidates are eliminated from round to round, the results of each round are fully independent of the previous rounds. How Voter 2 cast their ballot in round two has absolutely nothing to do with how they voted in round #3. The same is true of all other voters. Also also, in what world does someone change their ballot from round 1 to round 2 such that candidate X moves from least favorite to most favorite?

[@MustSeto]

It's not a "fallacy". The Arrow's dictator controls the election completely, their ballot is the only one that ever mattered. Even if you let everyone else change their votes, there's nothing they could do to change the result. The only way to change the result is for the dictator to change their ballot, in which case the result would be a copy of the same dictator's new ballot, and again everyone else would not be able to change the results no matter what. The first set of elections were a set of "test elections" to see how the election method behaves in an abstract way. Then they give an example "real" election at 8:25, and build off of those. But you can make that election whatever you want, you just have to follow the rules correctly to create the "modified ballots", which are derived from the example election as described. Then you go through the proof to prove that, if you use the same methods as what was used on the test ballots, and the method passes IIA and Unanimity, the results of the election must be a copy of the dictator's ballot. >Also also, in what world does someone change their ballot from round 1 to round 2 such that candidate X moves from least favorite to most favorite? A dictatorship, for one. Of course, most methods aren't dictatorships. They mostly just fail IIA instead. Or they use ratings instead of rankings, those are my favorite (Approval, Score, STAR)

[@thomasgregory4871]

@@MustSeto So, what you're saying is that if the 'dictator' votes blue, then blue is the winner, even if everyone else votes red? If this is the case, then you don't have an actual voting system. You have a literal dictatorship in which all votes are discarded except the dictator's. All of which negates the point of voting meaning that you aren't doing an actual voting experiment/model. How does "A dictatorship, for one" in anyway explain why a person would swap their least/most favorite candidates? Unless it's in some "vote for the dictator or we murder your entire family" type of a situation.

[@MustSeto]

@@thomasgregory4871 >So, what you're saying is that if the 'dictator' votes blue, then blue is the winner, even if everyone else votes red? If this is the case, then you don't have an actual voting system. You have a literal dictatorship in which all votes are discarded except the dictator's. All of which negates the point of voting meaning that you aren't doing an actual voting experiment/model. Yep. That the point. It's impossible to create a perfect ranked voting system, because the only "voting systems" which pass IIA and Unanimity are dictatorships, which are practically not real "voting systems" at all, except in the broadest, most vacuous sense. That's not to say all "real" ranked systems are equal. They can have different failure rates/severity. I'd still suggest a rated system, though. They aren't really covered by Arrow's Theorem, Undefined Behavior has another video on one example: "range voting" >How does "A dictatorship, for one" in anyway explain why a person would swap their least/most favorite candidates? Ah, sorry, I thought you were asking how one person changing their vote could flip someone from last place in the results to first place in the results. Keep in mind those were "test elections". They were to learn a bit about how an "unknown" method would behave. Just for diagnosing the system. They don't need to represent a realistic series of elections.

[@GordonHugenay]

I don't see why the challenge problem should be true: say one person votes A>B>C, and one person votes C>A>B, then C is a polarizing candidate, but what's wrong with the ranking A>C>B?

[@MustSeto]

Suppose that there are two voters, and they do in fact vote that way. A>B>C C>A>B And your method gives as a result A>C>B. Or in other words, A>B + A>C + C>B. But now let's suppose A and B swap places on both ballots. B>A>C C>B>A Now B is ahead of A on every ballot, so due to Unanimity it should be B>A But the relative rankings of A vs C and B vs C is the same, so by IIA it should remain A>C and C>B, but through transitivity that implies A>B, which contradicts Unanimity.

[@GordonHugenay]

thank you very much for the clarification (the definition of IIA is rather complicated), I think I can even see a proof of the claim now (it's basically just a slightly more generally phrased version of your comment): suppose for a contradiction that C is a polarizing candidate, but isn't placed first or last in the final ranking, i.e. there exists A, B such that A>C and C>B. now on every ballot with A>B, swap A and B such that B>A on every ballot. since C is a polarizing candidate, this is an irrelevant alternative with respect to C, so it must still hold A>C and C>B, but by unanimity B>A, which is a contradiction.

[@TheJayman213]

I think this shows pretty well that votes should be something to fall back on when practicing democracy, not something to be used by default. When a substantial debate leads to a concesus that is infinitely more democratic than a bunch of people checking boxes.

[@b43xoit]

liquid.us

[@AmosOfSynhome]

The Condorcet criterion was misstated: it should read 'every' not 'any'. If A beats B and B beats C and A beats C, according to the criterion with 'any' in it as you stated B must be the winner because B beats a candidate. But so must A because he also beats C. And that isn't even a paradoxical result!

[@AmosOfSynhome]

Ethan Bradley, I suppose you could interpret the word 'any' that way but it would definitely be clearer with 'every' in place of 'any'.