[EM] Proof idea that IRV can't be summable
Richard Lung
voting at ukscientists.com
Wed Dec 2 23:31:30 PST 2020
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
More information about the Election-Methods
mailing list