[EM] Which Condorcet completion method is best?

Rob LeGrand honky1998 at yahoo.com
Sat Apr 14 17:25:15 PDT 2001


Howdy all,

Here are the results of my simulations.  Each one ran 99999 elections
and each election had 10000 voters.  The only difference among the
simulations was the number of candidates per election: one had 4, one 10
and one 25.  The results tables use abbreviations for the methods that
are described below.  The first table ranks the methods by "total social
utility", which is calculated for each method by summing the total
ratings of the method's winner of each election and adjusting the result
so that 100% is the best a method could do (sum of all 99999 ratings
winners) and 0% is the worst.  The second table ranks the methods by how
often they chose the ratings winner of an election (maximum 99999).  As
a natural extension of the second table, I also kept track of how often
the methods agreed with each other.  I'll post those results if anyone's
interested.

Total social utility of method's winners
---------------------------------------------
 4 candidates   10 candidates   25 candidates
 BOR  96.720%    BOR  98.632%    BOR  99.422%
 BPm  94.942%    BPm  96.090%    BPm  96.690%
 TIm  94.932%    COm  96.009%    COm  96.612%
 COm  94.925%    TIm  95.858%    TIm  96.318%
 TIt  94.697%    BPw  95.478%    COP  96.304%
 TIw  94.649%    BPt  95.448%    BPw  95.927%
 BPw  94.625%    TIt  95.445%    BPt  95.899%
 COw  94.599%    TIw  95.414%    TIt  95.862%
 BPt  94.579%    COw  95.339%    TIw  95.845%
 COt  94.555%    COt  95.303%    COw  95.819%
 BPa  94.423%    BPa  95.104%    COt  95.789%
 COa  93.893%    COa  94.580%    BPa  95.469%
 COP  92.575%    COP  94.437%    COa  95.157%

Times method chooses the ratings winner
---------------------------------------------
 4 candidates   10 candidates   25 candidates
 BOR  79372      BOR  80474      BOR  83738
 BPm  73842      BPm  67741      BPm  63216
 TIm  73826      COm  67504      COm  62946
 COm  73814      TIm  66866      TIm  61195
 TIt  73373      BPw  65710      BPw  59852
 TIw  73183      TIt  65639      BPt  59729
 BPw  73166      BPt  65595      COw  59577
 COw  73125      COw  65450      TIt  59472
 BPt  73061      TIw  65441      COt  59465
 COt  73042      COt  65346      TIw  59320
 BPa  72838      BPa  64378      COP  58612
 COa  72016      COa  63184      BPa  57812
 COP  68766      COP  59883      COa  56907

*#+ BPm = beatpath(m)    = Path Voting
*#+ BPw = beatpath(wv)   = Cloneproof SSD
*#+ BPt = beatpath(wtv)  = Schulze's Method (practically)
    BPa = beatpath(av)   = Petry's Schulze(av)
*#+ TIm = Tideman(m)     = Ranked Pairs
*#+ TIw = Tideman(wv)    = Majoritarian Tideman
*#+ TIt = Tideman(wtv)   = Majoritarian Tideman "with ties"
*   COm = Condorcet(m)   = Minmax (margins)
*   COw = Condorcet(wv)  = Condorcet(EM)
*   COt = Condorcet(wtv) = Condorcet(EM) "with ties"
    COa = Condorcet(av)  = Simpson-Kramer
*#  COP = Copeland
    BOR = Borda

* always chooses the Condorcet winner if one exists
# always chooses from the Smith set
+ independent of clones
(m) margins
(wv) winning-votes
(wtv) win/tie-votes
(av) all-votes

Some clarifications about the (wtv) variations:  My beatpath(wtv) is
only "practically" Schulze's Method because Markus's preferred
formulation uses margins to break ties; I expect the difference in
practice to be vanishingly small.  The "with ties" versions of
Majoritarian Tideman and Condorcet(EM), like Schulze's Method, count
pairwise ties (say n:n) as defeats for both sides (of strength n),
rather than neither.

