Summability criterion: Difference between revisions
Added strong and weak summability for multiwinner generalizations, and cleaned up that section a bit.
(Mathified n^2 in notes section, and removed the generalization of Simmons' color-proportional summability, as I'm not sure it's correct.) |
(Added strong and weak summability for multiwinner generalizations, and cleaned up that section a bit.) |
||
Line 146:
==Multi-winner generalizations and results==
Most [[block voting]] methods that are based on summable single-winner methods are also of the same degree of summability in the multi-winner case.▼
=== Generalized criteria ===
There's no one extension of the summability criterion for multiple winners, because the summability criterion only considers two variables (the number of voters and the number of candidates), whereas there's one more variable for a multi-winner method: the number of seats. One possible extension of the summability criterion is as follows:<ref>{{cite web|url=http://lists.electorama.com/pipermail/election-methods-electorama.com/2011-July/092996.html|title=Weighted voting systems for proportional representation|website=Election-methods mailing list archives|date=2011-07-24|last=Munsterhjelm|first=K.}}</ref>
* '''Weak summability''': Suppose that the number of seats is fixed. Then the method should be summable in terms of the number of candidates and the logarithm of the number of voters, as a single-winner method is. However, the amount of information required may increase exponentially with the number of seats.
* '''Strong summability''': There must exist a summary that passes summability (i.e. <math>O(\log(V) \cdot c^k)</math> bits in total) which can, after being compiled, be used to determine the outcome for a multi-winner method for ''any'' number of seats.
=== Results ===
Unless otherwise specified, these results pertain to strong summability.
Any method that requires no more than <math>O(\log(V) \cdot c^k \cdot s^n)</math> bits for <math>s</math> seats, with <math>k</math> and <math>n</math> being constants, passes strong summability.
▲Most [[block voting]] methods that are based on summable single-winner methods are also of the same degree of summability in the multi-winner case, and strongly so.
Generally speaking, except for proportional [[:Category:FPTP-based voting methods|Category:FPTP-based voting methods]] (which notably include [[Party list]] and [[SNTV]]), there are no seriously used summable [[:Category:PSC-compliant voting methods|Category:PSC-compliant voting methods]].
Line 152 ⟶ 167:
[[Ebert's method]] is summable in <math>O(c^2)</math> for any number of seats.<ref>{{cite web | title=proof that sum of squared loads is precinct-summable | date=2020-01-14 | url=https://forum.electionscience.org/t/possible-improvement-to-pamsac-gets-rid-of-cfat/566/19 | access-date=2020-04-29}}</ref>
[[Proportional approval voting]] is weakly k-summable with <math>O(\log(V) \cdot c^k)</math> bits, where k is the number of winners.
[[Forest Simmons]] has constructed a color-proportional method that's summable in <math>O(\log(V) \cdot c)</math> for any number of seats.<ref name="RangeVoting.org 2007">{{cite web | title=answer to puzzle 15 | website=RangeVoting.org | date=2007-02-01 | url=https://rangevoting.org/PuzzQWEAns15.html | access-date=2020-02-11}}</ref>
It's unknown whether it's possible to construct a strongly summable Droop-proportional method
==Notes==
| |||