[EM] Summability and proportional methods

[Jameson Quinn]

Most proportional voting methods are not summable. Transfers, reweightings,
and otherwise; all of these tend to rely on following each ballot through
the process. This makes these methods scary for election administrators.

I know of 3 ways to get summability: partisan categorization, delegation,
and second moments. List-based methods (including partially list-based ones
like MMP) use partisan categorization. GOLD voting
<http://wiki.electorama.com/wiki/Geographic_Open_List/Delegated_(GOLD)_voting>
does
it by giving voters a choice between that and delegation. Asset voting and
variants use delegation.

The other way to do it is with second moments. For instance, if voters give
an approval ballot of all candidates, you can record those ballots in a
matrix, where cell i,j records how often candidates i and j are both
approved on the same ballot. This matrix keeps all the information about
the two-way correlations between candidates, but it loses most of the
information about three-way correlations. For instance, you can know that
candidates A, B, and C each got 10 votes, and that each pair of them was
combined on 5 ballots, but you don't know if that's 5 votes for each pair,
or 5 votes for the group and 5 for each. Note that those two possibilities
actually involve different numbers of total votes — 15 in the former, 20 in
the latter. In order to fix this, you can instead make separate matrices
depending on how many total approvals there are on each ballot — a "matrix"
for all the ballots approving 1, one for all those approving 2, etc. Thus,
in essence, you get a 3D matrix instead of a 2D one.

Once you have a matrix, you can essentially turn it back into a bunch of
ballots, and run whatever election method you prefer. The result will be
proportional insofar as the fake ballots correspond to the real ballots.
How much is that? Well, I can make some hand-wavy arguments The basic
insight of the Central Limit Theorem (CLT) — that second moments tend to
dominate third moments as the number of items increases — would seem to be
in our favor.

I think this could be an interesting avenue of inquiry. But on the other
hand, the math involved will immediately make 99% of people's eyes glaze
over.

If this is not possible, then the only 2 ways towards summability are
partisan categorization and delegation. GOLD uses both. For a nonpartisan
method, I don't think there's any way to be summable without forcing people
to delegate; and I think that forced delegation is going to be a
deal-breaker for some people.

So I'm frustrated in trying to design a nonpartisan proportional method
that's as practical as GOLD and 3-2-1 are for their respective use cases.

[Richard Lung]

Every stage of an STV count sums the whereabouts of all the votes in
their process of transfer. So it is not "scary" on that account. Gregory
method is a standard statistical technique called weighting in
arithmetic proportion. Statisticians are not thereby a scarified
profession. Of course, traditional STV counting does have anomalies. And
that is why I developed its generalisation in Binomial STV.
No need for the retrograde steps you mention.
from
Richard Lung

Post by Jameson Quinn
Most proportional voting methods are not summable. Transfers,
reweightings, and otherwise; all of these tend to rely on following
each ballot through the process. This makes these methods scary for
election administrators.
I know of 3 ways to get summability: partisan
categorization, delegation, and second moments. List-based methods
(including partially list-based ones like MMP) use partisan
categorization. GOLD voting
<http://wiki.electorama.com/wiki/Geographic_Open_List/Delegated_%28GOLD%29_voting> does
it by giving voters a choice between that and delegation. Asset voting
and variants use delegation.
The other way to do it is with second moments. For instance, if voters
give an approval ballot of all candidates, you can record those
ballots in a matrix, where cell i,j records how often candidates i and
j are both approved on the same ballot. This matrix keeps all the
information about the two-way correlations between candidates, but it
loses most of the information about three-way correlations. For
instance, you can know that candidates A, B, and C each got 10 votes,
and that each pair of them was combined on 5 ballots, but you don't
know if that's 5 votes for each pair, or 5 votes for the group and 5
for each. Note that those two possibilities actually involve different
numbers of total votes --- 15 in the former, 20 in the latter. In
order to fix this, you can instead make separate matrices depending on
how many total approvals there are on each ballot --- a "matrix" for
all the ballots approving 1, one for all those approving 2, etc. Thus,
in essence, you get a 3D matrix instead of a 2D one.
Once you have a matrix, you can essentially turn it back into a bunch
of ballots, and run whatever election method you prefer. The result
will be proportional insofar as the fake ballots correspond to the
real ballots. How much is that? Well, I can make some hand-wavy
arguments The basic insight of the Central Limit Theorem (CLT) ---
that second moments tend to dominate third moments as the number of
items increases --- would seem to be in our favor.
I think this could be an interesting avenue of inquiry. But on the
other hand, the math involved will immediately make 99% of people's
eyes glaze over.
If this is not possible, then the only 2 ways towards summability are
partisan categorization and delegation. GOLD uses both. For a
nonpartisan method, I don't think there's any way to be summable
without forcing people to delegate; and I think that forced delegation
is going to be a deal-breaker for some people.
So I'm frustrated in trying to design a nonpartisan proportional
method that's as practical as GOLD and 3-2-1 are for their respective
use cases.
----
Election-Methods mailing list - seehttp://electorama.com/em for list info

[Kristofer Munsterhjelm]

Post by Jameson Quinn
Most proportional voting methods are not summable. Transfers,
reweightings, and otherwise; all of these tend to rely on following each
ballot through the process. This makes these methods scary for election
administrators.

