LCM (marginal Schulze-type method)

Tue Nov 3 13:11:13 PST 1998

I thought it was a good idea to fully describe the method I advocate,
to avoid having to defend a vaguely defined group of methods called
Margins or Condorcet-type.  It is similar to Schulze, with modifications
made to use margins and obey SEC.  I have described it in a process
that I find more intuitive than that of Schulze.  Note that I have
eliminated the Schulze step of repeating the process on tied results.

I call the method "Least Contradicted Majority," or "LCM".  Obviously,
many people will feel that it does not deserve this name.  However,
I think it is more important to give a name that shows my goals
for the method than one everyone could agree to.

Although this method meets the Condorcet Criterion, I don't consider
it a tie-breaker.  When using this method, a tie is a situation
requiring a partly random result, not merely the situation of there
being no CW.

Least Contradicted Majority - LCM

The method is based on pair-wise comparisons between candidates.  If,
of the people who express a preference between A and B, most
rank A over B, then A I say A has a majority over B.  The size 
of a majority is equal to the number of people on the winning side 
minus the number on the losing side.  I also call this a victory
for A and a defeat for B, or say that A beats B.

You should also know what a beat path is.  If A beats B who beats
C who beats D, then there is a beat path from A to D.  If there
is a beat path from A to D, but not from D to A, that is a one
way beat path.  This method assumes that if there are beat paths
both ways, this forms a kind of contradiction.  It seeks to remove
the weakest majorities until such contradictions can be resolved.

So how LCM works is as follows:
- If there are any pair-wise ties between candidates, resolve them
  as described in Tie-Breaking.
- Remove all candidates who are defeated by one-way beat paths.  Now,
successively ignore the majorities starting from the smallest margin
and going up.  If ignoring a majority causes more candidates to be
one-way beat path defeated, remove them too.  If there is more
than one majority with the same margin, ignore them all at once.
- The method ends when there is only one candidate left, or all
majorities are ignored.  If there is more than one candidate left,
use the Final tie-breaker as described below.

Tie-Breaking

My tie-breaking procedure is fairly complicated.  I don't consider
this a big problem since almost all tie-breakers are complicated,
and when advocating a method, few people care what the tie-breaker
is.

To break ties, a technique called Random Digging is used.  A ballot
is drawn out at random, and used to decide ties.  If this ballot
does not provide a necessary preference (because it ranks them as
equal), more ballots are drawn to provide more preferences.  No
ballot ever overturns a preference expressed in a previously drawn 
ballot.  If no one expresses a preference between some candidates,
the preference can be determined purely randomly.  If a preference
order is established for pair-wise ties, these same preferences are
used for the Final Tie-breaker.

Pair-wise Tie-breaker
A pair-wise tie occurs between two candidates X and Y if as many 
people prefer X to Y as Y to X.  If there is a pair-wise tie between 
two candidates, the following rule applies:
	If every voter expressed a preference between these candidates,
this tie is, for the purposes of the procedure above not considered a
majority for either side.

	If some voters did not express a preference, a preference is
determined by random digging.  The winner is given a margin of 1 vote.
This occurs BEFORE the normal method is performed.

Final Tie-breaker

Use random digging to give a preference order where one of the tied
candidates is ranked above each of the others.  This candidate is
the winner.

I'm now going to provide some examples.  If you have trouble following,
it will probably help to draw a diagram.

Examples

Example 1:
The numbers are the margin of victory
A>B 2
B>C 3
C>A 1

{A,B,C}>D 7
E>A 8
E>B 5
E>C 4
D>E 6

There is a complete cycle
{A,B,C}>D>E>{A,B,C}
So no one way beat path at first.  
So we ignore C>A 1
Obviously C is the one we check for one-way beat defeat.
but C>D>E>{A,B,C}
Ignore A>B 2, B>C 3 still no change
Ignore E>C 4, that's the one we've been waiting for
C nolonger has any defeats, it has a one-way beat path to everybody,
everyone else is removed.

Example 2:

8 A B C D
8 B C A D
8 C A B D
20 D 

{A,B,C} > D 4
A>B 8
B>C 8
C>A 8

There is a one-way beat path to D, so D is removed.  Notice that this
first step has the same effect as reducing to the Smith set (except
in the case of pair-wise ties).
-D  -- I'm going to use this notation to remove candidates
-A>B,B>C,C>A --  I'm going to use this notation to remove majorities
So, the candidates A,B and C all remain.

A random ballot is drawn, for
example
D
This doesn't resolve the tie so another is drawn
B C A D
Because the first ballot has higher precedence, the preference order
is
D B C A

This means B is first among the tied candidates
So, B wins.  But either B or C could have won for a different random
ballot.  D could not win for any draw.

Example 3:
1 A=B C
1 A B C
1 B A C
1 C B A
1 C A=B
1 C A B

The important think to notice here is that A and B are clones.
A=B [margin of 0]
B=C
A=C

All pair-wise ties must be "resolved" before the process begins.
The pair-wise contests involving C had full participation, so
they are unchanged.  A vs. B, however, did not, so a random ballot 
is drawn.
A=B C
This doesn't resolve the question so another draw is made.
C A=B
Still no luck, we try again
C B A
Finally, the resulting order is 
B A C
And the resulting margins are
B>A 1
B=C
A=C

The remaining ties essentially start the process as if they were
ignored.  In fact ignoring majorities is the same as converting
them to ties.
-A
Only B and C are left.  B ranks higher on the random ballot, so B
wins.  In fact, the probabilities of victory are
A 25%
B 25%
C 50%

___

Blake
---
Blake

-----== Sent via Deja News, The Discussion Network ==-----
http://www.dejanews.com/  Easy access to 50,000+ discussion forums