By Warren D. Smith, April 2009.
I am not sure who first noticed the theorem that with a large number of other voters, all of whom vote randomly (hence all candidates equally likely to win), your strategically-best approval vote is to approve those candidates whose utility exceeds T, and disapprove the others, and your best choice of that threshold T is the arithmetic mean utility (for you) of all the candidates.
One proof is here and other people have also sent me proofs of it including Ivan Ryan and John C. Lawrence.
We shall now prove a more general theorem. Incidentally, these theorems apply to range voting where "approving" means scoring a candidate with the maximum allowed score and "disapproving" with the minimum.
The model:
What is your strategically-best choice of T (maximizing expected utility for you)?
THEOREM: In the above model, your strategically-best approval threshold T is
[Actually, if we sort the U() values into increasing order, then any T-value between the two U() values surrounding and immediately adjacent to this formula's value will do; all T in that real interval all are effectively equivalent.]
The old theorem had been just the special case of this when all the P(X) values happened to be equal, i.e. all candidates equally likely to win. The new theorem allows arbitrary relative likelihoods of victory (which can be highly non-uniform) so it seems much more generally applicable.
Proof: If you increase T from below to above U(C), the effect on your expected utility E, which is equal to [or merely proportional to; this does not matter, and the proportionality factor P(C) which will arise in the ΔE formula also similarly does not matter]is
Note that if U(C) were equal to the "weighted mean utility," that is if
then ΔE = 0. If however U(C)<WtdMean, then E is nonmaximum and increases if T is increased (since ΔE>0). On the other hand U(C)>WtdMean where now U(C)<T, then E would also be nonmaximum since it would similarly increase if T were decreased from above to below U(C).
Therefore the condition for E being maximum is that the threshold T be equal to
the weighted mean utility.
Q.E.D.
Credit: The weighted mean utility theorem, and related results, for Approval Voting traces back to Hoffman, Merrill, and Brams and Fishburn in the late 1970s and early 1980s. See Brams & Fishburn's book Approval Voting pages 74-88, also Appendix C of S.Merrill's book Making Multicandidate Elections More Democratic.
More generality still: If the probability that A and B are tied-for-lead instead is PAB which is now not required to be equal to P(A)P(B) [this latter expression is what would happen if the two component probabilities were independent] then finding the optimal range-vote is, essentially, the problem of maximizing
by choice of the N-vector V subject to the N constraints 0≤V(X)≤1. This is a "linear programming problem." It therefore is soluble in time polynomial in the number of bits in the input. Note that the optimum is always achieved by an "approval style" vote in which every V(X)=0 or 1 – but not necessarily by an "honest" approval-style vote. By going to even-more-general models (e.g. where three-way near-ties can happen with non-negligible probability) one can generate examples in which all approval-style range votes are non-optimal so you need a genuine range-style vote.
Connection to Ossipoff's "pleasant surprise" optimality theorem.