[EM] More mutual majority set results.
Kristofer Munsterhjelm
kmelmet at broadpark.no
Wed Feb 9 09:06:50 PST 2011
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 bruteforcer 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 bulletvote
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 writein could be a problem). I
think it's possible to say truncation and equalrank 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 :)
More information about the ElectionMethods
mailing list