[EM] MAM algorithm?
Gervase Lam
gervase.lam at group.force9.co.uk
Sat Jun 4 19:56:14 PDT 2005
While finding a way to group candidates together in order to find a
multi-winner pairwise method, I came up with a technique/algorithm for MAM
that partially works. It should also work for Ranked Pairs, considering
that RP is almost the same as RP.
Imagine that so far MAM has created a two "chains", A>B>C and D>E>F.
Suppose the next pairwise to be considered by MAM is C>E.
Since we know C is defeated by A and B, therefore E must also be defeated
by A and B. In other words, we copy the defeats by A and B to candidate E.
Also, since we know E beats F, therefore C must also beat F. In other
words, we copy the defeat(s) to F to candidate E.
Using this information, it is possible to build up a MAM pairwise matrix,
which I will describe. I'll use James Green-Armytage's example 9 that is
at
<http://fc.antioch.edu/~james_green-armytage/vm/survey.htm#ranked_pairs>.
A B C D E
A 31 35 32 23
B 25 22 38 36
C 21 34 19 30
D 24 18 37 29
E 33 20 26 27
Create an empty matrix. The matrix will be filled in as each pairwise
contest is considered.
38: B>D keep
A B C D E
A
B 1
C
D 0
E
37: D>C keep
A B C D E
A
B 1
C 0
D 0 1
E
So far, according to the matrix, C beats no one. However, D is beaten
by B. Therefore, "copy" the defeat(s) to D to candidate C...
A B C D E
A
B 1 1
C 0 0
D 0 1
E
36: B>E keep
A B C D E
A
B 1 1 1
C 0 0
D 0 1
E 0
So far, according to the matrix, B is beaten by no one and E beats no one.
Therefore, only B>E needs to be added to the matrix...
35: A>C keep
A B C D E
A 1
B 1 1 1
C 0 0 0
D 0 1
E 0
So far, according to the matrix, A is beaten by no one and C beats no one.
Therefore, only A>C needs to be added to the matrix.
34: C>B (skip)
The entry in the matrix for the pairwise contest between C and B has
already been filled in. So, nothing needs to be done.
33: E>A keep
A B C D E
A 1 0
B 1 1 1
C 0 0 0
D 0 1
E 1 0
So far, according to the matrix, E is beaten by B. Therefore, "copy" the
defeat(s) to E to candidate A...
A B C D E
A 1 0
B 1 1 1
C 0 0 0
D 0 1
E 1 0
According to the matrix, A beats C. Therefore, "copy" this defeats by A
to candidate E...
A B C D E
A 1 0
B 1 1 1
C 0 0 0 0
D 0 1
E 1 0 1
Note that C is last in the MAM ordering becuase, according to the matrix,
it has been beaten by all of the candidates. If we wanted to just know
who was last, we could just stop here.
32: A>D keep
A B C D E
A 1 1 0
B 1 1 1
C 0 0 0 0
D 0 0 1
E 1 0 1
So far, according to the matrix, A is beaten by E. Therefore, "copy" the
defeat(s) to A to candidate D...
A B C D E
A 1 1 0
B 1 1 1
C 0 0 0 0
D 0 0 1 0
E 1 0 1 1
According to the matrix, D beats C. Therefore, "copy" this defeat of C to
candidate A...
A B C D E
A 1 1 0
B 1 1 1
C 0 0 0 0
D 0 0 1 0
E 1 0 1 1
31: A>B (skip)
If the algorithm's rules were followed, then A>B would not be skipped.
However, it should be skipped, otherwise there would be three candidates
with a Copeland score of 3 according to the above matrix.
Therefore, I think that there should be a constraint in the algorithm to
say that no more than one candidate is allowed to have a certain Copeland
score.
30: C>E (skip)
29: D>E (skip)
Apologies for the untidiness. I need to get to bed now.
Thanks,
Gervase.
More information about the Election-Methods
mailing list