Strategic Range and Approval  Voting in the Absence of A Priori Information

There has been a debate about strategic voting in the range voting community. There is also an ongoing debate about the relative merits of range voting vs approval voting. Approval voting is seen to some extent as a strategic form of range voting, but there doesn’t seem to be any agreement among proponents of approval voting as to where to draw the line between approved and non-approved candidates. Warren Smith has proven the following theorem: mean-based thresholding is the optimal range-voting strategy in the limit of a large number of other voters, each random independent full-range. Mean-based thresholding is a strategy in which a voter computes the mean of his sincere range ratings where the ratings are values between 0 and 1, and then votes approval style giving each candidate a 1 if his sincere rating is greater than the mean and a 0 if his sincere rating is less than the mean. Warren’s theorem and proof can be found here: 
Theorem: Mean-based thresholding is optimal range-voting strategy in the limit of a large number of other voters, each random independent full-range. 
Proof: In this limit, it should be clear that the optimal strategy is to choose the threshold to maximize the sum of across-threshold utility-pair-differences. What is not obvious, and what we shall now prove, is that this is the same thing as mean-based thresholding. 
Let there be A utilities below threshold and B above. Let their means be μA and μB respectively, and the mean of the entire utility-set is μ where (A+B)μ = AμA+BμB. Consider moving the threshold slightly so that the greatest below-threshold utility X becomes above-threshold. The amount by which the sum of across-threshold utility-pair-differences changes (additively) is 
Δ = (A-1) (B+1) [ (BμB+X)/(B+1) - (AμA-X)/(A-1) ] - A B (μB-μA) 
which after simplification is the same as 
Δ = (A+B)(X-μ). 
Notice that Δ is positive (i.e. the motion was good, according to the utility difference) if and only if μ<X (i.e. if and only if it was good according to the mean-based-thresholding criterion). 
The best situation is when no motion improves utility, and that happens when the threshold is exactly located at μ. Q.E.D. 

If a general strategy for range voting in the absence of a priori information about the candidates could be devised, this would have ramifications for stability of the outcome and also would cast further doubt on Arrow’s General Possibility Theorem for social choice.

In Mathematics and  Democracy, Steven J Brams  states: “ [With appproval voting] if [the voters] have no strong preference for one candidate, they can express this fact by voting for all candidates they find acceptable.” (p. 4) Brams further states: “Although AV encourages sincere voting, it does not altogether eliminate strategic calculations. Because approval of a less-preferred candidate can hurt a more-preferred approved candidate, the voter is still faced with the decision of where to draw the line between acceptable and unacceptable candidates. A rational voter will vote for a second choice if his or her first choice appears to be a long shot — as indicated, for example, by polls — but the voter's calculus and its effects on outcomes is not yet well understood for either AV or other voting procedures.”

We attempt to show that there is a rational procedure for strategic voting using a combination of range and approval voting. We devise a strategy for voting that maximizes the expected value of individual utility or satisfaction. We  assume a range voting scale from 0 to 1, and expected utility, E(u) is defined as follows:

E(u) = p1 r1 + p2 r2 + … + pn rn

where ri is a sincere range rating of the ith candidate (0 < ri < 1). We assume that 
ri  = ui where ui is the voter’s utility rating for candidate i. We further assume that pi, the probability that candidate i is elected, is proportional to the voter’s rating,  ri. 

Therefore, pi =  k ri where k is a small constant.

If the rating is changed by an amount, , in a strategic attempt to change the outcome, we then can recalculate E(u) to see if the change has been successful in manipulating the outcome so as to increase the expected value of individual utility.

Therefore, E(u) = kr12 + kr2 + … + krn2
Raising a candidate’s rating would increase the chances of that candidate being elected while reducing the chances of the other candidates concomitantly since the probabilities have to add up to one since the sum of probabillities over all the candidates equals 1.

Let’s take a simplified example. Let’s consider 3 candidates – a, b and c and a specific individual. Let’s assume that the individual  has no prior knowledge of how others will rank the alternatives. All he knows is that the higher he ranks an candidate, the more likely it is that that candidate will win. Let an individual’s expected utility, E(u) = p1 r1 + p2 r2 + p3 r3 where pj = probability that candidate j is elected, j = 1, 2, 3. pj = krj

Let’s work an example where r1 = 1 and r3 = 0.

Then E(u) = p1  + p2 r2 = k + k(r2)2 = k(1 +  r22). 

If  r2 is increased insincerely, p2 will be concomitantly increased while real sincere utility will remain equal to r2. If p2 is increased by , p1 and p3 must decrease by /2 if the probability decrease is evenly distributed which we assume. We are increasing the rating insincerely, but keeping the real utility the same.

Therefore, E'(u) = k(1 – /2) .1 + k(r2 + ) r2 + k(0 – /2) .0 = =  k(1 + r22) – k( ½ – r2)

E'(u) –  E(u) = – k( ½ – r2)

This represents an increase in utility if r2 > ½ and a decrease if r2 < ½. 

If r2 = ½, E'(u) =  E(u). Therefore, increasing r2 > 1/2 will increase expected utility and increasing r2 < ½ will decrease expected utility. Expected utility is maximized for r2 > ½, if r is increased to 1.

