delta-p Approval strategy

[Richard Moore]

So the delta-P and pij approaches are a mathematical identity. Somehow
I'm reminded of a couple of identity theorems from calculus, Green's
Theorem and Gauss's Theorem. While it's been a couple of decades since
I studied those theorems I suspect that the delta-P and pij identity
is somehow related to Gauss's Theorem.

Regarding the possibility of vote-skipping affecting the number of
calculations, it's true that you might have to consider a greater
number of strategy possibilities than there are candidates, but
I don't think it's anywhere near 2^M. Say you have five candidates.
You decide to approve the first two and skip the third. Then, if
you find you should approve of your fourth, you recalculate the
values of your number two and three candidates to include your
approval for number four. If either of those changes, you may then
want to re-evaluate number four again. So you need to evaluate
candidates 2, 3, and 4 twice, meaning you have six sets of
calculations to do. Even if you have to go through the loop one
more time, owing to your number 4 choice changing the second time
through, you should never have to evaluate the same strategy more
than once.

In fact, worst I could see is you would have 2^(M-2) strategies to
consider, since you always approve your favorite and disapprove
your least favorite.

We don't like algorithms to be exponential in execution time. But
worst case isn't average case, and the majority of cases will not
encounter vote-skipping, which brings down the average number of
steps (I can't say if the result is exponential, however).

Also, it helps to realize that you never have vote-skipping unless
you have a known correlation among predicted votes (for example, if
voters for A have a strong tendency to also vote for B and against
C). Modeling those correlations requires using something better
than the cumulative probabilities, Ck, to represent the "i beats k"
probabilities, Bik. At this point, I don't know how to calculate
Bik any better than to use Ck, so the best method I know will never
require exhaustive analysis of all my possible ballots.

If anyone has a better way to model Bik, then utilizing it
thoroughly may require an exhaustive treatment (up to 2^(M-2)
possible ballots).

  -- Richard

----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em