[EM] Cumulative Repeated Approval Balloting for DSV

[Forest Simmons]

On Tue, 26 Feb 2002, Forest Simmons wrote in part:

> The method is not summable in polynomial size data structures, but an
> approximation can be done in O(K^3) where K is the number of candidates.

Here's the O(K^3) approximation I have in mind:

The input is any (multi)set of CR ballots of any resolution.  Since ranked
preference ballots can be converted into CR ballots by the Borda count,
they will do. For most elections the Five Slot Grade ballot would be
appropriate, not over-taxing the voter's patience, yet providing
sufficient resolution to distinguish Favorite, Compromise, and Nemesis, as
well as two in-between categories of candidates.

For more resolution in the case of twenty or thirty candidates, a plus or
a minus can be attached to the letter grade, in accordance with the custom
of some institutions of higher (or lower) learning.

Each ballot is used to fill in a KxKxK dimensional array A to be described
presently.  Those arrays are to be summed to get a single KxKxK array SA
with enough information to approximate the Cumulative Repeated Approval
Balloting (CRAB) race that we are talking about in this EM list thread.
Hereafter, I will refer to that approval accumulating process as a "crab
race."

The (i,j,k) entry of A is designated by A(i,j,k).  For i not equal to j,
the entry A(i,j,k) is a one or a zero depending on whether or not it would
be in the interest of the voter of the ballot to approve the k_th
candidate in the current stage of the crab race, given only the
information that the i_th candidate is the current leader in the crab
race, and the j_th candidate is the only other candidate less than one
standard deviation behind the leader.

For i equal to j, the entry A(i,j,k) = A(i,i,k) is a zero or a one
depending on whether or not it would be in the interest of the voter of
the ballot to approve the k_th candidate in the current stage of the crab
race, given only the information that the i_th candidate is the current
leader in the crab race, and no other candidate is within one standard
deviation of the leader.

So each voter's ballot is used to fill in a KxKxK array of zeroes and
ones.  Whether or not a particular entry should be a one depends on the
conditional expectations associated with the "givens" applied to the
ballot.

Simple decision theoretic methods (as in Cranor's dissertation) are to be
used to make these decisions.  Alternatively, the voter could choose from
among several simple strategies by checking an appropriate box on the
ballot. This latter approach would be more in line with the original idea
of Declared Strategy Voting; you declare (i.e. choose) which strategy you
want to be used on your behalf. The extreme would be to allow
sophisticated voters to fill in the A(i,j,k) zeroes and ones according to
their own personal strategy. [I'm not proposing that extreme.]

One simple (if not quite optimal) strategy would be to always approve down
to the current crab race leader, exclusive, UNLESS one of the following
reasons for including the leader exists:
(1) the leader has max allowable CR on the ballot, OR
(2) the leader has less than one standard deviation lead over the nearest
runner up AND is strictly preferred over that runner up by the voter
(according to voter's ballot).

Note that ballots of the type

Joe=Jane>Jill=Jack=June>Janice=Jorge=Jenny

naturally convey the necessary information to implement this strategy.
In other words, CR ballots would not be necessary; ordinal information
with equality allowed would be just right for this simple (though
sub-optimal) strategy.

However, the simplicity and clarity of the Five Slot Grade ballot is hard
to beat.

Once the A's have been formed and summed to get SA, this summary is to be
used as follows:

The k_th candidate's initial position in the race is given by the quantity
SA(k,k,k).

At each subsequent stage an amount x is added to the k_th candidate's
total, where x is determined according to two cases:

Case I.  For some i, the i_th candidate leads all other candidates by more
than one standard deviation. In this case the value of x is SA(i,i,k).

Case II. There is a non-empty set S of candidates each of which is within
one standard deviation of the leading (i_th) candidate. In this case x is
the average of the set of values
      { SA(i,j,k) : the j_th candidate is a member of S }.

As soon as some candidate accumulates the required quota, the crab race is
over. If two candidates surpass this quota at the same time, the one who
surpassed it the furthest is the winner.

That completes my description of the O(K^3) approximate simulation of
Cumulative Repeated Approval Balloting.

I believe this approximation is nearly immune to manipulation, even in the
simple sub-optimal strategy version.  It would be extremely risky for a
voter to submit an insincere preference order (or fake utilities) under
the auspices of this method.  The most sophisticated voter could only get
a tiny increase in expected advantage at the cost of extremely detailed
and precise knowledge of the other voters' preferences.

The larger the cumulative approval quota, the longer the race, the harder
to out-guess the method.

As Mike O. and Bart I. have pointed out more than once, Approval quickly
homes in on the right level of compromise. If you over-compromise in one
election, the election results show that you can get away with less
compromise in the next (assuming voter opinions don't change too
drastically between elections).

The main idea of this CRAB method (and its approximate simulation) is to
take advantage of this homing-in without having to wait until the next
election.

Forest