[EM] Preliminary Range PAV results

[Kristofer Munsterhjelm]

Kristofer Munsterhjelm wrote:
> Here are the results for Range PAV from my simulator so far. 

(...)

It turned out I had been a bit quick at writing that code, and a bug had 
slipped in. Instead of calculating a voter's satisfaction of having two 
candidates at rating x and y in the council as f(x + y), I mistakenly 
had it calculated as f(x) + f(y). This would reduce to simple 
majoritarian Approval in the Approval case, explaining the results.

With the bug fixed, I could rerun the program and get sensible results. 
I also took the time to abstract away the exhaustive search into a class 
so it could be extended easily, thus making it very simple to implement 
Warren's birational voting and LPV0+ (actually LPV 0.00001) methods.

"Greedy" means that the method finds the optimum for a single winner, 
then finds the optimum two-winner case by adding a single candidate to 
the single-winner result, and so on. This also means that the greedy 
methods are proportional orders and thus house-monotone; adding a seat 
can't push anyone who's already elected off.

As before, the first parameter is proportionality (by normalized SLI), 
the second is Bayesian regret:

4 candidates, 2 seats, other parameters as on my page:

  Round 77999
Range-Auction(Cumul)                              0.21268 0.05967
Range-Auction(Ordinary)                           0.31496 1e-05
Range_PAV(D'Hondt,_exhaust)                       0.16593 0.04359
Range_PAV(Sainte-Lague,_exhaust)                  0.11764 0.09835
Range_PAV(D'Hondt,_greedy)                        0.16775 0.04299
Range_PAV(Sainte-Lague,_greedy)                   0.12111 0.09653
Birational(exhaustive)                            0.0839  0.14421
Birational(greedy)                                0.09082 0.13803
LPV0+(exhaustive)                                 0.11779 0.37989
LPV0+(greedy)                                     0.11924 0.40599
Maj[Cardinal-20]                                  0.31721 0
Maj[Cardinal-20(norm)]                            0.313   0.00587
STV                                               0.12055 0.09508


5 candidates, 3 seats, other parameters as on my page:

  Round 77999
Range-Auction(Cumul)                              0.20469 0.07099
Range-Auction(Ordinary)                           0.40411 7e-05
Range_PAV(D'Hondt,_exhaust)                       0.1625  0.06899
Range_PAV(Sainte-Lague,_exhaust)                  0.11163 0.13053
Range_PAV(D'Hondt,_greedy)                        0.16399 0.06855
Range_PAV(Sainte-Lague,_greedy)                   0.11382 0.12962
Birational(exhaustive)                            0.06083 0.20635
Birational(greedy)                                0.06465 0.20284
LPV0+(exhaustive)                                 0.179   0.36136
LPV0+(greedy)                                     0.16449 0.38459
Maj[Cardinal-20]                                  0.4139  0
Maj[Cardinal-20(norm)]                            0.40599 0.00586
STV                                               0.08967 0.15652


10 candidates, 4 seats, other parameters as on my page:

  Round 77999
Range-Auction(Cumul)                              0.26478 0.08469
Range-Auction(Ordinary)                           0.36032 9e-05
Range_PAV(D'Hondt,_exhaust)                       0.11422 0.0801
Range_PAV(Sainte-Lague,_exhaust)                  0.08127 0.1295
Range_PAV(D'Hondt,_greedy)                        0.11466 0.08002
Range_PAV(Sainte-Lague,_greedy)                   0.08221 0.12922
Birational(exhaustive)                            0.03802 0.21721
Birational(greedy)                                0.03946 0.21558
LPV0+(exhaustive)                                 0.16795 0.33431
LPV0+(greedy)                                     0.14109 0.35035
Maj[Cardinal-20]                                  0.37049 0
Maj[Cardinal-20(norm)]                            0.36879 0.00863
STV                                               0.03814 0.20276

-

What patterns appear here? The most surprising, I think, is that the 
Range generalizations of PAV remain at roughly the same proportionality 
level, no matter how many seats. One would expect more seats to lead to 
better proportionality (the logical extreme being a council the size of 
the population, which would have perfect proportionality), but that 
doesn't happen with those methods. Birational voting, however, exhibits 
better proportionality as size grows, as does STV.

LPV0+ doesn't do as well, but that isn't really surprising if one stops 
to think about it: consider Warren's "representativeness" criterion, 
which LPV0+ passes. It means that if there's a council that gives every 
candidate a representative (that the intersection of approved candidates 
and the council is never zero, no matter to which voter; thus being a 
sort of set covering problem) then the method must pick that council.
A method that ensures this can't be proportional - just consider the 
following:

50: A
48: A B
  1: C

two to elect. A proportional method will elect A and B, but a method 
passing representativeness must elect A and C. Indeed, Warren showed as 
much in his paper.

Also of note is that even though STV only has access to ordinal 
information, none of the cardinal methods manage to dominate it.