Pairwise sorted methods

From electowiki

Pairwise sorted methods all share these properties:

  • The list of alternatives is first sorted top to bottom according to some numerical measure of strength such as approval score, average rank, median rank, average rating, etc. This can be considered to be a seed for the next sorting stage.
  • The list is then sorted by swapping adjacent alternatives that are "out of order" pairwise, until each alternative pairwise defeats or ties the alternative immediately below it on the list.
  • The winner is the candidate that ends up at the top of the list.

All methods of this type satisfy the Condorcet Criterion because until the "beats all" alternative is at the top of the list, it will be out of pairwise order with the alternative above it.

In particular, all Pairwise Sorted Methods that Bubble sort the seeded list satisfy the following slight modification of the Condorcet Criterion:

The winner is the lowest seeded candidate who, when compared in turn with each of the other higher-seeded candidates, is preferred over the other candidate.

In fact, all of these methods satisfy the Generalized Condorcet Criterion since the Smith set will be sorted above all non-Smith alternatives. They also produce a Smith set ranking of the candidates, since a candidate in the n-th Smith set will always be sorted above any candidates in lower Smith sets, since no candidate in a lower Smith set can pairwise beat or tie a candidate in a higher Smith set (by definition).

In other fields, the pairwise sorting stage is known as Local Kemenization. See, for example, Rank Aggregation Methods for the Web.

One nice by-product of local Kemenization is that it gives a "social ordering" of the alternatives: no matter the seed order, in the final order each alternative will defeat the alternative beneath it, so that the order itself provides a "beatpath" from winner to the lowest loser.

If there are no cycles in the pairwise relation, then any of these methods, no matter the seed order, and no matter the sort algorithm, will yield the same final order of the alternatives, namely the unambiguous pairwise order itself.

Otherwise both the seed order and the sort algorithm can affect the outcome. Approval Seeded Bubble Sort does not always yield the same winner as Approval Seeded Sink Sort.

Among pairwise sorted methods that have been suggested on the election-methods mailing list are

  • Pairwise Sorted Approval: Use total Approval score in descending order for initial seed. Bubble sort the list. (Bubble sort moves up the highest remaining out-of-order alternative first.)
  • Pairwise Sorted Borda: Use total Borda score in descending order for initial seed.
  • Approval Sorted Margins. Use total Approval score in descending order for initial seed. For subsequent pairwise sort, repeat until all pairs are ordered pairwise:
    • Search through the list for pairs that are out of order pairwise.
    • Of these, reverse the pair with the least difference in approval.
  • Score Sorted Margins. Use total Score sum in descending order for initial seed. Otherwise the same as Approval Sorted Margins except using the margin in score sum instead of approval.
  • Pairwise Sorted Dyadic Ballots. Initial Approval seeding, followed by multiple pairwise sorts using auxiliary dyadic pairwise matrices. See the page for more info.