# [EM] Linear summability Classic List Threaded 6 messages Open this post in threaded view
|

## [EM] Linear summability

 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
Open this post in threaded view
|

## Re: [EM] Linear summability

 > 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
Open this post in threaded view
|

## Re: [EM] Linear summability

 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
Open this post in threaded view
|

## Re: [EM] Linear summability

 > 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