[EM] Optimally Sorted Pairwise Methods (AWP/ASM/AM/CWP)

[Araucaria Araucana]

A couple of weeks ago, Forest directed my attention a couple to
Approval Margins Sort / Approval Sorted Margins:

,----
| http://wiki.electorama.com/wiki/Approval_Sorted_Margins
| 
| (1) Seed the list using with total approval score in descending
|     order.
| 
| For subsequent pairwise sort, repeat until all pairs are ordered
| pairwise:
| 
| (2) Search through the list for pairs that are out of order pairwise.
| 
| (3) Of these, reverse the pair with the least difference in approval.
`----

I've been thinking about this type of method since then since I like
the minimization property.

I think a good name for this specific method would be 

  Pairwise Sorted Approval - Min(Approval Margin)

or PSA-Min(am) for short.  But I'm not sure that minimizing the
approval margin is the best thing to be doing.

It occurred to me (probably not originally, I imagine that Forest
discussed all of this 4 years ago) that you could choose any optimal
measure to order the pairwise exchanges.

For example, you could choose the out-of-order pair with maximum
winning votes (wv).  Replace the last step of the method with

(3) Of these, reverse the pair with greatest wv defeat strength.

Call this method PSA-Max(wv).

This method appears to be just as strong as wv Ranked Pairs, Beatpath
or River but it uses the much easier approval seed sort to avoid
ranking the pairs.

What's really interesting to me is that you could measure the step-3
defeat strength by James Green-Armytage's "strong preference" (a less
confusing term than approval weighting), to get PSA-Max(sp):

(3) Of these, reverse the pair with greatest strong preference.

Note that in my terminology, I use plain "pairwise-sorted" to imply
that the pairwise sorting is bubble sort.  But when I tack on a "Min"
or "Max", I mean that the pairwise sorting uses non-local optimization
of some measure.

Any of these optimally sorted pairwise techniques will, like the
bubble-sorted pairwise methods, produces a social ordering.

If Jobst is then looking for a subset of candidates to use for a
random ballot method, he could use the set of all candidates ordered
above the approval winner.  But this set could include cycles, as
mentioned in an earlier post.

I was also thinking that seeding with Bucklin (add in lower ranked
votes until one candidate has > 50% approval) could be interesting as
well, and the approval cutoff could be used to prevent lower-ranked
candidates from receiving points in successive Bucklin rounds.

I would still like to find some "Sieve of Eratosthenes"-like
interpretation, though. ;-)

Ted
-- 
araucaria dot araucana at gmail dot com