[EM] Head to Head Comparison of Election Methods

Paul Dumais paul at amc.ab.ca
Tue Jun 8 13:40:35 PDT 1999

> >       a       b       c       d       e       tot
> > a             100     0       0       0       100
> > b     0               100     0       99      199
> > c     100     0               100     99      299
> > d     100     100     0               99      299
> > e     100     1       1       1               103
> >
> If everyone votes e ahead of a, and everyone votes a ahead of b, then
> everyone must vote e ahead of b.  The above, where 99 out of 100 vote
> b above e, is not possible.  This kind of problem is why I tend to
> give my examples starting with ballots instead of tables.

Good point. I've assumed any table can be achieved with a set of
votes (how wrong I was!). Producing the examples I'm looking for might
be difficult, but this is primarily because they occur with 4 or more
candidates. Does anyone have a good way of producing voting examples
given a pair-wise matrix? It is not as trivial as I had first assumed.
> Your previous example is also not possible, since if only one ballot
> gives a above c, it is not possible to have a beat b 53-47 and c lose
> to b 46-54.  This would imply at least 7 ballots where a is above c.
> > e is the path winner though it is not preferred 297 out of 400 times (in
> > the first count). Both C and D should be ranked higher than E since it
> > is preferred 299 out of 400 times (in the first count). Can you create
> > an example where the Dumais winner pair-wise loses against all
> > candidates but one while there exists another candidate who pair-wise
> > wins against all candidates but one, including the Dumais winner?
> > Perhaps this is how I should word the criterion.
> Here is an example where Dumais violates your revised criterion.
>    2 1 0-1-2
> 49 A B C D E
> 14 B C D E A
> 37 C D E A B
> C beats every candidate except B.  A loses to every candidate except
> B, including C.  A is the Dumais winner.
> A 98-28-37>0
> B 49+28-74>0
> C 14+74>0
> D -49+37<0
> E -98-14<0
>    1 0-1
> 49 A B C
> 14 B C A
> 37 C A B
> A 49-14>0
> B 14-37<0
> C 37-49<0
> I should point out that I think Dumais is actually coming to the
> correct decision in this example.

Me too. I guess I'll abandon that criterion.

> > > --snip--
> > > > >
> > > > > For a complicated example like the one you propose, it is very hard
> > > > > to conclusively say which candidate should win, or which information
> > > > > should be used.
> > > >
> > > > I think that it's not that complicated and it can be quite clear that
> > > > the winner by path voting should not win. Here's an example with 5
> > > > candidates:
> > > >
> > > >       a       b       c       d       e       tot
> > > > a             54      1       1       46      102
> > > > b     46              54      1       53      154
> > > > c     99      46              54      53      252
> > > > d     99      99      46              53      297
> > > > e     54      47      47      47              195
> > > >
> > > > The path winner is E even though it loses pair-wise against all
> > > > candidates but one. It seems clear to me that D should at least be
> > > > considered since it defeats all other candidates (including E) except
> C.
> > > > I think this is grossly unfair. Dumais could never produce a result
> this
> > > > unfair. Candidate C would rightfully complain (under path voting) that
> > > > it lost because the path voting system picks the winner using an
> > > > arbitrary subset of the available information. Path voting ignores
> > > > informatiuon about B>E C>E D>A D>B. Certainly this information is
> useful
> > >
> > > E wins.  If the B>E contest gave 55 to 45, instead of 53 to 47 then E
> > > would not win.  So, clearly the result of this contest is not being
> > > altogether ignored.  It is very important that B doesn't do better
> > > against E.
> >
> > That is true of path voting. However, I have extreme issue with the way
> > path voting allows information such as E>A far outweigh B>E, C>E. The
> > stipulation that the margins of B>E and C>E must be less than E>A is
> > better than nothing, but it doesn't take into account the cumulative
> > effects of having a possibly infinite number of candidates beat E by a
> > margin less than E>A. I really believe that path voting doesn't produce
> > good reslts in these situations.
> The Rock-Country-Folk example shows why I don't want a method that
> uses cumulative effects.
> --snip--
> >
> > I'm having difficulty believing that this is a significant problem with
> > Dumais. Can you show me an example where this is a very significant
> > problem? It seems that a single clone can change slightly who is
> > eliminated, but it seems to be only such that the candidate close to the
> > elimination line is the only one affected. In your country, rock, folk
> > example if we have 1000 country songs, about half would be eliminated in
> > each round under Dumais (the single folk song would of coarse be
> > eliminated).
> That's the problem.  Let's assume that the genre preferences are as
> follows
> I   35 C>F>R
> II  40 F>R>C
> III 25 R>C>F
> Under Dumais and Path Voting, Folk is the favourite genre, and if one
> song from each is nominated, Folk will win.  This is because although
> a majority prefer Country to Folk, it is the weakest majority.
> However, if three country songs are nominated, the preferences might
> look like this:
>        2  1  0 -1 -2
> I   35 C1 C2 C3 F  R
> II  40 F  R  C1 C2 C3
> III 25 R  C1 C2 C3 F
> F  -35+80-50<0
> C1 70+25>0
> C2 35-40<0
> C3 <0
> R  -70+40+50>0
> So, R v. C1, R wins.
> Remember your criticism of path voting that it
> > doesn't take into account the cumulative
> > effects of having a possibly infinite number of candidates beat E by a
> > margin less than E>A.
> What is defeating the folk song is those cumulative margins from all
> the country songs in the running.  If there were 1000 country songs in
> the running, then, based on cumulative margins, it would look like the
> folk song was a terrible choice.  But this would just be the result of
> voters' genre preference combined with the number of each being
> nominated, not an actual change of attitude on anyone's part towards
> Folk in general or the song in particular.

