[EM] Summability impossibility proofs

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

[EM] Summability impossibility proofs

Kristofer Munsterhjelm-3
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?
----
Election-Methods mailing list - see https://electorama.com/em for list info