Weighted Pairwise Comparison

If you use minimax, ranked pairs, or beatpath, with winning votes or margins, and everyone votes sincerely, then Bush will win. The problem with this isn’t just that Kerry has a (very slightly) higher utility score. The problem is that the 26 Dean > Kerry > Bush voters consider the Kerry --> Bush defeat to be much more valuable than the Dean --> Kerry defeat, and many of them would probably be willing to change their votes to Dean = Kerry > Bush, if given an opportunity after learning the results. Anxiety about this kind of cycle may actually create a subtle barrier against the entry of additional candidates in some situations.

Again, there is nothing strategically underhanded about this result; all of the voters were being good sports and voting out all of their sincere preferences. The problem is that some preferences are more important to voters than others, and a straight ranking ballot does not give voters an opportunity to express the relative strength of their preferences.

Hence, it seems that an ideal voting method would go beyond preference rankings to incorporate cardinal ratings information. But what is the best way to integrate this information into a Condorcet-efficient method? Simply running an ordinary pairwise tally and then falling back on the sum of cardinal ratings scores in the event of a majority rule cycle seems to be unsatisfactory. In the event of a cycle too much of the ranking information would be lost, and in many ways it would be equivalent to starting over from scratch with cardinal ratings instead of Condorcet. Cardinal ratings is problematic for known reasons, such as the strong strategic incentive for compressing preferences.

I think that a better method would be one that would integrate the ratings data more carefully into the process of pairwise comparison. That is the goal of the method which I describe here.

II The method:

Ballots:

1. Ranked ballot. Equal rankings are allowed.

2. Ratings ballot. e.g. 0-100, whole numbers only. Equal ratings allowed. Note: You can give two candidates equal ratings while still giving them unequal rankings. However, if you give one candidate a higher rating than another, then you must also give the higher-rated candidate a higher ranking.

Tally:

1. Pairwise tally, using the ranked ballots only. Elect the Condorcet winner if one exists.

If no Condorcet winner exists:

2. Determine the direction of the defeats by using the ranked ballots for a pairwise comparison tally.

3. Determine the strength of the defeats by finding the weighted magnitude as follows. We’ll say that the particular defeat we’re considering is candidate A beating candidate B. For each voter who ranks A over B, and *only* for voters who rank A over B, subtract their rating of B from their rating of A, to get the marginal utility. The sum of these winning marginal utilities is the total weighted magnitude of the defeat. (Note that voters who rank B over A, or rank them equally, do not contribute to the weighted magnitude; hence it is never negative.)

4. Now that the directions of the pairwise defeats have been determined (in step 2) and the strength of the defeats have been determined (in step 3), you can choose from a variety of Condorcet completion methods to determine the winner. Ranked pairs, beatpath, and the river method are the most promising alternatives.

Additional provisions:

1. There is one situation in which a defeat with lesser weighted magnitude is considered to be stronger than a defeat of greater weighted magnitude: If the winning side of one defeat constitutes a majority (of the valid vote), and the winning side of another defeat does not constitute a majority, then the majority defeat is necessarily considered to be stronger. Otherwise, the weighted magnitude is always the determining factor in relative defeat strength.

2. Once a Schwartz set has been established by the pairwise tally in step 2, it may be a good idea to maximize the voters' ratings differentials in scale between the candidates in the set. That is, to change each rating ballot such that the highest-rated Schwartz set candidate is at 100, the lowest-rated Schwartz set candidate is at 0, and the rating differentials between the Schwartz set candidate retain their original ratios. (For example, 50,20,10 would become 100,25,0.)

III Example:

26: Bush 100 > Dean 10 > Kerry 0

22: Bush 100 > Kerry 10 > Dean 0

26: Dean 100 > Kerry 90 > Bush 0

1: Dean 100 > Bush 50 > Kerry 0

21: Kerry 100 > Dean 90 > Bush 0

4: Kerry 100 > Bush 50 > Dean 0

