election-methods@mailman.electorama.com

Technical discussion of election methods

View all threads

Summability impossibility proofs

KM
Kristofer Munsterhjelm
Thu, Feb 20, 2020 11:30 PM

I was again looking through Electowiki when I got to thinking: do we
have proofs that particular methods are non-summable?

It's pretty easy to see that e.g. sending over all c! different
preference orders (along with their weights) is not summable, and thus
it's reasonable to suspect that IRV is not polyspace summable, but do we
have any rigorous proofs that there exists no data structure of
polynomial size that can be used to get IRV results?

Maybe I'm just not looking in the right places. How would one begin to
prove that e.g. there exists no Condorcet method that summable with an
array of length O(c) (i.e. not c^2 like the pairwise matrix) -- or that
there is no possible O(c) array that can be used to get the IRV winner?

I was again looking through Electowiki when I got to thinking: do we have proofs that particular methods are non-summable? It's pretty easy to see that e.g. sending over all c! different preference orders (along with their weights) is not summable, and thus it's reasonable to suspect that IRV is not polyspace summable, but do we have any rigorous proofs that there exists no data structure of polynomial size that can be used to get IRV results? Maybe I'm just not looking in the right places. How would one begin to prove that e.g. there exists no Condorcet method that summable with an array of length O(c) (i.e. not c^2 like the pairwise matrix) -- or that there is no possible O(c) array that can be used to get the IRV winner?