[EM] "summability"

[Daniel Bishop]

Russ Paielli wrote:

> Daniel Bishop dbishop-at-neo.tamu.edu |EMlist| wrote:
>
>> Russ Paielli wrote:
>>
>>> Folks,
>>>
>>> On the old "Technical Evaluation" page of ElectionMethods.org, I had 
>>> a criterion that I called "summability," which I defined as follows:
>>>
>>> "Each vote should map onto a summable array, where the summation 
>>> operation is associative and commutative, and the winner should be 
>>> determined from the array sum for all votes cast."
>>>
>>> The point was that plurality, Approval, and Condorcet all pass but 
>>> IRV fails. Well, after further consideration, I realized that IRV 
>>> actually passes too -- it just needs a much larger "array."
>>>
>>> Rather than putting an arbitrary size limit on the array...
>>
>>
>> "Summability" is still a very useful criterion.  All you need is a 
>> more precise definition.  I suggest:
>>
>> * An election method is "k-summable" (or "passes the k-Summability 
>> Criterion") if there exists a constant c such that in any election 
>> with n candidates, the required size of the "array" is at most c*n^k.
>>
>> * An election method is "non-summable" if there is no k for which it 
>> is k-summable.
>>
>> For example:
>> 1-summable methods: Plurality, Borda, Cardinal Ratings
>> 2-summable methods: most Condorcet methods, Bucklin, plus all 
>> 1-summable methods
>> 3-summable methods: Iterative Ranked Approval Voting*, plus all 
>> 1-summable and 2-summable methods
>> non-summable methods: IRV
>
> That's interesting. I had thought of something like that, but I did't 
> have the mathematical background to know the appropriate terminology.
> Speaking of terminology, what do you think about "first-order 
> summable," "second-order summable," etc.? They seem a bit more 
> appropriate for formal writing.

Good idea.

> As for the constant c in c*n^k, do you think it might as well just be 
> 1? Or are you aware of methods that pass for some constant other than 
> 1 but not 1? I don't see any point throwing in an arbitrary constant 
> if it isn't needed.

Suppose you had an election method like:

* Eliminate the candidate with the fewest first-choice votes, and the 
candidate with the most last-choice votes.
* Use Schulze's method to determine the winner.

This method requires n array elements for the first-choice votes, n for 
the last choice votes, and n(n-1) for the pairwise votes, for a total of 
n²+1 elements.

This method passes for c=2 (n²+n <= n²+n² = 2n²), but not for c=1.