[EM] Ease of River computation (was: Condorcet baseball rankings)

[Jobst Heitzig]

Hi!

I think the nice baseball example is perfect for showing that the River
method is a simple alternative to Beatpath and Ranked Pairs. So I would
like to show here in detail how the River winner can be determined
easily with pen and paper.

We start with the percentage of games won between each two teams, as
computed by Adam:

    a   b  c  d  e   f   g  h  i  j  k  l  m  n
a      67 44 56 44  78 100 56 56 53 65 86 47 44
b  33     53 33 50 100  67 44 26  0 78 58 71 58
c  56  47    67 43  86  67 33 58 89 56 74 44 74
d  44  67 33    53  42  68 47 43 22 78 67 67 43
e  56  50 57 47     47  58 37 33 67 56 50 11 71
f  22   0 14 58 53      42 37 57 44 56 50 44 67
g   0  33 33 32 42  58     37 17 22 29 33 44 50
h  44  56 67 53 63  63  63    33 29 56 44 71 67
i  44  74 42 57 67  43  83 67    78 67 79 56 63
j  47 100 11 78 33  56  78 71 22    58 78 55 67
k  35  22 44 22 44  44  71 44 33 42    29 37 22
l  14  42 26 33 50  50  67 56 21 22 71    22 50
m  53  29 56 33 89  56  56 29 44 45 63 78    78
n  56  42 26 57 29  33  50 33 37 33 78 50 22

In this example, a defeat X>Y is when the entry in row X, column Y is
larger than 50.

To determine the River winner, I will use the "semi-interactive" version
of River: we start with an arbitrary option and proceed along strongest
defeats until we get a cycle; then we break the cycle at its weakest
link and proceed with the next weaker defeat against the currently
undefeated option. To do so, we need not find the largest entry in the
whole table (as would be required by Ranked Pairs) but only in one
column at a time.

So, starting with a, we find that a<c is a strongest defeat against a,
so we draw an arrow a-->c and label it 56. In the c column, 67 is the
largest entry, so we proceed by drawing an arrow c-->h and label it 67,
and so on. The first cycle occurs in this situation:

a --56-> c --67-> h --67-> i --58-> c
         ^                          ^
Now, the weakest defeat in the cycle c<h<i<c is i<c, so we remove it and
proceed at i with the 2nd strongest defeat against i, which is i<f:

a --56-> c --67-> h --67-> i --57-> f --100-> b --100-> j --89-> c

Again, there's a cycle c<h<i<h<b<j<c and i<f is the weakest defeat in
it. Removing it leaves us with the following diagram (in which the two
"rivers" starting at a and f "join" at c):

                    a --56-.
                            -> c --67-> h --67-> i
f --100-> b --100-> j --89-´

Now we must examine with the 3rd strongest defeat against i, which is
i<a with strength 57. This introduces a cycle a<c<h<i<a which is broken
at a<c:

f --100-> b --100-> j --89-> c --67-> h --67-> i --57-> a

A strongest remaining defeat against a is a<e, and we proceed until the
next cycle occurs:

f --100-> b --100-> j --89-> c --67-> h --67-> i --57-> a --56-> e...

       ...e --89-> m --71-> b

We drop a<e and get:

        f --100-.
                 -> b --100-> j --89-> c --67-> h --67-> i --57-> a
e --89-> m --71-´

The next cycle occurs here:

        f --100-.
                 -> b --100-> j --89-> c --67-> h --67-> i --57-> a...
e --89-> m --71-´

      ...a --56-> n --78-> m

Again we break the cycle after a, that is, at a<n:

          f --100-.
e --89-.           -> b --100-> j --89-> c --67-> h --67-> i --57-> a
        -> m --71-´
n --78-´

Now we examine a<m (53), but we already have m<...<a with strength 57,
so a<m is not affirmed. Since there is no remaining defeat against a, we
begin to realize that a will probably win. However, we must still
consider those options not yet examined. Therefore we start a new
"river" at d (which does not occur in our diagram):

d --78-> j

We see that this river joins the rest at j, so we can proceed with the
next unexamined option, which is g:

g --100-> a

What about k?

k --78-> b

And finally l?

l --86-> a

Hence the final river diagram looks like this:

          f --100-.
e --89-.   k --78--> b --100-.
        -> m --71-´            -> j --89-> c...
n --78-´               d --78-´

        ...c --67-> h --67-> i --57-.
                             g --100--> a
                             l --86-´

Or rotated with the winner at the top:

   winner:
      a (=Anaheim)
     /|\
    i g l
    |
    h
    |
    c
    |
    j
   / \
  b   d
 /|\
f k m
   / \
  e   n

With this diagram, all "majority complaints" who argue that some option
(c, for example) was better than a can easily be rebutted by pointing at
the affirmed beatpath leading back to a (for example, c<h<i<a).

I hope this shows that, compared to Beatpath and Ranked Pairs, it is
relatively easy to determine the River winner.

For Ranked Pairs, we would have to find the largest, 2nd largest, 3rd
largest (and so on) entries in the *whole* table, that is, out of
14*13=182 entries, whereas for River, we only needed to find the largest
entries in each *column*, that is, out of 13 entries. The River diagram
shows only the smallest number of 13 defeats which are necessary to
rebut all majority complaints, whereas Ranked Pairs will affirm many
more defeats (I guess about 60 or 70 in the above example, did anyone
count them already?). Also, Ranked Pairs does not come with a
comparingly simple diagram showing which defeats are affirmed and which
are not.

For Beatpath, we would either have to compute all the 182 maximal
beatpaths by some sophisticated algorithm, or draw a complicated diagram
with about 90 arrows in which we would have to find cycles and erase
arrows repeatedly. Both seems to be unmanageable with only pen and paper.

Jobst