Definition of "Pairwise Method"

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

Definition of "Pairwise Method"

Craig Carey-2
Bruce (me) said:
<<"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?">>

Then Mike said:
<<"The following is an example of what I mean by "formulese", though not
a bad example of it, as formulese goes. Things that would be clear
in English can be made to sound complicated or involved when said
in formulese.
> 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.
No, because that definition doesn't say that any alternative which,
when compared separately to each one of the others, is ranked over it
by more voters than vice-versa shall be declared the winner.
But that omission is my fault, since I unintentionally left it out
of my definition too.
> DEFINITION 2:  A ranked-ballot single-winner voting method is a "pairwise
> method" if and only if it satisfies the Condorcet (winner) criterion.
That would be stretching it a little, since there's at least 1 Condorcet
Criterion method that doesn't explicitly do pairwise comparisons.
In informal brief language, a Pairwise method is a method that does
pairwise comparisons of what is ranked over what by how many voters,
and what beats what, and declares as winner any alternative that
beats everything else.
Maybe I should say it a little more carefully:
A Pairwise method is a method that, for pairs of candidates, A & B, counts
how many voters have ranked A over B, & how many have ranked B over A; and
which determines whether A is ranked over B by more voters than rank
B over A; and which gives the election to any alternative which, when
compared separately to each one of the other alternatives, is ranked
over it by more voters than vice-versa.
That definition doesn't say that each pair must be compared, because,
or course, an alternative that beats each of the others might be found
before all the pairs are compared.
This is what we've meant by Pairwise methods, though we didn't
explicitly state it.
> Is it either one of these, or is it something else?
The 1st definition is close, and needs only that addition about
picking as winner an alternative if it beats everything else.">>

Then Steve said:
<<"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.">>

Maybe I'm missing something, but it seems to be that Mike is saying that a
pairwise method is any method that satisfies both my definition-1 and my
definition-2; but that my definition-1 is too long and complicated and can be
said in a shorter and simpler way.  Conversely, Steve is saying that a pairwise
method is any method that satisfies just my definition-1; but that my
definition-1 is too simplistic and ambiguous and should be lengthened to more
fully explain the various possibilities.

I think that they are both correct in the following senses.

First, I think that it is quite reasonable and, in fact, useful to have multiple
ways of stating particular definitions, criteria, voting methods, etc..  These
ways could vary from "30-second sound bytes" that are, perhaps, quite imprecise,
but that do generally point in the right direction, through excruciatingly
detailed and unequivocally precise statements.

Second, I don't think that it is absolutely necessary to have an excruciatingly
detailed and unequivocally precise statement of things that are sufficiently
well defined (in writing) that no one, including "newcomers" just reading these
statements, sees any ambiguity in them.

Third, I think that it can be reasonable to only have vague, ambiguous, or
conflicting statements of some things if it is clearly stated and understood
that those things might well mean very different things to different yet
informed people.

What I personally find upsetting is the use of what I think are undefined terms
or imprecise or ambiguous statements that neither come with a warning that it is
realized that these terms and statements could be quite different things to
different readers, nor come with references to relatively precise and
unambiguous definitions of terms and corresponding statements.

I frequently read something that I think is insufficiently precise, but that
everyone else things is clear and unambiguous.  Some of these times, I just need
a slower step-by-step explanation in order to "see the light."  But occasionally
my confusion about the precise meaning is well founded.  I'd much rather go
"slow and sure" than talk past each other at high speed.

To address Steve's objection concerning ambiguity in my definition-1 above, let
me make it even more explicit as follows.

DEFINITION 1:  Let p(x,y) be the sum number of voters who explicitly rank x over
y plus the number of voters who explicitly rank x do not explicitly rank y, and
let q(x,y) be the sum of the number of voters who explicitly 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 using only the number of candidates, the
number of voters, and the values in p and q.

Steve:  Is this precise enough?

To address Mike's objection, let me replace my previous definition-2 with:

DEFINITION 2:  Let p(x,y) be the sum number of voters who explicitly rank x over
y plus the number of voters who explicitly rank x do not explicitly rank y, and
let q(x,y) be the sum of the number of voters who explicitly 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
both:  1) its set of winners can be calculated using only the number of
candidates, the number of voters, and the values in p and q, and  2) it
satisfies the Condorcet (winner) criterion.

Mike:  Is this an overly complicated but technically correct definition?

Steve says:

"...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."
and
"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."

I don't think it matters much whether "we" agree on one definition or the other,
or whether we agree to explicitly disagree here.  I slightly prefer the first
definition, basically for the same reason that Steve does.  Also, with the first
definition, Mike and always used the phrase "a pairwise method that satisfies
Condorcet's criterion" to specify the set of methods that he wants to define.  
However, I don't think that whether or not we happen to know if anyone "has
proposed a method which Mike's definition and my definition would disagree on"
is a good test.  Even if no one ever has, maybe someone will do so "tomorrow."  
In the particular case here, suppose a voting method computes its winners by
calculating f(i,j) = sum(Ci>Cj) - sum(Cj>Ci) and proceeds from there by
calculating JC(i) = "sum over j" of f(i,j), and then selects candidate i as a
winner if JC(i) >= JC(j) for every other candidate j.  For the obvious reason,
call this voting method the Jean-Charles voting method.  Then it certainly seems
to me that Jean-Charles's voting method satisfies Steve's definition and my
definition-1 of a pairwise method.

What do you (plural) think?

Bruce