[EM] Sequential dropping towards a spanning tree - another immune method related to ranked pairs and river

[Jobst Heitzig]

Here's another method which chooses an immune option.


SEQUENTIAL DROPPING TOWARDS A SPANNING TREE (SDST):
Start with the set of all defeats and process the defeats by increasing
magnitude. Drop a defeat whenever the remaining set still contains a
spanning tree. The root of the final spanning tree is the winner.


Recall that a (dual) spanning tree is a subset of the set of defeats for
which one option (the root of the tree) is undefeated and all other
options are defeated exactly once.

Remarks:

1. If only the winner is to be found, one can stop as soon as some
option is undefeated.

2. When looking at the *increasing* weight sequence of the final
spanning tree, that is, the sequence of magnitudes of defeats in the
tree, ordered by *increasing* magnitude, it turns out that this is
lexicographically maximal among all spanning trees. In particular, there
is no spanning tree whose smallest weight is larger.
	This is quite similar to the river method, where the *decreasing*
weight sequence of the resulting tree is lexicographically maximal, and
to ranked pairs, where the decreasing weight sequence of the resulting
*acyclic* relation is lexicographically maximal.

3. The winner is always immune. Proof: Assume that A wins, B>A, but the
beatpath from A to B which is contained in the final tree T contains a
defeat C>D of smaller magnitude. Note that replacing C>D by B>A gives
again a spanning tree T'. Hence, at the time C>D was considered for
dropping, the remaining set of defeats still contained a spanning tree,
namely T', so that C>D would have been dropped instead of affirmed. QED

4. With this method SDST, the resulting tree will probably contain
stronger beatpaths from the winner to all other options than with the
river method, which gives is some more "rebutting power" when it comes
to majority complaints (also compare my suggestion of River+ some weeks
ago). For example, when DA>CD>BD>AC>AB>BC, then SDST ends up with
B>D>A>C whose weakest link is A>C, while River ends up with C>D>A>B
whose weakest link is A>B which is weaker than A>C.
	

5. Using the same idea, one could try to improve ranked pairs in a
similar way like this:
	SEQUENTIAL DROPPING TOWARDS AN EULER PATH: Processing defeats from weak
to strong, drop a defeat whenever the remaining set still contains an
Euler path (that is, a "linear" spanning tree, without any branchings).
	This chooses a complete ranking whose weakest link is as strong as
possible. However, that method's winner would *not* be immune in general!


Jobst