[EM] Universal Approval is not computationally hard

[Forest Simmons]

In the EM message 8094 posted last 19 September 2001, 

http://groups.yahoo.com/group/election-methods-list/message/8094

, I was pessimistic about the computational burden of Martin Harper's
"Universal Approval"  because it requires counting the number of subsets
that have such and such properties, and the number of subsets grows
exponentially. 

However, more recently, while contemplating the definition of
Combinatorics as "the science of counting without really counting" I
thought of an effective way of doing the required calculations (i.e.
without having to enumerate the subsets one by one).

Briefly, dyadic notation: a ballot expressing the following
relative preference strengths

A < B << C <<< D < E << F

might look something like this:

A  000
B  001
C  010
D  100
E  101
F  110

In Martin Harper's Universal Approval each ballot is used to compare each
pair of candidates' relative approval in each subset of the candidates.

That sounds like a lot of computation. See the following (4 April 2001) EM
list posting for Martin's original description: 

http://groups.yahoo.com/group/election-methods-list/message/7160

>From Martin's matrix summary of the ballot you can figure out the
probability of candidate Y being approved over candidate X in a randomly
chosen subset of the candidates.

Now we get to the nitty gritty of how to effectively compute what needs to
be computed:

Suppose we are faced with a dyadic ballot in a 150 candidate race, and
that we want to calculate the number of subsets of size 35 in which
candidate Y beats candidate X.

Assuming that the ballot shows some degree of preference of Y over X, all
we have to do is count the number of candidate subsets of size 35 in which
X and Y find themselves on opposite sides of the strongest inequality
relation straddled by the subset.

To do this first we go up to the level of the strongest inequality
straddled by X and Y, i.e. the point where the branches to X and Y part
company in the binary tree structure, and ask ourselves, "How many
candidates would we lose if we lopped off both of these branches?"

Suppose for example that the respective binary ratings of X and Y are
1010100 and 1011101.  Then the candidates that would be lost if we lopped
off both branches would be all of those whose binary ratings were of the
form 101**** .  Let's say for example that there are 50 such candidates
counting X and Y.

Then the candidate subsets from among these 50 candidates are precisely
the ones that count.

So the number of subsets containing {X,Y} also of size 35 for which X and
Y straddle the predominant relation would be C(48,33) or "48 choose 33."

We use 48 and 33 instead of 50 and 35 because X and Y are given members of
the set. 

This computation is the key to doing Universal Approval and related
variants in polynomial time.  Universal Approval is effectively summable.

More details and examples later.

Forest