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
