[EM] Sequential dropping by "contestation" - a method related to the Banks set

[Jobst Heitzig]

In Laslier's nice book on tournament solutions I found a
characterization of the Banks set and of Schwartz' "tournament
equilibrium set" by a "contestation relation". The idea behind this
relation is that before replacing an option A by an option defeating A,
one should first choose between all those options defeating A and thus
find a "best" replacement B for A. Let us denote this by B>>A, that is,
define
	B>>A if and only if B>A and B wins among all C with C>A.

Now we can try to use this contestation relation to choose winners by
defining a recursive method. The Banks set, for example, is
characterized as the set of options B which fulfil B>>A for at least one
A. The tournament equilibrium set is somewhat more complicated and I did
not fully understand it yet. Both sets, however, are only defined by
means of defeats, ignoring magnitudes of defeats and thus wasting
information and being far from choosing a single winner in general.

What if we use this idea of "contestation" in the context of successive
breaking of cycles:


SEQUENTIAL DROPPING BY CONTESTATION:
-------------------------------------
If only one option exists, it wins. Having defined the method for
1,2,...,n-1 options, define it for n options:
For each option A, let s(A) be the set of all B with B>A, and let c(A)
be the winner of the method when only the options inside s(A) are
considered (these are at most n-1 options). Draw the diagram of all
defeats s(A)>A. If no cycle occurs, the "uncontested" options win. If
there is a cycle, find the weakest defeat that's in some cycle, say
c(A)>A, then remove c(A)>A from the list of defeats, remove c(A) from
s(A), recalculate c(A) for the new set s(A), redraw the diagram and
check again for cycles.


Note that in each of the diagrams each arrow can be on only one cycle. I
conjecture that there can only be one cycle at all, but did not yet
manage to prove it.

Although I don't know whether the method is monotone, I can prove that
it is IMMUNE: Assume that A wins, and B>A. Then in some iteration of the
method, c(A)=B, and c(A)>A has been removed from the list of defeats
because there was a stronger beatpath from A to c(A) in the diagram. QED

An EXAMPLE:

Writing the magnitude of A>B as AB, assume that CD>DA>AB>BD>BC>AC. Here
C is the only immune option, but the Banks set is {A,B,D}.
The above method starts with
	s(A)={D}, s(B)={A}, s(C)={A,B}, s(D)={B,C},
	c(A)= D,  c(B)= A,  c(C)= A,    c(D)= B.
In the only cycle B>>D>>A>>B, B>D is the weakest link, thus B is removed
from s(D), changing c(D) from B to C:
	s(A)={D}, s(B)={A}, s(C)={A,B}, s(D)={C},
	c(A)= D,  c(B)= A,  c(C)= A,    c(D)= C.
Now there is a cycle A>>C>>D>>A, and A>C is its weakest link, thus A is
removed from s(C), changing c(C) from A to B:
	s(A)={D}, s(B)={A}, s(C)={B},   s(D)={C},
	c(A)= D,  c(B)= A,  c(C)= B,    c(D)= C.
Finally, from the new cycle B>>C>>D>>A>>B, the weakest link B>C is
removed, leaving c(C) empty so that C wins!

Note that the 3rd smallest defeat is dropped first, then the smallest,
and finally the 2nd smallest. This is quite different from other methods
of sequential dropping or affirmation, where the order is according to
magnitudes. I will check that method on my 104 examples to see whether
it coincides with some well-known method...


Jobst