[EM] MAM algorithm?

[Gervase Lam]

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.