[EM] River method - a refinement, minor computational evidence, and a generalized IPDA criterion ISDA

[Jobst Heitzig]

Hello all!

Having studied Steve Eppley's wonderful website in more detail, in
particular the section about how to rebut majority complaints, I thought
about a certain refinement of the River Method and made some
computational simulations comparing Beatpath, MAM, and River.

Also, as it seems that IPDA is the first known criterion discriminating
between MAM and River (see Markus' recent post), I tried to work out
this point a bit further and came up with some straightforward
generalization of IPDA.

(For simplicity, all thoughts below only concern the general case of
pairwise different majorities.)


1. Majority complaints, and River+
----------------------------------

Concerning the set of affirmed majority defeats, the main difference
between MAM and River is that MAM affirms a maximal number of large
defeats, while River tries to affirm only so much defeats as are needed
to determine a unique winner. The main consequence of this difference is
that the River diagrams are much simpler (tree-like) and can thus show
the process and reasons for the final decisions easily and efficiently.

	When, after the decision for X, a majority should complain that they
prefer Y over X, the River diagram easily shows a larger beatpath from X
to Y. However, this beatpath may not be the strongest existing beatpath
from X to Y, hence the complaint would not be rebutted as strongly as it
could be. Although this can happen with MAM too, the MAM diagram usually
contains more majorities and one can expect some more "rebutting power"
here.

	One solution is of course to publish the River (or MAM) diagram showing
the process of the method and the reason for the decision, together with
a second diagram showing all strongest beatpaths from the River (or MAM)
winner to all alternatives. This second diagram is also tree-like in
general and could be called the "beatpath tree" of the winner. (I wonder
whether "beatpath trees" have perhaps already been discussed in the
context of the beatpath method for which they can of course also be
published to rebut majority complaints.)

	The problem with two published diagrams, however, would be that they
might erroneously be interpreted as showing two social orderings. This
is because although both trees show the same winner, the combination of
both diagrams could produce cycles. Although this might be more probably
in the MAM case where the original diagram shows already more majorities
than a tree, it can also easily happen in the River case.

	For the river method, a second possibility to increase its rebutting
power ex post is to incorporate additional information into the River
diagram after the winner has been determined:

Def. RIVER+:
First, construct the river diagram in whatever way (interactively,
semi-interactively, or top-down). Second, process all majorities again
by descending magnitude and incorporate those as dashed arrows into the
diagram which do not introduce cycles (but allowing branchings now).
Third, remove every dashed arrow which does not belong to some strongest
shown beatpath from the winner to any alternative.

In other words, perform River to *find* the winner (solid arrows), then
proceed with MAM to help *defending* that winner (dashed arrows).

	This results in a diagram with at most one solid and one dashed arrow
originating at every non-winner, hence containing at most 2n-2 arrows
for n options, which is still much simpler than a full MAM diagram which
in general contains O(n^2) arrows I fear. The solid lines show the
process of the method, the dashed arrows give additional "rebutting power".

	Of course, one could perform step three of the above definition also to
condense an MAM diagram by removing majorities inessential for defending
the winner. However, in contrast to River+, this can result in removing
majorities essential for *finding* the winner in the first place...


2. Some minor computational evidence
------------------------------------

To study the "rebutting power" of River+, I performed some simple
simulations. They are not as refined as Steve's simulations in that they
directly generate a random preference matrix instead of simulating
individual voters. I used three parameters: No. of options,
"Uncertainty" U and "Linearity" L.

(Details: For each pair of options Xi and Xj with 1<=i<j<=n
independently, first the fraction of voters with no strict preference
between Xi and Xj (="undecided voters") was drawn uniformly at random
between 0 and U. Then the fraction of "decided voters" preferring Xi to
Xj was drawn uniformly at random between L and 1. In particular, all
majorities were different with probability 1!)

For each of the simulated methods (Beatpath, MAM, and River), I computed
the winner and its beatpaths. For the MAM and River winners, also those
beatpaths contained in the MAM, River, or River+ diagrams were
determined, giving six groups of beatpaths:
(1) All existing beatpaths from the Beatpath winner,
(2) All existing beatpaths from the MAM winner,
(3) All existing beatpaths from the River winner,
(4) All beatpaths from the MAM winner affirmed by MAM,
(5) All beatpaths from the River winner affirmed by River, and
(6) All beatpaths from the River winner affirmed by River+.
For each of those beatpaths, I computed
(a) the strength (= magnitude of its weakest element),
(b) the margin (= strength - no. of voters prefering the alternative),
(c) a "probabilistic strength" (= product of all elements' relative
magnitudes), and
(d) its length.
In each of the six groups of beatpaths, I computed the minimum and mean
strength and probabilistic strength, and the maximum and mean length.
For all three winners, I additionally computed the number and sum of
defeats, the balance of defeats (= sum of defeats - sum of complaints),
and which winner beat which pairwise. Finally, the sizes of the Smith,
Weakly Immune, and Immune sets were computed, since all three winners
belong to them.

First results indicate that the three methods often find the same winner
and perform very similar judged from the above measures.

Example with 10 options, no uncertainty (that is, no truncated ballots),
and L=0.4 (that is, with some correlation between voters preferences):
In only about 1% of the cases, the River winner differed from both
Beatpath and MAM winner, and in only about 0.5% Beatpath and MAM were
the same but River was not. In contrast, in about 5% of the cases, River
and MAM were the same but Beatpath was not, and also in about 5% of the
cases, River and Beatpath were the same but MAM was not. There were only
about 11% of the cases where the Immune set was not a singleton. That
is, in almost *all* cases where there were more than one immune element,
MAM and Beatpath chose different winners. In other words, whenever they
are "immunologically allowed" to choose differently, it seems they
almost certainly do...

As for "rebutting power", the picture is unclear. Depending on which
measure you look at, either of Beatpath, MAM, and River+ performs
slightly better than the two others, where River+ is mainly either first
or second.

Example with 4 or 20 options, and no uncertainty or linearity:
Judging from min. strength or min. margin, we get
	Beatpath > River+ > MAM.
Judging from mean strength, mean margin, or balance of defeats, we get
	River+ > Beatpath > MAM.
Judging from mean probabilistic strength, we get
	River+ > MAM > Beatpath.
Judging from who beats whom, max. length, mean length, or sum of
defeats, we get
	MAM > River+ > Beatpath.
Judging from number of defeats (= Copeland score), we get
	either MAM > River+ > Beatpath
	or MAM > Beatpath > River+.

In all, River+ could make a nice compromise between Beatpath and MAM
when such performance measures are considered important.


3. River[+] fulfils generalized IPDA
------------------------------------

As Markus stated recently, River (but neither Beatpath nor MAM) fulfils
IPDA. However, Pareto-dominated alternatives seldom occur by chance
since they require that *all* voters vote in a certain way. But the
criterion can be generalized in a straightforward way:

Def. INDEPENDENCE OF STRONGLY DOMINATED ALTERNATIVES (ISDA):
Removing a strongly dominated alternative must not change the winner.
X is STRONGLY DOMINATED by an alternative Y if
(i) Y beats X
and, for all Z distinct from X,Y:
(ii)  if Z beats Y, Z beats X even stronger,
(iii) if Z beats X, Y beats X even stronger,
(iv)  if X beats Z, Y beats Z even stronger, and
(v)   if Y beats Z, Y beats X even stronger.

In the general case, Pareto-dominated alternatives are also strongly
dominated but not vice versa, hence ISDA is then stronger than IPDA. As
Steve already pointed out for Pareto-dominated alternatives, such
strongly dominated alternatives might be easily be found by a losing
party and be added strategically to change the winner, which should not
be possible.

River[+] fulfils ISDA.
Proof: Assume X is strongly dominated by Y and its removal changes the
River winner. Then the river diagram must contain arrows
Z---a-->X---b-->Y (a and b being the strengths), hence also Y beats Z
with some strength c, where b>c>a. As River affirms X>Z, it did not
affirm Y>Z before, so it affirms a beatpath from Z to Y even stronger
than c -- a contradiction since also Y>X>Z is affirmed!
(By the way, (ii) is not needed for the proof.)


Jobst