[EM] Hello again -- and a new method for you!

[Jobst Heitzig]

Hello election methods list!

Some years ago I have posted a few methods on the list, so some of you
might remember me vaguely... Though lacking time to actively participate
in your discussions, I have still visited the archives a number of times
in the meantime.

Today, I would like to ask you to consider the following Condorcet-type
group decision method. I made it up after reading about Ramon Llull’s
two election methods from the 13th century (which were later adopted by
Condorcet). The main appeal of the new method is that it can easily be
applied interactively without any technical equipment other than pencil
and paper, and it can be performed while discussing the options, helping
to visualize, structure, and focus the whole discussion. (This is
essentially what some researchers call "procedural".)
	At the same time, the new method is very similar to Tideman’s rule and
fulfils all the important criteria such as monotonicity and clone
consistency, for example. Like Tideman’s rule (and unlike other
Condorcet-type methods such as Sequential Dropping), the method
concentrates on the strongest rather than the weakest defeats, but in
contrast to Tideman's rule, it focuses on these strongest defeats
locally (that is, at every single option) instead of globally!
	The idea is to construct a simple, almost tree-like subgraph of the
whole graph of pairwise majorities. This subgraph shows a unique „best“
element and simultaneously shows why this element can be considered
better than the other options. For this, only one strong defeat must be
included for each loosing option, and it would be counter-productive to
include additional defeats for the same options, since they would only
result in the exclusion of strong defeats needed in other parts of the
graph. The dynamic of the whole construction process bears some
similarity to the flow of a system of rivers, so I call it the "River
Method". Here come the rules in non-technical language:


The River Method – Interactive Version:

	1. Let the deciders sit down in a circle. Using pencil, paper, and
eraser, they will draw a system of "rivers", originating from the
"worst" options and flowing past "better" options towards a common
destination: the "winning" option. Beginning with an empty sheet of
paper and an arbitrary decider, and proceeding in clockwise order, each
decider gets the opportunity to give part of her opinion by telling that
she likes some option X better than some other option Y and then shortly
argueing in favour of X and against Y. After each of these statements,
the system of rivers is changed by first "digging a river bed" between X
and Y and then checking the "course" of the rivers. This is done
according to the following easy rules:
	2. Directly after the decider has told his opinion that X be better
than Y, it is counted how many deciders agree in prefering X over Y and
how many disagree with it and prefer Y over X instead. (Some deciders
might also abstain from this partial decision.) If the second number is
not larger than the first, the new river bed allows a flow from X to Y,
otherwise it allows a flow from Y to X instead. In both cases a dashed
arrow between X and Y indicating the direction of the possible flow is
drawn, and the larger of the two numbers is written besides the arrow's
tail. This number is considered the "width" of the river bed between X
and Y. After the new river bed has been "digged" in this way, it is
checked whether the course of the rivers changes as a consequence:
	3. It is first checked whether the rivers actually use the new bed: a)
If there is already a river segment starting at the same point as the
new bed, and if its bed has a larger width than the new bed, the new bed
is not used and its arrow is erased. b) If there is already a river in
the system flowing from the point where the new bed ends towards the
point where the new bed starts, and if that part of the river has a bed
which has at all points the same or a larger width than the new bed,
then the new bed is also not used and its arrow is erased. Otherwise,
the rivers do use the new bed and its arrow is drawn as a solid line.
	4. When the new bed is indeed used by the rivers, it is then checked
whether perhaps some other segments of the rivers "run dry" or must be
"dammed": a) Each river segment starting at the same point as the new
bed and having a bed of smaller width changes its course into the new
bed, so that their old bed "runs dry" and its arrow is erased. b) As
long as there is any circular flow in the system of rivers, that segment
of the circular flow which has the narrowest bed is "dammed" and its
arrow is also erased from the drawing. (In the rare case that there is
more than one segment having the narrowest bed, all of these are dammed!)
	These possible erasures make sure that there do not remain any circular
