Voting system characteristics

governance

(Tim Peters) #1

Continuing the discussion from Python Governance Electoral System:

Splitting off a new topic here.

This was a addressed in a sub-thread here, but not reflected in PEP 8001:

But nothing new to say about that :wink:


Python Governance Electoral System
(Łukasz Langa) #2

Could you run simulations with fewer candidate PEPs to see how much it makes things better?

PEP 8016 is very similar to PEP 8015 and both are very similar in spirit to my own PEP 8012. I would consider withdrawing 8012 if it increases the odds of avoiding a voting fiasco. I recall @steve.dower considered the same.


(Tim Peters) #3

Sure, but it’s not realistic. We shouldn’t let the voting system drive anything. “Vote splitting” isn’t really a thing under Condorcet methods - at worst, two (or three …) similar PEPs get ranked equally by voters, which may increase the chance of a tie. Big deal. Then we vote again - and that’s the point at which someone may wish to withdraw a PEP for “voting system reasons”.

Here are empirical probabilities of getting a flat-out Condorcet winner for various pairs of number of voters (in the first column) and number of candidates (in the first row). For example, if there are 12 voters and 2 candidates, the chance of a Condorcet winner is about 77%.

      1   2   3   4   5   6   7
  1 100 100 100 100 100 100 100 
  2 100  50  34  25  20  18  15 

 11 100 100  92  83  77  71  66 
 12 100  77  62  50  42  36  31 

 21 100 100  92  83  75  70  65 
 22 100  83  67  55  48  42  38 

 31 100 100  91  83  76  69  64 
 32 100  87  72  62  52  46  41 

 41 100 100  92  83  76  68  63 
 42 100  88  74  64  55  49  43 

 51 100 100  92  83  75  69  64 
 52 100  90  75  64  56  50  45 

 61 100 100  91  83  76  69  64 
 62 100  90  77  66  58  52  46 

 71 100 100  91  82  76  68  63 
 72 100  91  78  67  60  53  47 

 81 100 100  92  83  76  69  64 
 82 100  91  77  68  60  53  48 

 91 100 100  91  82  75  69  64 
 92 100  92  79  69  61  55  48 

101 100 100  91  82  75  68  64 
102 100  92  79  69  62  55  49 

Notes:

  • Every voter picks a permutation of the candidates uniformly at random. This is highly unrealistic. In real life, many voters will have highly correlated rankings, increasing the chance of getting a Condorcet winner.
  • Every ballot here is a total ordering. We’re allowing partial orderings, which increase the chance of ties.
  • Because these ballots are total orderings, a pairwise tie is impossible when there are an odd number of voters. That’s why the results for even numbers of voters are so much worse. The lack of a Condorcet winner in the latter cases isn’t so much due to preference cycles, but due to “the best” candidate getting at least as many votes in all one-on-one pairings, but also tied in at least one.pairing. It’s not “a Condorcet winner” then.
  • If you run this simulation multiple times, the last digits may vary. The results are approximate.

Finally, here’s the code that produced the output above:

    def probcw(ncands, nvoters):
        from collections import defaultdict
        from itertools import combinations
        from random import shuffle

        ntries = ncw = 0
        oldmean = 0.0
        cands = list(range(ncands))
        V = defaultdict(int)
        while True:
            ntries += 1
            V.clear()
            for v in range(nvoters):
                shuffle(cands)
                for pair in combinations(cands, 2):
                    V[pair] += 1
            winner = None
            for i in cands:
                if all(i == j or V[i, j] > V[j, i] for j in cands):
                    winner = i
                    break
            if winner is not None:
                ncw += 1
            if ntries % 1000 == 0:
                mean = round(ncw / ntries, 3)
                if mean == oldmean:
                    return mean
                oldmean = mean

    print("      1   2   3   4   5   6   7")
    for nvoters in range(1, 102, 10):
        for nvoters in range(nvoters, nvoters + 2):
            print(f"{nvoters:3d}", end=" ")
            for ncands in range(1, 8):
                pcw = round(probcw(ncands, nvoters) * 100)
                print(f"{pcw:3d}", end=" ")
            print()
        print()

(Tim Peters) #4

FYI, some by-eyeball patterns in that table are legit:

  • The stark difference between odd and even numbers of voters diminishes the more voters there are, and tends to 0. But it remains highly significant with a number of voters as high as the table goes up to.
  • If the number of candidates >= 3, the probability of getting a Condorcet winner pretty rapidly approaches a limit (as the number of voters increases) strictly less than 1.0, and lower the more candidates there are. For an odd number of voters, this is entirely due to preference cycles among the best-scoring candidates (for an even number of voters, it’s also about pairwise ties).

As a sanity check, here’s a theoretical derivation of probabilities as the number of voters goes to infinity. There is no closed form expression, but there is a relatively simple integral of functions related to the normal distribution. The “infinite number of voters” values in the table following are already approximately matched by the voters=31 row of the earlier table:

candidates P(CW)*100
1 100.0
2 100.0
3 91.2
4 82.5
5 74.9
6 68.5
7 63.1
8 58.5
9 54.5

Actually, that’s clear as mud :wink:. It is unrealistic, but correlations can push things in either direction, depending on their precise nature. In most studies I’ve stumbled into, the rate of Condorcet winners in real life elections were higher than the model above suggests - but in some studies, the rate was lower. So “it depends” - but it’s unclear on what it depends.