election-methods@mailman.electorama.com

Technical discussion of election methods

View all threads

Funny summability result

KM
Kristofer Munsterhjelm
Mon, Jan 15, 2024 10:35 AM

So I'm looking more into summability, in particular a way to find the
minimum number of values required to determine who's the winner for a
particular method and number of candidates, using linear summability
(i.e. summaries are combined by elementwise sums).

And I must be doing something right because it found this funny
two-value summary for Plurality, for three candidates:

Let x_1 = fpA - fpC, i.e. (number of first prefs for A) - (number of
first prefs for C).
Let x_2 = fpB - fpC.

Now if A is ranked ahead of C in the social ordering, then x_1 > 0.
If B is ranked ahead of C, then x_2 > 0.

And for A vs B: x_1 - x_2 = fpA - fpC - fpB + fpC = fpA - fpB.

Thus we can determine if A is ranked ahead of B, A ahead of C, and B
ahead of C. Since the Plurality relation is transitive and acyclical,
that's all we need.

Since the x values are linear, we can just elementwise add different
districts' x values to get the total for the whole region.

Practical, 'tis not! But quite amusing.

The same approach says that three-candidate Bucklin can be summarized in
5 values. The simple positional matrix approach requires nine.

-km

So I'm looking more into summability, in particular a way to find the minimum number of values required to determine who's the winner for a particular method and number of candidates, using linear summability (i.e. summaries are combined by elementwise sums). And I must be doing something right because it found this funny two-value summary for Plurality, for three candidates: Let x_1 = fpA - fpC, i.e. (number of first prefs for A) - (number of first prefs for C). Let x_2 = fpB - fpC. Now if A is ranked ahead of C in the social ordering, then x_1 > 0. If B is ranked ahead of C, then x_2 > 0. And for A vs B: x_1 - x_2 = fpA - fpC - fpB + fpC = fpA - fpB. Thus we can determine if A is ranked ahead of B, A ahead of C, and B ahead of C. Since the Plurality relation is transitive and acyclical, that's all we need. Since the x values are linear, we can just elementwise add different districts' x values to get the total for the whole region. Practical, 'tis not! But quite amusing. The same approach says that three-candidate Bucklin can be summarized in 5 values. The simple positional matrix approach requires nine. -km