[EM] More mutual majority set results.

[Kristofer Munsterhjelm]

Kristofer Munsterhjelm wrote:
> If there is a polyspace summable method to determine the mutual majority 
> set, that method can't be using the pairwise matrix alone. After 
> tinkering a bit, I found an example where two different sets of ballots 
> give the same pairwise matrix, yet have different mutual majority sets; 
> since a method that only knows the pairwise matrix can't distinguish 
> between the two and thus will have to make at least one mistake.

Replying to myself, but my brute-forcer found an example for the 
positional matrix as well. These two ballot sets have the same 
positional matrix but different mutual majority sets, and thus one can't 
discover the set from the positional matrix alone.

1: A>C>B>D
1: B>A>D>C
1: B>D>C>A
1: C>A>B>D
1: C>D>A>B
1: D>B>C>A
1: D>C>A>B

has mutual majority set {ABCD}, and

1: A>B>C>D
1: B>A>C>D
1: B>A>D>C
1: C>D>A>B
1: C>D>B>A
1: D>C>A>B
1: D>C>B>A

has mutual majority set {CD}.

Both have two votes for every candidate but one in each place. There are 
two for each but A in first rank, two for each but B in second, two for 
each but D in third, and two for each but C in fourth.

As before, the sets aren't completely disjoint, which makes sense since 
there are methods that use the positional matrix alone and satisfy 
mutual majority. Bucklin is one such method, for instance, and Bucklin 
would claim a tie between C and D (since both have 4 points after the 
second ranks have been added in). If ties were to be broken in an "Ext" 
manner (by considering later ranks), C would win (with 6 points to D's 5).

-

But thinking about it, I think I can show it's impossible to have a 
polynomial space summable structure whose data can be used to determine 
the mutual majority set.

Consider what I've been calling the "DAC/DSC structure". It's a list of 
solid coalitions along with how many voters prefers the members of the 
set to everybody else. Such a structure can look like:

ABCD  25
ABC   10
B     8
AC    7
.. etc

Now assume this structure can hold a superpolynomial amount of data (wrt 
the number of candidates). There are potentially 2^c different sets, and 
each of these can hold a value. I haven't actually proved that - it's a 
bit more diffcult because a single vote can't both increase {AC} and 
{BD}, for instance - but it's reasonable.

Then say I have a magic summable method that gives the mutual majority 
set, and I wonder what the value for {AC} is. To do this, I first 
introduce a bunch of dummy candidates, and a bunch of voters who all 
rank a dummy candidate above whatever set's the current mutual majority 
set. If the method permits truncation, then the voters just bullet-vote 
for the dummy candidates. Repeat until the mutual majority is now the 
set of all the candidates.
Once that's done, I add in voters who vote A = C > rest. If truncation 
is permitted, the voters just vote for A = C. At some point, the new 
mutual majority set is either A, C, or {AC}. If it's {AC}, then I'm 
done: by counting the number of new voters along with the dummy voters 
added, I determine the value for {AC}. If it's A, I add voters who rank 
every candidate ahead of A, and if it's C, I add voters who rank every 
candidate ahead of C. Since the method is summable, I can add candidates 
and voters with little trouble.

Thus I could, given the magical method, reconstruct the DAC/DSC 
structure, which holds more information than any polynomial (given 
enough candidates). By the pigeonhole principle, no polynomial space 
structure can be up to that task, hence that magic method can't exist. W5.

It seems to be workable, though there are some assumptions that one may 
break. First, due to constraints, perhaps the DAC/DSC structure can be 
encoded into polyspace. Okay, but if that's the case, we can turn DSC 
summable, which would be quite interesting in its own right.
Second, it may be hard to add candidates and voters. Consider a 
Condorcet matrix where nobody fully ranks. It'll be quite hard to find 
out the number of voters (and so adding write-in could be a problem). I 
think it's possible to say truncation and equal-rank is not permitted 
and do as before. The change is that the A = C ballots have to be turned 
into half A > C and half C > A (which would be a pain if there are many 
candidates in the set to check), and that the dummy voters would have to 
vote all candidates in such an order that nobody who isn't a mutual 
majority member gets a mutual majority. One might use feedback here, 
e.g. if adding X1 > X2 > A > B turns {A, X1, X2} into a mutual majority 
set, change it to X2 > B > X1 > A, but I don't have proof that this 
won't lead to a situation where no possible completion can prevent a 
mutual majority set from showing up.

In short, this is all very quick and dirty, so if you see something 
wrong (or even if it all seems right), tell me :-)