Arrow's Theorem (2014) | Hacker News Reader

Arrow's Theorem (2014)

plato.stanford.edu

94 pointscscurmudgeon69 comments

So, if some of you have felt despair at the idea that this may indicate that true democracy is impossible, fear not: it hinges on the fact that some preferences can be cyclic: A wins over B who wins over C, who wins over A.

These situations are possible but rare and in such a case, it is arguable that all potential winners are legitimate.

Yep, this is when you have non transitive properties. A really cool embodiment of this same concept is non transitive dice.

https://en.wikipedia.org/wiki/Nontransitive_dice

Indeed, a non-transitive election like that means that there is no Condorcet winner. Some voting methods (including first past the post) are guaranteed to select a Condorcet winner if one exists, but when one doesn’t exist (if A>B>C>A), various voting methods will result in various winners.

I love reading about the theory behind voting methods, but one common criticism is that these edge cases are rare and thus a pure theoretical approach isn’t sufficient for getting a “desirable” (however you define that) outcome.

https://en.wikipedia.org/wiki/Condorcet_method

Arrows theorem is misleading because it only applies to rank order systems.

Range voting (i.e. 0-5 rating system) satisfies all the criteria. [0] So yes, democracy is theoretically possible.

[0]: https://youtu.be/e3GFG0sXIig

Good video, thanks for sharing that!

I think plurality/first-past-the-post gets an unjustified bad rap. If you focus only on the moment of election, it is not a very good system. But a broader view reveals something else. The process of settling on two options, that each represent a coalition of factions that have come together and compromised on a common platform, is doing most of the work that other systems try to do within the voting system itself.

Proportional voting also solves the problem in a similar way, except that the politicians representing each faction, rather than the faction at-large, do the work of forming coalitions with other factions.

Of course the distinction between the two is a little more blurry, since broad-coalition parties also exist in proportional systems, and politicians do play a large role in the at-large coalition-forming in plurality systems. But nonetheless, they clearly lead to different outcomes.

As for ranked and approval-type voting systems, I’m not really a fan since I think they don’t have any hope of representing coherent thought about politics. People have a hard enough time making a principled choice of one party to vote for; asking people to rank them seems likely to produce even less principled choices.

At recent times, American politics seems to suffer from getting stuck in a near 50-50 position with only two parties, and this probably is a direct consequence of the first-past-the-post voting system.

The Continental European system with proportional voting and multiple political parties with changing support seems more agile. New parties can form, gain and lose support, not quite as quickly as in one 4-year election cycle, but in about 3 or 4 election cycles the political landscape of a country can change.

But then again, the American democratic system has already had a pretty good run for over 200 years, so can we know if present-day problems are indicative of actual problems in the system, or something that will pass?

It’s hard to argue against the longest running democratic system in current existence.

No, it's not. American politics, especially recently, draws heavy criticism every day in a multitude of newspapers.

There are many other nation-states around the world that have been drawing heavy criticism for their politics. Even ones with different voting systems (or none at all). Such as UK, France, Netherlands, etc. Perhaps it’s not the system but some other factor influencing the current political climate. To me, the fact that political turbulence is occurring worldwide indicates that the issue is not with how one country votes, but likely from some other factor.

USA is not the longest running democratic system. Even if it were, it wouldn't mean anything.

Why do you think that people have a hard time choosing which of two parties to vote for? My impression is that the opposite is true, at least in the United States. My impression is that most elections are largely decided by the relative turnout of existing populations of individuals, each of which are firmly committed to one party and simply haven’t decided whether to actually show up and vote.

You make a good point, but a good percent of the population is swing voters and they do decide elections, in addition to turnout dynamics. All of the movement that you see in polls is people shifting their opinions, as well as moving from undecided to a particular preference. Some polls account for intention to vote, but others are of all registered voters, and others even all Americans. They see a lot of movement too.

Actually, apparently there is some reason to think that a lot of poll movement isn't really people shifting their opinion. Instead, people shift in how willing they are to talk to pollsters. On good news day for your candidate, you are much more likely to be willing to talk to a pollster about it.

> You make a good point, but a good percent of the population is swing voters