Borda obviously does very well given sincere votes, but it's a disaster
when strategic voting is possible.  I didn't include IRV because of its
complexity and ludicrous storage requirements for so many voters, but I
expect it would have been near the bottom (if not far and away the
worst) of the methods given sincere votes.  (If anyone has a way of
computing the IRV winner without having to save every last ranked vote,
I'd love to know it.)

No matter which Condorcet method is used, the results come out clearly
in favor of margins.

I absolutely agree with Mike that avoiding strategy problems is more
important than figuring out which candidate is "objectively" the best
given the votes.  If I didn't, I'd probably pick Borda as the best pure
ranked method (of course, Cardinal Ratings is even better), but if
strategy problems aren't avoided as much as is reasonable, the results
will in practice be tainted anyway.  So Mike and I agree there.  But
when it comes to margins vs. winning-votes (also known as votes-against
or defeat-support), I don't think strategy turns out to be an issue,
unfortunately, because winning-votes doesn't actually get around the
problem.  Under winning-votes, a voter can order sincere ties in
preferences randomly and get the same expected value as if they were
counted using margins.  Since sincere ties are most often among the
lower preferences, voting the ties sincerely is most often punished.
But when the sincere ties are among higher preferences, winning-votes
provides a voter with strictly more strategic options than in margins.
If we can assume that the voters are intelligent (or even just
well-informed), I don't think winning-votes will do any better inducing
sincere voting than margins.  Mike has argued that winning-votes meets
important strategy criteria that apply when no voter "falsifies a
preference."  To me, this simply means that winning-votes often forces a
voter to reverse preferences as the best strategy.  So those criteria
don't seem to make any important assurances after all, which is a shame,
because they sound great.  Mike also seems to be more worried about
preventing truncation than tied preferences in general.  I think of
truncation only as another case of tied preferences; in other words, I
think it's silly to consider votes like A>B>C=D=E=F as a separate case
from votes like A=B=C>D=E>F.

I also disagree with Mike's philosophical justification for
winning-votes.  He says that if A pairwise beats B, the strength of the
defeat should measured only by the support for A because the B voters
have already been overruled.  But shouldn't each side be ignored
equally?  If A beats B 50:49, A's victory is 50 strong.  But if there's
just one more B>A voter, it's a tie, and two more B>A voters give B a
victory 51 strong.  Doesn't that seem ridiculous?  It makes more sense
to me for the votes on the losing side to annihilate an equal number of
votes on the winning side, giving the margin (which is what I've always
understood the word "majority" to mean anyway).  Otherwise what good are
they?  Shouldn't a 48:30 victory be stronger than a 51:46?  I would feel
cheated if I were a voter among that 46.  Winning-votes seems very
peculiar and counterintuitive to me.

>From what I've read, I have little doubt that Condorcet would have
preferred margins, but of course by itself that's no reason to choose a
particular voting system.  Given that winning-votes only provides *more*
strategic options to the voter and that margins does appreciably better
on social utility in my simulations, I think margins is a clear choice
over winning-votes.  As much as I'd like to see a rule better than
margins at preventing strategic preference-reversal, winning-votes isn't
it.

But what about the differences among the best margins methods? The way I
see it, Path Voting's biggest advantage over Ranked Pairs is its
efficiency of computation, even with large numbers of candidates.  To
ensure that the best Ranked Pairs winner is chosen every time, an
exponential-time algorithm like Steve Eppley's Minimize Thwarted
Majorities must be used, since the straightforward Ranked Pairs
implementation can trip up on tied pairwise victories.  Path Voting has
an efficient algorithm of order O(n^3), where n is the number of
candidates.  I also think that my simulations clearly show that Path
Voting consistently picks better winners than Ranked Pairs, although the
difference isn't vast.  I disagree with Blake's assertion that the best
ranking of the candidates necessarily ranks the best candidate first; I
can illustrate with examples if requested.  So while I see Ranked Pairs
as one of the very best methods in theory, I don't think it holds any
theoretical or practical advantages over Path Voting.

Of the methods that satisfy important criteria, Path Voting consistently
had the best social utility in my simulations.  Ranked Pairs also did
very well.  I hereby endorse Path Voting as the best pairwise method,
with an honorable mention to Ranked Pairs.  Cloneproof SSD would do as
well only given a very small incidence of equal preferences among voters
(much smaller than I suspect to be the case in real elections).

Whew!  After all this, though, I still think Approval Voting is the best
public proposal, unless the public demands a ranked-ballot method, in
which case Path Voting has my support until a Condorcet completion
method that punishes preference-reversal is found.  I'm not optimistic.

(I hope it's obvious that I mean no disrespect to Mike or Blake.  I've
followed their contributions to the list for quite a while and I agree
with them most of the time.  Credit should also go to Markus for his
excellent beatpath idea.)

=====
Rob LeGrand
honky98 at aggies.org
http://www.aggies.org/honky98/

__________________________________________________
Do You Yahoo!?
Get email at your own domain with Yahoo! Mail. 
http://personal.mail.yahoo.com/



More information about the Election-Methods mailing list