Difference between revisions of "Pairwise Sorted Methods"

From Electowiki
Jump to: navigation, search
(Start the Pairwise Sorted Methods page)
 
m
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
Pairwise Sorted Methods all share these properties:
 
Pairwise Sorted Methods all share these properties:
* The list of candidates is first sorted top to bottom according to some metric.  This can be considered to be a seed for the next sorting stage.
+
* 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.
* Starting at the top of the list, each pair of candidates is processed in some way in accordance with their pairwise (one-to-one) contest.
+
* The list is then sorted by swapping adjacent alternatives that are "out of order" pairwise, until each alternative pairwise defeats the alternative immediately below it on the list.
 
* The winner is the candidate that ends up at the top of the list.
 
* The winner is the candidate that ends up at the top of the list.
  
Almost all methods of this type satisfy the [[Condorcet Criterion]] because a candidate that pairwise defeats every other candidate will eventually be bubble-sorted to 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 other fields, the pairwise sorting stage is known as Local Kemenization or Rank Aggregation.  See, for example, [http://www10.org/cdrom/papers/577/ Rank Aggregation Methods for the Web].
+
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.
  
One nice by-product of rank aggregation is that the initial seed order is acyclic --- any pairwise cycles that might exist are precluded from the final result.
+
In fact, all of these methods satisfy the Generalized Condorcet Criterion since the Smith set will be sorted above all non-Smith alternatives.
 +
 
 +
In other fields, the pairwise sorting stage is known as Local Kemenization.  See, for example, [http://www10.org/cdrom/papers/577/ 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
 
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.
+
* [[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 Approval]]:  Use total Borda score in descending order for initial seed.
+
* [[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:
 
* [[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 list for pairs that are out of order pairwise.   
+
** Search through the list for pairs that are out of order pairwise.   
** Reverse the pair with the least difference in approval.
+
** Of these, reverse the pair with the least difference in approval.
 +
* [[Pairwise Sorted Dyadic Ballots]].  Initial Approval seeding, followed by multiple pairwise sorts using auxiliary dyadic pairwise matrices.  See the page for more info.

Latest revision as of 15:00, 16 November 2016

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 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.

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.
  • Pairwise Sorted Dyadic Ballots. Initial Approval seeding, followed by multiple pairwise sorts using auxiliary dyadic pairwise matrices. See the page for more info.