If r2 is decreased by , pa and pc must increase by /2 if the probability decrease is evenly distributed. We decrease the rating insincerely while keeping the utility the same.

Therefore, E'(u) = k(1 + /2) .1 + k(r2 – ) r2 + k(0 + /2) .0 = =  k(1 + r22) + k( ½ – r2)

E'(u) –  E(u) = + k( ½ – r2).

If r2 < ½, r2 can be decreased insincerely and the expected utility will increase. Expected utility is maximized if r2 is set to 0. If r2 > ½, then decreasing the ranking will result in a decreased utility.

Let’s try a different calculation where p1 is not necessarily = 1 and p3  is not necessarily 0.

Then 	E(u) = k r12 + k r22 + k r32

If we increase r2 by  and decrease r1 and r3 by /2, we get

	E'(u) = k(r1 – /2) r1 + k(r2 + ) r2 + k(r3 – /2) r3

		= k r12 – k r1 /2 + k r22 + k r2 + k r32 – k r3/2

	E'(u) – E(u) = – k r1 /2 + k r2 – k r3/2

			=  – k{ r1/2 – r2 + r3/2}

This is negative if r1+ r3 > 2 r2

So if  r2 < (r1+ r3)/2, then increasing it will decrease expected utility. If r2 > (r1+ r3)/2, then increasing it will increase expected utility. If  r1 = 1 and r3 = 0, then any r2 > ½ can be increased to 1 with a concomitant increase in utility.

Now let’s decrease r2 by . 

		E'(u) = k(r1 + /2) r1 + k(r2 - )r2 + k(r3 + /2) r3 = 

k r12 + k r1 /2 + k r22  - k r2 + k r32 + k r3/2

			= k r12 + k r22  + k r32 + k( r1 /2 – r2 + r3/2)

		E'(u) - E(u) = k( r1 /2 – r2 + r3/2)
		
		E'(u) - E(u) is positive if (r1+ r3)/2 > r2 and r2 can be decreased to r3 without decreasing expected utility.

If  r2 > (r1+ r3)/2, then E'(u) - E(u) is negative and r2 can’t be decreased without a concomitant decrease in utility.

If  r1 = 1 and r3 = 0, then any r2 < ½, can be decreased to 0 without a concomitant decrease in utility.

Therefore, increasing an alternative whose utility is greater than ½ to 1 will increase expected utility and decreasing an alternative whose utility is less than ½ to 0 will also increase expected utility. If an alternative has utility equal to ½, then the rating should remain equal to ½ .

What happens if there are more than 3 alternatives?

Let’s say the alternatives are 1, 2, 3 and 4. 1 > 2 > 3 > 4.

Therefore,

E(u) = kra ra + k rb rb + k rc rc + k rd rd = k ra2 + k rb2 + k rc2 + k rd2

Let’s say we raise rb by . Then the other alternatives must be decreased equally by /3.

Therefore,

pa = pa – /3; pb = pb + ; pc = pc – /3; pd = pd – /3.

Therefore,

E1(u) = k(ra – /3)ra + k(rb + ) rb + k(rc – /3) rc + k(rd – /3)rd 

= k ra2 – kra /3 + k rb2 + krb + k rc2 – krc /3 + k rd2 – krd /3	
	= k(1 – /3 + rb2 + rb + rc2 – rc /3)
	
	= k ra2 + krb2 + k rc2 + k rd2  – k( ra /3 – rb + rc /3 + rd /3 )

E1(u) – E(u) = – k( ra /3 – rb + rc /3 + rd /3 ) 

If rb > ra /3 + rc /3 + rd /3, then E1(u) – E(u) is positive. 

In general, if n equals the number of alternatives, E1(u) - E(u) is positive if rb > , 	
									i ≠ b	

Therefore, rb can be raised to 1 if the condition holds.

Now, let’s say we have 4 alternatives and we lower rb by . Then the other alternatives must be increased equally by /3.

Therefore,

pa = pa + /3; pb = pb – ; pc = pc + /3; pd = pd + /3.

Therefore,

E1(u) = k(ra + /3)ra + k(rb – ) rb + k(rc + /3) rc + k(rd + /3)rd 

	= k ra2 + krb2 + k rc2 + k rd2  + k( ra/3 – rb + rc/3 + rd/3 )

E1(u) – E(u) = + k( ra/3 – rb + rc/3 + rd/3 )

E1(u) – E(u) is positive if  rb < ra/3 + rc/3 + rd/3

In general, for number of alternatives equal n, E1(u) – E(u) is positive if

rb < , i ≠ b.

Therefore, if rb is greater than the average of the other ratings, it can be increased to 1 in order to maximize expected utility, and if it is less than the average of the other ratings it can be decreased to 0 in order to maximize expected utility.

A general strategy for zero information range voting then would be to vote approval style with a threshold based on the mean of sincere utilities. A voter would first specify his sincere utilities, then convert them to zero or one and vote accordingly. If all voters did this, the voting system should be stable with maximum expected social utility for a stable voting system. Presumably, this utility would not be as great as the social utility if all voters voted sincerely, but sincere voting is unstable because it is vulnerable to being gamed by an insincere voter(s).