Page 1 of 6 123 ... LastLast
Results 1 to 10 of 51

Thread: Vote-counting

  1. Top | #1
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    10,103
    Archived
    16,829
    Total Posts
    26,932
    Rep Power
    85

    Vote-counting

    This is about systems of counting votes, both actually used and theoretically proposed. Comparison of electoral systems has a big comparison of them, using a variety of criteria. We've had threads on some methods:

    Elections are to be interpreted broadly -- votes for *anything*.

    I'll start off with a very simple method, first-past-the-post or plurality voting. Imagine you and 11 friends want to vote on what topping you want to put on a pizza. It seems easy. Everybody votes for a topping, and whichever topping gets the most votes is the topping that the pizza gets.

    Let's say that one has sausage and green peppers. Easy. 5 of your group want sausage and 7 want pepper. Pepper wins, and everybody has pepper pizza.

    Let's say that the vegetarians want more variety. They make artichoke a possibility. The meat lovers are satisfied with sausage, however. So they vote on what to put on their pizza. 5 want sausage, 4 want pepper, and 3 want artichoke. It's the sausage that gets put on the pizza. The vegetarians lost because of the spoiler effect: vote splitting from similar candidates.

  2. Top | #2
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    10,103
    Archived
    16,829
    Total Posts
    26,932
    Rep Power
    85
    That is a reason for interest in alternatives to FPTP. Though they are more complicated, some of them are immune to the spoiler effect. They all involve each voter being able to cast more than one vote, and some FPTP defenders defend FPTP by interpreting "one person one vote" too literally. But the spirit of that slogan is that everybody in some election must have equivalent voting power -- have the same ballot and be weighted the same.


    A simple solution is to allow voting for more than one candidate -- approval voting. One then adds up the vote as with FPTP. Back to the pizza. With approval voting, the votes are: sausage 5, green pepper 2, artichoke 1, GP+AC 4. That gives totals sausage 5, green pepper 6, artichoke 5. Green pepper wins.

    A fancier version is to use values between 0 and 1 -- rated vote.

    A version that is used in elections of the Secretary General of the United Nations adds disapproval to approval. So one can vote (approve, neutral, disapprove). That is equivalent to a rated vote with values 0, 1/2, and 1.

    Cumulative voting is where everybody gets some number of votes, and that they can be distributed how one likes on the ballot -- concentrated in some favorite candidate or spread out between more than one candidate. This is equivalent to a rated vote with values that sum up to 1.

  3. Top | #3
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    10,103
    Archived
    16,829
    Total Posts
    26,932
    Rep Power
    85
    An alternative to such vote multiplicity is multiple elections -- runoffs.

    A simple sort is a top-two runoff or a two-round/two-ballot system. In the first election, all the candidates compete, and the top two of them then compete in a second election. This second election is sometimes skipped if the first election gives a candidate with the majority of the vote.

    Thus, in that pizza example, we start with sausage 5, green pepper 4, artichoke 3. Artichoke drops out, and sausage and green pepper go head-to-head, getting sausage 5, green pepper 7.

    An alternative is the exhaustive ballot or sequential runoff, where in each round of voting, the candidate that did the worst is dropped before continuing. The vote ends when one candidate is left or else when one candidate has gotten a majority of the votes.

    -

    Can one compress these elections into one election? Yes one can, by doing ranked-choice or preference voting. One ranks the candidates by one's preference: first choice, second choice, etc.

    With only a second vote, one gets a system called variously the contingent vote or the supplementary vote. The first preferences are counted first, and if no candidate wins a majority, then all but the top two are eliminated, and if any second-preference top-two ones are then revealed by this elimination, then they are included in the count. It is a compressed version of top-two runoff.

    For more levels of preference, it's instant runoff voting, a compressed version of sequential runoff.

    -

    For preference / ranked-choice voting, there are numerous ways of counting the ballots.

    A simple one is the Borda count. For n candidates, one's top choice gets weight n, one's next choice weight (n-1), one's next choice weight (n-2), and so forth. Essentially turning the vote into a kind of rated vote.

  4. Top | #4
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    10,103
    Archived
    16,829
    Total Posts
    26,932
    Rep Power
    85
    There is a theoretically interesting criterion called the "Condorcet criterion". It involves having a "Condorcet winner", the candidate who beats every other candidate if the ballots are interpreted as sets of one-on-one contests where the more preferred one wins, a sort of virtual round robin. One can add up the outcomes of the contests to make a "Condorcet matrix" and then work for there.

    Some sets of ballots may not have a Condorcet winner, and some methods do not necessarily produce such a winner when one is present -- all the methods that I've discussed previously.

    I've found several examples of how different vote-counting methods can give different results. Math Alive — Voting & Social Choice — Lab 1 and L27 - Does the Majority always rule? have the same preference ballots under different names.

    How Many 1st 2nd 3rd 4th 5th
    18 Sausage Artichoke Mushrooms Peppers Anchovies
    12 Anchovies Mushrooms Artichoke Peppers Sausage
    10 Peppers Anchovies Mushrooms Artichoke Sausage
    9 Artichoke Peppers Mushrooms Anchovies Sausage
    4 Mushrooms Anchovies Artichoke Peppers Sausage
    2 Mushrooms Peppers Artichoke Anchovies Sausage

  5. Top | #5
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    10,103
    Archived
    16,829
    Total Posts
    26,932
    Rep Power
    85
    Top One (First Past the Post, Plurality)
    • Sausage: 18
    • Anchovies: 12
    • Peppers: 10
    • Artichoke: 9
    • Mushrooms: 6

    Sausage

    Top-Two Runoff:
    • Round 1
      • Sausage: 18
      • Anchovies: 12
      • Peppers: 10
      • Artichoke: 9
      • Mushrooms: 6
    • Round 2
      • Anchovies: 37
      • Sausage: 18

    Anchovies

  6. Top | #6
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    10,103
    Archived
    16,829
    Total Posts
    26,932
    Rep Power
    85
    Sequential Runoff:
    • Round 1
      • Sausage: 18
      • Anchovies: 12
      • Peppers: 10
      • Artichoke: 9
      • Mushrooms: 6
    • Round 2
      • Sausage: 18
      • Anchovies: 16
      • Peppers: 12
      • Artichoke: 9
    • Round 3
      • Peppers: 21
      • Sausage: 18
      • Anchovies: 16
    • Round 4
      • Peppers: 37
      • Sausage: 18
    • Round 5
      • Peppers: 55

    Peppers

    Borda Count:
    • Artichoke: 191
    • Mushrooms: 189
    • Peppers: 162
    • Anchovies: 156
    • Sausage: 127

    Artichoke

  7. Top | #7
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    10,103
    Archived
    16,829
    Total Posts
    26,932
    Rep Power
    85
    Condorcet matrix:
    Anchovies Artichoke Mushrooms Peppers Sausage
    Anchovies 0 26 22 16 37
    Artichoke 29 0 27 43 37
    Mushrooms 33 28 0 36 37
    Peppers 39 12 19 0 37
    Sausage 18 18 18 18 0
    Condorcet Winner:

    Mushrooms

    Mushrooms beat anchovies 33-22, artichoke 28-27, peppers 36-19, sausage 37-18

    The different results of the different vote-counting methods is something related to Arrow's Theorem, derived by economist Kenneth Arrow. It states that there can be no algorithm for counting preference votes that always satisfies certain nice theoretical properties.

    But that does not seem to be much of a problem in practice.

  8. Top | #8
    Veteran Member
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,960
    Archived
    4,797
    Total Posts
    8,757
    Rep Power
    62
    A modest proposal: Reverse Sequential Runoff

    Round 1
    • Sausage: 37
    • Anchovies: 18
    • Peppers: 0
    • Artichoke: 0
    • Mushrooms: 0

    Round 2
    • Anchovies: 29
    • Peppers: 16
    • Artichoke: 10
    • Mushrooms: 0

    Round 3
    • Peppers: 34
    • Artichoke: 12
    • Mushrooms: 9

    Round 4
    • Artichoke: 28
    • Mushrooms: 27

    Round 5
    • Mushrooms: 55


    Matches the Condorcet winner in your example, and, I think, usually. Always produces an outcome, unlike Condorcet. Easier to explain to people than Condorcet.

  9. Top | #9
    Administrator lpetrich's Avatar
    Join Date
    Jul 2000
    Location
    Eugene, OR
    Posts
    10,103
    Archived
    16,829
    Total Posts
    26,932
    Rep Power
    85
    Having a Condorcet winner is a property that is satisfied by several algorithms for counting preference votes.

    The Schulze beatpath method tries to find a sequence of candidates where the smallest margin of victory along that sequence is as large as possible. It seems like it runs in factorial time, needing O(n!) operations for n candidates, but a version of something called the Floyd-Warshall algorithm reduces it to O(n^3).

    The Copeland method counts up how many victories each candidate has over other candidates while subtracting that number of defeats. The highest score gives the winner.

    The minimax method finds the best performance of other candidates against each one. The lowest of these best performances gives the winner.

    The Kemeny-Young method goes through every permutation of the candidates, then for each permutation, adds up the scores for each candidate's victory over later candidates in the permutation. The highest total score gives the winner.

    The Dodgson method does permutations of the ballot entries, the same permutation for each one. For each permutation, it finds the Condorcet winner, if there is one, and the one with the smallest "permutation distance" of its permutation gives the winner. The "permutation distance" is the minimum number of interchanges needed to go from the identity permutation to that permutation. That distance is (size of permutation) - (number of cycles in it).

    The Kemeny-Young and Dodgson methods both run in O(n!) time, since they need to go through every possible permutation of n entities.

    The Tideman ranked-pairs algorithm first sorts each pair of candidates by how well one of them beats the other, and then starts with the best-performing one of these. It then attaches the best remaining one that does not produce a loop, making a Directed Acyclic Graph. When it is done, the top one is the winner.

    The maximum-lotteries algorithm essentially generalizes the notion of Condorcet winner to make partial Condorcet winners. It does so by doing some linear programming. I implemented that one with the simplex algorithm. The highest partial fraction gives the winner. Linear programming is, in general, NP-complete, meaning that there is no known algorithm guaranteed to work in polynomial time for it.

    I have some implementations: lkpetrich/Preference-Voting: For counting votes in preference voting. Implements a large number of algorithms.

  10. Top | #10
    Veteran Member
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,960
    Archived
    4,797
    Total Posts
    8,757
    Rep Power
    62
    Quote Originally Posted by lpetrich View Post
    The maximum-lotteries algorithm essentially generalizes the notion of Condorcet winner to make partial Condorcet winners. It does so by doing some linear programming. I implemented that one with the simplex algorithm. The highest partial fraction gives the winner. Linear programming is, in general, NP-complete, meaning that there is no known algorithm guaranteed to work in polynomial time for it.
    Linear programming is not NP-complete. There are polynomial algorithms for it, such as Karmarkar's algorithm.

    Also, that's not what NP-complete means. A problem being NP-complete means all the other NP problems are reducible to it. There are a variety of NP problems that have no known polynomial algorithms but that aren't NP-complete; the most famous is the problem of finding the prime factors of large composite numbers. If somebody finds a polynomial solution for that next year, it will kill RSA encryption and make a mess of the internet credit card economy, but it won't solve the traveling salesman problem. It's an asymmetrical situation -- if somebody finds a polynomial solution for the traveling salesman problem next year, that will automatically also provide a solution for factoring RSA keys.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •