[EM] Proof idea that IRV can't be summable

[Richard Lung]

Of course, all that learning won't alter what John Stuart Mill knew over 
150 years ago that maiorocracy is not democracy. The fixation on single 
winner methods, (the monarchism hang-over) is candidate-centred not 
voter-centered or politician-based not people-based.

Richard L.


On 01/12/2020 22:25, Kristofer Munsterhjelm wrote:
> Here's an idea that may be used to prove that any attempt to find a
> clever way of making IRV summable (in a linear sense) will fail: that
> it's not just the case that we haven't found such a solution, but that
> it can't be done.
>
> It's not a complete proof, but perhaps someone can complete it :-) And,
> of course, it could be wrong; I could be missing something.
>
> Consider a voting method as a union of convex polytopes expressed as
> sets of linear inequalities. The unknown variables are the ballot
> numbers: e.g. in the three-candidate no-truncation case, they're ABC,
> ACB, BAC, BCA, CAB, CBA: the number of people who expressed each preference.
>
> Then if the c!-dimensional vector is inside this union of convex
> polytopes, A wins (if the union is called a win region); or A wins or
> ties for first (if the union is called a win-or-tie region)[1]. As far
> as summability is concerned, we can pick whichever is more convenient as
> long as the difference between the win-and-tie region and the win region
> is not of full dimensionality (which means that as the number of voters
> approach infinity, the proportion of ties approach zero). This is, to my
> knowledge, the case for IRV.
>
> My strategy is to show that for (almost) any pair of ballot variables,
> there exists some win region with some polytope with some inequality
> that treats both ballot variables equally by scaling both equally; and
> another that treats them differently (by scaling them by different
> amounts).
>
> The inequalities need not be in the same polytopes, since the argument
> is that the inequality requires the method to distinguish between two
> variables (or treat them equally); and thus that any summary must also
> allow the method to do so. A violation of this will degrade at least one
> of the win regions.
>
> So, letting the two ballot variables be X and Y, the inequality that
> treats X and Y equally proves that if IRV is summable, the sums can't
> all have a term that amounts to (X-Y), because then the inequality in
> question could not treat X and Y equally. The second case proves that if
> IRV is summable, the sums can't all have a term that amounts to (X+Y),
> because then the inequality can't treat X and Y differently.
>
> If this can be proven for all pairs, then there must be c! different
> summed variables (since no pair can be treated differently nor equally),
> and since c! is not polynomial in c, we're done.
>
> Now, to familiarize, consider the win region for A. For IRV, the union
> is of the form (three candidate example given here):
>
> "B is eliminated, A wins pairwise against C" or
> "C is eliminated, A wins pairwise against B"
>
> If either of these is true, then A wins with certainty; otherwise, A
> does not. In this particular case, the inequalities of the first
> constituent polytope look something like:
>
> ABC + ACB - BAC - BCA > 0	(A outscores B in the first round)
> ABC + ACB - CAB - CBA > 0	(A outscores C in the first round)
> CAB + CBA - BAC - BCA > 0	(C outscores B in the first round)
> ABC + ACB + BAC + BCA - CAB - CBA > 0	(A beats C pairwise)
>
> So now take two ballot orders X and Y, but not so that Y is X reversed.
>
> Let the set S_1 be the set of candidates that must be removed so that
> the first candidate of X and Y match. Since Y isn't X reversed, this set
> is at most two candidates smaller than the set of all candidates. Then X
> and Y have a common factor in an inequality belonging to a polytope
> where all the candidates of S_1 have been eliminated; because both X and
> Y then count towards the first preferences of someone not in S_1, vs
> someone else not in S_1.
>
> Then let the set S_2 be the set of candidates that must be removed so
> that the first candidate listed differs. Since X is not Y, the set is at
> most two candidates smaller than the set of all candidates. Then,
> similarly, in the scenario where the candidates in S_2 are all
> eliminated, X counts towards someone's first preferences while Y counts
> towards someone else's. So if cX is the candidate listed first on X
> after the candidates in S_2 have been eliminated, then a polytope
> dealing with cX's win region after the candidates in S_2 have been
> eliminated will have a X + ... - Y - ... > 0 inequality.
>
> The cases where Y is the exact reverse of X can't be treated this way,
> but that's no problem as there are only O(c) of them anyway: hence these
> being summable won't make IRV itself polynomially summable.
>
>
>
> Caveat: I haven't shown that every pair of constituent polytopes for A's
> win region is nonconvex as a whole, and that there are no redundant
> inequalities (that each polytope's inequality matrix is full rank).
>
> That's necessary to make sure the win region can't be reconstructed in a
> way so that the tricky inequalities disappear. In other words, if I
> don't do this, then the following "proof" for the non-summability of
> Plurality would work:
>
> A wins if one of the following is true (one polytope per inequality):
> 	for i = all 2^k subsets of ballots that begin in A
> 		for j = all 2^p subsets of ballots that don't
> 			e_i * x > e_j * x
> for some numbers k and p; where x is the ballot vector, and e_i and e_j
> are the indicator vectors for the respective sets.
>
> Then one could claim that due to the superpolynomial amount of
> inequalities, Plurality is non-summable. The flaw lies in that e.g. the
> inequalities
> 	ABC > CBA
> 	ACB > CBA
> are entirely subsumed by the inequality
> 	ABC + ACB > CAB + CBA.
> So the method doesn't need to discriminate between two situations that
> it seems like it needs to at first glance.
>
> I would also, strictly speaking, need to show that (win or tie region) \
> (win region) is not of full dimensionality; or deal with the win-or-tie
> region directly.
>
> Finally, I have a feeling there's some kind of more general matrix rank
> argument hiding in there somewhere. Perhaps it could be used to show
> just what kind of positional elimination systems are non-summable.
> Borda-elimination is summable because you can get the Borda score from
> the Condorcet matrix; why is it different? Are there any other systems
> like it?
>
> -km
>
> [1] Note that these methods are deterministic. If there are any random
> tiebreaks, they will have to be determined ahead of time. It's then
> clear that some random tiebreaks may make an otherwise summable method
> non-summable if they're "random enough".
> ----
> Election-Methods mailing list - see https://electorama.com/em for list info