[EM] Dyadic Weighted Pairwise ( was S/WPO )

[Forest Simmons]

On Tue, 22 Mar 2005, James Green-Armytage wrote:

>
> James G-A replying to Forest, on the subject of cardinal-weighted pairwise
> (CWP)...
>>
>> I've delayed bringing this up because I didn't want to dampen your
>> spirits; I think that Cardinal Pairwise suffers from a "bunching up" near
>> the extremes problem similar to straight CR, and that S/WPO and Approval
>> Weighted Pairwise avoid this problem.
>
> 	This doesn't dampen my spirits; you're not the first person to make this


I'm glad that you are not easily discouraged.  Most people are not 
persistent enough in following through on their good ideas.


> point. I've answered it before. First of all, I'm not fully convinced that
> this incentive for extreme ratings will be as strong as you say. (So far,
> no one has presented me with a proof that the incentive will even exist,
> given moderately incomplete information) Secondly (and much more
> importantly) even if there is a strong incentive for extreme ratings
> assignments, then the worst case scenario is that it will reduce to AWP.


If all of the ratings go to the extremes of zero and 100, then the ordinal 
information is lost.  Otherwise the strategic voter preserves the most 
important ordinal information by squeezing all of the important candidates 
into ratings of 0, 1, 99, and 100.

It may not be a serious problem in most elections, but you might like my 
suggestion anyway once you see it.

> Which is not bad at all. If CWP offers even a little bit more resolution
> than AWP, it can only be an improvement. Plus, a 0-100 scale is more
> intuitive to voters than an "approval cutoff", even though an approval
> cutoff is technically simpler.
>>
>> To get the additional resolution that you seek from Cardinal Pairwise you
>> should interpret your Cardinal Ratings ballots dyadically.
>
> 	How do you propose to do that?


Calculate the pairwise matrix M as usual from the ordinal information in 
the CR ballots.

Then for defeat strength purposes convert the ratings (by uniform 
stretching and shifting if necessary) to a scale of zero to 255 in the 
form of eight bit bytes:

               00000000 to 11111111.

Some minor rounding will be necessary if your original scale is one to 
ten, zero to one hundred, i.e. whenever the resolution is some non-integer 
power of two.

Now form a second pairwise matrix from each ballot as follows:

The entry in row i and column j of this matrix is ...

      zero if candidate i is rated below or equal to candidate j,

      else  2^(8-k)  when the binary rating of candidate i first differs
             from the the binary rating of candidate j in
             bit number k , counting from the left, i.e. the most
             significant end of the byte.

Sum these matrices over all ballots, and call the result M'.

[Divide the result by 255 in case the "one vote per person" folks get wind 
of the algorithm.]

If candidate i beats candidate j according to the pairwise matrix M, then 
the dyadic approval strength of the defeat is given by matrix M' in row i 
and column j.

The strongest effect is exerted by the left most bit.  This can be thought 
of as the approval bit.  The next bit has the next strongest effect, etc.

Most folks at first blush think that this is just CR in disguise, but it 
is not.

For example, suppose that the respective ratings for candidates i and j 
changed from 10000000 and 01111111 to 11111111 and 00000000.

In marginal pairwise this would really boost the strength of the defeat of 
i over j, but in "dyadic pairwise" it makes no difference in the strength 
of that defeat since in both cases they differ in the very first binary 
place.

Hence (as in Approval Weighted Pairwise) there is no incentive to 
artificially inflate the difference between the ratings of the two 
candidates (beyond getting them on opposite sides of the approval cutoff).

The same can be said at any level: if the respective ratings of i and j 
change from 11111000 and 11110111 to 11111111 and 11110000, it does not 
affect the defeat strength of i over j, even though the ratings move 
further apart, since they still first differ in the fifth bit from the 
left.

This preserves elbow room for the ordinal information, while preserving 
most of the relative strength information implicit in the cardinal 
ratings.

To understand this better consider the following ballot based on CR with 
resolution eight:

Candidate  Rating  Binary
   A         7       111
   B         6       110
   C         5       101
   D         4       100
   E         3       011
   F         2       010
   G         1       001
   H         0       000


Using the >, >>, >>> notation we could summarize this ballot as

           A>B>>C>D>>>E>F>>G>H.


The strongest preference is governed by the >>> relation, which can be 
thought of as the approval cutoff.

In this particular example, on each side of this strongest cutoff there is 
a >> relation, which refines the relative approval and disapproval within 
each of the two main approval classes.

On each side of the >> relation there is a > relation that further refines 
the expressed preferences.  Presumably the most important preferences are 
represented by the greatest number of >'s.

If we were to add the strengths of the relations separating two 
candidates, then we would get the difference in CR.

But instead of adding we just use the strength of the max strength 
relation separating the two candidates.  This is a good example of how 
replacing "sum" with "max" can reduce incentives for distortion of 
preference information.

[For another good example consider the use of the pairwise margins matrix 
for computing the Borda winner and the MinMax winner.]

The entries for this ballot's contribution to the usual pairwise matrix M
are

           0  1  1  1  1  1  1  1
           0  0  1  1  1  1  1  1
           0  0  0  1  1  1  1  1
           0  0  0  0  1  1  1  1
           0  0  0  0  0  1  1  1
           0  0  0  0  0  0  1  1
           0  0  0  0  0  0  0  1
           0  0  0  0  0  0  0  0



The entries in this ballot's contribution to the dyadic strength matrix M' 
are proportional to

          0  1  2  2  4  4  4  4
          0  0  2  2  4  4  4  4
          0  0  0  1  4  4  4  4
          0  0  0  0  4  4  4  4
          0  0  0  0  0  1  2  2
          0  0  0  0  0  0  2  2
          0  0  0  0  0  0  0  1
          0  0  0  0  0  0  0  0

Note that the strength of candidate D over E is the same as the strength 
of A over candidate H.

Similarly, the strength of F over G is the same as E over H.

In general the strength is determined solely by the length of the longest

               >>...>

relation straddled by the two candidates.

An interactive voting machine can elicit the dyadic approval information 
directly.  First it helps you sort the candidates into approved and 
disapproved bins, by asking which of them you find acceptable relative to 
the rest.

In this case, our voter put A,B,C, and D in the approved category, so 
the rest ended up in the disapproved category.

Then the machine asks you which of the approved ( A, B, C, and D in this 
case) you would still approve if the rest of the candidates ( E, F, G, and 
H in this case ) were eliminated.

Apparently our voter responded with A and B.  [She seems to like 
lexicographical order.]

Then which of these two does she prefer?

Then if A, B, C, and D were eliminated, which of E, F, G and H would she 
approve?

Etc.


If I haven't lost you by now, you have a better attention span than I do.

My Best,

Forest