Pairwise comparisons (using rankings information)

Bush > Dean : 52 > 48

Bush < Kerry : 49 < 51

Dean > Kerry : 53 > 47

Magnitude of defeats (using ratings information)

Bush --> Dean

(26x(100-10)) + (22x(100-0)) + (4x(50-0)) = 4740

Dean --> Kerry

(26x(10-0)) + (26x(100-90)) + (1x(100-0)) = 620

Kerry --> Bush

(26x(90-0)) + (21x(100-0)) + (4x(100-50)) = 4640

Completion by minimax

1. No unbeaten candidates

2. Drop defeat of least magnitude, Dean --620--> Kerry

3. Kerry is unbeaten

Completion by beatpath

beatpath Bush-->Dean: Bush--4740-->Dean: 4740

beatpath Dean-->Bush: Dean--620-->Kerry--4640-->Bush: 620

Bush has a beatpath victory over Dean.

beatpath Bush --> Kerry: Bush --4740--> Dean --620--> Kerry: 620

beatpath Kerry --> Bush: Kerry --4640--> Bush: 4640

Kerry has a beatpath victory over Bush.

beatpath Dean --> Kerry: Dean --620--> Kerry: 620

beatpath Kerry --> Dean: Kerry --4640--> Bush --4740--> Dean: 4640

Kerry has a beatpath victory over Dean.

Kerry is a beatpath winner. Complete ordering is Kerry-->Bush-->Dean.

Completion by ranked pairs

4740: Bush-->Dean keep

4640: Kerry-->Bush keep

[620: Dean-->Kerry] skip (would cause a cycle, Bush-->Dean-->Kerry-->Bush)

Kept defeats produce ordering Kerry-->Bush-->Dean.

IV Coping with strategic manipulation:

The primary purpose of the weighted pairwise method is to provide more meaningful solutions to majority rule cycles when sincere votes are cast. However, in addition to this, there is some reason to believe that weighted pairwise is actually less vulnerable to strategic manipulation than most other Condorcet-efficient methods. I will try to illustrate this using a few simple examples, which I believe can provide insight into a variety of more complicated situations. In these examples, there are two candidates A and B who are relatively similar to one another, and account for 53% of the first choice vote, and a candidate C who accounts for the remaining 47%.

Case 1.0, sincere preferences:

23: A>B>C

5: A>C>B

23: B>A>C

2: B>A>C

25: C>A>B

22: C>B>A

Pairwise comparisons:

A>B = 53>47

A>C = 51>49

B<C = 48<52

This example deals primarily with the possibility of strategic incursion by the voters who favor candidate C. If sincere votes are cast, A beats both B and C, while C beats B. However, those whose preferences are C>A>B have an opportunity to gain an advantage by insincerely voting C>B>A. If we are using a version of minimax that is based on margins, then the C>A>B voters can achieve them simply by truncating their ballot, effectively voting C>A=B. If 9 of them do this, we have

Case 1.1, altered preferences:

23: A>B>C

5: A>C>B

23: B>A>C

2: B>C>A

16: C>A>B

9: C>A=B (sincerely C>A>B)

22: C>B>A

Pairwise comparisons:

A<B = 44<47

A>C = 51>49

B<C = 48<52

The resolution to this cycle depends on whether we are focusing on margins or winning votes. The defeat of least margin is A-->C (51-49), but the defeat of least winning votes is B-->A (47-44). The latter defeat is artificial, and the former genuine. In general, margin-based versions allow a group of voters to change the result from a Condorcet winner to another candidate they prefer simply by truncating. In winning votes versions, it is necessary for voters to actually reverse preference orders to achieve this result. In this way, strategic manipulation is generally easier in margins-based versions. Therefore, for the rest of my analysis here I will focus on winning votes Condorcet, and compare this to the weighted pairwise method. (We can assume that the completion method is minimax, since it does not differ from beatpath or ranked pairs in three-candidate examples.)

