Summability and resistant set election: two other options excluded
About a month ago, I wrote in my post "Resistant set incompatibility and
passing methods", that
I couldn't find any such "disjoint collisions" with the same first
preference counts and pairwise matrices, leaving open the
possibility that a combination of the two could be used to create a
summable Resistant method.
Well, here's a disproof found by linear programming, showing that a
method using only the pairwise magnitudes and first preferences can't be
resistant. Surprisingly, using the full positional matrix doesn't help
either.
Election 1:
2: A > B > C > D
1: A > D > C > B
1: B > A > C > D
2: B > D > C > A
1: C > A > D > B
1: C > B > D > A
2: D > A > B > C
1: D > B > A > C
A disqualifies B and C, and B disqualifies D. Hence the resistant set
consists of A alone.
Election 2:
3: A > B > C > D
2: B > A > D > C
1: B > D > C > A
1: C > D > A > B
1: C > D > B > A
1: D > A > B > C
1: D > A > C > B
1: D > B > C > A
This election has the same first preference counts as election 1, and
the same Condorcet matrix. It even has the same positional matrix
(number of first preferences, second preferences, etc, per candidate).
But D disqualifies A. Hence the two elections' resistant sets are
disjoint despite having the same pairwise magnitudes and first
preference counts.
A method that only uses first preferences and the pairwise matrix can't
distinguish between the two and must get at least one of them wrong.
This also holds for any refined subset of the resistant set, since if
the resistant sets are disjoint, subsets are too.
This is a minimal example in the total number of voters over two
elections. It would in theory be possible to make a "partially
resistant" method that elects from the resistant set for every
four-candidate election with fewer than 11 voters. Perhaps such a method
would generalize to provide partial protection at larger voter and
candidate numbers, but it's hard to tell. For that matter, it's hard to
tell how to construct such a method.
With all of this, summability is looking pretty unlikely. But perhaps
there is a particular structure that works... or a relaxation of the
resistant set that retains its strategy resistance and admits summability.
With three candidates, pairwise + first preferences suffice, as shown by
fpA - fpC.
-km
It depends on sub-elections, so it's not entirely surprising that pairwise comparisons might not be sufficient. In that case, the ballots themselves might be as simple as you can go (resistant set is a function of all 2- through n-candidate sub-elections, which in turn is a function of the original ballots).
On 1/6/24 12:37, Kristofer Munsterhjelm wrote:
About a month ago, I wrote in my post "Resistant set incompatibility and passing methods", that
I couldn't find any such "disjoint collisions" with the same first
preference counts and pairwise matrices, leaving open the
possibility that a combination of the two could be used to create a
summable Resistant method.
Well, here's a disproof found by linear programming, showing that a method using only the pairwise magnitudes and first preferences can't be resistant. Surprisingly, using the full positional matrix doesn't help either.
Election 1:
2: A > B > C > D
1: A > D > C > B
1: B > A > C > D
2: B > D > C > A
1: C > A > D > B
1: C > B > D > A
2: D > A > B > C
1: D > B > A > C
A disqualifies B and C, and B disqualifies D. Hence the resistant set consists of A alone.
Election 2:
3: A > B > C > D
2: B > A > D > C
1: B > D > C > A
1: C > D > A > B
1: C > D > B > A
1: D > A > B > C
1: D > A > C > B
1: D > B > C > A
This election has the same first preference counts as election 1, and the same Condorcet matrix. It even has the same positional matrix (number of first preferences, second preferences, etc, per candidate).
But D disqualifies A. Hence the two elections' resistant sets are disjoint despite having the same pairwise magnitudes and first preference counts.
A method that only uses first preferences and the pairwise matrix can't distinguish between the two and must get at least one of them wrong. This also holds for any refined subset of the resistant set, since if the resistant sets are disjoint, subsets are too.
This is a minimal example in the total number of voters over two elections. It would in theory be possible to make a "partially resistant" method that elects from the resistant set for every four-candidate election with fewer than 11 voters. Perhaps such a method would generalize to provide partial protection at larger voter and candidate numbers, but it's hard to tell. For that matter, it's hard to tell how to construct such a method.
With all of this, summability is looking pretty unlikely. But perhaps there is a particular structure that works... or a relaxation of the resistant set that retains its strategy resistance and admits summability.
With three candidates, pairwise + first preferences suffice, as shown by fpA - fpC.
-km
Election-Methods mailing list - see https://electorama.com/em for list info
On 2024-01-06 19:19, Joshua Boehme wrote:
It depends on sub-elections, so it's not entirely surprising that
pairwise comparisons might not be sufficient. In that case, the ballots
themselves might be as simple as you can go (resistant set is a function
of all 2- through n-candidate sub-elections, which in turn is a function
of the original ballots).
Sometimes we get lucky. E.g. determining the smallest mutual majority
set is (to my knowledge) not doable with polyspace (summable) arrays,
but a method can still pass the mutual majority criterion and be
summable. Clone sets generally can't be identified with summable
information either (again to my knowledge), but methods can be cloneproof.
I was just hoping that something like that might be the case here. No
luck so far.
-km