[EM] Approval discussions

[Richard Moore]

I haven't posted any comments in a while because I've been swamped, but
I've followed some of the dialogs, particularly those regarding Approval
voting strategy.

First, I'd like to respond briefly to Rob L.'s comment on candidate
behavior under Approval. The notion that Approval will cause candidates
to move toward the position of a "compromising weasel" while Condorcet
will encourage candidates to move toward a position of a strong centrist
seems like a distinction without a difference. How would compromising
under one method to pick up more votes make a candidate strong while the
same action under another method would make the candidate weak? I just
can't see candidates moving voluntarily along a strong/weak axis; they
are strong or weak according to their own nature.

On outcome tendencies, it's been stated here that Approval will tend to
select the candidate closest to the voter centroid or perhaps the voter
median. While this is partly true, I noticed in my simulations last year
that the tendency is skewed toward a point somewhere in between the
voter centroid and the candidate centroid. However, I think this is at
least partly due to a bias in my simulations, since I simulated voter
strategy using a "two front-runners" approach, and the simulation's
somewhat arbitrary front-runner selection has a statistical bias towards
the region where most of the candidates are. In real life, I suspect if
most of the candidates are to one side of the center, and another
candidate is the sole representative of the other side (Nader,
perhaps?),
then that sole candidate could easily become a front-runner in Approval.
So in short, I noticed a tendency but I'm not certain if it's real or
not.

Now on to voting strategy.

The following Approval strategies have some valid mathematical reasoning
behind them. Let u(i) be your utility for candidate i.

1. delta-p strategy: If delta-p(i,j) is the increase (positive or
negative) in the probability of candidate i winning caused by your
vote approving candidate j, then the strategic value of approving
candidate j is

	s(j) = sum_over_i( delta-p(i,j)*u(i) )

Approve candidate j if s(j) > 0; disapprove if s(j) < 0; if s(j) = 0
then it doesn't matter. This is the only exact optimum strategy formula
I know of. The others are approximations. Of course, the delta-p values
are hard to know, which makes an approximate strategy desirable.

2. p(i,j) strategy: If p(i,j) is the probability, given a two-way
first-place tie, that it will be between candidates i and j, then the
utility of approving j is

	s(j) = sum_over_i( p(i,j)*(u(i)-u(j)) )

In http://groups.yahoo.com/group/election-methods-list/message/6706,
I showed this to be almost equivalent to the delta-p strategy. The
source of error (I think) is that this strategy only considers two-way
ties. For a large electorate, that error term will be exceedingly
small. Again, we have some values -- p(i,j) in this case -- that are
hard to know.

3. geometric mean strategy: This is the approximation discussed by Mike
at http://www.barnsdle.demon.co.uk/vote/strat.html, wherein the p(i,j)
values are each replaced with sqrt( p(i)*p(j) ), and p(i) and p(j)
are the individual winning probabilities of candidates i and j. So
this method is an approximation of an approximation. There are
underlying assumptions in this approximation about the distribution of
ballots. More on that later.

4. above-expected-utility strategy: Forest Simmons, Joe Weinstein, and
I have all mentioned this method in the last couple of months. The
expected utility of the election is

	EU = sum_over_i( p(i)*u(i) )

and we vote for candidate j if u(j) > EU. This strategy can easily
translate into an intuitive strategy. In just about every election,
we all have some expectation going into the election about how much
we will like the outcome.

Say the front-runners are Gore and Bush, and the other candidates are
given only extremely remote chances of winning. Our expectations going
into the election lie about halfway between the utilities of the top two
candidates. According to this strategy, we would vote for everyone we
like better than this expectation. That might include Gore plus the
Green (and possibly Libertarian) candidates, for some voters; Bush and
the Libertarian for others; Bush and Buchanan for still others. That
might be the scenario going into the first Approval-based Presidential
election. Eventually, it would become evident that the "minor" parties
are doing nearly as well as the "major" parties: We now would have a
true multi-party system. Many voters' outcome expectations would rise,
and they would no longer feel compelled to vote for one of the
(original) major parties if those parties failed to produce acceptable
candidates.

Like strategy #3, strategy #4 has underlying assumptions about the
distribution of ballots. Those assumptions can sometimes lead to
problems. Here is a (very contrived) example:

Suppose, in a four-way election, your utilites are A(100), B(60), C(40),
D(0). Strategies 3 and 4 would both fail in the following scenario.

x1:	AB
x2:	CD
x3:	A
x4:	B
x5:	C
x6:	D

Let x1 be either 1000 or 2000 (each at 50% probability), and let
x2 be 1500. Also, allow the other four variables to range from 0
to 100 in identical distributions. Clearly all candidates have the
same chance of winning (25%). Now with method 3, we would calculate
the following strategic values as follows:

	s[0] = sum_over_i( .25 * [ 0 40 60 100 ] ) = 50
	s[1] = sum_over_i( .25 * [ -40 0 20 60 ] ) = 10
	s[2] = sum_over_i( .25 * [ -60 -20 0 40 ] ) = -10
	s[3] = sum_over_i( .25 * [ -100 -60 -40 0 ] ) = -50

We find that we should approve A and B, and disapprove C and D. With
method 4, the calculation is simpler:

	EU = .25( 100 + 60 + 40 + 0 ) = 50

So we approve the two candidates with utilities higher than 50, which
again gives A and B.

But on closer inspection, it is never possible for A and C to tie,
nor A and D, nor B and C, nor B and D. Either A and B are the two
front-runners, or C and D are. So if there's a tie, it must be
either between A and B, or between C and D; each combination has
a 50% probability, conditioned on the existence of a tie.

So, since (by method 2)

s[0] = sum_over_i( [ 0 .5 0 0 ] * [ 0 40 60 100 ] ) = 20
s[1] = sum_over_i( [ .5 0 0 0 ] * [ -40 0 20 60 ] ) = -20
s[2] = sum_over_i( [ 0 0 0 .5 ] * [ -60 -20 0 40 ] ) = 20
s[3] = sum_over_i( [ 0 0 .5 0 ] * [ -100 -60 -40 0 ] ) = -20

the most valuable strategy to the A>B>C>D voter is to vote AC. That
way, if it is a close race between A and B, the voter gives needed
support to A, and if it is a close race betwen C and D, the voter
gives needed support to C. If you were to approve B, the only time
that would be a deciding vote is when it helps to defeat A.

Method 1 should also lead to the AC decision.

This of course goes against the conventional wisdom, that voters
should never reverse a preference in Approval. It requires that
voters are aware of correlations between A and B votes, and of
correlations between C and D votes. Maybe polling won't reveal
correlations but it depends on what format the polls take. At any
rate, poll data may not be a reliable enough incentive for voters
to reverse preferences.

Finally:

I like the recent idea of the Approval Nash equilibrium winner being
the CW, even if it isn't strictly true. Maybe it applies to stable
equilibria (stable meaning that there is an actual *decrease* in
utility for any party that moves away from the equilibrium point).
I suspect if there is no CW then there will be more than one stable
Nash equilibrium winner, and those winners will match the Smith set
(or the Schwartz set?). However, there is a difference between
extrapolating Approval voting Nash equilibria when all voted
preferences are known (and assuming voters decide in blocks), and
counting actual Approval votes cast by individual voters with their
assorted fine-grained utilities and probability estimates. So
real-world Approval voting likely won't always converge to a stable
Nash equilibrium.

Incidentally, if you could quantify how stable each equilibrium
point is, and select the most stable one, then you would have a new
Condorcet-compliant method. Any ideas on how such a quantification
could be made?

   -- Richard