[EM] R.B.MacSmith

[Jobst Heitzig]

...no, this is not the name of another voting theory hero but the
working title of my latest method design, inspired by Forest's
suggestion to use Random Ballot on the Smith set:


   "Random Ballot Most Approved Cover in the Smith set"
   (R.B.MacSmith)

is a method designed to be a compromise between

   - Condorcet,
   - Approval, and
   - Random Ballot

which is

   - simple,
   - monotonic,
   - clone-proof,
   - moderately but sufficiently randomized,
   - honours strong individual preferences, and
   - provides for short beatpaths to all more approved alternatives.


Here comes the definition:


Def.: R.B.MacSmith
-------------------------------------------------------------------
The most approved member of the Smith set who beats all candidates
beaten by the top candidate of a random ballot wins.
-------------------------------------------------------------------
In more words:
0. Ranked ballots with approval cutoff.
1. Determine approval scores and pairwise beats. (Note: Resolve ties
using a tie breaking rank order (TBRO) constructed from randomly drawn
ballots, for example)
2. Pick a random ballot and call its top candidate the "proposed
winner". (Note: When there is a tie at the top, use the TBRO to break it)
3. Find all candidates beaten by the proposed winner and call this the
"beaten set".
4. Find all candidates who beat everyone in the beaten set and call
this the "alternative winners". (Note: These are exactly the proposed
winner and all its covers)
5. From the alternative winners, remove every candidate who is beaten by
some candidate to whom s/he has no beatpath back. (Note: This reduces
the set to Smith candidates)
6. The most approved one of the remaining alternative winners is the
final winner.


Properties
-----------

Simplicity:
   The method can easily be applied without any reference to cycles,
defeat strengths, Smith set, covering or any other complicated notion.
The only  point which might be difficult to understand for an ordinary
voter could be the concept of beatpath which is unfortunately
unavoidable for the reduction to the Smith set in step 5. Also, note
that there is no need to sort the defeats by strength!

Condorcet:
   Although using ideas from Random Ballot and Approval, the method is
a Condorcet method since the winner is guaranteed to come from the Smith
set.

Awareness of strengths of individual preferences:
   The method honours strong individual preferences in two respects:
First of all, direct support in the form of being the top candidate on
many ballots is important in step 2. Second, large approval is important
in step 6.

Majority complaints:
   When a majority complains that they all prefer some Y to the winner
X, this can be rebutted in the following way:
   (a) When Y has less approval than X, pointing to this fact is
perhaps the easiest rebuttal.
   (b) When Y has more approval than X, there is some member Z of the
"beaten set" which beats Y (otherwise Y would have won since it is also
in the Smith set!). In that we can point out that X has a short beatpath
back to Y, namely X>Z>Y.
   I other words, the winner always has beatpaths of length one or two
to all more approved candidates!

Clone-proofness:
   This is fulfilled in the strong sense that the winning probabilities
are not changed by cloning. We need only assume that on each ballot
either all or no clones are approved. Since then all approval scores and
the probability that some clone is the "proposed winner" are unchanged
by cloning, and also the set of "alternative winners" is essentially
unchanged, clone-proofness is not too difficult to see.

Monotonicity:
   Surprisingly, unlike most clone-proof randomised methods I tried
lately, R.B.MacSmith is monotonic!
   Proof by case distinction:
   (a) When the only modification is an increase in X's approval, then
obviously steps 1-5 give the same as before, while in step 6 X has a
better chance of being the most approved alternative winner.
   (b) When approval scores and pairwise beats remain the same and the
only modification is that one ballot is changed from Y>X>... to X>Y>...,
then we need only look at what happens when this ballot is chosen in
step 2 and X was the winner before the modification. If so, X is in the
Smith set and none of its covers has a larger approval, hence X will win
after the modification, too.
   (c) Finally, assume that the approval scores and the tops of all
ballots remain the same, that the only modification is that X now beats
some Y which beat X before, and that X was the winner before. Then X was
and is still in the Smith set, and beat and still beats everything in
the beaten set. Moreover, the new set of alternative winners is a subset
of the old one, and the new Smith set is a subset of the old Smith set,
hence X is still the most approved member. Pooh!

Amount of randomization:
   Although in step 2 Random Ballot is used to find a "proposed
winner", the degree of randomization introduced by this is much smaller
than in pure Random Ballot. This is because the final winner is chosen
from a not too small set of alternative winners by maximizing approval.
In public elections, most likely every candidate will be covered by one
of the three most approved members of the Smith set, hence the winner
will also be one of those three.
   However, the randomization is still strong enough to ensure that
(almost) every candidate except is beaten by a possible winner. (Recall
that this is necessary to avoid the obvious strategic incentive for some
majority to produce a fake CW when there is no sincere CW!) The only
exception to this are candidates who beat all other candidates who have
a non-zero direct support.

Coveredness:
   Although the winner need not belong to the uncovered set in general,
the covering relation still has a large influence on the result since
because of step 4 the final winner is always a cover of (or equal to)
the "proposed winner". In other words, the fewer covers a candidate has,
the larger the probability that s/he remains the final winner once s/he
has been drawn as the "proposed winner"; and the more candidates one
covers, the larger the probability to belong to the "alternative winners".
   Also, we can define a slightly stronger version of coveredness by
saying that Y strongly covers X when (i) Y beats X and everything X
beats and (ii) Y has larger approval than X. This "strong covering"
relation is a transitive subrelation of the ordinary covering relation,
and the winner of R.B.MacSmith is guaranteed not to be strongly covered
by anyone.

Pareto-efficiency:
   When X is Pareto-dominated by Y, it is also covered by Y and the
latter will almost surely have a strictly larger approval score. Hence
whenever X is an alternative winner, then so is the more approved Y,
thus X cannot win.
   However, removing a Pareto-dominated candidate X could affect the
outcome since it can affect the covering relation: When X but not Y
belong to the "beaten set", removing X may enlarge the set of
"alternative winners". Hence the method does not fulfil IPDA.

Independence of certain alternatives:
   The outcome is independent from non-Smith candidates which have no
direct support, since they cannot become "proposed winners".

Special cases:
   (a) In the (unlikely) case that the Smith set has very small direct
support, so that the "proposed winner" is most likely outside it, the
method is roughly equivalent to Smith//Approval since the set of
"alternative  winners" then almost surely contains the whole Smith set.
   (b) In the case that the Smith set is a cycle of three front-runners
who also get most of the direct support, the method chooses one of them
with a probability approximately proportional to their direct support
(that is, in this case it is almost equivalent to Random Ballot, but
without the possibility of getting a winner with minority support).

Anti-strategic properties:
   I did not yet test many anti-strategy criteria, but the main
anti-strategic feature is that, due to the above-mentioned
randomization, in every majority which thinks about producing a fake CW
by voting strategically there is someone who takes the risk of actually
getting worse off by doing so.

Drawbacks:
   The outcome is not independent from Pareto-dominated candidates (see
above) and is neither independent from non-Smith candidates which
possess some direct support.


Jobst