Talk:Summability criterion: Difference between revisions

Is DSC really second-order summable, or is this an error? If it's not an error, then how do you construct a cn² summation array?

For practical purposes, it's correct only for small numbers of candidates. Otherwise, the number of summation array entries will be so large that it's simply more efficient to record the actual ballots. For example, consider an IRV election with 12 candidates and 10 000 voters. With a summation array, this takes 12×(2^11-1) = 24 564 entries of 2 bytes each, for a total of 49 128 bytes. By storing the actual ballots, encoded as 4-byte numbers (the minimum needed with 479 million possible fully-ranked ballots), you would need only 40 000 bytes. Contrast this to a Condorcet matrix (n(n-1) entries), in which the summation array requires fewer bytes than the ballots even with 7000 candidates. [[User:DanBishop|DanBishop]] 17:17, 3 Jul 2005 (PDT)

I'm curious how one would prove that e.g. IRV can't possibly be summable. Most of the arguments go that IRV requires the full ballot count and that the full count is obviously not summable, but a proper proof would have to show that there exists no polynomial-space structure that can sum up the ballots in a way that an algorithm can use to return the result IRV would. I'm not aware of any proof of that sort, so it might be useful to add some sources to the "not summable" column.

In contrast, proving that something ''is'' summable is easy enough: just show an algorithm. [[User:Kristomun|Kristomun]] ([[User talk:Kristomun|talk]]) 14:12, 20 February 2020 (UTC)

The article says "Election methods with lower summability levels are substantially easier to implement with integrity than methods with higher summability levels". While I understand what this says, it seems potentially confusing to use "lower" to mean "more easily summable" and vice versa. I won't change it, but I'm curious if anyone has solutions. [[User:BetterVotingAdvocacy|BetterVotingAdvocacy]] ([[User talk:BetterVotingAdvocacy|talk]]) 08:41, 24 April 2020 (UTC)

MJ is now in summability order 2, along with Bucklin. That's where it should be: it used to be in the "non-summable" column. To use an <math>\mathcal{O}(c^2)</math> array to calculate the MJ winner, let <math>a_{ij}</math> be the number of people who gave candidate <math>i</math> the <math>j</math>th best grade. If <math>i</math>'s median grade is higher than <math>k</math>'s, then (by definition) a majority of the voters graded <math>i</math> at the same grade or a higher grade than they did <math>k</math>. That's how Bucklin works. The tiebreaker can similarly be handled by subtracting one from the relevant column for both candidates until the majority is attained at different grades for the two candidates. [[User:Kristomun|Kristomun]] ([[User talk:Kristomun|talk]]) 09:10, 6 May 2020 (UTC)

Looking at [[w:Nanson's method]], there is a source (http://rsnz.natlib.govt.nz/volume/rsnz_46/rsnz_46_00_005780.html) showing how Nanson's method can be computed off of a pairwise matrix. If this is the case, then we can move it to 2nd-order summability; can someone verify this? [[User:BetterVotingAdvocacy|BetterVotingAdvocacy]] ([[User talk:BetterVotingAdvocacy|talk]]) 06:05, 15 May 2020 (UTC)