[EM] evolving weighted pairwise proposal

[James Green-Armytage]

Okay folks, here again is another edition of my weighted pairwise
comparison proposal. The main development is that I've applied the
principle to CPO-STV. There's a detailed explanation of how it works in
part IV below. It's a bit trickier than I initially thought it would be,
but I think it makes sense the way I have it now. 

_______________________

The Weighted Pairwise Comparison Method
	by James Green-Armytage

I	The problem that this method addresses:
	Consider the following set of sincere preference rankings and ratings
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
	If you use a standard Condorcet method (such as minimax, ranked pairs,
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. This actually may 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 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. Beatpath and ranked pairs are my preferred choices.

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 0 > Kerry 0
22: Bush 100 > Kerry 0 > Dean 0
26: Dean 100 > Kerry 100 > Bush 0
1: Dean 100 > Bush 50 > Kerry 0
21: Kerry 100 > Dean 100 > Bush 0
4: Kerry 100 > Bush 50 > Dean 0

Pairwise comparisons (using rankings information)
	Bush	Dean	Kerry
Bush		52	49
Dean	48		53
Kerry	51	47

Defeats (using rankings information)
Bush --> Dean
Dean --> Kerry
Kerry --> Bush

Magnitude of defeats (using ratings information)
Bush --> Dean
	(26x(100-0)) + (22x(100-0)) + (4x(50-0)) = 5000
Dean --> Kerry
	(26x(100-100)) + (26x(100-100)) + (1x(100-0)) = 100
Kerry --> Bush
	(26x(100-0)) + (21x(100-0)) + (4x(100-50)) = 4900

Completion by minimax
1. No unbeaten candidates
2. Drop defeat of least magnitude, Dean --100--> Kerry 
3. Kerry is unbeaten

Completion by beatpath
beatpath Bush-->Dean:	Bush--5000-->Dean: 5000
beatpath Dean-->Bush:	Dean--100-->Kerry--4900-->Bush: 100
	Bush has a beatpath victory over Dean.
beatpath Bush --> Kerry:	Bush --5000--> Dean --100--> Kerry: 100
beatpath Kerry --> Bush:	Kerry --4900--> Bush: 4900
	Kerry has a beatpath victory over Bush.
beatpath Dean --> Kerry:	Dean --100--> Kerry: 100
beatpath Kerry --> Dean:	Kerry --4900--> Bush --5000--> Dean: 4900
	Kerry has a beatpath victory over Dean.
	Kerry is a beatpath winner. Complete ordering is Kerry-->Bush-->Dean.

Completion by ranked pairs
5000: Bush-->Dean	keep
4900: Kerry-->Bush	keep
[100: Dean-->Kerry]	skip (would cause a cycle, Bush-->Dean-->Kerry-->Bush)
	Kept defeats produce ordering Kerry-->Bush-->Dean.


IV	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
]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
is10685.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 maximize 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.


V	Variations on the primary proposal:
	Returning to the single-winner realm, here are two alternate versions of
the proposal which involve different ballot structures. I consider the
primary proposal to be superior, and I only include these for the sake of
completeness.

V.1	A variation using approval cutoffs:
Ballots:
Ranked ballots with approval cutoff, that is, a single line that can be
drawn in any ranking gap (but only one), which indicates that you approve
of those above the line, but not those below it.

Tally:
1. Pairwise tally using the ranked ballots. Elect the Condorcet winner if
one exists.
	If there is a majority rule cycle:
2. Determine the direction of the defeats by using the rankings for a
pairwise comparison tally.
3. Determine the strength of the defeats as follows: For a given defeat A
over B, the magnitude of the defeat is defined by the number of voters who
place A above their approval cutoff and B below their approval cutoff.
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.

Comments:
	I prefer the primary version of the proposal to the approval cutoff
variation.The only advantage of the latter is that it uses somewhat
simpler ballots.

V.2	A variation based on ratings gaps rather than full cardinal ratings:
	In this variation, the ballots would be different. One would rank the
candidates as before, but instead of ratings them from 0 to 100, one would
give a point value to each rankings gap. There would be a limited range of
point values allowed, e.g. 0 to 10.
	Ratings differentials would have to be calculated differently in this
variation.For example, let's imagine a ballot marked as follows:
	A>0>B>2>C>8>D>10>E
	The ratings differential between A and E would not be the sum of the gaps
between A and E, as in the primary version of the proposal. Instead, it
would be defined as the largest gap between A and E, in this case, 10.
Likewise, the differential between D and E would be 10, the differential
between B and D would be 8, and so on.
	This"greatest gap"method of calculation becomes necessary when you are
placing a limit on single ratings gaps but not a limit on the sum of
ratings gaps, as in the primary proposal.

	Comments:
	This variation is closer to versions of Condorcet that only use ranked
ballots,with the added feature that voters are able to de-emphasize
specific preferences in the event of a cycle. At present, I prefer the
primary version of the proposal. Looking at the example above, it seems
counter-intuitive that the ratings differential between A and E should be
no greater than the differential between D and E.

__________________________
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.