[EM] Equivalence of two approval strategy formulas

[Richard Moore]

Here's a proof that the Weber approval strategy formula is equivalent
to the formula I put forth recently.

Disclaimer #1: I am not familiar with Weber's work except from the
recent references provided on the EM list.

Disclaimer #2: I have not proposed a new strategy method. What I
posted previously is a general formulation of strategy. It is reasonable
to suppose that Weber started with such a formulation when deriving
his method. If so then the derivation that follows will most likely be
similar to what he has already done. The purpose of this post is not
to introduce any new findings but to respond to statements challenging
the validity of the general strategy formulation I stated.

The Weber method, as described on this group recently, is to approve
candidate i if

    sum over all j ( Pij(Ui - Uj) )

is positive. Pij is the probability, for any two-way tie for first place,
that i and j are the candidates involved in that tie. This probability
is equal to

    Pijt / Pt

where Pijt is the joint probability that there is a first-place tie and
that it is between i and j, and Pt is the probability of any first-place
tie.

The general formulation, the one I gave, is to approve candidate i if

    sum over all j ( deltaPj|i * Uj )

is positive. deltaPj|i is the change in probability of j winning the
election caused by a single vote for i.

(Actually the general strategy if we are given only one choice
is to take the choice with the highest strategic value as given by
the formula, but since we can make multiple choices in approval
we get to pick all choices with positive strategic value, thus
giving us the highest possible total strategic value).

The probability of i winning without my vote is Pi. If I add my vote,
then the probability of i being in a tie, which I'll call Pit, is
converted into an increase in the probability of a  win for i. So

    deltaPi|i = (Pi + Pit) - Pi = Pit

The probability of j winning is Pj. For j not equal to i, the probability
of j being in a tie with i is Pijt. Removing one vote for i increases
j's probability of winning by Pijt. Adding one vote for i decreases
j's probability by (Pijt - Eij). Because the probability function is
not linear, a step in from x-1 votes for i to x votes for i does not
produce the same change in probability that a step from x vote
for i to x+1 votes for i produces. Hence we need the error term
Eij. Now we can state that

    deltaPj|i = (Pj - Pijt + Eij) - Pj = -Pijt + Eij

For large populations, the error term related to a single vote is
insignificant, so long as the probability function is smooth (no
large-valued second derivatives).

So the strategic value of voting for i can be rewritten as

    Pit * Ui - sum over all j except i ( (Pijt - Eij) * Uj )

The probability of i being in a tie, Pit, is the sum of probabilities
Pijt that i is in a tie with j, for all j not equal to i. That means
that the strategic value of an i vote is

    sum over all j except i ( Pijt * (Ui - Uj ) ) +
    sum over all j except i (Eij * Uj)

Ignoring the error term, and noting that Ui - Uj is zero for
i = j, we can also express this as

    sum over all j ( Pijt * (Ui - Uj) )

Since we have already established that Pijt/Pt = Pij, we
can write this as

    Pt * sum over all j ( Pij * (Ui - Uj) )

which is Weber's formula multiplied by Pt. Since Pt > 0, this
means that the results of the two formulas are either both
positive, both negative, or both zero. Both methods are
decided on the sign of the result, so both methods will make
the same strategic decision. (QED)

Three-way and higher ties are ignored.

 -- Richard

P.S. -- If Mike responds predictably, he will object to the
presence of the error term in this derivation. Rather than
get into a long exchange, I will provide a justification now
and leave it at that.

The error term represents a small inaccuracy in using
-Pijt as a substitute for deltaPj|i. A simple illustration for
a two-candidate election follows. The initial probabilities
are Pa1, Pb1, and Pt1, for candidates A and B winning and
for a tie. If you add one B vote, then the new probabilities
are Pa2, Pb2, and Pt2. The following relationships hold:

Pb1 + Pt1 = Pb2 (adding a B vote converts a tie to a B win)

Pa2 + Pt2 = Pa1 (removing a B vote converts a tie to an A win)

So deltaPa|b is -Pt2. deltaPb|b is Pt1. The difference between
Pt1 and Pt2 is the amount of error the Pijt approximation
introduces.

I say using Pijt (or Pij, after scaling) introduces the error, and
not the other way around, because we are trying to maximize
the expected utility of the election's outcome. This means
maximizing the sum (over all possible outcomes) of the
products of each outcome's probability and utility. Thus we
want each of our choices to make a positive change in the sum
of products. Since the candidate utilities are not affected, the
change is simply the sum of the products of the probability
deltas and the utilities. If the most accurate strategy is
required, then deltaPj|i is the value to use. Since calculating
this with high precision is about twice as difficult (by my
estimate) as the Pij approximation, the Pij approximation is
considered good enough for general discussion of approval
strategy as well as practical uses (for anyone who would
want to apply it to real elections).