{"id":31350,"date":"2016-11-21T13:30:38","date_gmt":"2016-11-21T18:30:38","guid":{"rendered":"http:\/\/blogs.ams.org\/mathgradblog\/?p=31350"},"modified":"2016-11-21T12:10:10","modified_gmt":"2016-11-21T17:10:10","slug":"mathematical-democracy-mission-impossible-not","status":"publish","type":"post","link":"https:\/\/blogs.ams.org\/mathgradblog\/2016\/11\/21\/mathematical-democracy-mission-impossible-not\/","title":{"rendered":"Mathematical Democracy: Mission Impossible? Maybe not\u2026"},"content":{"rendered":"

\"vote_12345\"<\/a>In 1950, a 29-year-old PhD candidate at Columbia published a stunning theorem that later won him a Nobel Prize: \u201cThere is no such thing as a fair voting system.\u201d<\/strong>\u00a0 Or so the legend goes.<\/em>\u00a0 Let\u2019s dive into this claim and see to what extent Arrow\u2019s Impossibility Theorem does and does not quash our hopes for a fair representative democracy.\u00a0 For a background of voting systems, see Rina Friedberg’s post last month<\/a>\u00a0or Stephanie Blanda’s 2014 post<\/a> on how Olympic host cities are chosen.<\/p>\n

 <\/p>\n

<\/p>\n

What does Arrow\u2019s Impossibility Theorem actually say? Like Euclid\u2019s parallel postulate, Arrow\u2019s Theorem is frequently transformed into a variety equivalent formulations that are either more intuitive to grasp or more relevant to problem at hand (to read Kenneth Arrow\u2019s original paper, click here<\/a>). \u00a0The formulation below is based on a\u00a0paper<\/a> by\u00a0John Geanakopolos, who according to the acknowledgments, consulted\u00a0Kenneth Arrow prior to publication.<\/p>\n

Consider a society of N voters and at least 3 candidates.\u00a0 Each voter has transitive preferences, meaning they can mentally rank all the candidates (with ties allowed).\u00a0 A voting system is a system that produces a single ranking on behalf of society (i.e. it determines a winner, but also a second place runner-up, third place, etc.).\u00a0 Consider the following three fairness criteria:<\/p>\n

    \n
  1. Universal Domain:<\/strong> Voters can rank their candidates in any order they like. \u00a0No matter what combination of ballots it receives, the system will always produce a ranking.<\/li>\n
  2. Unanimity:<\/strong> If everyone prefers A to B, the voting system should rank A above B.<\/li>\n
  3. Independence of Irrelevant Alternatives (IIA):<\/strong> Whether the voting ranks A above B should not depend on how voters rank C (or any other candidate).<\/li>\n<\/ol>\n

    Theorem:<\/strong> The only voting system that respects universal domain, unanimity, and IIA is a dictatorship.<\/strong><\/em><\/p>\n

    Note: The dictator in this case is not a candidate, but a rather voter who has the power to decide the winner every time, no matter what the rest of society thinks (more precisely, a dictator can always force the voting system to rank A above B).<\/p>\n

    A two-page proof, accessible to any outsider who is used to proving things, can be found here<\/a>.\u00a0 To give you a taste, I\u2019ll walk you through the first lemma (or you can skip to the next section see why Arrow\u2019s Theorem might not be so\u00a0doomsaying after all):<\/p>\n

    Lemma:<\/strong> If every voter ranks one candidate as their highest or lowest choice, then the voting system must as well.<\/strong><\/em><\/p>\n

    Proof:<\/em> Suppose, on the contrary, that even though every voter has put B either first or last, the voting system ranks A>B>C. \u00a0Thus every individual voter ranks\u00a0B>(A and C) or (A and C) > B. \u00a0Suppose every voter decides they like C better than A, but leaves B\u2019s rank unchanged (they’re allowed to rank them however they want under universal domain<\/em>).\u00a0By the independence of irrelevant alternatives<\/em> condition, the voting system must still rank A>B and B>C. Now, every voter\u2019s mental ranking is now C>A>B or B>C>A.\u00a0 By the unanimity <\/em>criterion, the voting system must rank C >\u00a0A. The two rankings A>C and C>A are not compatible so our original assumption is impossible. The voting system must rank B either first or last. QED<\/p>\n

    The proof then uses this lemma to show that there is a unique voter who can cause B to go from being last to first in the rankings and that this voter must in fact be a dictator.<\/p>\n

    Is there no hope?<\/h1>\n

    Before we throw up our hands and declare that no voting system can be fair, let\u2019s pause and consider how reasonable these assumptions and \u201cfairness\u201d criteria actually are.\u00a0 Unanimity does not sound like an assumption we ought to relax: directly contradicting the wishes of literally every voter sounds about as bad dictatorship. \u00a0Likewise, we could\u00a0limit the voting system\u2019s universal domain, but prohibiting voters from ranking candidates a certain way because it will cause the system to malfunction hardly seems fair either.\u00a0 If we force there to only be two candidates, then all our contradictions go away, but presumably you will need some system of primary elections to narrow your choices down to two, so this only kicks the can back up the road. \u00a0Even if we don\u2019t need our voting system to produce a ranking but rather just a single winner, unanimity affects affects \u201cwinner\u201d just as much as any other choice.\u00a0 But what about IIA?<\/p>\n

      \n
    1. A dictatorship,<\/li>\n
    2. Prevents one of the candidates from ever winning, or<\/li>\n
    3. Is vulnerable to strategic voting\u00a0(i.e. savvy voters can tip the election by misrepresenting their true preferences).<\/li>\n<\/ol>\n

      Again, whether strategic voting is a bad thing depends on your point of view.\u00a0 It does seem unfair in that some voters who are less informed might naively vote their true preferences, while others may vote strategically and exert an undue influence.\u00a0 Even if everyone had perfect information, some voters (say, voters who prefer a hopelessly small party) are in a much better position to swing the election to their second choice than anyone else.\u00a0 But perhaps this is a difference we can live with\u2014after all, a voter who is fiercely dedicated to one candidate and will vote for them come hell or high water is far less influential than a swing voter who can be persuaded to change their vote, no matter what the system.\u00a0 Still, it seems prudent to try to limit the advantage that a small group of savvy, strategically-minded voters have over the rest of us, just as it seems prudent to lessen the chances of an irrelevant alternative causing an upset.<\/p>\n

      This observation then, bring us to our solution, if you can call it that, to the seeming impossibility of a fair system.\u00a0 While in theory no system can meet\u00a0all the fairness criteria we may desire, our challenge\u00a0is to design a system that will minimize the likelihood of an unfair outcome. Thus, our “perfect design” problem becomes an optimization problem, and luckily there are many candidates: instant runoff voting<\/a>, approval voting<\/a>, and the Condorcet method<\/a> to name a few (Wikipedia\u2019s coverage of these topics is extensive).\u00a0 The plurality system (the most common one used in the US) is almost certainly not<\/em> the optimal solution since its highly manipulable by strategic voters and violates a number of other fairness criteria, though its simplicity does have great appeal. \u00a0Instant runoff voting, used in Australia and some local U.S. elections, has a number of weird flukes, such as a\u00a0vote for your favorite candidate actually hurting their chances, though it’s unclear if this is more of a concocted scenario that is likely never to pop up in the real world. \u00a0“Most systems are not going to work badly all of the time,” <\/strong>Kenneth Arrow stated, in the lead up to the 2008 election. “All I proved is that all can work badly at times.”<\/strong> \u00a0(See here<\/a> for full discussion this paragraph is based on). Perhaps one of you will find a system that is likely to never behave badly in real world conditions.\u00a0 While that may sound modest, finding such a system could still be a huge contribution of mathematics to the\u00a0the\u00a0fairness of democracies around the world.<\/p>\n

      Works Cited:<\/p>\n

      Arrow, Kenneth J. “A difficulty in the concept of social welfare.” The Journal of Political Economy<\/i> (1950): 328-346.<\/p>\n

      Geanakoplos, John. “Three brief proofs of Arrow\u2019s impossibility theorem.” Economic Theory<\/i> 26.1 (2005): 211-215.<\/p>\n

      McKenna, Phil. “Vote of no confidence.” New Scientist<\/i> 198.2651 (2008): 30-33.<\/p>\n

      Graphics in public domain, available:\u00a0https:\/\/en.wikipedia.org\/wiki\/Voting#\/media\/File:Vote_12345.jpg<\/p>\n

      Also consulted:\u00a0https:\/\/en.wikipedia.org\/wiki\/Arrow%27s_impossibility_theorem<\/p>\n

      <\/div>","protected":false},"excerpt":{"rendered":"

      In 1950, a 29-year-old PhD candidate at Columbia published a stunning theorem that later won him a Nobel Prize: \u201cThere is no such thing as a fair voting system.\u201d\u00a0 Or so the legend goes.\u00a0 Let\u2019s dive into this claim and … Continue reading →<\/span><\/a><\/p>\n

      <\/div>\n","protected":false},"author":93,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[12,14,15,163,1,118],"tags":[261,257,124,260,259],"class_list":["post-31350","post","type-post","status-publish","format-standard","hentry","category-math","category-math-in-pop-culture","category-mathematics-in-society","category-social-justice","category-uncategorized","category-voting-theory","tag-arrows-impossibility-theorem","tag-elections","tag-math","tag-social-choice","tag-voting"],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p3gbww-89E","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/31350","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/users\/93"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/comments?post=31350"}],"version-history":[{"count":5,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/31350\/revisions"}],"predecessor-version":[{"id":31362,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/posts\/31350\/revisions\/31362"}],"wp:attachment":[{"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/media?parent=31350"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/categories?post=31350"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ams.org\/mathgradblog\/wp-json\/wp\/v2\/tags?post=31350"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}

    On its surface, this criterion seems like the sort of fairness we would want in a system, though like Euclid\u2019s parallel\u00a0postulate, it does seem a bit more complex than the other basic assumptions. Most\u00a0systems around the world violate IIA. \u00a0The 2000 Gore versus Bush election, for example, likely constituted an IIA violation: that is, presence of third party candidate Ralph Nader tipped the election from Gore to Bush, even though the\u00a0Nader\u00a0voters did not necessarily like Bush more Gore.\u00a0 This does seem unfair, at least to Gore and Bush, though not necessarily for the voters.\u00a0 Arrow\u2019s Impossibility Theorem assumes the people actually vote according to their mental ranking of the candidates: that is, they vote naively, <\/em>not strategically.\u00a0 <\/em>If you assume these Nader voters knew the potential outcome of their actions (and that\u2019s a big “if”), then the system was taking into account their preferences: that is, they cared so much about Nader that they were willing risk\u00a0Gore losing even if they preferred him over Bush.\u00a0 Note that Arrow\u2019s Impossibility Theorem only takes into account\u00a0rankings<\/em>, not ratings<\/em>. <\/em>Allowing voters to rank each candidate on scale of 1-10 (or grade them A-F), a system known as range voting<\/a> actually avoids Arrow\u2019s paradox altogether.\u00a0 However, if at least some of our voters are strategic, then this system is highly manipulable (e.g. even if don\u2019t think your second choice candidate is so bad, you give her an F if you think the election is going to be close).\u00a0 In fact, the even more consequential (though less famous) impossibility theorem known as Gibbard\u2013Satterthwaite Theorem<\/a><\/strong>\u00a0<\/strong>states that every voting system is either:<\/p>\n