flows in the system and that the rivers only branch when they find beds
of exactly equal width. (On rare occasions, if the drawing shows
complicated slopes since many arrows have been erased, it might be
useful to redraw the current system of rivers on a new sheet of paper
and choosing better positions for the options.)
	5. After each decider has had the opportunity to suggest new river
segments several times in this ways, the system of rivers will finally
be stable, all rivers will end in one and the same point, and no further
changes will be possible. In general, the final destination does not
depend on the order in which statements are made! That common
destination is the winning option, and the final course of the rivers
represents the course of the discussion. The final drawing also shows
easily why the winner can be considered better than all other options,
since from each other option a sequence of arrows leads towards the
winner, each arrow representing a majority opinion none of which can be
contradicted by other majority opinions of equal strength. (However,
even if the final drawing might be one linear flow, it must not be
interpreted as a complete ranking! To determine a 2nd choice winner when
the 1st choice becomes unavailable, the final arrows to the 1st choice
winner must be removed and the discussion must be continued without the
1st choice winner, until the system gets stable again!)

Summary:
1. ARGUE:
A decider issues a statement of the form "X is better than Y".
2. VOTE:
Count agreements and disagreements with this statement, but allow
abstentions.
Draw a new "river bed" as a dashed arrow in the direction of the
majority's preference.
Annotate the majority's number alongside the new bed as its "width".
3. VERIFY:
Erase the new bed if
a) there is a wider branch at that starting point, or
b) it would become the narrowest segment in some circular flow.
Otherwise redraw the new arrow as a solid line.
4. FIX:
Erase each river segment which
a) runs dry since it is at a branching point with a wider branch, or
b) must be dammed as the narrowest segment in some circular flow.
5. REPEAT
in clockwise order until stable. The common destination of all rivers wins.


Here's an example:

7 times	A>C>D>B
6 times	B>A>C>D
4 times	B>C>D>A
3 times	D>B>A>C
2 times	D>A>B>C
2 times	D>C>A>B
1 time	D>B>C>A

Number of deciders	...over...				
preferring...		A	B	C	D		Sum:		
		A	-	(11)	18	13		42
		B	14	-	16	(10)		40
		C	(7)	(9)	-	17		33
		D	(12)	15	(8)	-		35

Selected River Method applications (A>B means an arrow from B to A!):

(i)	C>D?	17+ 8-	(added)			D ---> C
	B>C?	16+ 9-	(added)			D ---> C ---> B
	D>B?	15+ 10-	(not used)
	A>B?	11+ 14-	(B>A added)		D ---> C ---> B <--- A
	A>C?	18+ 7-	(added, B>C runs dry)	D ---> C ---> A ---> B
	D>A?	12+ 13-	(A>D not used)
	D>B!		(added, B>A dammed)	B ---> D ---> C ---> A

(ii)	B>A?	14+ 11-	(added)			A ---> B
	D>B?	15+ 10-	(added)			A ---> B ---> D
	C>D?	17+ 8-	(added)			A ---> B ---> D ---> C
	A>C?	18+ 7-	(added, B>A dammed)	B ---> D ---> C ---> A
	D>A?	12+ 13-	(A>D not used)
	B>C?	16+ 9-	(not used, A wins)

(iii)	A>C?	18+ 7-	(added)			C ---> A
	C>D?	17+ 8-	(added)			D ---> C ---> A
	B>C?	16+ 9-	(not used)
	D>B?	15+ 10-	(added)			B ---> D ---> C ---> A
 	B>A?	14+ 11-	(not used)
	A>D?	13+ 12-	(not used, A wins)

In all three constructions, A wins. This is also the case if Plain
Condorcet, Smith/Condorcet, Sequential Dropping, Schwartz Sequential
Dropping, the Beat Path Method, Borda Counts or Approval (with cut-off
in the middle) were applied. Plurality would elect B instead. Also
Tideman would elect B since it would add B>C and thus drop D>B. In
contrast, the River Method does not introduce B>C since it has already
the stronger A>C to show that C is not best! It seems that IRV would
elect D, but I can't quite believe that...