So, using winning votes Condorcet, C>A>B voters can gain an advantage from case 1.0 by reversing their preferences and voting C>B>A. For example...

Case 1.2, altered preferences:

23: A>B>C

5: A>C>B

23: B>A>C

2: B>C>A

19: C>A>B

28: C>B>A (6 of these are sincerely C>A>B)

Pairwise comparisons:

A<B = 47>53

A>C = 51>49

B<C = 48<52

Now, the weakest defeat is A-->C (51-49), and dropping that leads to the election of C. As it stands the strategy has been successful. Now, if the method is winning votes Condorcet, and it is suspected ahead of time that this strategy will be used, what can be done about it?

Voters who have already ranked A first cannot do anything more to help A; actually the only change they can make is for the 5 A>C>B voters to change their vote to A>C=B, which reverses the C-->B defeat and makes B a Condorcet winner. Of course, this change is not an improvement for an A>C>B voter. Hence the only possible value of the possibility is that perhaps if the A>C>B threaten to do this before the election, they might be able to deter the C>A>B voters from trying their strategy. However, such a counter-strategy is fraught with instability, since the different groups of voters have no way of knowing how the other groups will vote until it is too late to make a change.

Another possibility is for the B>A>C voters to compromise by voting B=A>C. If at least 3 of them do this, the B-->A defeat will be the weakest in the cycle, and will be dropped. The problem with this (counter)-strategy is that voters will not have perfect information before the election. Instead, they will face the possibility that B is a sincere winner (even a sincere Condorcet winner), and that voting B=A>C instead of B>A>C would be to needlessly hand the victory over to A. Hence the B>A>C voters will face a dilemma between voting B>A>C, leaving open an opportunity for the C voters to steal the election, and voting B=A>C, giving up the hope of getting their first choice elected.

However, when the weighted pairwise method is used instead, it seems that this dilemma can be avoided. In many cases, I think that the initial strategy of the C>A>B voters switching to C>B>A wouldn’t even be effective in the first place; hence counter-strategy would be unnecessary. That is, going with the assumption that candidates A and B are relatively similar, it is likely that the ratings gaps between A and B will be relatively small, and the ratings gaps between {A, B} and C should be relatively large. For example,

Case 1.0 revisited, sincere preferences, with ratings exaggerating the largest sincere utility gap:

23: A 100 > B 100 > C 0

5: A 100 > C 0 > B 0

23: B 100 > A 100 > C 0

2: B 100 > C 0 > A 0

25: C 100 > A 0 > B 0

22: C 100 > B 0 > A 0

Pairwise comparisons, with weighted magnitude:

A>B = 53>47, 500

A>C = 51>49, 5100

B<C = 48<52, 4700

Again, A is a Condorcet winner, and C beats B. The C voters cannot change the fact that A beats C. Also, even if they reversed the A>B defeat to make a cycle, they couldn’t do anything to get the A-->C defeat anywhere close to being the weakest in terms of weighted magnitude. Hence, no matter what they do, C won’t win. The C>B>A voters can’t do anything to change the result, and although the C>A>B voters could cause a cycle by voting C>B>A, there’s no reason that they would want to do this, since the cycle would be very unlikely to resolve in favor of C, likely to resolve in favor of A, and possible that it would resolve in favor of their last choice, B. The latter would happen if the C>B>A voters put most of their ratings gaps between B and A. So, it is nice to see that the C voters who are needed to cause the cycle are precisely the ones who have the least to gain from it. Also, of course, the B>A>C voters as a group can’t do anything to get a better result, since voting B>C>A will simply make C a Condorcet winner instead of A. The B>C>A voters cannot change anything either, since they are already voting in retrograde to the full transitive ordering of A>C>B. And of course, none of the A>B>C or A>C>B voters are interested in changing the result. So, this is a relatively stable outcome when weighted pairwise is used.

