[EM] Linear summability

[Kristofer Munsterhjelm]

Some time ago I was wondering how to prove that a method is nonsummable.
Just because we don't know of any way to make e.g. IRV summable doesn't
mean there isn't any. I couldn't figure out how you'd definitely exclude
every possible polyspace array.

But I think I've found something that works; or at least a foundation
for something that works.

Suppose the summability we're concerned about is with the plus operator
instead of just any general associative commutative operator. (So no
cell holds e.g. the maximum of all precincts' cells.)

And suppose the win regions for the candidates (i.e. the criteria that
have to hold for a candidate to win) are unions of convex polytopes
(which seems to be true for any method I can think of).

Then the method, for a candidate A, needs to be able to distinguish
between every point that is in A's win region and every point that
isn't. In particular, in the case that each win region is a convex
polytope, the data given by the summable precinct counts must form a
basis for the space formed by the constraints. And if the dimension of
that vector space grows as a polynomial of the number of candidates,
then the method is summable, otherwise it is not.

If the win region is a union of such convex polytopes, then the same
logic should still hold for every individual polytope as long as it's
not redundant (not implied by some other).

Formally, I *think* something like this should work: if the no union of
the convex polytopes is in itself a convex polytope, then suppose that
the dimension of the vector space given by the summable data structure
(call it X) is less than the dimension of the vector space given by
every constraint. Then there exists an election inside one of the
polytopes where A wins, but it's possible to add a vector that doesn't
change the representation in X, but does push the election outside of
the current convex polytope part of A's win region. Since no union of
the convex polytopes is itself a convex polytope, it is possible to push
the election outside of this polytope without it immediately entering
another. So two elections that appear the same in X-space conflict as to
whether A wins, which contradicts the claim that X shows that the method
is summmable.

E.g. for DSC, the win region for A is (unless I missed something)
	AB > AC and AC > BC and A>B (C is excluded and then A wins vs B)
or	AC > AB and AB > BC and A>C (B is excluded and then A wins vs C)
or	A > BC                      (A wins outright)

where the labeled variables are coalition counts, e.g. AB is ABC and A
is ABC + ACB. The dimension of the space with (A, AB, AC, BC, A, B, and
C) as bases is six, so the summation array for DSC must be at least six
long for three candidates.

Now enter extreme handwaving: because this matches the "natural" count
of 2^c-2 for the number of coalitions (all possible subsets minus the
set of every candidates and the empty set), that implies that DSC
requires every coalition count to decide if A is the winner; and if it's
denied any of them (or has one of them replaced by a linear combination
of the others), you can construct a pair of elections where A wins and
doesn't win, but that looks the same when you consider every coalition
apart from the missing one. And thus, the dimension of the constraint
space is 2^c-2, which is superpolynomial in c, and hence DSC is not
summable.

But I haven't actually *proven* that. Still, it's a strategy, which is
better than not knowing where to begin :-) The rest is an engineering
problem, etc.

I suspect the way to go about proving it for DSC would be inductively,
but I can't quite get at how. It's much easier for IRV, where A wins the
four-election if A is not eliminated and then wins the resulting
three-election. In either case, it would be necessary to show that every
introduced constraint is linearly independent of the others; or to
remove those that are, and show that the dimension of the space induced
by those that remain still grows superpolynomially.


Similar reasoning would indicate that a linear-summable Condorcet method
requires at least O(c^2) elements in the summation array, because
identifying A as a CW requires all pairwise victories involving A, and
so for every other candidate, and it's impossible to get one pairwise
victory from a linear combination of the others. But here we'd have to
be careful: a method could possibly be Condorcet plus something else in
such a way that the union of the Condorcet criterion and the something
else is a simpler convex polytope that nevertheless does not intrude
into anyone else's "is a CW" win region.

That's probably why explicitly identifying the smallest mutual majority
set seems to be much harder than just making a method that passes mutual
majority, or how methods can be independent of clones without ever
directly identifying any clone sets.