[EM] Summability machinery

[Kristofer Munsterhjelm]

Here's the machinery I used to determine the funny summability result in 
my post about Plurality.

If we characterize single-winner methods by their win regions, i.e. a 
function f(A) that's > 0 if A wins, = 0 if A ties, and < 0 if A loses, 
then most single-winner methods can be cast as a collection (union) of 
convex polytopes, of the form:

A wins if
	OR over i = 1..k
		AND over j = 1..m
			A_j,m * x > b_j,m

For instance, for Plurality with three candidates:

let x = [ABC ACB BAC BCA CAB CBA]^T where the variables denote how many 
voters ranked the candidates in the order given.

A wins if [1, 1, 0, 0, -1, -1] x > 0  (A has more first prefs than C) and
	[1, 1, -1, -1, 0, 0] x > 0 (A has more first prefs than B)

Similarly, B wins if [0, 0, 1, 1, -1, -1] x > 0 and [-1, -1, 1, 1, 0, 0] 
x > 0,
and C wins if [0, 0, -1, -1, 1, 1] x > 0 and [-1, -1, 0, 0, 1, 1] x > 0.

Now take all the rows of the individual polytope matrices, stack them, 
and determine the rank of this matrix.

For Plurality, the stacked matrix is
	[1, 1, 0, 0, -1 ,-1]
	[1, 1, -1, -1, 0, 0]
A =	[0, 0, 1, 1, -1, -1]
	[-1, -1, 1, 1, 0, 0]
	[0, 0, -1, -1, 1, 1]
	[-1, -1, 0, 0, 1, 1]

which has rank 2. One possible set of basis vectors is
	[1, 1, 0, 0, -1, -1]
	[0, 0, -1, -1, 1, 1]
fpA-fpC and fpB-fpC as in my other post.

The point is that if the stacked matrix has rank k, then we can project 
the vote vector x to its k-dimensional space and then use that as a 
summary. Since the matrix operation is linear, these projections can be 
summed together at the central location, and can be used to determine 
the values for all A_j,m * x, hence all the information we need to 
determine who won (or tied).

Thus for Plurality, since the A matrix rank is 2 and the space is 2D, we 
only need two values.

There's a small caveat. If the b values are not constant but instead 
derived from the vote data, then they need to be included in the 
summaries. For instance, consider a majority criterion (say, a part of IRV):
	[2, 2, 0, 0, 0, 0] x > numvoters
then we need to also keep count of the number of voters. The easiest way 
to check if that's already in the space would be to just append the row 
[1, 1, 1, 1, 1, 1] to the A matrix. (In the Plurality case, this 
increases its rank to 3.) Alternatively, for such checks, one can do

	[2, 2, 0, 0, 0, 0] x > numvoters
is equivalent to
	[2, 2, 0, 0, 0, 0] x > [1, 1, 1, 1, 1, 1] x
=
	[1, 1, -1, -1, -1, -1] x > 0.

Not all methods can be cast this way. For instance, STV depends on 
surplus transfers where the value of the surplus matters. But I think 
they can still be handled this way if one's being appropriately clever. 
(Maybe not Meek though.)

I also suspect that the rank-based summary results are minimal, i.e. you 
can't have a smaller number of summary values and sum them using the 
addition operator. But I don't have a proof of this. My sketch is 
something like: suppose f is based on a union of convex polytopes, and 
returns only -1, 0, or 1. Suppose the A matrix has rank k. Let g be a 
function that accepts the summary of length m < k and returns f for the 
election. Given f, I think it can be shown that the polytopes can be 
reconstructed (it would be computationally hard, but that doesn't matter 
to a theoretical ragument). Then since g is linear (assumption), 
sweeping over every value of g produces a polytope collection in at most 
m-dimensional space. But that contradicts that A has rank k.
Something roughly along those lines.

A major problem is that this approach only gives the number of variables 
to summarize an election with k candidates, since the A matrix and x 
vector length differ based on the number of candidates. It can't give an 
asymptotic summability order directly.

-km