[EM] Summability and proportional methods

[Kristofer Munsterhjelm]

On 06/08/2017 06:33 PM, Jameson Quinn wrote:
> 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.

> 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".

> 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.

> 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