Summability criterion: Difference between revisions
Add precise definition that closes a loophole, and add multiwinner results.
Jonah Thomas (talk | contribs) |
(Add precise definition that closes a loophole, and add multiwinner results.) |
||
Line 5:
Each vote should map onto a summable array, where the summation operation is associative and commutative, and the winner should be determined from the array sum for all votes cast. An election method is ''kth-order summable'' if there exists a constant ''c'' such that in any election with ''n'' candidates, the required size of the array is at most ''cn<sup>k</sup>''. If there is no value of ''k'' for which the method is ''k''th-order summable, the method is ''non-summable''.
Strictly speaking, a method is kth-order summable if an election involving <math>V</math> voters and <math>c</math> candidates can be stored in a data structure (a summary) that requires <math>O(\log(V) \cdot c^k)</math> bits in total, where there exists a summation operator that takes any two such summaries and produces a third for the combined election, and the election method itself can use these summaries instead of ballot sets to produce the same results. This definition closes the obvious loophole of using a few very large numbers to store more data than would otherwise be permitted.
== Summable Methods ==▼
== Multi-winner generalizations and results ==
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> The same approach can be generalized to make a Droop-proportional method that's fixed-parameter summable in <math>O(log(V) \cdot c^s)</math> where <math>s</math> is the number of seats, by keeping a separate count for each solid coalition of size <math>s</math> or less.
It's unknown whether it's possible to construct a Droop-proportional method that's summable in <math>O(log(V) \cdot c^k \cdot s^n)</math> for constant <math>k</math> and <math>n</math>.
{| class="wikitable" align="center" |border="1"
| |||