[EM] How to clone proof your favorite method (whether deterministic or stochastic).

Forest Simmons fsimmons at pcc.edu
Wed May 7 15:02:48 PDT 2014


First we need the concept of a covering of a set S of candidates by a
subset K of S: a subset K of S covers S iff every member of S that is
beaten (pairwise) by another member of S is also beaten by a member of K.
A minimal covering is a covering with as few members as possible.

Suppose that your favorite election method FEM is clone dependent.

Let us designate the winner of the clone fixed version of FEM applied to a
set S of candidates by the notation CloneFix(FEM, S).  To compute this
winner ...

(1) Among minimal coverings of the set S let K be the one with maximum
total approval.

(2) If K is a singleton, elect its only member.  Otherwise ...

(3) Let k be the member of K that is elected by (unadorned) FEM restricted
to K.

(4) Let S' be the set of candidates that have the same pairwise relation to
the other members of K that k has, i.e. candidate s' is a member of S'
whenever (for each candidate x in K) candidate s' is beaten by x if and
only if candidate k is beaten by x.

Elect CloneFix(FEM, S') by recursion.

Example: Suppose that FEM is Random Candidate, and that the pairwise
defeats are given by

A>B>C>A for every member A of the clone set {A1, A2, A3},

and that within the clone set the defeats are  A1>A2>A3>A1.

In this case all three minimal covering sets are of the form  {A, B, C}
where A is a member of the clone set {A1, A2, A3}.

Suppose that A is the clone with greatest approval.  Then K = {A, B, C},
and each member of this set has equal likelihood of being candidate k.

If k is B or C, respectively, then B or C is elected.

If k is A, then S' is the clone set {A1, A2, A3}.

In that case, we elect CloneFix(FEM, S') which is A1, A2, or A3 with equal
likelihood.

In sum the probabilities are 1/9 for each member of {A1, A2. A3},
and 1/3 for each member of {B,C}.

This distribution of probability respects the clone structure, unlike the
raw FEM (i.e. random candidate) distribution which would assign a
probability of 1/5 to each of the five candidates.

Note that in our example the approval scores tuned out to be irrelevant.

Some other way (besides approval scores) of selecting the best minimal
covering K from among minimal coverings of S could be used.  For example,
the covering with the least Sum (over the candidates in the covering) of
the Max (over the candidates in S) pairwise opposition.

If approval scores are used, I suggest singling out the best minimal
covering as the one with the highest Proportional Approval Voting score
(PAV score).

If approval scores are not used, and randomization is acceptable, I suggest
going with the minimal covering that ranks the highest according to some
random ballot order. (There are various ways of doing this.)

Also note that FEM = Copeland gives the same result as FEM = Random
Candidate when Copeland ties are broken by random candidate, at least in
examples where the minimal coverings have three or fewer members, which is
probably true for almost all public elections (even when the Smith set is
much larger).

For those that remember it, note the similarity with the "Condorcet
Lottery."  Only this clone fixed version of random candidate is fully
monotonic if I am not mistaken.

Does anybody else like this idea?  Does anybody have a FEM method and
ballot set that they would like to see it applied to?

Forest
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20140507/2a334126/attachment-0002.htm>


More information about the Election-Methods mailing list