[EM] New use of ranked pairs
Forest Simmons
forest.simmons21 at gmail.com
Fri Sep 29 18:13:43 PDT 2023
Let pairs (X>Y) of defeats be listed in order of "strength" according to
some gauge of strength ... I like the gauge of winning votes plus losing
absentions ... but use your own ideas ...
To gauge the strength of a candidate ranking R, create a binary signature
S(R) in which the n_th binary digit from the left (i.e. most significant)
end is a one or a zero depending on whether or not the first candidate of
the n_th pair in the list is ranked (by R) ahead of the second candidate in
that pair.
The strength of the R is the numerical value of its binary signature.
The candidate finish order for our new version of ranked Pairs is the
ranking R with the greatest strength as given by S(R).
In general, maximizing S(R) is computationally intractable because of the
factorial explosion of the number of possible rankings that need to be
checked.
But when rankings are restricted to transitive beat paths (i.e. "chains"),
then the computation is polynomial time (second degree) in the number of
candidates, because if a set of candidates does organize into a chain,
there is only one way to do it ... unlike in the case of organizing
candidates into general beatpaths.
So our efficiently comparable version of Ranked Pairs is to select as
finish order, among all possible chains of the candidates, the strongest
one.
Of course, in general different gauges of defeat strength can lead to
different finish orders, but because they are all maximal chains, the head
of the finish order will always be a Banks candidate ... therefore always a
member of Landau.
[If the head were covered by X, then the chain R would not be maximal, so
S(R) would get k new defeat pairs to increase the value of its signature
S(R), etc]
The signature can be thought of as a measure of how hard it would be to
reverse the ranking R, since every pair respecting the R order would be
reversed.
fws
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20230929/b44a3255/attachment.htm>
More information about the Election-Methods
mailing list