[EM] Linear summability

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

[EM] Linear summability

Kristofer Munsterhjelm-3
Some time ago I was wondering how to prove that a method is nonsummable.
Just because we don't know of any way to make e.g. IRV summable doesn't
mean there isn't any. I couldn't figure out how you'd definitely exclude
every possible polyspace array.

But I think I've found something that works; or at least a foundation
for something that works.

Suppose the summability we're concerned about is with the plus operator
instead of just any general associative commutative operator. (So no
cell holds e.g. the maximum of all precincts' cells.)

And suppose the win regions for the candidates (i.e. the criteria that
have to hold for a candidate to win) are unions of convex polytopes
(which seems to be true for any method I can think of).

Then the method, for a candidate A, needs to be able to distinguish
between every point that is in A's win region and every point that
isn't. In particular, in the case that each win region is a convex
polytope, the data given by the summable precinct counts must form a
basis for the space formed by the constraints. And if the dimension of
that vector space grows as a polynomial of the number of candidates,
then the method is summable, otherwise it is not.

If the win region is a union of such convex polytopes, then the same
logic should still hold for every individual polytope as long as it's
not redundant (not implied by some other).

Formally, I *think* something like this should work: if the no union of
the convex polytopes is in itself a convex polytope, then suppose that
the dimension of the vector space given by the summable data structure
(call it X) is less than the dimension of the vector space given by
every constraint. Then there exists an election inside one of the
polytopes where A wins, but it's possible to add a vector that doesn't
change the representation in X, but does push the election outside of
the current convex polytope part of A's win region. Since no union of
the convex polytopes is itself a convex polytope, it is possible to push
the election outside of this polytope without it immediately entering
another. So two elections that appear the same in X-space conflict as to
whether A wins, which contradicts the claim that X shows that the method
is summmable.

E.g. for DSC, the win region for A is (unless I missed something)
        AB > AC and AC > BC and A>B (C is excluded and then A wins vs B)
or AC > AB and AB > BC and A>C (B is excluded and then A wins vs C)
or A > BC                      (A wins outright)

where the labeled variables are coalition counts, e.g. AB is ABC and A
is ABC + ACB. The dimension of the space with (A, AB, AC, BC, A, B, and
C) as bases is six, so the summation array for DSC must be at least six
long for three candidates.

Now enter extreme handwaving: because this matches the "natural" count
of 2^c-2 for the number of coalitions (all possible subsets minus the
set of every candidates and the empty set), that implies that DSC
requires every coalition count to decide if A is the winner; and if it's
denied any of them (or has one of them replaced by a linear combination
of the others), you can construct a pair of elections where A wins and
doesn't win, but that looks the same when you consider every coalition
apart from the missing one. And thus, the dimension of the constraint
space is 2^c-2, which is superpolynomial in c, and hence DSC is not
summable.

But I haven't actually *proven* that. Still, it's a strategy, which is
better than not knowing where to begin :-) The rest is an engineering
problem, etc.

I suspect the way to go about proving it for DSC would be inductively,
but I can't quite get at how. It's much easier for IRV, where A wins the
four-election if A is not eliminated and then wins the resulting
three-election. In either case, it would be necessary to show that every
introduced constraint is linearly independent of the others; or to
remove those that are, and show that the dimension of the space induced
by those that remain still grows superpolynomially.


Similar reasoning would indicate that a linear-summable Condorcet method
requires at least O(c^2) elements in the summation array, because
identifying A as a CW requires all pairwise victories involving A, and
so for every other candidate, and it's impossible to get one pairwise
victory from a linear combination of the others. But here we'd have to
be careful: a method could possibly be Condorcet plus something else in
such a way that the union of the Condorcet criterion and the something
else is a simpler convex polytope that nevertheless does not intrude
into anyone else's "is a CW" win region.

That's probably why explicitly identifying the smallest mutual majority
set seems to be much harder than just making a method that passes mutual
majority, or how methods can be independent of clones without ever
directly identifying any clone sets.
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Linear summability

robert bristow-johnson


> On April 25, 2020 7:49 PM Kristofer Munsterhjelm <[hidden email]> wrote:
>
>  
> Some time ago I was wondering how to prove that a method is nonsummable.
> Just because we don't know of any way to make e.g. IRV summable doesn't
> mean there isn't any. I couldn't figure out how you'd definitely exclude
> every possible polyspace array.

i don't think there is a way to exclude any meaningfully different ballot ranking.  remember, every candidate unranked is the same as being ranked last.  whether you rank your least-desired candidate the lowest rank or leave that candidate unranked makes no difference.

