[EM] Approval from rankings

[Forest Simmons]

As Bart and Richard have pointed out, approval ballots cannot always be
inferred from ranked preference ballots without knowing the relative
strengths of preference as well as horse race information from the polls.

Approval ballots and preference ballots contain overlapping information
but each contains some information not contained in the other.

However, suppose that instead of looking at approval of individual
candidates, we focus on approval of rankings.

Suppose we are counting a ballot with order ABC and we want to know if
this voter would approve the ranking CBA.

Since the two orders are diametrically opposed (at maximum distance apart
in the metric that counts neighbor swaps required to convert one into the
other) we can be assured that this voter does not approve of the CBA
ranking.

Let's say that two rankings more or less agree if they are closer together
than the reverse of one of them is to the other (unreversed).

Here's a method based on this idea:

The method output is the ranking that more or less agrees with the
greatest number of ranked ballots.

[end of description of method]

Example:

4 ABC
3 BCA
2 CAB

ABC more or less agrees with only 4 ballots.
BCA more or less agrees with only 3 ballots.
CAB more or less agrees with only 2 ballots.
CBA  """""""""""""""""""""""""""" 5 ballots.
ACB  """""""""""""""""""""""""""" 6 ballots.
BAC  """""""""""""""""""""""""""" 7 ballots.

So BAC is the method output.

Is there a clever way to efficiently compute the method winner for large
numbers of candidates?

Note in this example that if we bubble sort (i.e. "locally Kemenize") BAC
we get ABC, the Ranked Pairs order.

In general if we both sink sort and bubble sort the method order, and then
go with the order that yields the smaller Kemeny sum, the method is
converted into a Condorcet method satisfying reverse symmetry.

Who can find the simplest example that shows that this Condorcet method
does not always yield the Kemeny order?


----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em