You make some very good points. It seems to me that Dumais will have
"problems" when similar choices are introduces because it treats all
candidates as being dissimilar to a certain degree. Path voting on the
other hand has "problems" when candidates are viewed as dissimilar yet
the voting information treats them as being similar. I will need some
help to develop good examples for the above "problem" with path voting
(if they exist) because they would involve situation involving 4 or more
candidates (with the "problems" potentially getting worse). Perhaps
Steve Eppley's program would help us to do some statistical analysis on
the space of possible outcomes. Does Steve provide this program for
others to try? Particularly, I'm interested in determining how serious a
problem Dumais voting encounters with similar candidates. I would also
like to examine the space of possibilities where intuitively I see some
severe problems (my intuition could be very wrong).
	Here's my intuitive arguments (feel free to ignore this wishy-washy
talk). It seems impossible to tell before hand the impact of introducing
multiple similar candidates. With the examples we've seen, it seems that
intoducing clones would rarely help the clone (if ever). So as long as
candidates representing a certain ideal (like country music) do not have
a predictable advantage by introducing many candidates and candidate
introduction has a cost to it, then intoducing clones of yourself would
be rare.
	Path voting treats much of the voting information as not important.
This may be good where there are many clones, but where candidates are
quite different from each other, we could get situations where the
cumulative effect of many votes with margins less than the smallest path
margin for a givin path winner are ignored. This could produce grossly
unfair results. So the head to head winner of Dumais vs Path may very
well come down to which method has the most severe "problems" and how
often do these problems occur in real situations (but we should look at
factors such a simplicity, meaningfullness, etc). Some software will
probably help us discover this more quickly (via statistics) than we
could by providing isolated examples.

> Let's imagine that the nominating committee dislikes folk music, they
> can ensure folk is eliminated just by nominating more country songs,
> while still appearing to give this genre a fair chance.

Polling information would have to be quite accurate. Introducing clones
could very well help folk music under different circumstances. In any
case, a nominating committee perhaps shouldn't be used for Dumais.

> To take this back to the world of politics, if a legislative body is
> holding a vote between several proposals using Dumais, then it is
> possible for people to cleverly nominate similar proposals with the
> hope of having the above effect.

They would have to be very clever.
> If you are unaware of voter preferences, and just want to torpedo a
> particular proposal, there is a more direct way.  Just nominate other
> similar proposals.  I'll show this vote splitting effect for the music
> example.
>        2  1  0 -1 -2
> I   35 C  F1 F2 F3 R
> II  40 F1 F2 F3 R  C
> III 25 R  C  F1 F2 F3
> C 70-80+25>0
> R -70-40+50<0
> F1 35+80>0
> F2 40-25>0
> F3 -35-50<0
> More folk songs have made the rock song seem like a worse choice.
> The effect is that the rock song is eliminated.  This weakens the
> standing of folk, since it won against rock; in general, it is bad to
> have alternatives that you defeat eliminated.  This effect is also
> what causes the violation of monotonicity.
> I   35 C  F1 F2
> II  40 F1 F2 C
> III 25 C  F1 F2
> It is obvious that the country song now wins, since it is the first
> choice of a majority among the non-eliminated alternatives.
> ---
> Blake Cretney
> See the EM Resource:
>      http://www.fortunecity.com/meltingpot/harrow/124
> My Path voting Site:
>      http://www.fortunecity.com/meltingpot/harrow/124/path

I don't understand your above argument. How can you help a chosen
candidate by introducing clones of a candidate without having good
polling information before hand? It seems good polling information is
required for the above example as well.

I would like to introduce other arguments against the use of path
voting. Isn't it difficult to impliment? Given 100 candidates, how long
would it take you to find a winner (without a computer). How easy is it
to state the method in such a way that people will understand and trust
this method? How meaningful is a path anyway? To say that there is a
path from A>B>C>D uses the information B>C and C>D. Is it valid to use
this information to support the choice of A as the winner? Isn't this
information arbitrary as B>C and C>D information was never meant to be
used to support or not support A. How would voters feel knowing that
such information was used to choose A as the winner while information
such as B>A and C>A was ignored (except that it was less than the
margins in B>C and C>D)? Dumais provides intuitively valid information
in quantities that are easily understood (ie A is preferred 347/500 when
compared to all candidates).

Paul Dumais

More information about the Election-Methods mailing list