maybe a decade ago i posted the formula and a proof that Warren Smith first did that shown the number of ballot piles that are summable as

  number of piles = floor( (e-1)×C! - 1 )

  if the number of candidates is C .

i haven't been able to grok the rest.


--
 
r b-j                  [hidden email]
 
"Imagination is more important than knowledge."
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Linear summability

Kristofer Munsterhjelm-3
On 26/04/2020 04.42, robert bristow-johnson wrote:

>
>
>> On April 25, 2020 7:49 PM Kristofer Munsterhjelm <[hidden email]> wrote:
>>
>>  
>> Some time ago I was wondering how to prove that a method is nonsummable.
>> Just because we don't know of any way to make e.g. IRV summable doesn't
>> mean there isn't any. I couldn't figure out how you'd definitely exclude
>> every possible polyspace array.
>
> i don't think there is a way to exclude any meaningfully different ballot ranking.  remember, every candidate unranked is the same as being ranked last.  whether you rank your least-desired candidate the lowest rank or leave that candidate unranked makes no difference.
>
> maybe a decade ago i posted the formula and a proof that Warren Smith first did that shown the number of ballot piles that are summable as
>
>   number of piles = floor( (e-1)×C! - 1 )
>
>   if the number of candidates is C .
>
> i haven't been able to grok the rest.

Oh, sorry if I was being confusing. I'm not talking about unranked
candidates; as with my differential inequality idea, I've implicitly
been assuming full ranks (i.e. truncation and equal-rank not allowed).
Though there's nothing preventing the method from being applied to a
wider set of ballots - with equal-rank and truncation - I thought I'd
keep things as simple as possible while I explore what *can* be done by
this approach.

floor( (e-1) * C! - 1) is the number of distinct ballots if truncation
(but not equal-rank) is allowed. The corresponding number for equal-rank
(but not truncation) is sum m=1...C (m-1)^C / 2^m. It's recorded in the
OEIS as A000670. Those are RangeVoting puzzles 91 and 110 respectively.
If I recall correctly, if you allow for both equal-rank and truncation,
then the number of distinct ballots is twice the number than when only
equal-rank is allowed (except when there's only one candidate); OEIS's
A000629.

For summable methods, even though the number of distinct ballots grow
very quickly, you can make do with only a summary of the data. If the
method is nonsummable, then those summaries will grow superpolynomially
anyway and so there won't be much of a point.

Though I'm pretty sure IRV is indeed nonsummable, I've never seen a
proof of it; just "obviously, you can't use any known structure to
summarize an IRV election because there isn't enough data there". That
still leaves the possibility open that there is such a precinct subtotal
scheme and we simply haven't found it yet. So my post is an attempt to
find out how to go about settling the issue and showing that it is
indeed impossible to construct such a subtotal.

What I suspect will happen (for IRV) is that depending on the
elimination order, you'd be comparing cross-cutting sums of the
different ballot counts. That is, for every polynomial way to do a
precinct subtotal, some elimination order will require the knowledge of
just a part of what contributes to one of the elements.

But it would still have to be proven, so I should look into how to
calculate the determinant of very large matrices, to show linear
independence. Or use induction. The case of IRV isn't all that
interesting on its own, beyond as (hopefully) showing that my approach
works.
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Linear summability

robert bristow-johnson


> On April 26, 2020 8:17 AM Kristofer Munsterhjelm <[hidden email]> wrote:
>
...
>  
>
> floor( (e-1)×C! - 1) is the number of distinct ballots if truncation
> (but not equal-rank) is allowed.

which is essentially the case for all RCV (the new name for what used to be "IRV") elections i am aware of for government office.
 
> For summable methods, even though the number of distinct ballots grow
> very quickly, you can make do with only a summary of the data.

i think i would agree, but it's an imprecise definition of summability.  i think what would be better is just state the number of subtotals each precinct needs to tally and report.

if C is the number of candidates, the number of subtotals each precinct must tally and report it:

First-past-the-post:    C
Condorcet-compliant:    C×(C-1)
Instant Runoff Voting:  floor( (e-1)×C! - 1 )

> If the
> method is nonsummable, then those summaries will grow superpolynomially
> anyway and so there won't be much of a point.
>
> Though I'm pretty sure IRV is indeed nonsummable, I've never seen a
> proof of it;

you have to define what "nonsummable" means.  of course it's "summable" (in a sense of the word) but the number of subtotals each precinct must tally and report is very large as the number of candidates, C, grows.  FPTP it's O(C).  Condorcet it's O(C^2).  IRV it's O(C!), which is a lot more than O(C^2) as C grows.

Now with this virtually Condorcet-compliant IRV-BTR method, that I am actively lobbying both the Vermont state legislature and the Burlington city council to adopt, would still be IRV so the individual ballot records would still have to be securely transported to the central tallying location for the kabuki dance we call the "single transferable vote" to take place, but since it's virtually Condorcet, the precincts can report the C×(C-1) subtotals that can be summed and *if* there is a Condorcet Winner, we will know who it is from the sums of the C×(C-1) subtotals.  (the IRV-BTR is, in my opinion, *virtually* Condorcet-compliant because, since it is STV, there can be no equal rankings of candidates on the ballot.)

--
 
r b-j                  [hidden email]
 
"Imagination is more important than knowledge."
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Linear summability

Kristofer Munsterhjelm-3
On 27/04/2020 06.35, robert bristow-johnson wrote:

>
>
>> On April 26, 2020 8:17 AM Kristofer Munsterhjelm <[hidden email]> wrote:
>>
>> Though I'm pretty sure IRV is indeed nonsummable, I've never seen a
>> proof of it;
>
> you have to define what "nonsummable" means.  of course it's
> "summable" (in a sense of the word) but the number of subtotals each
> precinct must tally and report is very large as the number of
> candidates, C, grows.  FPTP it's O(C).  Condorcet it's O(C^2).  IRV
> it's O(C!), which is a lot more than O(C^2) as C grows.
My definition is: A method is summable (in the restricted sense here) if
the number of numbers (elements of the vector or array) required for a
precinct subtotal grows as a polynomial function of the number of
candidates in the election.

Plurality is summable because it's O(C). Matrix Condorcet methods like
Ranked pairs are (at most) O(C^2). There are even some methods out there
that are (at most) O(C^3).

I suspect, but haven't proven, that DSC is O(2^C). I suspect, but
haven't proven, that IRV is O(C!). Neither of those are summable if I'm
right. What I was trying to do with the linear summability idea is to
find a way to go from "suspect" to "have proven".

Note that the "suspect" is very strong. I would be very surprised if my
suspicions were wrong. I just have to prove it to be *absolutely* sure :-)

