[EM] Seven +/- Two
Forest Simmons
fsimmons at pcc.edu
Wed Sep 19 10:29:26 PDT 2001
I like Richard's reference to Martin Harper's Universal Approval, but I
haven't totally digested the variation he suggested, though it seems quite
promising.
I have been thinking of another possible variation of Universal Approval.
Remember Martin came up with Univeral Approval by noticing that when
counting (non-truncated) dyadic ballots in a certain way with all
candidate subsets of size two, you end up with the Condorcet pairwise
matrix. On the otherhand if you use the same counting method but based on
the entire set of candidates you end up getting the Approval counts for
the candidates.
So for Universal Approval he suggested not just using subsets of size two
and size n (the number of candidates) but counting the effects of all of
the intermideiate sized subsets as well, to get a genuine common
generalization of both Approval and Condorcet.
He went on to prove certain properties satisfied by Universal Approval
when minmax is used as the completion method.
This last part (using minmax for completion) is the part that has always
seemed sub-optimal to me.
Anyway here's a variation:
Start with ordinary pairwise comparisons based on candidate subsets of
size two. If there is no CW, then do "the count" on subsets of size three.
If there is no "beats all" candidate on that basis, then go to subsets of
size four. If it doesn't terminate before reaching the whole set count,
then it will terminate at that stage because that stage is equivalent to
Approval which doesn't suffer from the problem of cycles.
This method satisfies the Condorcet Criterion and the FBC.
Unfortunately it doesn't seem to be summable in polynomial size summaries.
It is too complicated for public proposal, but it may serve some
theoretical purposes, like showing that certain combinations of properties
are theoretically attainable.
It could be approximated by using only the subsets of size 2, 1+n/2, and
n, where n is the number of candidates. This approximation would be
summable in data structures requiring fewer than n^4 entries.
Demorep's method can be thought of as an approximation where all
intermediate sized subsets are skipped (and the initial quota of approval
must be met).
Are there any two bit methods that beat either Richard's or Demorep's
suggestions?
Forest
More information about the Election-Methods
mailing list