[EM] Trying to prove things with geometry

[Kristofer Munsterhjelm]

Lately I've been trying to follow the win region idea (from my rank 
observations) and find more general results about summability. Here is 
one that I think is correct, but do correct me if something is wrong.

Every voting method that passes Tideman's resolvability, consistency, 
and scale invariance is first- or second-order summable, no matter what 
kind of ballots it uses, in the sense that we can determine who won 
based on the summary.

And here's the proof:

Let an election vector v be the count of how many voters cast ballots of 
each type. For instance, for a strict ranked election with three 
candidates, v has six elements: the number of voters voting A>B>C, A>CB, 
etc, ...,  C>B>A. I'll refer to elections by their vectors, e.g. "an 
election v" is an election with vector v.

Let a candidate A's win region be the set of election vectors v where A 
wins or ties. It follows from resolvability and scale invariance that if 
the vector is on the boundary of the win region, then A ties for first, 
and if it's in the interior, then A is the sole winner.[1]

Let M be some method that passes all the three criteria.

Suppose for some elections v_1 and v_2, M elects A (either first or tied 
for first). Then by scale invariance, for any x > 0, M elects A for all 
elections x * v_1 and x * v_2. Thus M elects A for every election lambda 
* v_1 + (1 - lambda) * v_2, 0 <= lambda <= 1.

Thus every win region for method M is convex.

Since A only ties on the boundary of A's win region, and two candidates 
can't both be the unique winner of an election, the candidates' win 
regions have disjoint relative interiors.

By the hyperplane separation theorem, there exists a separating 
hyperplane between two convex sets with disjoint relative interiors. So 
there exists a normal vector n_{A, B} and a constant b_{A, B} so that if 
one or both of A and B are winners, then:
	if v dot n_{A,B} < b_{A,B}, A is a winner and B is not;
	if v dot n_{A,B} = b_{A,B}, A and B are tied for first,
and	if v dot n_{A,B} > b_{A, B}, B is a winner and A is not.[2]

If the ballot format is so that an empty election (zero ballots of any 
type) is an n-way tie, then b_{A,B] = 0 for all pairs A,B.

Let the summary values be v dot n_{A, B} for all pairs of candidates. 
Since the dot product is linear, the precincts' values can be summed to 
get the summaries for the whole election; and there are n^2 pairs of 
candidates, hence the method is at most second order summable.

There's a final snag. If neither A nor B is a winner, then v dot n_{A,B} 
could conceivably be arbitrary. So we want to be sure we don't mistake 
such arbitrary data and call the wrong winner. But this can be handled 
by just taking the Smith set, because if A is in the winner set, then A 
beats everybody who isn't in it (and ties everybody else who is in it). 
By doing so, we can determine the winner set.

Which was what was wanted.

Does that seem right?

-km

[1] Consider some election v where A ties. In the election vx where x is 
some large positive number, A still ties, by scale invariance. Then, by 
resolvability, there exists a single vote that, when added, makes A 
uniquely win. Adding this vote and then dividing the resulting vector by 
x shows that we can add some very small value to v and break the tie. 
Since this value can be arbitrarily small, for every point where A ties, 
there exists an arbitrarily close point where the win is unique. Hence 
the tie point is on the boundary.

[2] I'm not *entirely* sure that's what the h.s.t. says because it 
usually just says: if the relative interiors are disjoint then there 
exists a b s.th. every point in A's win region is <= b and every point 
in B's is >= b. But I think I can justify this. Suppose that we shrink 
the win regions so that wins produced by adding a ballot of weight k 
from a tie don't count. Then the resulting win regions are properly 
disjoint and strict separation exists. We can make k arbitrarily small, 
so any unique win for A will be properly separated from any unique win 
for B. Hence they only overlap where there's a tie.