[EM] Summability impossibility proofs

Kristofer Munsterhjelm km_elmet at t-online.de
Thu Feb 20 15:30:16 PST 2020


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?


More information about the Election-Methods mailing list