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

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Kristofer Munsterhjelm-3
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
Reply | Threaded
Open this post in threaded view
|

Re: [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
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Kristofer Munsterhjelm-3
On 03/12/2020 08.31, Richard Lung wrote:
>
> 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.

I have a hunch that anything that passes Droop proportionality must fail
strong summability: that it's impossible to find a Droop-proportional
multiwinner method where you can construct an array of numbers
polynomial in the number of candidates, and then later use that array to
find the outcome for any number of seats. The same approach could
possibly be used to prove this, although it would be a lot harder.

Proving multiwinner STV non-summable would not be too much harder than
what I did in the post you replied to. There's nothing there that has to
necessarily be single-winner. It's not clear whether the corresponding
regions should be of candidates, or councils, though. (E.g. do we
consider the region "A is on the council" as some analog of a win-or-tie
region for A, or should the region be "the two-seat council is AB"?)

If told to create something democratic without concern to current
constraints, I'd probably just skip right to sortition. This would not
just invalidate single-winner methods, but voting altogether; except,
possibly, the method the assembly itself uses to decide.

-km
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Kevin Venzke
Le jeudi 3 décembre 2020 à 04:20:54 UTC−6, Kristofer Munsterhjelm <[hidden email]> a écrit :
>If told to create something democratic without concern to current
>constraints, I'd probably just skip right to sortition. This would not
>just invalidate single-winner methods, but voting altogether; except,
>possibly, the method the assembly itself uses to decide.

In this exchange "democratic" must mean that the assembly's seats are allocated proportionally. This leaves the issue of allocation of actual policy-making power as you suggest.

Maybe there is a way to determine policy proportionally, and without using randomness. I don't think it can be based on decay of individual delegates' voting power (because if you use your power sub-optimally you may fail to influence policy) or on how many things you vote on (because proposals could be clones of each other etc.). So it might have to be based on time... A faction gets an amount of time in power.

But realistically there is probably a minimum faction size you would want to allow to wield power. And to prevent whiplash you'd probably want a minimum amount of time that a faction could be in power. Could a faction representing 25% of the voters be allowed to set policy for even a year? If not, can we defend that without invoking the principle of majority rule? (I doubt it... And for me that is always the limitation, that no matter what, you have to implement majority rule somewhere in the process.)

Kevin
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Richard Lung
In reply to this post by Kristofer Munsterhjelm-3

On 03/12/2020 14:01, Richard Lung wrote:

>
>
> Droop proportionality fails, because it is the minimally proportional
> election. That means that candidates may be elected on statistically
> insignificant majorities -- whether single member majorities (like 51
> out of 100) or multi-member majorities, (like two winners with 34
> votes each out of 100). The Droop quota superseded the Hare quota for
> historical reasons. But there is also logical reason for its
> democratic short-comings: in the most extreme case, a single member
> requires all the votes, to be elected, which could only be achieved by
> a completely deferential electorate. That is why the first of my four
> averages, in FAB STV, is (my innovation of) the harmonic mean quota,
> V/(S + 1/2), as the harmonic mean of the Hare and Droop quotas. The
> use of the HM quota does imply multi-member constituencies, of at
> least 4 or 5 members, but that is what democratic diversity requires.
>
> Your last paragraph of democratic skepticism is in contrast to the
> view that there is a right and a wrong way to do voting method. In
> this respect, I follow the tradition of Hare, Mill, Wells, Hoag and
> Hallett, and Lakeman. and many other estimable people, up against
> "current constraints."
>
> Richard L.
>
>
> On 03/12/2020 10:20, Kristofer Munsterhjelm wrote:
>> On 03/12/2020 08.31, Richard Lung wrote:
>>> 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.
>> I have a hunch that anything that passes Droop proportionality must fail
>> strong summability: that it's impossible to find a Droop-proportional
>> multiwinner method where you can construct an array of numbers
>> polynomial in the number of candidates, and then later use that array to
>> find the outcome for any number of seats. The same approach could
>> possibly be used to prove this, although it would be a lot harder.
>>
>> Proving multiwinner STV non-summable would not be too much harder than
>> what I did in the post you replied to. There's nothing there that has to
>> necessarily be single-winner. It's not clear whether the corresponding
>> regions should be of candidates, or councils, though. (E.g. do we
>> consider the region "A is on the council" as some analog of a win-or-tie
>> region for A, or should the region be "the two-seat council is AB"?)
>>
>> If told to create something democratic without concern to current
>> constraints, I'd probably just skip right to sortition. This would not
>> just invalidate single-winner methods, but voting altogether; except,
>> possibly, the method the assembly itself uses to decide.
>>
>> -km
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

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

Kristofer Munsterhjelm-3
In reply to this post by Kevin Venzke
On 03/12/2020 19.04, Kevin Venzke wrote:
> Le jeudi 3 décembre 2020 à 04:20:54 UTC−6, Kristofer Munsterhjelm
> <[hidden email]> a écrit :

>> If told to create something democratic without concern to current
>> constraints, I'd probably just skip right to sortition. This would
>> not just invalidate single-winner methods, but voting altogether;
>> except, possibly, the method the assembly itself uses to decide.

> In this exchange "democratic" must mean that the assembly's seats are
> allocated proportionally. This leaves the issue of allocation of
> actual policy-making power as you suggest.
>
> Maybe there is a way to determine policy proportionally, and without
> using randomness. I don't think it can be based on decay of
> individual delegates' voting power (because if you use your power
> sub-optimally you may fail to influence policy) or on how many things
> you vote on (because proposals could be clones of each other etc.).
> So it might have to be based on time... A faction gets an amount of
> time in power.

