On Generalizing Condorcet’s Original Plan To Resolve Cycles
Summary: Condorcet’s original ideas of 1785 to 1788 are shown to lead naturally to Ranked Pairs, a well-known Condorcet-compatible method that is free of influence by clones. The computa- tional effort of solving for the rank order of the candidates under Ranked Pairs is shown for N candidates, whose least upper bound is O(N3) in worst case, to be empirically O(N1.8) when averaged over a large number of random elections, even for values of N up to 1024. Methods are demonstrated whereby an elections official or a common voter can prepare information that allows a voter who has no recourse to a computer to judge whether a Ranked Pairs rank-order has been computed correctly. As one method, the definition and implementation of the circ operation, which sorts all possible permutations of the candidates into an ordered list with the Ranked Pairs rank order at the head, are simplified so it is an O(N2) and not an O(N2 lnN) process, and one that runs ever faster the closer the Kendall-tau distance between two permutations becomes.