In order to get a quick solution with the interactive version of the
River Method, it is helpful when X is always among the current
destinations of the system and Y is an option with good chances against
X (this was the case in example (ii)). If we can manage to always choose
Y to be the option with the best chances against X that has not already
been compared with X, there will always be a unique destination from the
beginning, and we will never need to choose a different X than the
current destination. Hence the following version:


The River Method – Semi-Interactive Version:

0. Choose an arbitrary option as the beginning source (and destination).
1. DISCUSS alternatives to the current destination(s).
2. VOTE: By pairwise comparisons, determine the widths of the most
promising river beds that start at (one of) the current destination(s)
and have not been erased before.
3. VERIFY: For each of the widest among these, check whether the rivers
do follow it and draw it in that case.
4. FIX the system as in the interactive version.
5. REPEAT until stable.


In the above example, this could look like this:
Start: A					A
B,C,D > A?	B 14+ 11-	(B>A added)	A ---> B
C,D > B?	D 15+ 10-	(D>B added)	A ---> B ---> D
A,C > D?	A 13+ 12-
		C 17+ 8-	(C>D added)	A ---> B ---> D ---> C
A,B > C?	A 18+ 7-
		B 16+ 9-	(B>A dammed)	B ---> D ---> C ---> A
B,D > A?	B!		(not used, A wins)


Mathematically speaking, the River Methos finds a special acyclic
subgraph T of the weighted directed graph G of all pairwise majorities.
T is acyclic, and if it contains two edges with the same source, they
have equal weight. I will call this class of subgraphs "almost-trees".
In the "general case" where all weights are different, T is a dual tree
in the usual sense. (Indeed, I could have called this the "Tree Method"
as well, but that would have been confused with "decision trees" too
easily, which are something quite different.)
	In the "more general case" where every cycle in G contains a unique
smallest weight, T is in a certain sense optimal among all almost-trees
of G. Sort the weights of all edges in T by descending order and
continue this finite sequence by a sequence of zeroes, calling this the
"weight sequence" of T. It turns out that T has a lexicographically
maximal weight sequence among all almost-trees of G. (The lexicographic
order orders two sequences by the leftmost entry in which they differ.)
In other words, no edge can be added to T without removing some edge of
at least the same weight or introducing a cycle or a branching with
different weights.
	In this more general case, also Tideman's rule finds a subgraph of G
with a lexicographically maximal weight sequence, but it does so among
all acyclic subgraphs. Hence also Tideman's rule could be stated in a
way similar to the interactive version of the River Method. Indeed, we
need only remove steps 3a) and 4a) from the method and get an
interactive version of Tideman's rule. But that would of course be of
little use since the resulting acyclic graphs are in most cases by far
too complicated to be drawn in such an interactive way! In contrast,
(almost-)trees are a very simple structure. The most simple kind of
subgraph which would still guarantee a unique winner in every graph
would be the dual trees in the usual sense, but there is a reason why I
chose almost-trees instead of dual trees: allowing branchings with
equally weighted branches, the method becomes "component consistent" in
a very strong sense, in particular, it becomes immune against cloning.
Also Tideman's rule fulfils this important axiom, while the beat path
method does not.
	It would perhaps be interesting to study other classes of subgraphs.
For example, when we take the top element of the lexicographically
maximal sub-chain of G, we get an element of the well-known Banks set
(the latter consisting of all top elements of inclusion-maximal
sub-chains of G).

The analogy to Tideman's method also indicates that in the more general
case, there is also a non-interactive, top-down method, which requires
all pairwise comparisons to be made beforehand though:


The River Method – Top-Down Version:

1. DISCUSS all options at once.
2. VOTE: By pairwise comparisons, determine the widths of all possible
river beds.
3. SORT the widths and process the river beds in groups of equal width,
in descending order.
4. VERIFY: For each river bed in the current group, check whether the
rivers do follow it and draw it in that case.
5. PROCEED with the group of river bed of the next smallest width until
all have processed.

In this version, no fixing is needed!


I am quite curious to hear your opinion about this...
Jobst Heitzig