One of the benefits of sortition is that how well you represent an
opinion with, say, 10% support among the people depends entirely on the
assembly size, not on the number of people you're drawing from[1]. So
the same process works on a city level as on a global level, and has the
same fidelity (assuming the same assembly size).

That given, the assembly must necessarily contain people with a mix of
opinions. So there's no easy way to determine who a certain faction
belongs to, and thus to give different factions different power. It'd be
analogous to if you elected a bunch of nonpartisan Condorcet winners to
an assembly: they're all consensus candidates, so how could you find any
factions to sweep the power over, over time?

Time can be used to diminish variance, though. Suppose you have an
assembly that uses Heitzig's nondeterministic consensus method. Then I
wouldn't be surprised if there exists a way to downweight the candidates
who got their wish in one election for the next, so as to reduce the
total swing over time while still having the same asymptotic properties.
Or in pure sortition, you can replace, say, 1/8 of the assembly every
1/8th of the period instead of all at once.

In a slightly related vein, I read a paper once suggesting to use voting
rights instead of money in a Clarke-Tullock system. The members who get
their way have to abstain from future influence depending on how much it
cost them to overrule the others. I have my doubts about whether CTT can
ever be useful, but it illustrates the principle.

Warren also suggested a party list method using time-based reweighting:
since you can't give every MP power exactly reflecting the number of
voters who voted for them (without weighted parliamentary votes),
instead adjust the quota so that if each MP of one party has too little
power, then eventually that party will get one extra.

[1] It's not entirely true if the assembly is very large compared to the
population because you're drawing without replacement. But if that's the
case, you have few enough people that you can just use direct democracy.

> But realistically there is probably a minimum faction size you would
> want to allow to wield power. And to prevent whiplash you'd probably
> want a minimum amount of time that a faction could be in power. Could
> a faction representing 25% of the voters be allowed to set policy for
> even a year? If not, can we defend that without invoking the
> principle of majority rule? (I doubt it... And for me that is always
> the limitation, that no matter what, you have to implement majority
> rule somewhere in the process.)

That sounds like variance. Your mechanism swings too much; a good method
continuously tracks what the people want, and changes the composition of
the representatives (or their power) just enough to reflect that. Loring
once compared two-party rule to a pendulum. To quote:

" A political pendulum swings; it cuts down forests and species,
families and towns. Agencies and businesses often lose wealth when a
council changes hands and changes laws.  These reversals are a major
cause of war-like politics. "
(https://www.accuratedemocracy.com/a_primer_blue.htm)

Reducing variance/entropy mitigates that kind of thing. But it shouldn't
be so reduced so much that the people can no longer hold the assembly
accountable. It's hard to get the balance right.
----
Election-Methods mailing list - see https://electorama.com/em for list info