Hi folks!
In this message, I'd like to discuss beatpath strength vs. beatpath
length and introduce a method (Short Ranked Pairs, SRP) designed to
elect a candidate who has short beatpaths.
As an introductory example, consider 10 candidates X1..X10 with the
following defeat strengths (1=weak, 2=strong):
X1 2 3 4 5 6 7 8 9 10
X1 - 1 1 1 1 1 1 1 1
X2 2 - 1 1 1 1 1 1 1
X3 - 2 - 1 1 1 1 1 1
X4 - - 2 - 1 1 1 1 1
X5 - - - 2 - 1 1 1 1
X6 - - - - 2 - 1 1 1
X7 - - - - - 2 - 1 1
X8 - - - - - - 2 - 1
X9 - - - - - - - 2 -
X10 - - - - - - - - 2
Obviously, most of our favourite methods including most methods which
drop defeats (like Minimax, SD, Beatpath) or affirm defeats (like Ranked
Pairs and River) elect X10 here since the 1s are dropped before the 2s,
or the 2s are affirmed before the 1s, respectively. The resulting social
ordering would be X10>X9>...>X1.
However, some methods (like Kemeny, ROACC, and Copeland) elect one of
X1,X2,X3 instead.
How can this difference be explained? Most methods which process defeats
in the order of their strength lead to strong beatpaths without caring
about the length of the beatpaths. For example, all methods which elect
an "immune" candidate guarantee that majority arguments can be rebutted
by a sequence of equally strong arguments. These rebutting sequences can
however become quite long as the above example shows: When X10 wins and
the majority which prefers X1 to X10 complains, then we can rebut this
argument only by stating that X10>X9>X8>X7>X6>X5>X4>X3>X2>X1 which is a
sequence of 9 defeats. This sequence is considered better evidence for
the fact that X10 is better than X1 than the direct defeat X1>X10 is
evidence for the fact that X1 is better than X10, simply because each of
the nine former defeats is slightly larger than the latter. The
complaining majority will not be very impressed by such a rebuttal,
however. So, the usual definition of beatpath strength is mathematically
elegant but not very adequate in case of long beatpaths.
The Copeland method does not care about beatpaths but only about direct
defeats, hence it elects X1 or X2 as a candidate which is defeated by
only one other candidate. Copeland has well-known drawbacks, however.
Many of those problems have to do with the fact that the method involves
taking a sum over candidates, which makes a method almost surely fail
cloneproofness for example.
Kemeny elects X1 since the vast majority of all defeats indicates the
social ordering X1>X2>...>X10. It ignores the long beatpath X10>...>X1
since it is not supported by any other defeats. But also Kemeny involves
sums (or products) over candidates and has thus many problems.
Finally, ROACC will elect one of the elements of the Banks set
{X1,X2,X3} with different probabilities. But it has the disadvantage of
not considering the defeat strengths at all.
So what could we do if we would like to see rather X1 than X10 elected
in the above example, but still want the method to consider defeat
strengths and be cloneproof?
One way would be to slightly modify one of the nice immune methods, like
Ranked Pairs. Recall that Ranked Pairs affirms the lexicographically
maximal acyclic subset of defeats. The idea is to consider only acyclic
subsets which provide for short beatpaths too:
Definition: SHORT RANKED PAIRS (SRP)
------------------------------------
Affirm the lexicographically maximal *short* acyclic subset of all defeats.
Def.: SHORT ACYCLIC SET OF DEFEATS
----------------------------------
An acyclic set of defeats is *short* if whenever a beatpath X>...>Y is
affirmed, also a beatpath X>...>Y of length at most 2 is affirmed (that
is, either the defeat X>Y or a beatpath X>Z>Y).
This will guarantee that the winner is an uncovered candidate, that is,
a candidate which has beatpaths of length 1 or 2 to all other candidates!
Fortunately, this method can be proved to be monotone and cloneproof,
and there is also a constructive way to find the winner:
Algorithm for SHORT RANKED PAIRS (SRP)
--------------------------------------
Process the defeats in order of decreasing strength. When X>Y is the
defeat at hand, determine whether there exists a short acyclic subset of
all defeats which contains X>Y and all defeats already affirmed but
which doesn't contain a defeat already skipped.
Let's see what happens in the following example:
X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X1 - 12 15 10 18 19 13 10 16
X2 20 - 10 15 11 19 16 12 11
X3 - 27 - 11 14 10 12 10 17
X4 - - 21 - 10 15 16 12 13
X5 - - - 26 - 14 11 10 14
X6 - - - - 24 - 18 13 17
X7 - - - - - 25 - 19 10
X8 - - - - - - 22 - 18
X9 - - - - - - - 28 -
X10 - - - - - - - - 23
SRP will start with affirming X9>X8, X3>X2, X5>X4, and X7>X6, since they
build a short acyclic set. The next defeat, X6>X5, would not introduce a
cycle either and would thus be affirmed by Ranked Pairs. SRP will skip
this defeat however, since together with the two defeats X7>X6 and X5>X4
it would build a beatpath X7>X6>X5>X4 which cannot be supported by any
other defeats in order to give a beatpath X7>...>X4 of length at most 2.
That is, the 5 defeats X9>X8, X3>X2, X5>X4, X7>X6, and X6>X5 are not
contained in any short acyclic subset of all defeats, hence X6>X5 is
skipped. We proceed by affirming X10>X9. Then we skip X8>X7 since it
would give X10>X9>X8>X7 which is also in no short acyclic subset of all
defeats. Also X4>X3 is skipped, but X2>X1 is affirmed. X7>X9, X2>X7 and
X1>X7 are all affirmed since we can later support the long resulting
beatpaths by adding X1-3>X6-10. X8>X10 is skipped since we affirmed
already X10>X9>X8. Finally, all other defeats but X1>X3 are affirmed,
giving a social order of
X3>X2>X1 > X5>X4 > X7>X6 > X10>X9>X8.
What about majority complaints in this example? The majority argument
X1>X3 of strength 12 can be rebutted by the two affirmed defeats
X3>X2>X1 of strengths 27 and 20, that is, by a beatpath which is *both*
short and strong. The other majority argument X4>X3 can be rebutted by
the short beatbath X3>X5>X4 or by the short beatbath X3>X2>X4.
Let me summarize: Strong but long beatpaths are perhaps not sufficient
to rebut majority complaints. Short but weak ones could be better. Short
Ranked Pairs (SRP) is a modification of Ranked Pairs into the direction
of methods like Kemeny and Copeland. It is monotonic and cloneproof and
elects a candidate from the Uncovered Set. What about the anti-strategic
properties of SRP?
Jobst