[EM] Universal Approval

Martin Harper mcnh2 at cam.ac.uk
Wed Apr 4 10:43:59 PDT 2001

couple of changes to original proposal:
1) use Dyadic votes - they'll do just as well
2) allow = - count it in the obvious way.

monotonicity is quite tricky upon dyadic votes, though - the main difficulty
is in determining exactly what constitutes a change in the position of X which
doesn't affect the positions of any other candidate.

Suppose that X is directly between some W and Y. If the size of X>Y is not 1,
do the following:

1) add one to the size of every comparator, to create space in the tree (just
in case).
2) remove X from the vote  - this is easily done on dyadic approval votes, and
has been detailed by Forest. This will leave ....W>>>>>Y...., for some number
of '>'.
3) reinsert X such that ....W>>>>>X>Y...
4) normalise the resulting tree so that we don't have any empty leaves and
such. For example, "A>>>B>C" goes to "A>>B>C".

Alternatively, if there is a single '>' between X and Y, then change it to an
'='. If there is an = between X and Y, then change it to W>>>>>Y>X. These
simple changes only affect the {X,Y} election, reducing the score X or
increasing the score for Y. Thus they are clearly monotonic for any sensible

The three step bit is trickier. Obviously adding one to the size of every
comparator will make no difference, so we can focus on steps 2 and 3. In terms
of margins, this can increase the margins by which X has lost, or decrease the
margins by which W or Y has lost, or increase the margins by which some C has
lost, relative to W or Y. It is this last case which is a potential problem,
if C and X are vying for top place.

I can't see a way of dealing with this simply, though - it was actually a
problem before, but I overlooked it: switching to Dyadic votes made it clearer
to me...

More information about the Election-Methods mailing list