[EM] R. B. MacSmith

[Forest Simmons]

I would like to mention some other properties of the variation on MacSmith 
that I suggested below.  For reference first I give a brief description of 
the method:

"Random Ballot, Non Strongly Covered"

Ballots are ordinal or cardinal with approval cutoffs or some other way of 
indicating approval.

The winner is decided by random ballot among the candidates that are not 
strongly covered.

Definition of "Strongly Covered:"

    Candidate A strongly covers candidate B

                iff

    B has no more approval than A
              AND
    A (pairwise) beats every candidate beaten by B.

Strong covering is a transitive, anti-reflexive relation, so its digraph 
is acyclic.  The candidates that are not strongly covered are the 
"sources" in this digraph.

When the original approvals and pairwise beats are restricted to these 
"sources" a new non-empty strong covering relation may be induced relative 
to these remaining candidates.  To get the most for our money we should 
continue removing strongly covered candidates until no candidate is 
strongly covered relative to the remaining candidates.

In addition to the properties listed below I would like to mention the 
following:

6. A non-Smith candidate will have positive winning probability only if 
some non-Smith candidate is the Approval winner.

7. A Condorcet Loser candidate will have positive winning probability only 
if it is the Approval winner (which is highly unlikely).

These two properties assure us that this method is a vast improvement on 
plain old random ballot, in which a candidate who is both the Condorcet 
Loser AND the approval loser will still have a positive probability of 
winning if he votes for himself.

8.  If every (non-strongly covered) candidate is top ranked (shared or 
not) on at least one ballot, then every non-strongly covered candidate has 
a positive chance of winning.  And in that case the converses of 
properties 6 and 7 are also true.

I don't know yet how this method fares with respect to the strong FBC.

Forest

On Tue, 1 Mar 2005, Forest Simmons wrote:
>> Date: Mon, 28 Feb 2005 23:37:05 +0100
>> From: Jobst Heitzig <heitzig-j at web.de>
>> Subject: [EM] R.B.MacSmith
>
> <snip>
>
>> 
>> 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.
>> 
>
> Unfortunately there is still some strategic incentive for inducing a beat
> cycle where there was none. [See examples below.]
>
> Accordingly I propose the following variation on Jobst's idea:
>
> 1. List all of the candidates in order of decreasing approval.
>
> 2. Go down this approval list crossing out candidates that are covered by
> (remaining) candidates higher up on the list.
>
> 3. Strike off the ballots all of the candidates that were crossed off the
> approval list (but do not change approvals even if all remaining
> candidates on a ballot are in the same approval category).
>
> 4. (optional) Iterate steps 2 and 3 until no remaining candidate is
> strongly covered among the remaining candidates.
>
> 5. Choose the winner by random ballot from among the remaining candidates
> (ignoring the stricken candidates).
>
> As the following examples will show, non-Smith members may have positive
> probabilities.  As the examples also show, this is essential for
> discouraging insincere order reversal:
>
> Example 1:
>
> Sincere preferences are
>
> 45 A>>C>B
> 30 B>C>>A
> 25 C>A>>B .
>
> Any Smith method will give the win to C with certainty.  Then there is an
> incentive for the first faction to reverse the order of C and B, since any
> cycle resolution method is going to give some (if not all) of the
> probability to A.
>
> Let's see how my (non Smith) variation plays out:
>
> With sincere ballots, candidate B is the only strongly covered candidate
> (even after the optional iteration since A's approval remains greater than
> C's).
>
> The respective probabilities for A and C in this sincere case are 45
> percent and 55 percent.
>
> Now suppose that the first faction (insincerely) considers voting
> either  A>>B>C  or  A>B>>C .
>
> This introduces a beat cycle ABCA, so no candidate covers (let alone
> strongly covers) another, so no candidates are eliminated.
>
> The respective winning probabilities would be 45, 30, and 25 percent,
> which would leave A's chances the same but share C's chances with B.
>
> Therefore the contemplated order reversal is unrewarding for those
> contemplating it.
>
>
> Example 2:
>
> Sincere preferences are
>
> 49 C>>A=B
> 24 B>>A>C
> 27 A>B>>C
>
> Approval order is BCA, while (pairwise) A beats both B and C, and C is
> beaten by both A and B.  So C is strongly covered by B.  Once C is
> eliminated we have
>
> 24 B>>A
> 27 A>B
>
> so neither of the two remaining candidates strongly covers the other.
>
> The respective winnning probabilities are 24/51 and 27/51 .
>
> Now suppose that the second faction contemplates truncating A so that
> their ballots become  B>>A=C .
>
> Then a beat cycle ABCA comes into play, so there canot be any kind of
> covering of one candidate over another.
>
> The respective winning probabilities are 27, 24 and 49 percent for A, B,
> and C, which would punish the faction contemplating insincere truncation.
>
> [To see this, notice that A and B still have the same odds relative to
> each other, but now their worst alternative C has gained a positive chance
> of winning.]
>
>
> [End of examples]
>
>
> Properties:
>
> 1. Some member of the Smith set will have positive probability since no 
> member of the Smith set can be strongly covered by any non Smith candidate.
>
> 2. Pareto is satisfied, since (as Jobst pointed out) if A is ranked above
> B on every ballot, and B is not strongly covered, then A is not strongly
> covered, so when random ballot time comes, if B is still on the ballot, A
> will still be there also, so B cannot be picked.
>
> Pareto comes out slightly better if we define strong covering by saying
> that A strongly covers B iff A covers B and A has at least as much
> approval as B.  Then we can say that our method is Independent of Pareto
> Dominated Alternatives, since Pareto domination would then imply strong
> covering, and all strongly covered candidates are stricken from the ballots 
> in the course of the procedure.
>
> 3. Jobst's clone proof argument still works.
>
> 4. Monotonicity.  Candidate A moving up in the ranks relative to the other
> candidates cannot decrease its approval (and increasing wouldn't hurt) nor
> can it decrease the number of pairwise beats, nor can it decrease A's
> chances of being chosen at the random ballot stage. Furthermore it cannot 
> increase the number or candidates that are not strongly covered. Putting all 
> of this together, we see that A's winning probability cannot be decreased by 
> moving A up relative to the other candidates.
>
> 5. Independence of zero probability alternatives. If every candidate is in 
> top position on at least one ballot (by voting for self, say), then this 
> independence from zero probability alternatives condition holds, since after 
> all but the strongly covered candidates have been stricken, then every 
> remaining candidate will have a positive chance of being chosen by random 
> ballot.
>
> More examples of potential order reversal incentives are needed for
> testing this method.
>
> Thanks for your inspiring work Jobst!
>
>
> Forest
>