No, they aren't. Studies have repeatedly shown that US voters have very high party voting consistency, and that those that identify as independents are almost as consistent as those that identify with a party.

Turnout and change in composition of the electorate decides elections, more than anything.

FPTP leads to the long-term creation of a duopoly. That's bad for humans in any situation. You need for parties to refresh their platforms, as well as politicians, and the fastest way to do that is to have competition among parties. Also, primaries are made to make people think they have a multitude of options, but it's usually people within the same line of thinking with the party that win, and the rest are marginalized.

Proportional voting also has higher turnout rates and especially the list-based system seems to have a higher number of women in politics.

FPTP countries tend to have the highest inequality, too, likely because there is that lack of competition, which tends to allow powerful people to have a bigger influence on the two parties over time.

Coalition of parties is better than the alternative of one party dominating the whole government, because then parties are forced to work with each other and compromise on their most extreme views. That's usually a good thing. Plus, you don't get totally opposite platforms every 4 years. Like say if Democrats were to dominate once, raise taxes for everyone to 40%. Then Republicans came. Lowered them to 10%. Then Dems came again, raised them to 30%, and so on.

RCV is a little harder to understand. But so is the caucus system, and the electoral college system, and other quirks the current American political system has.

RCV has some real advantages, like optimizing for positivism in elections rather than negativity (because you may need your opponent's voters). That's usually a good thing.

I don't believe people have a hard time choosing parties. If anything, what happens in most countries, even PR countries, is that people say that they don't have a good option.

Ultimately, FPTP is also undemocratic, because it allows parties to dominate the government when they have less than 50%, sometimes even less than 40% of the voters' support (at it has happened in Canada, and sometimes in mid-terms in the US). I don't know why anyone would support FPTP when that is the case. Why would a party dominate the government with less than 40% support in election day?

RCV has some weaknesses compared to Condorcet methods (which use the same voting mechanism of ranking candidates but different ways of determining the winner). RCV can punish people for voting according to their true preferences.

For example, say a country is 49% Republicans and 51% Democrats. In addition, a Socialist candidate is running. 30% of the Democrats actually prefer the Socialist candidate, but under a plurality system they would vote for the Democrat candidate because the Democrat has broader appeal.

If those 30% chose to rank the Socialist as their #1 choice, then the Republican will win the election, because the Democrat will be eliminated in the first round. So the Democrats are incentivized to not vote their actual preference.

Look at the various Condorcet methods [1], and also check out Approval Voting [2] for a system that produces fairer outcomes without the complexity of RCV/Condorcet.

[1] https://en.wikipedia.org/wiki/Condorcet_method

[2] https://en.wikipedia.org/wiki/Approval_voting

I'm with you on Condorcet methods producing more equitable results between tactical and non-tactical voters, and I'd love it to be used for the election of singular positions (e.g. a mayor, a president, etc). But all single winner systems distort outcomes in parlimentary bodies (house of representatives, Canada's parliament, etc). Look instead to MMP or STV.

I disagree. I think plurality tends to create a polarized system where there are two parties with opposite extreme views.

The two parties don't have an incentive to represent the entire populace, they simply have to represent half the voter base as best as possible. A two-party system is a zero sum where shooting down the opposing party advances you just as much as making meaningful positive contributions.

Also, a two-party system means that views that overlap both of the two extremes on different issues aren't represented.

Approval voting could potentially fix these problems, without any additional complexity at the ballot box (it's really simple! the only difference is you're allowed to vote for more than one candidate), but sadly has seen almost zero traction. Adopting approval voting more broadly could go a long way towards fixing the somewhat broken political system we have in the United States, for example.

I'm not a political scientist so take my opinion with a few grains of salt :)

[1] Approval Voting on Wikipedia: https://en.wikipedia.org/wiki/Approval_voting

My sense is that approval voting will just select a milquetoast agreeable candidate who lacks any real conviction or vision, other than avoiding upsetting anyone. It is the ultimate protector of the status quo and the enemy of bold leadership.

I feel like score voting is much better in that regard. It lets people express their whole range of opinions.

In my opinion, that's actually better. In the United States the Republicans are actively trying to dismantle all the legislation that was passed by the previous Democratic congress, and there seems to be little rhyme or reason to their platform other than that if the Democrats support it, they're against it. This is especially noticeable with healthcare, and the volatility around the government's stance on healthcare has lead to real uncertainty for insurance companies that has led to higher premiums and spottier coverage.

Approval voting actually allows candidates that break the mould of existing parties, because voters can support a candidate with unorthodox views without compromising the campaign of their party's primary candidate.

I have a favorite article on voting [1]. It has good visual descriptions of how different systems favour different styles of candidates.

Plurality voting is a lot better than not having a democracy; imho at least the worst candidate will be excluded. My understanding is also that democracies of any form (including republics) tend to get much better military results than dictatorships, but I don't have any actual evidence to cite :(.

[1] http://zesty.ca/voting/sim/

The Dictator's Handbook by Bruce Bueno de Mesquita and Alistair Smith is about just this issue, and if you want a more theoretical take (along with a detailed model) try The Logic of Political Survival by the same writers.

While good and illustrative, that page is based on the very restrictive view, that of choosing only one candidate. This applies to presidential elections, sure. There can be only one president.

But most countries don't have one-member sized voting districts in their parliament elections, rather they choose 10 to 30 members per voting district.

> I think plurality/first-past-the-post gets an unjustified bad rap. If you focus only on the moment of election, it is not a very good system. But a broader view reveals something else.

Yes, it reveals that empirically, it produces a narrower political dialogue, poor participation, and low satisfaction with government compared to systems that produce better proportionality. See Lijphart's Patterns of Democracy.

For us who haven't seen Lijphart's _Patterns of Democracy_, how does one establish such a conclusion, measure the width of political dialogue, for that matter? It would seem that a proper, randomised trial could be difficult to make, or has it been done on a small scale and extrapolated to country size?

One measure could be the typical voter turnout in elections. Lower turnout could mean less trust in the political system.

    United States (2016): 56%
    India (2014):         65%
    Germany (2017):       76%
    Denmark (2015):       86%

Voter turnout essentially reflects whether their vote is worth it. If they think everything is going to get worse no matter how they vote, they won't bother. But the same happens when they think everything will be alright no matter how they vote! So you can't really distinguish between those cases based on voter turnout alone.

The short version is you compare actual existing democracies on multiple axes.

The long version is, well, Lijphart's Patterns of Democracy.

>it reveals that empirically, it produces a narrower political dialogue, poor participation, and low satisfaction with government compared to systems that produce better proportionality.

I am very skeptical of studies purporting to run statistical analysis on such small data sets as the recent history of countries, let alone the recent history of democracies. It seems that in the quest to produce quantitative political science research, people forgot all the statistical lessons about sample size, confounding factors, and so forth.

Weak empirical data is still stronger than abstract speculation with no evidence.

That's not true. The conclusions you derive from the data can be totally wrong because of how weak the data is, but now you have a false confidence in it.

First, that's at least as much of a danger with basing conclusions on abstract speculation without evidence, and second, that's not a matter of which is stronger, it's a matter of treating either as stronger support than it is.

One of the cognitive science labs was hiring experts in graph theory, and it turns out they wanted to express Arrow's Theorem -- and the related theories -- in the form of a graph so they could reason about decision making in the brain.

If I recall correctly, the paradox of voting gets represented as a top cycle which leads to irrational decisions. They wanted to come up with mechanisms where they break top cycles. (In these graphs a higher ranked decision was higher on the Y axis.)

The paradox of voting usually refers to a different claim: that the cost of an individual voting tends to be greater than the expected benefit to the individual.

Confusingly, the term (and the extremely similar “voting paradox”) sometimes refers to the Condorcet paradox, which notes that collective preferences between three or more options can be intransitive. I expect that is the concept you are referring to.

https://en.wikipedia.org/wiki/Condorcet_paradox

Yes, the latter.

I find this is one of the best videos on the subject:

https://www.youtube.com/watch?v=tJag3vuG834

This video really helped me to digest the concept. Thanks for sharing!

Great video, sounds like CGP Grey's twin brother.

Great video except that it's misleading at the end. Arrow's theorem is only about rank-order voting. But if e.g. you can express your preferences as numbers (e.g. if you can state your preferences as 10% strawberry, 30% vanilla, and 60% chocolate) then it no longer applies.

Indeed. It seems that those voting systems too can be proven [0] to have these problems, though.

[0] https://politics.stackexchange.com/questions/14015/does-gibb...

Holy hell, that is mindblowing. Thank you for sharing this.

Like a car swerving side to side as 2 drivers wrestle for control of the wheel, the 2 party system is an erratic vehicle.

But I have good news: we can steer a more stable course with score voting.

Score voting doesn't violate Arrow's Theorem (because it's not a ranked-choice system).

Here's how it works:

* Each voter gives candidates a score from 0 to 1.

* The highest average score wins. (The average can be weighted to account for abstentions.)

The upshot:

* No political parties are needed.

* It resists gerrymandering because it's non-partisan.

* If there's a bias in the system, it's towards the center.

* Simulations indicate score voting is socially optimal.

* Arrow, himself, expressed preference for approval voting (a variant of score voting)

Further reading:

electology.org

en.wikipedia.org/wiki/Range_voting

So in the U.S. then Dems will vote 0-10 and Republican 10-0. I'm not sure I see the difference as long as there is only one winner

What the U.S. really needs is proportional representation, similar to parlimentary systems of other countries

> So in the U.S. then Dems will vote 0-10 and Republican 10-0.

Then someone who identifies as neither could get a 6 on average and get elected. (Assuming both other candidates are close to tied.)

That said as a Canadian I'm down with almost any change in the voting system.

You replace the claim about voting method with a claim about who can get on the ballot. That is as big of a change as changing the voting method.

There are options for managing ballot access:

* Since there is no spoiler effect, you could just let everyone on the ballot. Letting abstentions count as zero votes, obscure candidates cannot win. (Less severely, abstention could count as a fractional zero vote, i.e. 0 in the numerator of the average and 0<x<1 (say x = .25) in the denominator...)

* Or require a certain number of signatures to let a candidate on the ballot.

Why give a 6 when you could give a 0 or a 10 depending on advance polling data? Score voting devolves into approval voting for sufficiently informed and tactical voters, and provides less impactful ballots to the tactically naive.

No, a new single winner election system is a distraction. What we need is proportional representation, to ensure that more people actually have representatives in proportion to their political desires.

You didn't understand the parent's point. The independent has 60% of the population giving him a 10.

> Score voting doesn't violate Arrow's Theorem (because it's not a ranked-choice system).

Right, but it could still have those problems that Arrow's theorem talks about. Do we have a proof to the contrary? I have a hunch that it promotes strategic voting, like plurality voting ("first past the post") does.

It's fairly straightforward to prove that score voting does not violate the conditions of Arrow.

For example, adding an additional candidate should not affect the average score of the rest of the candidates, hence there is no problem with "independence of irrelevant alternatives". (I leave the rest of the conditions as an exercise to the interested reader.)

That having been said, all voting systems can be vulnerable to strategic considerations. However, simulations and theory suggest it's much less the case for score voting compared to ranked choice systems. See electology.org for some pointers to research.

> For example, adding an additional candidate should not affect the average score of the rest of the candidates, hence there is no problem with "independence of irrelevant alternatives".

It is non-obvious to me that rational voters in such a situation should not adjust their scores for the initial candidates. In fact, it seems like you should adjust scores in the prototypical situation where you prefer candidate A to candidate B, and detest candidate C. With only A and B present, you give A a high score and B a low score. When C enters the picture, you change your score for B to a high one, so that you make it maximally difficult for C to win.

Range/score voting suffers from the vary serious problem that there is no consistent mapping from subjective preferences to ballot markings; it suffers from the cultural variability that affects numeric ratibg systems in general; approval voting has a similar problem.

These systems can be very good in situations different from common public elections where there is a consistent meaning for ballot markings (e.g., approval makes good sense in non-secret-ballot elections where a vote to approve an option is a binding commitment to participate if the option is selected.)

> Score voting doesn't violate Arrow's Theorem (because it's not a ranked-choice system).

This is very much like the idea that radix-sort can run in linear time worst-case, because it's not a comparison sort. While absolutely true, both statements can be misleading without context. Just as radix-sort has the weakness of depending on the size of the keyspace (and therefore being poorly suited for sorting small vectors of large numbers), score voting has some issues that do not appear in ranked-choice systems.

Most obvious: There is incentive to vote tactically (as is always the case), but the tactics are more complicated than in most other systems. Most serious: Not using a ranked-choice system prevents us from reliably finding a Condorcet winner.

One could make the case that these disadvantages aren't as bad as those of ranked-choice systems, just as one can make the case that radix-sort is a generally good way to sort records by a lexographic key. Simply listing advantages doesn't do that, though.

It sounds appealing, but I wonder if in practice range voting tends to collapse into first-past-the-post, with people voting tactically to maximize the chances of a popular candidate winning (instead of voting for the candidate they most prefer). This is why systems such as optional preferential voting appeal to me despite their (different) flaws. I wonder if monotonicity and trying to avoid circular electoral preferences are slightly overrated goals. I suspect that a good electoral system might involve a bit of satisficing, of producing great outcomes even when the theoretically best outcome isn't consistently achieved.

> I wonder if in practice range voting tends to collapse into first-past-the-post

Of course it will. The fundamental problem is selecting only one representative per voting district. However fancy and complicated voting algorithm you make, it will most probably collapse anyway. It's the size of the voting districts that leads to a two-party system, not the voting mechanics.

But then: Just pool nearest 20 voting districts [x] into one large voting district, from which you elect 20 representatives, and any kind of simple proportional voting mechanics [xx] will do. If you elect 20 representatives, any party that manages to get at least 5% of the voes will get their representative to the Parliament. New political parties start to appear, and a multi-party system emerges on its own.

[x] Or 15, or 30 or whatever.

[xx] Such as the D'Hondt method, https://en.wikipedia.org/wiki/D%27Hondt_method

It’s hard for me to imagine that the actual outcome of such a proportional representative system would be worse (in my judgment) than the current US federal district system, but the theoretical criticisms are obvious. For instance, it makes sense to have representatives represent a specific area who were supported by a majority of voters from that area. That way, the representative can in theory represent specific interests that are disproportionately important to citizens from that specific area (e.g. agricultural issues for rural areas or public transportation issues for urban areas).

Of course, drawing these districts (in either system) is an inherently arbitrary process which can lead to counterintuive or obviously unideal results, the most obvious example of which being gerrymandering. But at the end of the day, unless we have a one world democracy, borders must be drawn. National borders are “easy” in the sense that they tend to be formed not by a democratic political process but rather historical conflict.

" people voting tactically to maximize the chances of a popular candidate winning (instead of voting for the candidate they most prefer)"

I'm not sure I understand your comment. There is no "instead" -- you can vote honestly for both your preferred candidate and the popular candidate.

In fact it collapses into aproval voting, which is like range voting except every score is 0 or 1, or equivalenty like FPTP except that you can vote for more than one person.

But it turns out that approval voting is itself considered a very good voting system (I remember reading an article about how a conference of experts voted on their favourite voting systems and approval voting won, but I can't find it because "voting system vote" isn't a very good Google search).

I think The main theoretical problem with most approval and range voting methods is that they fail the Condorcet and majority criteria. A candidate who is preferred over every other candidate by a majority of voters can lose, which sucks, but in practice it is debatable how common such an occurrence would be.

The problem I have with this is that the score from 0 to 1 isn't tied to any strong foundation.

Suppose that I rate a candidate 0.7, and my neighbor ranks the candidate 0.6 . Does this mean that I like the candidate more than my neighbor does? What does that mean? How can we tell?

Suppose you take two people who would vote in the same way, but then you take all the scores of one of the people, and square them. These are all still scores between 0 and 1, and so a valid way to vote, and it keeps the preference order in place. But what do the difference in these scores mean? "amount of happiness"? How could we quantify this?

The way that seems to make the most sense to me is a normalized vNM utility. A person's least favorite candidate (or least favorite candidates if some tie for this position) get(s) the rating 0, and their favorite candidate(s) get(s) the score 1. All other candidates are scored as the probability r such that the voter is indifferent between that candidate, and (probability (1-r) of [least favorite candidate]) and (probability r of [most favorite candidate]).

This gives a well defined foundation for what score a voter would give a candidate, a clear definition for what a 0.6 means vs a 0.7 .

The system where you just pick the candidate with the highest average rating though, does not incentivize voting in this manner.

I have an idea for a system which I think would incentivize voting this way, and which would optimize the expected value of a weighted sum of everyone's vNM utility. (it is a weighted sum because the utilities are normalized between 0 and 1, and different people's vNM utilities are incommensurate. The weighting is in the normalization. It is I think the most neutral weighting it can be.)

However, it would probably be entirely impractical.

The idea is this:

Each person states their utility for each of the candidates listed, and the system makes sure that these utilities are normalized.

Then, each voter gets 1 (arbitrarily subdivisible) point of voting probability.

Then, a bunch of "trading" is automatically done, where say, as an example, if two people have different first picks, but would both prefer some other candidate as a close second, they could both give up some "undifferentiated" voting probability in exchange for some which is restricted in some way, based on whatever deal they made.

All the deals would probably be made automatically, because it would just be so incredibly inconvenient otherwise, and also having the result be biased towards voters who are better at trading probably wouldn't be great.

Once there are no more trades to be done, all the remaining undifferentiated voting probability goes to the voters' first choice.

Then, the winner is chosen randomly, with the probability of winning corresponding to the proportion of the voting probability that was assigned to them in the end.

Assuming an efficient market, this should optimize the expected value of a weighted sum of the voters' vNM utility (assuming rational voters).

Unfortunately, it is rather complicated, and I think it would probably be too computationally intensive to run.

Oh well.

> Suppose that I rate a candidate 0.7, and my neighbor ranks the candidate 0.6 . Does this mean that I like the candidate more than my neighbor does? What does that mean? How can we tell?

Each voter should rationally vote in whatever way maximises the expected value of his utility of the outcome. The extent to which your vote "looks like your actual preferences" depends on how the voting system is designed.

Sure. My point was that the "pick the one with the highest average rating" doesn't obviously incentivize a particularly meaningful way to vote.

I think that ideally, if it is possible without giving up too much, it is desirable that how a person would rationally vote doesn't depend very much on what they know about how other people will probably vote (though this probably isn't the most important consideration).

If the system is based on people giving ratings, and there isn't anything that these ratings are designed to exactly mean, then it seems likely to me that the system wouldn't just so happen to be such that the way people are incentivized to vote would mostly not depend on how others are expected to, and also unlikely that the way people would rationally vote would match particularly well with the way that the designers of the voting system imagined.

The system I gave was intended to be one in which the way people would be incentivized to vote would correspond to their preferences in a clearly defined (and sensible) way.

What stops everyone from voting 0 for everyone and 10 for one candidate? It's how like our system is now, where no one votes for who they want, but the person they can tolerate most, and can win.

I think you misunderstand the system. It's not that you have 10 points to distribute across the candidates, but that you give each candidate a score. What score you've given to other candidates doesn't constrain what score you can give this candidate - you pick separately from the whole range for each.

So if 10 is the maximum (0-1 was the range given above, but whatevs), then sure if I prefer Hillary to Trump and they're the only two that seem likely to win, maybe I'll give her a 10. But for anyone I prefer to Hillary, why would I give them a zero? Of course I should give them a 10 as well!

Yeah I understand that. I still feel that voters will eventually converge to giving other candidates the lowest score possible because it increases the likely hood of their candidate getting elected.

edit: definitely willing to try the system though :D

Am I the only one who finds that the Stanford encyclopedia of philosophy is generally less clear than the matching Wikipedia article?

I almost always scroll down for the Wikipedia article when Google puts sources like the Stanford Encyclopedia of Philosophy or Investopedia or WebMD or IMDb first.

For me, it’s less about which source I trust more, and more about my familiarity with and enjoyment of the writing/organizational style of Wikipedia articles.

Reply on news.ycombinator.com