I know that IRV is definitely O(C!) when it's counted the "obvious" way.
But that's no proof that there's no sophisticated counting approach that
beats this bound. That's why I've said "at most" for the claims above,
too: that there's an algorithm that does Ranked Pairs in O(C^2) doesn't
mean there doesn't exist one that does it in O(C). However, again, I
very strongly suspect that the O(C^2) bound is *exact*.

> Now with this virtually Condorcet-compliant IRV-BTR method, that I am
> actively lobbying both the Vermont state legislature and the
> Burlington city council to adopt, would still be IRV so the
> individual ballot records would still have to be securely
> transported to the central tallying location for the kabuki dance we
> call the "single transferable vote" to take place, but since it's
> virtually Condorcet, the precincts can report the C×(C-1) subtotals
> that can be summed and *if* there is a Condorcet Winner, we will know
> who it is from the sums of the C×(C-1) subtotals.  (the IRV-BTR is,
> in my opinion, *virtually* Condorcet-compliant because, since it is
> STV, there can be no equal rankings of candidates on the ballot.)

Yes, that's true.

I wonder if it would be a good idea to point at this "speculative"
precinct summability as a benefit of BTR-IRV compared to ordinary IRV,
or if it would get in the way of the central point, which is that
BTR-IRV avoids center squeeze.

(As far as I know, the standard way to extend IRV to do equal-rank is to
count the first preferences fractionally, but I don't know of any public
elections that have been conducted by such rules.)
----
Election-Methods mailing list - see https://electorama.com/em for list info
Reply | Threaded
Open this post in threaded view
|

Re: [EM] Linear summability

robert bristow-johnson


> On April 28, 2020 9:26 AM Kristofer Munsterhjelm <[hidden email]> wrote:
>
>  
> On 27/04/2020 06.35, robert bristow-johnson wrote:
...

> >
> > Now with this virtually Condorcet-compliant IRV-BTR method, that I am
> > actively lobbying both the Vermont state legislature and the
> > Burlington city council to adopt, would still be IRV so the
> > individual ballot records would still have to be securely
> > transported to the central tallying location for the kabuki dance we
> > call the "single transferable vote" to take place, but since it's
> > virtually Condorcet, the precincts can report the C×(C-1) subtotals
> > that can be summed and *if* there is a Condorcet Winner, we will know
> > who it is from the sums of the C×(C-1) subtotals.  (the IRV-BTR is,
> > in my opinion, *virtually* Condorcet-compliant because, since it is
> > STV, there can be no equal rankings of candidates on the ballot.)
>
> Yes, that's true.
>
> I wonder if it would be a good idea to point at this "speculative"
> precinct summability as a benefit of BTR-IRV compared to ordinary IRV,
> or if it would get in the way of the central point, which is that
> BTR-IRV avoids center squeeze.

