[EM] Convergent Allied Comparison: new fpA-fpC generalization, producing a comparison matrix

[Filip Ejlak]

I've got a new fpA-fpC-compliant method and this time I am very satisfied
with its behaviour (after checking some test examples that some other
methods failed, though I guess it needs some robust checks on
monotonicity). Instead of just pairwise comparing the candidates, it
compares the "alliances" of these candidates in order to create a special
pairwise comparison matrix (in a more burial-resistant manner). The
mechanism tends to break Condorcet cycles, even though there are some rare
cases where it doesn't clear *all* the ambiguity and a completion method
has to be used.

The "agreement" rule was created specifically to make the method cloneproof
(but it also had to be strict enough so that a) the burial resistance was
not weakened, b) the method didn't stop converging, i.e. achieving stable
solutions).

It's worth noting that - in a given iteration - a covered candidate can't
have any allies against the covering candidate, so a covering relation
should cause a visibly strong defeat.


*Convergent Allied Comparison (CAC)*

Definitions:

·       (A>B)-ally - a candidate that pairwise beats B, doesn't pairwise
beat A and is not in agreement with B against A

·       (A,X)-agreement against B - occurs when A and X are in the same
pairwise relation with B (win, lose or tie), number of A>=X>B votes is
greater than number of A>=B>X votes and number of X>=A>B votes is greater
than number of X>=B>A votes

·       (A>B)-alliance - a set that consists of A and all (A>B)-allies

·       score(A>B) = [number of votes that prefer some member of the
(A>B)-alliance to every member of the (B>A)-alliance] + [number of votes
that prefer A to every member of the (B>A)-alliance if A pairwise beats B,
otherwise 0]

Procedure:

·       Calculate the scores and use them to create a pairwise comparison
matrix - then use this matrix to redefine which candidates are pairwise
beaten by whom (which in turn can affect the alliances and the scores).
Repeat until the comparison matrix does not change with a new iteration -
this is the final CAC matrix.

·       If there exists a candidate that is unbeaten according to the CAC
matrix, choose this candidate. Otherwise apply a defeat-dropping Condorcet
method (River, RP/MAM or Schulze) to the CAC matrix.


Example:

9: A>B>C

6: B>C>A

8: C>A>B

There's no agreement between any candidates. (A>C)-alliance is {A,B},
(B>A)-alliance is {B,C}, and (C>B)-alliance is {A,C}. Scores in the first
iteration are as follows:

  |    A   |    B   |    C

A |    -   | 9+9=18 | 9+6=15

B | 6+8=14 |    -   | 6+6=12

C | 8+8=16 | 9+8=17 |    -

So we already see a strict order (C>A>B) in this matrix, but as the beating
relations (and, with them, the alliances and the scores) have changed,
let's see the next iteration to make sure that the solution is stable. Now
the only multi-member alliance is the (C>B)-alliance: {A,C}.

  |      A     |      B     | C

A |      -     | 9+8+9+8=34 | 9

B |      6     |      -     | 6

C | 6+8+6+8=28 |  9+8+8=25  | -

The pairwise relations remain unchanged, so this is the final CAC matrix,
with C candidate confirmed as the winner.

- Filip Ejlak
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230519/9bab53e8/attachment-0001.htm>