Generalized Approval Strategy (Was Re: [EM] election's utility approach)

[Richard Moore]

Richard Moore wrote:
 > MIKE OSSIPOFF wrote:
 >
 >> Richard, what's a precise way to calculate an estimate of the delta-p?
 >
 >
 > A challenging question, that. I'll look into it if I can.

Here is the delta-p Approval strategy developed into a very general form.
To start with, we'll need a few definitions.

For multi-way tie-breakers, let's suppose that every candidate in the tie
has a random number between 0 and 1 added to his/her Approval score. That
way, each tied candidate has an equal chance of winning, and in addition,
a complete ranking of the tied candidates is obtained, so that any two
candidates involved in the multi-way tie can be compared. This way, the
definitions I give below will work.

Now, let Fi(X) be the probability that candidate i will receive exactly
X votes in the election.

Let Bij(X) be the probability that candidate i will beat candidate j, if
candidate i receives exactly X votes. This includes the probability that
i will beat j in any tie-breaker that includes both i and j, even if it
is more than a 2-way tie.

Then Wi(X) = product_over_j( Bij(X) ), for all j != i, is the probability
that candidate i will win if candidate i receives exactly X votes. It is
the probability that i beats every other candidate, so it is a simple
product. Since Bij already includes the probability that i beats j if
both are in a tie-breaker of any size, the definition of Wi(X) also
includes tie-breakers of all sizes.

The probability that i will win the election is given by

Pi = sum_over_X( Fi(X)*Wi(X) ), for X = 0, 1, 2, ..., Xmax.

Now suppose we compare i's probability of winning if we approve j to
i's probability of winning if we do not approve j. Call the probability,
if we disapprove j, P1i, and the probability, if we approve j, P2i. Then,
delta-Pij is as follows:

delta-Pij = P2i - P1i = -sum_over_X(Fi(X)*Gj(X)*product_over_k(Bik(X)))

where the product is for all k except i and j, and where

Gj(X) = Bij(X) - Bij(X-1).

The delta-Pij equation is for j != i.

We also need the effect of voting for i on i's own probability:

delta-Pii = -sum_over_j( delta-Pij ), for j != i.

This equation for delta-Pij above is a general expression that applies
to any Approval election (large or small population, zero info or rich
info, correlated or uncorreslated voting patterns, etc.). We can make
various assumptions to reduce this equation to a form suited for a
specific type of situation.

Let's consider two specific cases. In one case, we have "rich"
statistical data; i.e., there is enough data to predict not only
Fi(X) for any candidate i and any number X of "yes" votes, but also
to calculate Bij(X) for any pair of candidates i and j and any X.
Then delta-Pij could be computed numerically by brute force. Even
more significant is that, if the statistical distribution Fi(X)
and the beat probabilities Bij(X) can be expressed as parameterized
functions, and the products and summations can be performed
algebraically using those expressions, we would then have a formula
for delta-Pij that simply accepts the predicted approval scores,
margins of errors, and whatever statistical data (such as correlation
coefficients) go into Bij(X), and produces a delta-P value.

I'll have to admit that doing this is beyond me.

In the second case, we have very "light" statistical data. By this,
I mean that there is enough information to generate Fi(X), but not
to generate Bij(X). In this case, we would have to infer Bij from Fi.
To do this, we assume that the candidate's scores are statistically
independent; i.e., there is no correlation between candidate i's score
and candidate j's score. (Or to put it better, we have zero information
about any such correlation, though one may exist). In that case, the
following can be assumed:

Bij(X) = Cj(X) = sum_over_T( Fj(T) ) + Fj(X)/2, for T = 0, 1, ..., X-1.

The cumulative probability function Cj(X) includes the probability
that j gets anywhere from zero to X-1 votes, plus the probability
that j gets exactly X votes and receives a lower score in the
tie-breaker than i.

We can also derive an expression for Gj(X) to use in this case:

Gj(X) = Bij(X) - Bij(X-1)
	= sum_over_T( Fj(T) ) + Fj(X)/2
	- ( sum_over_T( Fj(T) ) - Fj(X-1) + Fj(X-1)/2 ),
	for T = 0, ..., X-1

which can be simplified to

Gj(X) = ( Fj(X) + Fj(X-1) )/2.

Thus if we know how to get Fj, we can also find Gj.

Next I'll see if I can develop a small example.

   -- Richard