[EM] (3) EM: VoteFair/Kemeny-Young: Steve's 3rd dialogue with Kristofer and Richard

Tue Oct 6 07:10:00 PDT 2015

On 10/01/2015 08:16 AM, steve bosworth wrote:
>  
> 
> Hi Kristofer and Richard,
> 
>  
> 
> Richard Fobes says that his VoteFair popularity ranking method is just
> another name for the Condorcet-Kemeny or Kemeny-Young method. 
> Accordingly, Richard’s relevant pages in his book (Ending the Hidden
> Unfairness…) are basically the same as the relevant part of the
> ‘Kemeny-Young’ Wikipedia article.
> 
> Still, I have a question about the way these articles explain how the
> ranked alternatives are to be scored in order to find the winner.  The
> ‘Kemeny-Young’ Wikipedia article offers the follow:

[snip]

> S:  My question is, why could we not always find the winning sequence
> without have to score /every possible sequence/ as illustrated above? 
> Why not simply add how many times the 100 voters have preferred each
> alternative?  At least in this example, the same winning sequence would
> have been discovered in this way:
> 
>  1. Roland   200
>  2. Elliot      150
>  3. Selden    130
>  4. Meredith 110

Because it doesn't hold in every case. Kemeny is close to sum of
victories because it seeks to find an ordering

X1 > X2 > ... > Xn

so that the sum of
(X1 > X2) + (X1 > X3) + ... + (X1 > Xn) +
(X2 > X3) + (X2 > X4) + ... + (X2 > Xn) +
... +
(Xn-1 > Xn)

is maximized.

When there's no cycle, this is the same as sum of victories. However, if
there is a cycle, Kemeny breaks the cycle in the way that maximizes the
sum above. Sum of victories takes the sum over both sides of the cycle,
and that may alter the outcome.

Here's an example:

6: A > C > B
4: B > A > C
1: C > A > B
4: C > B > A

The magnitudes of the pairwise matchups are:

A>B:  7
A>C: 10
B>A:  8
B>C:  4
C>A:  5
C>B: 11

The majorities are:

A>C: 10
B>A:  8
C>B: 11

If we use wv (i.e. consider only majorities), then sum of victories gives:
A's score: 10
B's score: 8
C's score: 11

so its outcome is C>A>B.

However, Kemeny isn't permitted to consider both sides of a cycle, so if
we check the score for C>A>B along with another possible ordering...

Kemeny:
C>A>B: (C>A) + (C>B) + (A>B) = 0 + 11 + 0 = 11
A>C>B: (A>C) + (A>B) + (C>B) = 10 + 0 + 11 = 21

so A>C>B is a better Kemeny ordering. (Unless there's a bug in my voting
simulator, it is in fact the best Kemeny ordering.) Pretty much every
Condorcet method gives the win to A for this example - see
http://www.cs.wustl.edu/~legrand/rbvote/calc.html.

It's possible to construct similar examples if we consider every
pairwise result (not just majorities), but I suspect sum of victories
(sum of pairwise matchups) would in that case fail the Condorcet
criterion outright. But if you'd like to check anyway, try

5: A > B > C
2: B > A > C
5: C > A > B
3: C > B > A

The best Kemeny ordering is C>A>B but sum of pairwise matchups gives A>C>B.

> My second question responds to Kristofer’s answer in our 4^th [EM]
> dialogue. He suggested that ‘Ranked Pairs/MAM’{i.e. maximize affirmed
> majorities} is  ‘a simple yet good Condorcet method, how about [1]? It
> works like this:
>  1. Sort all the pairwise contests in order of strongest to weakest.
>  Discard those that are weaker than a majority.
>  2. Go down the list and lock in a pairwise contest unless it contradicts
>  a contest you locked in earlier[2].
>  3. Once you're done, reassemble the pairwise contests into a ranking.
>  The candidate that is ranked first on it wins.
>  
>  Some additional details are required for breaking ties, but I've left
>  those out here.’
> S:  Is MAM significantly different from Kemeny-Young/VoteFair?  

Yes. RP/MAM passes independence of clones whereas Kemeny does not. It
does this because RP/MAM uses maximum instead of addition.

Consider a situation where Kemeny gives the same result as sum of
victories. Then there's a vote splitting problem: if A beats B, A might
go from losing to winning if B is cloned because A's victory against B
counts multiple times. The Kemeny vote-splitting example on the
Wikipedia page about independence of clones works in a similar way.

On the other hand, the Ranked Pairs mechanism doesn't have this problem.
Suppose C beats A (i.e. C>A). If A>B is locked before C>A before the
cloning, then no matter how many clones you add, A>Bk will be locked
before C>A is (where Bk is some clone) and this prevents Bk>A from being
locked later on.

Kemeny has no problem summing up the margins of victory of contests, and
that makes it possible to make some contests weigh more heavily than
others by adding clones. However, the Ranked Pairs mechanism takes the
strongest victory and in essence breaks the tie (among all orderings
consistent with the strongest victory) with the next strongest victory
and so on down (skipping contradictions). And since at least one clone's
relative position is locked when the original would have been, the
clones can only break ties consistent with the social ordering of the
first clone.

On the other hand, Kemeny passes reinforcement while neither RP nor MAM
does so. Reinforcement states that if you have the same social ordering
(ranking by the method) in every district and you combine the ballots to
get a nationwide result, then the nationwide social ordering will be the
same as that of the districts. Kemeny is the only Condorcet method that
passes that criterion.

By the logic above, I would imagine that judging by minimal sum of
defeats (same as maximal sum of victories when ballots are complete),
you'd get

Kemeny > MAM > River+ > Beatpath,

i.e. that Kemeny is closest to what sum-of-defeats provides. But from a
clone perspective, it's *too* close to sum-of-defeats.

In the Wikipedia clone example, MAM locks

B1 > B2, B1 > B3, B2 > B3
then B1 > C, B2 > C, B3 > C
and C>A, producing the ordering
B1 > B2 > B3 > C > A,
hence avoiding the clone problem.

The locking nature of RP/MAM also makes it easier to reason about RP/MAM
than about Kemeny. If you pick, say, A>B in Kemeny and there's a cycle
A>B>C>A, that might block a later path through C>B where, even though
A>B is stronger than C>B, the best path passing through C>B might give
you a higher score than the best path that passes through A>B. It
becomes rather like a puzzle where earlier decisions block off later
ones. On the other hand, when you do RP/MAM, it's easy: if A>B is
stronger than C>B, you affirm A>B before C>B, end of story, no lookahead
required. The only potential for needing to look ahead is if there's a
tie involving a cycle, but RP/MAM breaks that by random ballot (well,
random voter hierarchy) instead of doing any of that lookahead.