Let "weak summability" for multiwinner methods be that if you hold the
number of seats constant, you can do precinct totals that require a
number of bits that is polynomial with respect to the number of
candidates and the logarithm of the number of voters.

Let "strong summability" be that if you don't hold the number of seats
constant, you can do precinct totals that require a number of bits that
is polynomial wrt the number of candidates, the number of seats, and the
logarithm of the number of voters.

I suspect that you can't have both Droop proportionality and strong
summability. My hunch is that you can get at a superpolynomial number of
the bits in the solid coalitions data by adding voters and candidates,
thus adjusting the Droop quota. Perhaps something like constructing
enough logical implications that the entire DAC/DSC data can be
recovered. But I don't have anything close to a proof of this. (The
solid coalition data contains 2^n rows - one for each solid coalition -
worst case, which is not polynomial in n, and if equal rank and
truncation is permitted, you can set all but one of them to whatever you
want.)

I furthermore suspect that weak summability is compatible with the DPC.
Consider a "subset Condorcet" method (in the vein of CPO-STV, Schulze
STV, etc) with n candidates and s seats. There are n choose s possible
assemblies to consider, and n choose s is O(n^s), so the number of
pairwise contests is on the order of n^2s. If s is a constant, 2s is
also just a constant. All you have to do is make the individual pairwise
contests summable, i.e. that you can go from "potential assembly A vs
potential assembly B score" in districts x and y to "potential assembly
A vs potential assembly B" for both, and make the CW obey DPC.

(I may also have an idea of how to make a weakly summable Bucklin-type
method. I have to think about it further.)

But perhaps you can get "not quite polynomially summable" and it'll be
good enough. E.g. suppose you could make a proportional method that uses
only the solid coalition data. For reasonable numbers of candidates, 2^n
* log2(V) bits is not *that* bad.

Even if I could construct a proof along the lines I mentioned above, it
only lower bounds the amount of data needed to that amount.

Post by Jameson Quinn
I know of 3 ways to get summability: partisan
categorization, delegation, and second moments. List-based methods
(including partially list-based ones like MMP) use partisan
categorization. GOLD voting
<http://wiki.electorama.com/wiki/Geographic_Open_List/Delegated_(GOLD)_voting> does
it by giving voters a choice between that and delegation. Asset voting
and variants use delegation.

Another option is communication, like STV or IRV does. Technically
speaking, that's more a sidestep. The method then has a finite number of
rounds that go like this:

- Each precinct reports some polynomial amount of data to the central
- The central uses this data and specifies a transformation
- Each precinct applies this transformation
- The method loops to the beginning until it's done.

In IRV, the transformation is "eliminate the loser according to the
current count".

Post by Jameson Quinn
The other way to do it is with second moments. For instance, if voters
give an approval ballot of all candidates, you can record those ballots
in a matrix, where cell i,j records how often candidates i and j are
both approved on the same ballot. This matrix keeps all the information
about the two-way correlations between candidates, but it loses most of
the information about three-way correlations. For instance, you can know
that candidates A, B, and C each got 10 votes, and that each pair of
them was combined on 5 ballots, but you don't know if that's 5 votes for
each pair, or 5 votes for the group and 5 for each. Note that those two
possibilities actually involve different numbers of total votes — 15 in
the former, 20 in the latter. In order to fix this, you can instead make
separate matrices depending on how many total approvals there are on
each ballot — a "matrix" for all the ballots approving 1, one for all
those approving 2, etc. Thus, in essence, you get a 3D matrix instead of
a 2D one.
Once you have a matrix, you can essentially turn it back into a bunch of
ballots, and run whatever election method you prefer. The result will be
proportional insofar as the fake ballots correspond to the real ballots.
How much is that? Well, I can make some hand-wavy arguments The basic
insight of the Central Limit Theorem (CLT) — that second moments tend
to dominate third moments as the number of items increases — would seem
to be in our favor.
I think this could be an interesting avenue of inquiry. But on the other
hand, the math involved will immediately make 99% of people's eyes glaze
over.

There are other possible ways to do lossy transformations. Forest once
suggested splitting ballots into heaps based on what candidate was
ranked first, and then aggregating within those heaps - a sort of
implicit partisan categorization method.

Another possibility is to relax the concept of proportionality. If it
turns out you can't get Droop proportionality and strong summability,
the "dual question" (so to speak) is "how much proportionality can you
get with strong summability"?

I guess that's what the lossy transformations do: they relax
proportionality under any ballot set to proportionality under ballot
sets where only second moments or first preferences cause the
variability in the votes that PR should capture.

Perhaps one could make a weakly summable method that's fully
proportional up to s seats for a space cost of O(n^s) elements, and
that's fully proportional up to that number of seats and partially
proportional from thereon for any number of seats greater than s. Then
it would be possible to tune the proportionality according to what level
of s one's willing to accept.

Post by Jameson Quinn
If this is not possible, then the only 2 ways towards summability are
partisan categorization and delegation. GOLD uses both. For a
nonpartisan method, I don't think there's any way to be summable without
forcing people to delegate; and I think that forced delegation is going
to be a deal-breaker for some people.
So I'm frustrated in trying to design a nonpartisan proportional method
that's as practical as GOLD and 3-2-1 are for their respective use cases.
----
Election-Methods mailing list - see http://electorama.com/em for list info

----
Election-Methods mailing list - see http://electorama.com/em for list info