In general, I think that in weighted pairwise, when there is one candidate who is a sincere winner, it is very hard to steal the election in favor of another candidate, when those who favored the sincere winner over the artificial winner put a large ratings differential between the two candidates. To be more specific, if any defeat in a three-candidate cycle has more than 1/3 of the highest possible weighted magnitude, it can’t be dropped. For example, there are 100 voters and the ratings ballots are 0-100, and a given defeat of candidate Y by candidate X has a weighted magnitude of 3334, candidate Y cannot win. If a majority (1/2+) prefers X over Y, and they assign at least 2/3 of their rating differentials to the gap between X and Y, then you already have the weight needed to assure that Y will not win.

However, what about strategic manipulation by supporters of a candidate who is relatively similar to the sincere winner? This question brings us to...

Case 2.0, sincere preferences, with ratings exaggerating the largest sincere utility gap:

28: A 100 > B 100 > C 0

25: B 100 > A 100 > C 0

24: C 100 > A 0 > B 0

23: C 100 > B 0 > A 0

Case 2 is pretty similar to case 1, the only major difference being that in case 2, B has a pairwise win against C rather than the other way around. A is again a sincere Condorcet winner, but in this case there is a possibility of strategic incursion by the B voters. Using winning votes Condorcet, some B>A>C voters can reverse their later preferences to get this result.

Case 2.1, altered preferences:

28: A>B>C

18: B>A>C

7: B>C>A (sincerely B>A>C)

24: C>A>B

23: C>B>A

Pairwise comparisons:

A>B = 52>48

A<C = 46<54

B>C = 53>47

Now the A-->B defeat is dropped and B wins instead of A, due to his underhanded supporters. How can the other voters respond to this in winning votes? As in case 1, although the A voters can’t do anything further to elect A, they can threaten to punish the B voters by truncating. If the B voters order-reverse as above, and at least 2 of the A>B>C voters truncate (vote A>B=C instead), then C will win. So if the A voters threaten to truncate, the B voters may repent and vote sincerely. However, again, this is a fundamentally messy and uncertain counter-strategy. What if the a spokesman for the A voters threatens to truncate, and a spokesman for the B voters promise to vote sincerely, so the A camp agrees not to truncate... but then on election day a contingent of B voters take matters into their own hands and truncate anyway, stealing the election for B after all? That’s bad news. Or, what if a group of A voters decides to go ahead and truncate in case the B voters try a reversal strategy, and a group of B voters truncate in case B is the Condorcet winner but the A voters try a reversal strategy? If a small fraction of voters from each camp truncates, then they will hand the election directly over to C, which is the last thing they want. The C>A>B voters could take it on themselves to settle the issue by voting C=A>B and ensuring A’s victory, but they probably won’t want to do that if they’re not yet sure who will win the sincere A-B pairwise contest. So there’s a fair amount of risk-taking and guesswork, with a chance for disaster if people guess wrong.

Can the weighted pairwise method improve the situation at all? Well, a bit, perhaps. It might be more necessary to use conscious counter-strategy than it was in case 1, but the counter-strategies that can be applied is arguably less risky than their counterparts in the winning votes system.

First, the “deterrent” strategy used by the A supporters in winning votes Condorcet. In weighted pairwise, they can get a similar effect by maintaining sincere rankings but altering their ratings information to increase the gap between A and B, that is, voting A 100 > B 0 > C 0 instead of A 100 > B 100 > C 0. Hence, they decrease the chances that an A-->B defeat will be dropped, thereby decreasing the incentive for the B voters to create a cycle. This counter-strategy is somewhat more stable than the deterrence-by-truncation strategy. That is, even if lots of A voters and lots of B voters mistakenly employ it in the absence of actual order-reversal strategy, it doesn’t affect the direction of the pairwise defeats. Hence, in this example, it would have no impact, since C is a Condorcet loser and hence none of the C voters have an order-reversal incentive.

