[EM] Summability criterion: do I have this right?

[Kristofer Munsterhjelm]

On 10/7/23 06:26, James Faran wrote:
> I'm not certain about the second item.  My worry is the following method 
> that someone must have thought of before me and rejected.
> 
> Given any single ballot, we can use it to create the pairwise matrix.  
> The entries will be +1, 0, or -1. From that pairwise matrix we can 
> reconstruct the preference order given on the ballot. Concatenate all 
> such pairwise matrices. This "summary", an n by n by v array, has size 
> on the order of n^2*v, where n is the number of candidates and v the 
> number of voters. The combination of these is by concatenation in the 
> "v" direction of the array.  This is quadratic in n (just as good as a 
> pairwise method) and linear in v (pairwise methods are logarithmic in 
> v). Plurality is linear in n and logarithmic in v (when v gets bigger we 
> just have to increase the number of digits used to describe the totals). 
> The point is that this method transfers complete ballot information, yet 
> clearly is not a method one would want to use.  And we certainly, in 
> avoiding discussion of polynomial growth, don't want to suddenly need to 
> explain logarithmic growth.
> 
> As v has a tendency to get bigger than n, I think "polynomial in n" and 
> "logarithmic in v" might be a good standard.  (A rough calculation leads 
> me to believe this method beats just listing the number of ballots of 
> each of the n! types when (n-2)! > v, so is only really a help when n is 
> large.  For 10^7 voters, I think n=14 might do it.)  All in all, as it 
> stands the second point is good enough. We'd just want to avoid 
> responding to a "What does that mean?" question with "You don't want to 
> know," or "You wouldn't understand." However, for studying the question, 
> a more precise definition is needed, lest every method be "summable".  
> Should the amount of calculation time needed to analyze the "summary" 
> come into it?

Yes, the current mathematical standard defined in the Electowiki article 
is "polynomial in candidates, logarithmic in voters" for just the reason 
you mentioned: the number of voters increases much more quickly than the 
number of candidates. Strictly speaking, I suppose polylogarithmic could 
also work, but nobody has ever made such a summary so I shouldn't 
complicate matters too much.

Perhaps something like "should grow slowly in the number of candidates 
and even more slowly in the number of voters". But even that's adding 
more detail to a brief summary.

In any case, my idea was that the summary should be brief, and then 
questions like "what does *slow* mean" can be answered by pointing at 
the mathematical definition, or by a longer elaboration that first 
explains the justification (e.g. "there will be more voters than 
candidates"), and then does a rigorous definition.

-km