[EM] Approval Equilibria

[Forest Simmons]

If voters' utilities for the candidates are distributed continuously, then
it is possible to calculate certain kinds of Approval Equilibria.

Strictly speaking to get such a continuous distribution would require an
infinite number of voters. But it is common to approximate continuous
distributions with large finite distributions, and vice-versa.  For
example, when

                   n*p*q > 30,

it is common to use the (continuous) Normal distribution with mean n*p and
variance n*p*q as an approximation for the (discrete) Binomial
distribution with parameters n and p.


An alternative approach to continuity is through using Interval CR
ballots, where the voters do not specify precise CR values.  Instead they
assign each candidate to a CR interval.  See my recent posting on the
subject of "CR/Approval and cutoffs" for more details.

Moving onward ...

Suppose that the number of candidates is n, and that we start with n
non-negative numbers w1, w2, ... wn, not all of which are zero.

On each ballot B use these numbers as weights in a weighted average of the
respective candidates' CR estimates to get an expected CR rating r(B).

Let I be the CR interval to which some candidate C is assigned on ballot
B.  The fraction of this interval that lies above the value r(B) is the
contribution of ballot B to the approval count of candidate C.


Let a1, a2, ... an be the candidates' respective approvals.


The function F that takes the vector (w1, w2, ... wn) to the vector
 (a1, a2, ... an) is continuous, because an infinitesimal change in the
weights will result in an infinitesimal change in the r(B) cutoff's, which
in turn, will result in an infinitesimal change in the approval values,
since a finite sum of infinitesimals is still infinitesimal.

If we restrict the domain of this function F to the set of all possible
approval vectors, then it will be a continuous transformation of an n
dimensional ball into itself, which is guaranteed to have an equilibrium
vector V=F(V), according to the Brouwer Fixed Point Theorem.


What is the significance of this equilibrium approval vector?

To answer this question think of the rule that picks the winner by
randomly drawing a ball from a bag, where each candidate's approval
determines how many of the balls are marked with his name.

If the r(B) approval cutoffs were determined using the equilibrium vector
V values for the weights, then no voter could improve his CR expectation
by adjusting his r(B) upward or downward.


The trouble with this rule is that this resulting equilibrium is apt to
give a significant probability of even the least popular candidate getting
into office.

The good news is that modifications of the rule yield equilibria that give
only the best candidates positive chances of winning.


To see how this is done, first consider that if we apply some continuous
function g to the components of function F's output vector, then the
resulting composition G=g(F) is still continuous, and if g is
non-decreasing and takes non-negative numbers to non-negative numbers,
then the transformation G will still have an equilibrium vector W=G(W).


Here's an example of a function g that will yield a slight improvement:

     g(x) = max(0,x-1).

The function G obtained by composing F and this little g is still a
continuous transformation, and will still have an equilibrium.

This equilibrium corresponds to the following rule:

Pick the winning candidate by randomly drawing a ball from a bag in which
there are zero balls for candidates with one or none approval vote, and
there are c-1 balls for each candidate with approval count c.


Now let g(x)=max(0,x-z) where z is the largest whole number such that the
corresponding G=g(F) has a non-zero equilibrium vector W.

This equilibrium corresponds to the rule ... pick the winning candidate by
randomly drawing a ball from a bag which has zero balls for candidates
with fewer than z approval votes, and has c-z balls for each candidate
with approval count c.

It turns out that if there is a Condorcet Winner, then the highest z value
will be sufficient to filter out all of the other candidates.  Only the CW
will have higher approval than z, so the CW has all of the balls in the
bag, and wins with certainty.

If there is no CW, then some other candidate or set of candidates may have
positive probability as well.


Forest