Second, the “compromising” strategy used by the C>A>B voters in winning votes Condorcet, voting C=A>B in order to protect A. In weighted pairwise, they can get a similar effect by voting C 100 > A 100 > B 0 instead of C 100 > A 0 > B 0. Thus, if some of the B>A>C voters switch to B>C>A, creating a false A-->B-->C-->A cycle, this strengthens the A-->B defeat, and increases the chance that A will win rather than B. Again, this strategy is less likely to be regretted than the equal-ranking compromise in winning votes Condorcet, since it has no effect on the direction of the A-C pairwise comparison.

Of course, none of this is to say that the weighted pairwise method is totally invulnerable to strategic manipulation, or that strategy will never lead to an unfair or unstable outcome. However, I do think that it is marginally less vulnerable to strategy than most other Condorcet methods, whether based on margins or winning votes. In the unlikely event that a group of voters will be able to manipulate the result to steal the election for their favorite candidate, there is a significant limit as to how different that candidate can be from the sincere winner. Also, when people anticipate strategy and engage in counter-strategy, there are effective counter-strategies available in the weighted pairwise method which are more stable and less risky than their counterparts in margins and winning votes.

V Application to CPO-STV:

I believe that this principle can also be applied to CPO-STV (comparison of pairs of outcomes by single transferable vote, see http://www.econ.vt.edu/tideman/rmt.pdf), although the application is a bit tricky. Let me illustrate my solution with an example.

3 seats to be decided. 400 voters. Newland-Britton quota = 400/(3+1) = 100 votes.

Ballots:

150:A 100>B 100>C 100>X 0>Y 0>Z 0

60:A 100>B 90>C 80>X 0>Y 0>Z 0

190:X 100>Y 90>Z 80>A 0>B 0>C 0

This is a good example of how CPO-STV achieves proportionality. Although a clear majority (210/400) would prefer the outcome {ABC} over any other outcome, the weight of their votes is almost entirely absorbed by the election of A and B, so that X wins the remaining seat rather than C. Hence, CPO-STV is not simply majority rule Condorcet voting on different outcomes, and this spirit of proportionality should be incorporated in our system of calculating winning marginal utilities between outcome pairs.

I'll just do one comparison of outcome pairs, and I'll show how to calculate the winning marginal utility for the defeat that results. The outcomes I want to compare are {AXB} and {AXY}. This can be seen as the key comparison, since it's obvious that the ABC faction and the XYZ faction will each get at one seat, it's obvious that the first seats that the factions get will be for A and X (the universal first choices among those factions). So the main question is who will get the more closely-contested third seat, B or Y.

First, the standard CPO-STV outcome comparison, to determine the direction of the defeat.

{AXB} vs. {AXY}

A X B Y

Initial count 210 190 0 0

Transfer -110 -90 +110 +90

Final count 100 100 110 90

{AXB} = 100 + 100 + 110 = 310

{AXY} = 100 + 100 + 90 = 290

So, we have learned that {AXB} beats {AXY}. Now we need to calculate the winning marginal utility of {AXB} over {AXY}.

Here's the key: the options A, B, X, and Y can be divided into common options and contested options. The division is specific to the outcomes being compared: common options are in both outcomes, and contested options are only in one outcome or another. In this particular outcome comparison, A and X are common options, and B and Y are contested options. (C and Z are neither... they have no impact on this outcome comparison.)

Now, when you get to the final count of the STV tally for a given outcome comparison, people have their votes invested in different places. Assuming that you are using a fractional transfer method of some sort, people may often have different fractions of their votes allocated to different candidates.

When calculating the winning marginal utility here, I propose that we look only at ballots, or the fractions thereof, that are invested in contested options. Note that while a given ballot may be invested partly in common options and partly in contested options, no ballot will be fractionally invested in more than one contested option, because if an option is contested, it does not transfer a surplus in CPO-STV. Hence, the fractions of a ballot invested in contested options will only weigh on one side or the other of an outcome comparison. The ballot fractions that weigh on the winning side are the ones that we will look at to determine the winning marginal utility.

With that said, the rest of the procedure should be fairly straightforward. It seems sensible enough to define the utility of the outcome for a voter as the sum of their rating of the different candidates in the outcome, and then to define the marginal utility as the difference between the utility of the outcomes being prepared.

Although it is impossible in the single winner version of weighted pairwise, in the CPO-STV version it is possible (although very unlikely) that the winning marginal utility will be a negative number. Even if this is true, however, the direction of the defeat is not overturned, although the weighted magnitude of the defeat is extremely low, and therefore the defeat is very likely to be dropped in the event of a top cycle among outcomes.

So, let's find the weighted magnitude of the {AXB}-->{AXY} defeat. Again, we already know that {AXB} beats {AXY}. We also know that A and X are common options, while B and Y are contested options for this comparison. So, we want to find out which ballot fractions are invested in contested options, and specifically, which ones are invested in B, since B is the only contested option in the winning outcome {AXB}.

Going back to the STV tally,

A X B Y

Initial count 210 190 0 0

Transfer -110 -90 +110 +90

Final count 100 100 110 90

we recall that A started out with 210 votes, and transferred a surplus with a weight of 110. Hence the votes which make their way to B were transferred at a fractional value of approximately .52. Likewise, X began with 190 votes, and transferred a weight of 90; hence the votes were transferred to Y at a fractional value of approximately .47.

Here, we are specifically interested in the 210 votes which were transferred to B at 52% value. Those votes were divided into two groups, which had the same ranking information but slightly different rating information. The actual size of the groups was 150 and 60, but the ballot fractions invested in the contested option B only represent 52% of the original totals. Hence, for the purpose of calculating the winning marginal utility, the weight of each ballot is reduced to 52%. The group of 150 now has a weight of 78.57, and the group of 60 now has a weight of 31.43. We can plug these in as the new multipliers, and calculate the winning marginal utilities by finding the difference between the utility for each outcome, as follows:

78.57:A 100>B 100>C 100>X 0>Y 0>Z 0

{AXB}= 100 +0 + 100 = 200

{AXY}= 100 + 0 + 0 = 100

{AXB}- {AXY} = 200 - 100 =100

31.43:A 100>B 90>C 80>X 0>Y 0>Z 0

{AXB}= 100 +0 + 90 = 190

{AXY}= 100 + 0 + 0 = 100

{AXB}- {AXY} = 190 - 100 =90

Now, to find the total winning marginal utility of {AXB} over {AXY}, all we have to do is to calculate (78.57)(100)+(31.43)(90) Our grand answer is 10685.7. That is, to sum up, {AXB} beats {AXY}, and the winning marginal utility is 10685.7

Of course, funnily enough, the winning marginal utilities are totally irrelevant in this particular example, because the outcome {AXB} beats all other outcomes. As in the single-winner case, winning marginal utility values only come into play when there is a top cycle among outcomes. I just chose this example because it was relatively simple and straightforward. Examples that involve top cycles in CPO-STV tend to be more complex.

Note: If desired, the ratings information on weighted CPO-STV could be maximized in scale to some degree. The ratings that are important are the ones for candidates who are in some of the Schwartz set outcomes but not all of them. You can have a rule that automatically maximizes the ratings differentials between these candidates on each ballot, such that the highest becomes 100, the lowest becomes 0, and the different gaps in between remain in their original ratios.

click here for variations on the primary proposal

click here to return to the main page

__________________________

The weighted pairwise comparison method was invented and first proposed by James Green-Armytage on June 8, 2004. The variations on weighted pairwise as presented in this paper were also invented by James Green-Armytage, that is, the application to CPO-STV (June 30, 2004), the approval cutoff variation (June 8, 2004), and the ratings gaps variation (June 19, 2004). Please cite the author when discussing these methods.