Summability criterion: Difference between revisions

[[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.

Summability focuses to a large extent on the number of data value types, not just the amount of data overall that has to be captured. This can make a difference in certain cases; for example, the regular [[pairwise counting]] approach only requires (<math>n^2-n)</math> data value types to be captured for all ballots, whereas the [[Negative vote-counting approach for pairwise counting]] requires (<math>n^2)</math> value types. This is because the latter not only records preferences in each pairwise matchup, but also the number of ballots ranking each candidate. Yet, depending on implementation, the negative counting approach actually has the same upper bound on number of data values to capture as the regular approach, and in practice could require fewer.