[EM] Second (and higher)-order methods?

[Kristofer Munsterhjelm]

On 04/30/2012 11:11 PM, Paul Kislanko wrote:
> I always thought the “Condorcet is like a round-robin athletic
> tournament” analogy was weak, because individual voters don’t get to go
> through the round-robin and make their pairwise preferences explicit.
> (As a voter, I’d find a “better/worse” pairwise choice for all pairs
> easier than filling out a ranked ballot, but that just may be because
> I’ve been making pairwise choices between the /ophthalmologist’s//
> /lenses since I was six.) N x (N-1) “A or B” choices is an easier way to
> fill out a ballot than “rank A1,A2,A3…” so no matter what method you use
> to translate my ranked ballot into pairwise comparisons I have no way to
> know if you counted my A<>B preferences the way I would have.

If your preferences are transitive, you don't even need N * (N-1) - O(n 
log n) will suffice. Just reduce from computer sorting by having the 
sorting algorithm ask you whether you prefer A to B whenever it would do 
a comparison between A and B :-)

> Now, I don’t think it’s a coincidence that JUST looking at PM^2 gives
> the same winner (E) as Schultze does, since it’s counting the x->y->z
> chains, giving extra credit to x >> z based upon x’s wins over
> alternatives that themselves have {}->z wins, and that’s explicitly part
> of the motivation for Schultze.
>
> But *if* that is equivalent to Schultze (I’ll leave that test to people
> who know better than I how it works) I find it more cosmetically
> appealing than the Schultze definition.

I don't think it is equivalent to Schulze, because Schulze considers 
paths of lengths up to the number of candidates. Instead, it sounds like 
PM^2 would pick an uncovered candidate (rather like Copeland, which is 
also used in sports).

If I'm right, then the Condorcet matrix corresponding to

40 D>B>C>A
30 A>B>C>D
30 C>A>D>B

should elect someone other than D. River, RP, and Schulze all elect D, 
but D is covered by A.

> There’s no “eliminate candidate based upon…” which has always rubbed me
> the wrong way – too IRVish. All ballots and all alternatives are
> directly involved in the final count.

One can describe Schulze without having to refer to eliminations, too. I 
think this explanation is correct (if it isn't, Schulze, correct me):

- Candidate X beats Y if more voters prefer X to Y than vice versa. The 
magnitude of this direct victory is the number of voters who prefer X to Y.

- X indirectly beats Y by a magnitude of no less than p if there exists 
a sequence of candidates beginning in X and ending in Y so that every 
candidate beats the one next in the sequence by at least magnitude p.

- The magnitude of X's indirect victory over Y is equal to the greatest 
value of p for which the above is true. If no such sequence exists no 
matter p, the magnitude of X's indirect victory is zero.

- X is a winner (or a tied winner) if no other candidate has a greater 
magnitude of indirect victory against X than X has against that other 
candidate.