Arrow's Impossibility Theorem | Infinite Series
ฝัง
- เผยแพร่เมื่อ 28 ก.ย. 2024
- 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...
I feel these videos would be even better without colourblindness.
The Wikipedia article on Single transferable vote uses food emojis. :D
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")
She should have used simple shapes - square/circle/etc
I like algebra, it's fun.
As with voting, there are problems with any system - some people have trouble seeing the difference between such shapes.
i dont understand voting with colors.. maybe you could use animals like lions... just saying
iswydt CGPG
("I see what you did there, C. G. P. Grey)
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!
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).
This helped me a lot, thank you!
Exactly! Rigged just like the real thing
bro the homework to the watcher makes no sense to me. wtf is wrong with them
"You can focus on the important things like how to pack spheres in a 9 dimensional space" best Squarespace plug *ever*.
Yay! so glad you finally did one on Arrow's impossibility theorem! please do more on social choice theory and fair division
William Daly I think they already did fair division.
Your Waifu Sucks ahhh yes! I can't believe I missed the rent division one, thanks for pointing that out!
Maybe in the future they'll do Cake Cutting algorithms!
please cover cardinal voting systems!
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.
This is why ordinal (rank) voting is dumb. Cardinal systems are superior in every way
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.
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
can you do a video on cardinal voting
You'll have to wait until they elect a new pope.
@@treyforest1999, cardinal voting will defeat the two-party scam.
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.
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.
Could you do a video on Gödel's incompleteness theorems? That would be amazingly interesting...
I suspect it MAY just take more than one video! That may also be true, but unprovable within the system.
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.
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."
(Review was by D. Gale)
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).
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.
I had a thought - what if the voting function was to randomly choose a dictator (perhaps it could be called the lottery dictator, unless such a voting system already has a name)? The law of large numbers suggests that it would tend to be fair to the voting group, and it would probably encourage more people to vote (and vote honestly). Personally, I find this relatively fair, given that no one knows who the dictator is prior to voting.
That being said, I'm not sure how that actually works with the fair voting. Strangely, it seems that if the randomization occurs every time the function is run (I'm sort of considering the function like a program), then it is not necessarily fair by any criterion, but in particular, it is obviously not independent - you can get different results with the same exact inputs. But if you choose a random dictator function, then it is "fair" (putting aside the dictator).
Yeah, that's called "sortition". Bayesian Regret studies show that it does even more poorly than First Past the Post.
2 continuous videos on topics discussed by undefined behaviour!
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)
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.
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.
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?
Same outcome as Borda count, just using golf scores.
What about the randomized condorcet voting system ? That is also pretty interesting.
Are you also going to talk about the Gibbard-Satterthwaite theorem ?
i want cardinal voting where you can vote with anything between 0[,1].
i like the idea of going voting and filling in `0[` to every candidate -> i would finally have the choice of going to vote and say 'ney'. Our current system only allows the options "don't vote" and "say: 'arr'"
Mo' bettah have your [0...1] continuous score, but also, in addition to the human candidates, include "none of the above" (NOTA). If NOTA gets a majority, new candidates have to be sought.
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
I love this show so much
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?
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.
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.
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.
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.
I know right... I really want to understand it, but that part just bugs me.
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.
+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.
this theorem is always cited as some important fact about voting, and it assumes ordinal voting. if we use cardinal voting we can solve this all kerfuffle. sure, cardinal voting doesn't guarantee a definite answer in all cases, but if our system is fair (whatever that means) and has concluded that two candidates are identically good in the eyes of the populous - than just flip a coin, who cares. they're both literally exactly as good.
is there another more substantial downside to cardinal voting? or did arrow's theorem just came about because we purposelessly imposed the restriction of ordinality upon ourselves?
I suppose that when Arrow found the theorem, nobody was considering cardinal systems yet.
The challenge's proof: Consider all ballots at once. The relations of the polarizing candidate (p.c.) with each of the other candidates are the same. So are those relations in the election result. Hence, the p.c. is only ranked first or last.
There is no (axiomatic) reason why a voting system should treat different candidates equally, just like there is no reason why a voting system should treat different voters equally.
The Manx Loiner The second property in Arrow's theorem guarantees that the same relations in ballots lead to the same relations in the result, if we only consider comparative relation. I think that is the case. Btw, there IS axiomatic reason to treat candidates equally.
"guarantees that the same relations in ballots lead to the same relations in the result, if we only consider comparative relation"
I am not sure this is true. Consider this example: If you had 2 candidates, you could have the system "A wins unless B has top preference amongst *every* voter." This satisfies the first two properties but does not treat the candidates equally. I imagine you could extend this example to include as many candidates as you want.
Great video, will re-watch to go through the dictator part slowly as that baffled me.
I was wondering though, a dictator sounds bad but it is really? Number 2 didn’t know that they are the dictator beforehand and other voters don't know a dictator is out there (or is not themselves) beforehand
This voting method's results will always be a copy of the ballot of whoever it identifies as "voter 2" regardless of what any of the ballots say. Even if you did another election, where everyone voted against voter 2, voter 2 would still get their way exactly. Which doesn't sound great even if voter 2 doesn't know who they are.
You can sort of do this without the dictator knowing who they are if you make identities more abstract. For example, if voter 2 isn't a specific citizen, but instead "the second person to submit a ballot". In other words, like a random election. But then from the perspective of the citizens, it fails IIA
If you were to randomly pick a dictator you'd have a high chance of picking an unpopular candidate. But a random dictatorship is good in the sense that it is not subject to strategic voting.
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!
Ethan Bradley, I suppose you could interpret the word 'any' that way but it would definitely be clearer with 'every' in place of 'any'.
So, what does this say about how difficult it is to influence a 'plurality-system' when you have access to particular groups via (say for example) some 'social-media' or 'cable-tv-channel' and you can 'plant' items that influence the folks who cling to that particular social-media feed or cable-tv-channel so that their choices are bent toward the outcome you desire?
And, assuming, that it is the case that this can be done easily then we really need to look carefully at our current system with an eye toward future elections.
asitoughttobe.com/2010/07/18/score-voting/
From this video's explanation, the only thing I saw is that there exists at least one voter whose ranking lines up with the overall ranking. I'm confused as to how that makes them a dictator, rather than an average voter.
That's my main problem with this video and another that I've seen. It technically proves it but it doesn't make it clear that the dictator is determined beforehand by the voting system. But it's true. The only system which can possibly satisfy Unanimity and IIA is one that doesn't even have to look at or process any ballot except the dictator's.
I swear, since the first video in this channel, this is the first that got me confused, fully confused. I've learned to kill hydras, to hack quantum computers, to imagine cubes or spheres in n dimensions (ok, maybe not that much, but you get the idea) but I couldn't understand the ideas of this video. Last one was very simple and interesting, but I got completely lost in this one.
I'll rest for a while, maybe tomorrow I'll watch it again in order to try to understand something, but I'm seeing myself all weekend long reading papers and articles in Wikipedia.
wouldn't a mean value ranking system satisfy most of these? Sort of the inverse of a point system. any time a color is ranked 1st it recieves 1 point, 2nd place is 2 points, etc, and the total is averaged, so the mean value comes very close to the rank that color recieves most often. the colors are then ranked by this new mean value. in the case of a tie, a second round of just those two colors is calculated.
this satisfies unanimity and independence of irrelevant alternatives. it's also not dictatorial.
using this system the switch for purple occurs evenly across all rounds, as it should, and does not affect the rankings of any of the other colors, other than bumping one to achieve its rank
Isn't this equivalent to Borda? It prefers smaller scores, but gives smaller scores to higher ranked candidates. Using means shouldn't change the final ranking. And Borda fails IIA. Using a common "Capital of Tennessee" election example between (M)emphis, (N)ashville, (C)hattanooga, and (K)noxville:
42x M>N>C>K
26x N>C>K>M
15x C>K>N>M
17x K>C>N>M
Means:
Memphis: 2.74
Nashville: 2.06
Chattanooga: 2.27
Knoxville: 2.93
Nashville wins
But if voters who preffer Chattanooga to Nashville use strategic burial:
42x M>N>C>K
26x N>C>K>M
15x C>K>M>N
17x K>C>M>N
Means:
Memphis: 2.42
Nashville: 2.38
Chattanooga: 2.27
Knoxville: 2.93
The C vs N orders did not change on any ballots, but the winner changed from N to C
(hopefully I did the math correctly)
@@MustSeto I hadn't considered strategic burial. Also, yes, this is effectively an inverted form of Borda that achieves roughly the same results. I may have to crunch the numbers to see if it ever differs, but it also fails the Condorcet Criterion so... perhaps a better method could be used.
can anyone explain whay purple above green at 10:41 😅
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.
question to all: does a polorizing candidate contradict the want for independence of irrelevant variables? Consider, a candidate is in last place. If you start to hate another candidate more, then the candidate will now jump to the front thus changing the order of the *relevant* candidates. Isn't this an issue?
Note: this would be an issue in a dictatorship as well!
I feel that Arrow's Theorem is highlighting a bellweather coincidence. Watch the James Stewart film "Magic Town" (1947) to see what I mean. TL;DR if a candidate gets in, someone must have voted for them? (oh the irony ;-)
What if you had a voting system where the dictator was randomized? For example, put all the votes in a hat and pull out a vote at random.
Produces a range of outcomes and the worst could be pretty bad. How about Approval Voting instead (assuming we can't get rid of single-winner offices)?
Okay. 10:40 does not follow. Green is ranked by the group over purple so I don't see how purple beat green...
No one said the method was majoritarian. For example, The Borda Count is a rank-based voting system which is not majoritarian (and neither are dictatorships... which means no rank-based method that passes Unanimity and IIA can be majoritarian, since they must be dictatorial).
I think the overall rankings at 10:40 are wrong. shouldn't green be above purple, since it's above purple in 3/5 of the ballots?
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.
For getting punched in the face my score is (Grahams number)^-1
I'm gonna go vote secondly next election.
Does your cardinal vote mean you would ask a million bucks in the consequent lawsuit?
3:10 someone please explain to me how orange ranks first here? Seems to me it should be green, blue, then orange 1-3
It's totally hypothetical. Not all possible voting methods make traditional sense. Maybe the method ignores _ALL_ ballots and always returns Orange > Green > Blue > Purple > Red. This would pass IIA (but would fail Unanimity)
Then there's the American way: it's having a plurality system, but pick the second one, not the first one :D
14:50 Wait, so are you saying that you wouldn't take $950K if it meant you'd get punched in the face?
Why is purple first in round three? Shouldn't it be last?
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.
I don't understand any videos on this channel, but some are interesting anyway. This isn't one of them.
I'd be willing to get punched in the face for less than a million dollars
7:11 from arount here, you are stating wrong statements. In round 3, purple is still last. How the hell did you figured out that it is different? Also in round four the candidate Purple is not first, but second. That means, there is not "flip", but there is a transition.
I need more explanation on how you determine those.
How you know Purple is last in round 3? She never said what the method she was using was. It might not be majoritarian. We only know it passes IIA and Unanimity.
But Purple can never be second. Because Purple was only put first or last, and it's possible to prove that if a candidate is only put first or last, and the method passes IIA or Unanimity, Purple must be first or last in the final results.
10:31 I am trying to figure out how P > G in this part. What am I missing other than a better brain. To me it clearly looks like G > P.
It would be if the system were majoritarian. But we didn't assume that, only IIA and Unanimity. So even bizarre "methods" that no one would use in practice can't escape the theorem, as long as they use ranks.
how the hell are we gonna vote on which one to use?
Use all voting systems to vote on the voting system, and see whether they disagree.
Voter 2 doesn't present independence of irrelevant alternatives in the graph at 6:58.
What do you mean?
@@MustSeto The order of the colors change when the purple circle is displaced. The relative preferences of the remaining colors is not maintained when the purple circle is moved from being the most preferential color to the least preferential color for voter number two.
>The relative preferences of the remaining colors is not maintained
At that specific timecode, they don't even show final rankings. IIA says that if X does not change relative to Y on any ballots, it must not change in the final rankings either.
And it only counts as a "change" if it goes from being above, to being below, or the reverse. If X was above Y, then gets closer, but is still above Y, it's still not considered changed relative to Y. So if a ballot says X>P>Y, and it changes to P>X>Y, X has _not_ changed relative to Y.
Skyval Ream Voter 2 (Round 2: red
Oh my, you're right! I guess it's a graphical mistake, like they copied from the cells above.
Wow
Does the idea of a tyrant--a singularity--sound like a singularity in physics? Or is that just me 4-dimensional buzzing them together with Space Time.
We could vote for a voting system, then vote. But first, we need to vote on how to vote the voting system....
And then we must vote the voted upon voting system in using the voted upon voting system's method of voting.
And then we have fractals.
This is actually the problem we are having in British Columbia right now
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.
@@b43xoit But isn't that, in itself, a voting system? Who's going to vote on whetever that is good or bad?
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.
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.
Nicholas Wright It didnt; that was just an exampe. She could have just as easily said the switch happened in round n, where 1
It has to switch at some point, 2 was just an arbitrary example.
But in round 3 purple is last not first?!?
Purple was the winner of round three. 7:14
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
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.
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.
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.
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.
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.
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."
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.
In my unimportant opinion, the example ballots might be easier to follow if each color was accompanied by its own shape.
Colour blind guy agrees
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.
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
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.
Please bring this channel back
so we're doing cardinal voting next, right? this video made too much of a buildup for you guys to do otherwise :P
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.
Yeah read some sen(1970) but interpersonal comparison is debated
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)
@@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
@@ivarangquist9184 thankfully, STAR Voting was invented in 2014 to mitigate that problem among others!
That was a lot to take in. Definitely going to rewatch like five more times!
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.
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.
Orange was definitely the polarizing color.
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.
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 ?
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.
Desperis, I wrote the proof that your "fairness" derives from unanimity on another thread:
th-cam.com/video/AhVR7gFMKNg/w-d-xo.html&lc=z13lyxtxmom1tv51y23tzluompyzg5xkw.1498299129602777
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.
+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.
Awesome video
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
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.
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.
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.
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).
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)
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.
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.
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.
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.
So confusing
This series hasn't yet touched on the purpose and value of votation and systematicization (but neither did probability-and-statistics textbooks 50 years ago)-Single-objective voting itself is nearly impossible to realize, so we'll count it roguish nation (e.g. war vs. snooze)... more-realistic votation systems should probably serve up choices of decision-graphing....
[04:13] Also, How does Independence-of-Irrelevants relate to Distinguishable-from-random-voting (which you don't mention, the entropic-zone width)...
?
What would happen if candidates were allowed to have the same ranking?
Vast improvement.
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.
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.
PBS doesn't get enough Thanks for their free content.
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?
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)
@@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.
@@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.
Dictator and ties don't matter. Neither does it matter if there is a circular condorcet mapping. What matters is that plurality is an extremely poor voting method because in a real situation with hundreds of candidates and millions of voters, a condorcet vote could have opposite results than plurality. It doesn't matter if there's a tie because it's not a lie, whereas a plurality vote gives results based on the candidate space. That's why they tried to hack the math by adding parties.
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.
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?
god I love your videos, but you ruined the fun for me :S you see I'm colorblind so everytime you talked about blue and purple at the same time (a big chunk of the video) I couldn't evaluate your claims cause I don't know which is which :S still, nice video.
I agree - the coloured circles should have been distinct shapes and contained a simple image, (I'd have picked a subset of the zodiac sign symbols.)
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.
Would you really pay a million dollars to not get punched in the face? I'm impressed.
Well, Arrow's Theorem made me feel like I'd been "punched in the face, lol!
I'm So confused, especially since the ranked voting system made so much sense. Now I can't make a determination that ANY of these alternative voting systems have ANY advantage, even though I thought, at the very least, the RVS seems to provide the voter with more free will to choose from a list of more voters. I could see this system as good for giving alternate parties (i.e. Libertarians) a better chance to be elected. I've always been of the opinion that having a multi-party system would help to prevent polarization - you're either a Dem or a Republican. In the current system, Libertarians are forced to either align with one of the two parties or not participate. Rand Paul is an excellent example. Since the Republican party is the "lesser of the two evils", he chose to join the GOP to stand any chance of being elected as Senator of the state of Tennessee, and this is regardless of the fact that his father is the great Ron Paul, one of the greatest political minds to grace Washington politics.
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.
How exactly does the transition occur between rounds 2 and 3 at 7:55? In Round 3, Purple is ranked BELOW all other colors three times and ABOVE all other colors two times. He should, therefore, be ranked AT THE BOTTOM in the overall rankings of Round 3. Isn't it Round 4, and thus Voter 3, that determines the election? And besides, in Round 4 you could shuffle Voters 1, 2, and 3 around and call ANY of them the dictator. Is "dictator" just shorthand for "a member of the majority"? This video was VERY poorly explained.
The transition between 2 and 3 was decided arbitrarily. It doesn't matter where it is in the abstract, one was just picked to make a slightly more concrete example. If you used a different example, that would be a different method, who considered a different voter the dictator.
For Arrow you only need to assume IIA and Unanimity -- not Majoritarianism. So Purple being ranked last by a majority doesn't mean anything. And again, if you changed the example so that they started winning only once they happened to be ranked 1st by a majority, that would be a completely "different", but still dictatorial method (the difference being who the dictator is)
Is there any way you could avoid using blue and purple together in future videos? I'm colorblind and I couldn't distinguish between them.
What if I told you that there is country where they effectively eliminated all but two options and still don't manage to get a system where the choice voted by the majority wins.
But surely, that can only be a backwater country that doesn't even use international measurements in 2023, right?
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.
Challenge Problem Solution: (EDIT: When I originally wrote this, I accidentally assumed that all candidates are treated equally and I didn't notice, but luckily this is still provable using unanimity!)
If we have an election with a polarizing candidate, consider all groups of two candidates where one of the candidates is polarizing.
Every group of two will have exactly the same voting pattern, with each voter either preferring the polarizing candidate or not preferring them.
So however our voting procedure decides a relative ranking between the polarizing candidate and another candidate, (assuming all candidates are treated equally, [1]) the relative ranking will be the same regardless of the other candidate.
This means that the procedure prefers the polarizing candidate to every other candidate or prefers every other candidate more than the polarizing candidate.
So by of the Independence of Irrelevant Alternatives, the polarizing candidate will come in either first or last place.
Q.E.D.
References:
[1] David de Kloet, "I can prove your extra assumption using unanimity", Reply to Cantor's Cat's Solution, 24 June 2017.
There's no (axiomatic) reason why the voting system would treat all candidates equally!
Crap - Thanks for pointing that out!
I like the reference!
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.
Not trying to start something because i know you all worked hard, but around the 7 min point whats up with box lining the boxes together?? Its slightly off. Where the layers not in the same program? Its driving me bananas. But good vid overall. Rant over. Thanks. Good job
Getting punched in the face is -1,000,000? Really? I'd rate it like -20. I'd take a punch in the face for $20.
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.
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.
Range Voting satisfies all 3 of Arrow's fairness criteria, which it can do since it's not a ranked-order voting system. Arrow himself said in 2012 that a score-voting system (like Range Voting) is probably the best single-winner system. Read more here: governology.wordpress.com/2017/09/05/kenneth-arrow-is-a-dick/
I'm glad you mentioned cardinal voting (ie score-voting) at the end!
Also, the condorcet criterion is stupid. It prioritizes popular divisive candidates over total societal happiness.
Condorcet algorithms are good for voting, though, not range ones. Arrow's theorem doesn't matter because only Condorcet criterion matters, not the other criterion like ties or dictator. You only have a "dictator" if it is almost a tie. Condorcet and plurality voting give extremely different results, and you don't need a party system if you use Condorcet-valid algorithms because you can introduce or remove candidates without changing the results of the others. Also, the Condorcet paradox doesn't matter as you can just cancel out any cycles by subtracting them down until there is no longer a cycle.
@@TimJSwan Anything is better than plurality, but I don't believe that the best option is always the candidate that would win in every head-to-head election. Score voting is far more likely to select candidates that better represent the population than any condorcet method.
I feel like this could all be sorted if we got rid of government and just had anarchism. After all states do by force what communities do naturally. Im for anarcho capitalism. Which doesnt mean no laws as many people wrongly believe. For one Irish Brehon law was in an anarchism system, and most countries have their state law derived from law community made. And under such a system it would be legal for communist communes to exist provided they didnt steal any of that property and accumulated it themselves. They have to respect the property rights of others, and respect the non aggression principle.