Talk:Summability criterion

This is the discussion page (the "Talk:" page) for the page named "Summability criterion". Please use this page to discuss the topic described in the corresponding page in the main namespace (i.e. the "Summability criterion" page here on electowiki), or visit Help:Talk to learn more about talk pages.

DSC

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?

I couldn't make it work. DSC needs 2^n numbers. That's still much more feasible than IRV, though. -Kevin Venzke

The article says "The votes cannot be compressed by summing as in other election methods because votes may need to be transferred according to which candidates are eliminated in each round." Is this really entirely accurate? In each round the candidate to be eliminated is determined from the number of votes placing each uneliminated candidate first in the set of uneliminated candidates. This means (assuming tie-break rules that don't create added complication) that recording, for every set of 2 or more candidates, the number of votes giving top place within the set to each candidate in the set, will suffice. This is a summable array of n(2^(n-1)-1) numbers, still failing the criterion but enough to make the statement that "the votes cannot be compressed by summing" incorrect. Am I missing something? - DPJ

Interesting argument. KVenzke

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. DanBishop 17:17, 3 Jul 2005 (PDT)

Disproofs

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. Kristomun (talk) 14:12, 20 February 2020 (UTC)

Lower vs higher to describe level of summability

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. BetterVotingAdvocacy (talk) 08:41, 24 April 2020 (UTC)

Bucklin and MJ

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 ${\mathcal {O}}(c^{2})$ array to calculate the MJ winner, let $a_{ij}$ be the number of people who gave candidate $i$ the $j$th best grade. If $i$'s median grade is higher than $k$'s, then (by definition) a majority of the voters graded $i$ at the same grade or a higher grade than they did $k$. 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. Kristomun (talk) 09:10, 6 May 2020 (UTC)

Condorcet-Borda hybrids

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? BetterVotingAdvocacy (talk) 06:05, 15 May 2020 (UTC)

After having looked at the page, I agree that both Nanson and Baldwin are 2nd-order summable. This has to do with a relation between the pairwise matrix and Borda scores (in the absence of equal-rank); I just didn't think of it before now. I'll make the change. Kristomun (talk) 18:47, 22 May 2020 (UTC)