Talk:Summability criterion

From Electowiki
Jump to navigation Jump to search

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[edit source]

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)