Precinct summability is not the main point, and in my opinion, this "center squeeze" point *should* not be.

We do not want Condorcet because it somehow favors (w.r.t. IRV) the "center".  The Center is just another political interest and we do not want our election methods to explicitly favor any specific political interest over the others whether it's Left, Right, or Center.  Here are the reasons I use to sell this Condorcet compliance:

Two axiomatic principles:

1.  One-person-one-vote.  It doesn't matter if I really really really like my candidate over yours and you only marginally like your candidate over mine.  Your tepid vote for your candidate counts just as much (but no more) as my enthusiastic vote for my candidate.  This is because you and I have equal franchise.  This, of course, leaves out Score Voting as a consideration.

2.  Majority rule.  If more voters mark their ballots preferring Candidate A over Candidate B than the number of voters marking their ballots to the contrary, then Candidate B is not elected.  This was explicitly the failure of IRV in Burlington Vermont in March 2009.

Further desired properties:

3.  Avoiding spoiler effect.  If more voters express on their ballots that they prefer Candidate A over Candidate B, that preference should be unaffected by the presence of a third candidate C.  If Candidate C enters the race, Candidate B should not be elected if more voters express on their ballots a preference for Candidate A.

4.  Removing the burden of tactical voting.  This is what Fairvote and other RCV advocates keep saying: "Vote your hopes, not your fears."  We want to remove the burden of tactical voting from voters and allow them to vote sincerely.  Again, in Burlington 2009, there were about 1510 voters that marked the Republican as their first choice, the Democrat as their contingency choice, and the Progressive was their last choice.  We promised them that they could vote their hope (their conservative choice) without fear of electing their fear (the left-wing progressive choice).  That was an empty promise in 2009 and we still cannot get Fairvote and the IRV happy-talkers to acknowledge that.  If 1 out of 4 of those 1510 voters had insincerely marked the center candidate, their contingency choice, as #1 instead of their true first choice, they would have prevented their "fear" candidate from being elected.  This "Vote your hopes, not your fears" slogan should apply to everyone, not just those on the left.

BTW, both Score Voting and Approval Voting fail this tactical voting property at the get go.  I keep asking, and never get a satisfactory answer from proponents, how much should I score or approve my second-choice candidate (or third).  There *is* no satisfactory answer.

5.  Precinct summability.  This is for election transparency and integrity.  There is something "fishy" about having to opaquely transport the tally records to the central location where it is opaquely tallied in this kabuki dance called "STV".  A Condorcet-compliant method can have precinct subtotals reported *at* *the* *precinct* before the voting machines are transported securely back to city hall for the official aggregate tallying.

6.  Convenience to voters in removing the need to return to the poll for a runoff.  The legitimacy of an election is greater with greater voter turnout.  If less than half of the voters return to the polls for a delayed runoff, that runoff election carries less democratic legitimacy than if the entire crowd weighs in.  Making elections less convenient to the average voter decreases turnout.

These are the six selling points that I am using to promote a Condorcet-compliant RCV method.  IRV-BTR is what I am trying to sell, because it has the simplest and smallest modification to the existing proposed RCV language.  Simpler and more understandable legal language has promotional value.  Something like Ranked-Pairs or Schulze would be a harder sell even though I think they would be better methods.  If there is no Condorcet Winner and if the Smith set is three candidates (the simplest case), IRV-BTR will elect the candidate with the most first-choice votes out of the three (also assuming the three top vote-getters are the Smith set).  While this would happen rarely, it's a natural way (requiring no additional language) to resolve a cycle, but RP and Schulze (using margins) might resolve it differently.  However, I am willing to live with that because, to me, what's more important than "which Condorcet?" is "GET Condorcet!"

> (As far as I know, the standard way to extend IRV to do equal-rank is to
> count the first preferences fractionally, but I don't know of any public
> elections that have been conducted by such rules.)

Any kind of fractional vote scheme is dead-on-arrival.  STV in any governmental election cannot have equal ranking because we would not know how to transfer the vote for two equally-ranked candidates or to count them if they bubble up to the remaining shared first-choice.

--
 
r b-j                  [hidden email]
 
"Imagination is more important than knowledge."
----
Election-Methods mailing list - see https://electorama.com/em for list info