[EM] Head to Head Comparison of Election Methods

[Blake Cretney]

Paul Dumais wrote:

> > >       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.

Good question.  I find that when making these examples, I start out
with a guess of ballots that might work, and adjust them until the
pair-wise matrix is acceptable for my purposes.  That makes it harder
to code, because a specific matrix might not be possible, but you
rarely need a specific matrix.

--snip--

> > 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). 

What would you consider a problem situation?  Is it one where the
Borda count of the PV winner is very low compared to some of the
losers?

> Perhaps
> Steve Eppley's program would help us to do some statistical analysis on
> the space of possible outcomes. 

I have seen the program.  I think the task you describe is
significantly different from what the program is now doing.

> 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).

Consider the following example:

51 A B C
49 B C A

This is often used as a Borda bad example.  If you see B and C as
clones, it clearly comes to the wrong conclusion.  But if you don't,
if the candidates really are independent, as Borda assumes, the result
makes perfect sense.  That is, if they are independent, it makes sense
to say that A doesn't do as well as B does against C, and this
information should be used against A.

Since there is no way to tell which of a voter's opinions are
independent, even for rated ballots, there will never be a perfect
solution to this problem.

Path Voting seems to be based on getting as much information as
possible out of the ranked ballot, without assuming any level of
independence in voter choices.  This means that sometimes, where there
is more independence, a method that assumes this will come to a better
conclusion.  However, a method that assumes more independence will
also have these problems:

1.  The method will be more likely wrong when the Path Voting
assumption is closer to correct.
2.  If the method differs little from the assumptions of Path Voting,
it will have only a slight advantage over it, even if its assumptions
are closer to correct.
3.  Methods that assume levels of independence end up with clone
problems.  These are fairly bad strategy problems.  As well, the
strategies they encourage often make the method's assumptions further
from true.  For example, Borda assumes independence.  The result is a
method that encourages clones.  This reduces independence.
4.  If levels of independence are found for one group at one time,
they may not hold for a different group or a different time.
5.  The "correct" level of independence search will result in methods
that are designed arbitrarily.  Just as happens if people use
positional methods, and allow themselves to assign arbitrary points
for various ranks.


> 	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.

I agree that introducing clones of yourself would be rare.  Instead
voters and candidates would work to avoid splitting the vote.

> 	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.

It wouldn't have to be all that accurate, in the sense that small
differences between expected and actual outcome won't tend to cause
the strategy to back-fire.  I am woried about strategies like this,
because they would be easier to orchestrate than convincing large
numbers of people to vote insincerely.

I see the nominating committee as an important example because
referendums might often be presented on this basis.

> > 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.

Particularly for members of legislative bodies ;)

> > 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.
> > 

> 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.

You can't help a chosen candidate by introducing clones of it (at
least it doesn't happen often).  The example shows how you can defeat
a candidate you particularly dislike, however.  In the above example,
the mischievous nominator was trying to avoid a Folk win, not
particularly to cause a Country win.

> 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). 

You can start by reducing to the Smith set.  Non-Smith set candidates
have no effect on the result.

I have in the past suggested a couple of convenient ways to find a
winner by hand.  One I called the Goldfish algorithm, and is good if
you have a matrix.  The other way (which is easy if you draw a
diagram) is to follow this procedure:

1.  Reduce to the Smith set.  If all a candidate's paths to the Smith
set have dropped members, then it is considered no longer in the Smith
set.
2.  Drop the victory with the smallest majority.  Once a victory has
been dropped, it is no longer considered.
3.  Return to step 1.

This is the method I use to find a winner quickly by hand.

> 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)? 

Well, if you agree that A>B provides evidence that A is better than
B, then it follows that
A>B B>C C>D D>E
provides evidence that A is better than E, since if the majority is
correct in each of these cases, this is inevitably true.  As well, the
stronger these majorities are, the better evidence it seems to be. 
Path Voting provides a simple way to decide a winner based on this
information.

That's my non-rigorous, intuitive argument.

> Dumais provides intuitively valid information
> in quantities that are easily understood (ie A is preferred 347/500 when
> compared to all candidates).

Our intuitions differ on this point.  Note that the number you say is
intuitive, 347/500, does not actually directly decide the election. 
It is only when this is combined with eliminations that we get Dumais.

---
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