[EM] Solution to approval strategy puzzle, Part 2

[Richard Moore]

Now that we've calculated the raw probabilities, what do I mean by
"strategy matrix" and all those delta Ps?

With the probabilities known for each outcome, we can calculate how
a specific way of voting affects the probabilities. In particular, we
are
interested in the difference between voting for A only and voting AB.

The delta Ps due to voting A, vs. not voting at all, are:

deltaPA|A = 19/24 - 1/3 = 22/48
deltaPB|A = 5/48 - 1/3 = -11/48
deltaPC|A = 5/48 - 1/3 = -11/48

The delta Ps due to voting AB, vs. not voting at all, are:

deltaPA|AB = 23/48 - 1/3 = 7/48
deltaPB|AB = 23/48 - 1/3 = 7/48
deltaPC|AB = 1/24 - 1/3 = -14/48

If you exhaustively list all the possible votes you can cast, one per
row, and list the deltas for each candidate across each row, then
you would get a matrix like this:

                deltaPA    deltaPB    deltaPC
no vote        0                0                0
A                22/48        -11/48        -11/48
AB             7/48            7/48            -14/48
AC             7/48            -14/48        7/48
B                -11/48        22/48         -11/48
BC              -14/48        7/48           7/48
C                -11/48        -11/48        22/48
ABC           0                0                0

This 6x3 matrix can be multiplied by the 3x1 utility vector (transpose
of [100 70 0]) to get a 6x1 vector of strategic values. Picking the
maximum value from this vector gives our best vote.

In principle, this process can be used for any election method.
Calculate the deltaPs for every possible combination/permutation
that you can vote, multiply the matrix by your utilities, and read
down the resulting values to find the maximum.

It would be simpler, however, to work with nice, compact,
square matrices. If there are a lot of candidates the number of
rows can get quite large (32 for a 5-candidate approval election,
and 120 for a ranked election with 5 candidates disallowing
truncation). In the case of approval, it is possible to represent
the strategy with a square matrix, since we know we will
never approve one candidate without approving the higher-ranked
candidates:

            deltaPA        deltaPB        deltaPC
A                22/48        -11/48        -11/48
AB             7/48            7/48            -14/48
ABC            0                0                    0

ABC isn't needed but is included to square off the matrix. But
we should go one step further. We really should consider the
difference between voting A and voting AB, and between voting
AB and voting ABC. Taking the difference between successive
rows, we have

            deltaPA        deltaPB        deltaPC
A            22/48            -11/48           -11/48
B            -15/48           18/48            -3/48
C            -7/48             -7/48            14/48

I labeled the rows this way for simplicity, but the B and C rows
are not the same as the B and C rows in the original 6x3.
When the number of voters is large, the B and C values in the
compact matrix will approach the B and C values in the large
matrix, because the effect of a single vote for one candidate
will not significantly alter the effect of a single vote for another
candidate.

Because of the last step, we have to interpret the resulting
strategic value vector differently:  The first entry of the resulting
vector will be the strategic value of voting A alone, the second is
the difference in strategic value caused by going from A to AB,
and the third is the difference in strategic value caused by going
from AB to ABC. So using this third form of the matrix, we would
pick all the entries having positive strategic value, instead of the
one having maximum strategic value.

There are two things I would like to point out about the third
matrix. Note that all the entries on the diagonal are positive.
This is a very good thing. In particular, if the diagonal is
non-negative for all input probabilities, the method is monotonic.

The second thing is that the value on the diagonal is the
greatest value on its row (even better, it's the only positive
value). Any election method for which this isn't true is going
to have the undesirable property that "a vote for X is really
a vote for Y". I have previously called this property "aliasing".
I suspect that any method that discards candidates without
fully evaluating all expressed preferences are inherently
vulnerable to aliasing.

The large strategy matrix exists for all election methods
(whether it can be calculated is a different matter). The
compact strategy matrix exists for plurality, approval,
cumulative, and Borda methods. I think it exists for
Condorcet and is the identity matrix (so you can skip the
probability calculations in a  Condorcet election).

For some ranked voting methods I think the compact matrix
does not exist. To see why, imagine the effect in IRV of
changing your rankings from ABC to ACB. The effect will
not be the same as changing a BCA ranking to a CBA
ranking, even though in both cases we have only moved the
B and C candidates by one position each. Therefore, you
cannot have a single row representing the effect on
outcome probabilities of promoting a given candidate by
one position. You might be able to have a row giving an
approximation of this effect, averaged over all pairs of
permutations for which B changes by one position. This
would generate a compact strategy matrix that could
be used as an approximation but the large matrix would
be needed for real accuracy.

-- Richard