Additional notes on the paper

Remarks on Example 10

(with apologies)

This example shows that, in the case of tournaments, the ranking by choosing procedure induced by the Slater choice procedure is not very weakly monotonic.

This example was obtained following a trial and error heuristic search process early in 1995. At that time, I used the very nice piece of software by Alain Guénoche, called A.B.C.D., that, for small instances, enumerates all the linear orders at minimal distance from a tournament using a B&B algorithm described in Barthélémy J.P., Guénoche A., Hudry O. (1989), Median linear orders: Heuristics and a branch and bound algorithm, European Journal of Operational Research 42, 313-325.

The guiding idea in this heuristic search was to find a tournament having "many" Slater winners and for which the linear orders at minimal distance would be relatively far from the tournament. I expected that in such a case, increasing the position of an alternative could lead to violations of (weak) monotonicity of the ranking by choosing procedure.

I indeed found such an example (with 9 alternatives, the linear orders at minimal distance being at distance 10 from the tournament, whereas it is well know that with 9 alternatives, the maximal possible distance is 12). This is example 10 reported in the paper. At that time, I used Alain Guénoche’s software to solve the optimization problem. Unfortunately, this software only runs on "ancient" Macintosh computers, which are not likely to be much available nowadays.

When preparing the paper, I checked the results obtained in 1995 using a standard Integer Linear Programming formulation of the problem using a commercial ILP code (CPLEX). I then looked for an analytical proof of reasonable length, which, I confess, I have been unable to find. Since I think that the example is interesting, I decided nevertheless to include it in the paper. I provide below a "simple" but quite ugly "proof" that it works. I would clearly be nice to find an elegant analytical proof. It would also be interesting to investigate whether this example is minimal.

Consider the tournament T on X defined by:

1 T 2, 1 T 5, 1 T 7, 1 T 8, 1 T 9,

2 T 3, 2 T 5, 2 T 6, 2 T 7, 2 T 9,

3 T 1, 3 T 4, 3 T 5, 3 T 6,

4 T 1, 4 T 2, 4 T 5, 4 T 9,

5 T 6, 5 T 8,

6 T 1, 6 T 4, 6 T 8, 6 T 9,

7 T 3, 7 T 4, 7 T 5, 7 T 6, 7 T 8,

8 T 2, 8 T 3, 8 T 4, 8 T 9,

9 T 3, 9 T 5, 9 T 7.

It is not difficult to check that 5 is covered by 7 and that 9 is covered by 2. None of them can be therefore at the top of a Slater order.

Considering the scores of each alternative (it is well known that only alternatives having a score greater or equal than the integer part of n/2 (here 4) can be Slater winners) leaves again all alternatives except 5 and 9 as potential winners.

It is also not difficult to check that this Tournament has 9 arc-disjoint circuits:

9 3 6 9

9 5 8 9

9 7 4 9

8 4 1 8

8 2 6 8

7 6 1 7

6 4 5 6

4 2 3 4

1 2 7 3 1

The orders at minimal distance must therefore be at least at distance 9 from T.

We assert in the paper that linear orders at minimal distance of T are at distance 10, that there are exactly 40 such orders and that we have SL(X, T) = {1, 2, 4, 6, 7, 8}.

Lacking any analytical proof of decent length, and since not all reader will have a commercial LP package available, I wrote a few lines of code enumerating all Hamiltonian paths of T (although this is definitely not nice, this, at least gives a check that the example works while not requiring the use a commercial LP software). It is well known that only such paths can be Slater orders. There are exactly 2383 such paths (in order to keep the code as simple as possible, I did not take into account the fact that 5 and 9 cannot be winners). For each of them, I computed the distance wrt T. The list of all these paths (sorted by increasing distance with T) is here (Excel file). This enumeration only takes a few seconds on an ordinary PC.

It is clear that the restriction of T to {3, 5, 9} is the linear order 9 > 3 > 5.

Hence we have 9 >_{SL}(T) 3.

Consider now the tournament V identical to T except that 9 V 1.

I assert in the paper that there at 11 linear orders at minimum distance (this minimal distance is 10) from V and that SL(X, V) = {2, 7, 8}. Again, I have no nice proof of this fact and I resort to the same ugly enumeration trick as before. V has exactly 2537 Hamiltonian paths. The complete list (sorted by increasing distance with V) of these paths can be found here (Excel file).

I also assert that SL(X\{2, 7, 8}, V) = {3}, so that we now have 3 >_{SL}(V) 9 although V improves the position of 9 wrt T, which shows that SL does not induce a very weakly monotonic ranking by choosing procedure.

There is only one linear order at minimum distance (2) from this reduced tournament. This is easily proved. Indeed, we have the following reduced tournament:

1 V 5,

3 V 1, 3 V 4, 3 V 5, 3 V 6,

4 V 1, 4 V 5, 4 V 9,

5 V 6,

6 V 1, 6 V 4, 6 V 9,

9 V 1, 9 V 3, 9 V 5.

Considering the scores of the alternatives, it is clear that 1 and 5 cannot be Slater winners. Observe that any order having 3 on top is at least at distance 1 from V. Considering now the remaining alternatives, there is no Condorcet winner once 3 is removed.

Hence, an order at minimal distance from V having 3 on top must be at least at distance 2 from V. There is one such order at distance 2 from V:

3 > 6 > 4 > 9 > 1 > 5.

Let us now prove that 3 is the unique Slater winner, i.e. that any order having 4, 6 or 9 on top is at least at distance 3 from V. Let us take the case of alternative 4. Alternative 4 is beaten by 3 and 6. hence the minimal distance must be at least 2. Now, there is no Condorcet winner once 4 is removed. Hence the minimal distance is at least 3. The case of alternatives 6 and 9 is deal with similarly.