Definition of pairwise (was Re: Reply on EM to Mike's...)
Steve Eppley
seppley at alumni.caltech.edu
Tue Apr 9 18:22:59 PDT 1996
Bruce Anderson wrote:
[snip]
>Let me suggest two quite different possible definitions.
>
>DEFINITION 1: Let p(x,y) be the number of voters who rank x over
>y, and let q(x,y) be the sum of the number of voters who rank X as
>tied with y plus the number of voters who do not explicitly rank
>either x or y, and let p and q be the corresponding arrays of
>values of p(x,y) and q(x,y). Then a ranked-ballot single-winner
>voting method is a "pairwise method" if and only if its set of
>winners can be calculated from the values in p and q.
>
>DEFINITION 2: A ranked-ballot single-winner voting method is a
>"pairwise method" if and only if it satisfies the Condorcet
>(winner) criterion.
>
>Is it either one of these, or is it something else?
I haven't encountered Def1 before, and its properties looks
sufficiently nonobvious to me that I can't say offhand whether it's
a good definition of pairwise. Therefore I conclude that for our
purposes it's not. (Just kidding :-) I think it captures the
relevant properties, and is much better than Def2.
There's some ambiguity in the definition of q(x,y) where Bruce uses
the phrase "either...or". Consider the truncated ballot {A}. This
voter hasn't explicitly ranked B. So is (A,B) an item for p or for
q, or both? It looks like both, the way it's worded. Shouldn't it
instead say "both unranked"?
By Condorcet criterion in Def2, I assume you mean that if one
candidate beats all the others pairwise, then this candidate is the
winner. I don't think this makes for a good definition: I think the
definition shouldn't be based on an emergent property but on the
common portion of the tallying algorithm.
Here's what I think is the common portion: the tallying algorithms
treat the voter's ballot {A,B,C,...} as a compact expression of
{A>B, A>C, B>C, ...} and sum these pairvotes. For each pair
Ci and Cj of candidates, they calculate sum(Ci>Cj) - sum(Cj>Ci) and
proceed from there.
To be complete, I should allow for equal rankings (Bruce's q(x,y)
term in Def1), but I'm pressed for time.
I've gone beyond Def1 and specified the basic portion of the
calculation which sums the votes. Perhaps this unnecessarily rules
out other methods which deserve to be called pairwise; if someone
proposes one we can wrestle for it two falls out of three.
All the methods which share that portion of the algorithm and which
I've seen proposed *so far* do elect the candidate which beats all
others, if there is such a candidate. But that's because other
pairwise methods which I haven't looked at have been pruned away
because they stink. For example, I'd say a method which follows
the above algorithm, and then declares the winner to be the biggest
pairwise loser, is a pairwise method. This would be a horrible
method, and not meet Bruce's Def2.
I note Mike O's reply to Bruce's question about pairwise definitions,
in which Mike says he prefers that any method which doesn't elect the
beats-all-others candidate should not be considered to be a pairwise
method. As I say above, I'd prefer to consider such a method to be a
terrible pairwise method. So at the moment Mike and I have a minor
difference of opinion. If it matters, I'd be happy to go along with
the group view if we can determine it. Perhaps Bruce will explain
why he thinks it matters, since no one has proposed a method which
Mike's definition and my definition would disagree on.
--Steve
More information about the Election-Methods
mailing list