[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