Goldfish (single-winner method)

[Norman Petry]

Blake,

You wrote:

>>My previous posting turns out to be incorrect as an implementation of
original Tideman.  However, I still like it better than Goldfish 0.2, so I
am calling this algorithm Goldfish 0.3.  I also like it better than Tideman,
and it passes the GMC test from the

You're right, it's definitely not Tideman.  In fact, it's much better than
Tideman.  I think what you've discovered with Goldfish 0.3 is a very
efficient algorithm for the Schulze method.

After you first posted Goldfish 0.2, I applied it to a few of the test
cases, and found it to be pretty good.  It passed most of Markus' bad
examples for SC and Tideman, except the "Tideman fails No-Show" test from
June 10/98.  Goldfish 0.2 also failed No-Show, and didn't seem to offer any
particular advantages over other methods (except implementation), so I
didn't post my results.

Things look _much_ better with Goldfish 0.3.  So far, I've applied it to a
number of previous examples, and it has always produced the same result as
Schulze.  In particular, it seems to satisfy the No-Show criterion, and
correctly solved Mike's 8-candidate clone-independence failure for SD,
posted on August 9/98 ("Maybe None Clone-Independent").  This is
significant, as it means we now have an algorithm which produces results
_better_ than SD, and is easy to implement, even if it turns out later that
it's not exactly the same as Schulze.


Norm Petry


-----Original Message-----
From: Blake Cretney <bcretney at my-dejanews.com>
To: election-methods-list at eskimo.com <election-methods-list at eskimo.com>
Date: August 26, 1998 1:47 PM
Subject: Re: Goldfish (single-winner method)


>On Tue, 25 Aug 1998 21:43:54   Blake Cretney wrote:
>>My previous posting turns out to be incorrect as an implementation of
original Tideman.  However, I still like it better than Goldfish 0.2, so I
am calling this algorithm Goldfish 0.3.  I also like it better than Tideman,
and it passes the GMC test from the archive.  The arguments I made for GITC
and MIIAC for Goldfish 0.1 still seem to hold here.  I think its probably a
lot like Schulze, as I understand it.  I'm working on a proof or
counter-example.
>>
>>Here's the algorithm in almost pseudo-code form.  I resolve ties using the
random ballot method I've been discussing.
>>
>>Start with array (M) size nXn, where M[x][y] is the number of voters who
chose x over y, if x beats y, otherwise 0.  Set M[j][j]=MAXINT, where MAXINT
is any number higher than the number of votes.
>>
>>Start with an array (D) size n, where D[j] is set to "false".  D stands
either for Dead or Defeated.
>>
>>While there is more than one undefeated candidate
>>FIND
>>1   Find the highest value in the matrix less than MAXINT, from among the
rows for which D[i] is "false".  Call the cell containing this value ballot
i,j.  If there is more than one such cell, arbitrarily choose one of those
whose row appears first on the tie-breaking ballot.
>>KILL
>>2   Set D[j]=true, it might be already.
>>EAT, I also call this the merge step.
>>3   For k=1 to n, if M[i][k]<M[j][k] set M[i][k]=M[j][k]
>>That is copy all greater values in the losing row to the winning row.
>>
>
>Here's my attempt to prove a similarity between Goldfish 0.3 and Shulze.
>
>Consider the case where there are candidates X and Y.  Is it possible for Y
to directly defeat X without having a beat path from Y to X that is equal or
greater than any from X to Y?  For this discussion I refer to the value of a
beat path as the score for its weakest link.
>
>Theorem 1
>If a candidate (Y) has no beat path to a candidate (X) then M[y][x] will
never be non-zero.
>Proof:
>At the start, M[y][x] non-zero means that Y pair-wise beats X, so it is
obviously true at the start.
>Now consider a single step of the procedure, assuming the theorem has held
so far, can a single step provide a contradiction?:
>     A cell is found M[i][j] non-zero.  Because it has been true so far,
this means that I has a beat path to J.  It also means that if M[j][k] is
non-zero, J has a beat path to K.  Therefore I has a beat path to K, and it
is safe to copy any values from the j row to the i row without contradicting
the theorem.
>
>Since it starts true, and no step can make it untrue, it must always be
true.
>-----
>Theorem 2
>If X has a beat path against Y of value m, and the FIND procedure has
dropped below value m, and X has not been eliminated, Y has been eliminated.
>
>Proof:
>X -> C1 -> C2 -> C3 -> ... Cn -> Y
>Since X has not been eliminated and X->C1 has a score higher than the FIND
procedures current level, we know that C1's row has merged with X.  That is,
all of C1's victories, including C1->C2 have been copied.  Since this is
also a score higher than the find, X will have merged this too, and so on to
Y.
>
>A slight wrinkle is that the merge copy copies MAXINT values.  A row can
only get a MAXINT value in its column for another candidate if it merges
with that candidate, or merges with a candidate who merges with that
candidate, etc.  I'll leave this as obvious.
>-----
>
>Assume that there is no beat path from Y to X, can Y still eliminate X?
>Well, for this to happen M[y][x] must not be 0 at some point along the
procedure.  This would violate theorem 1, so it can't be possible.
>
>Assume that the strongest path from Y to X, but it has a lesser value than
one of those from X to Y.  Let m be the value of the weakest link in the
strongest path from Y to X.  Assume for the moment that at no stage is a
value of m chosen by the FIND step in the Goldfish algorithm.  A value only
has an effect when it is chosen, so in this case all values in the matrix of
m or less might as well be 0 from the start.  But that means that this weak
link could be eliminated altogether, which I proved was impossible in the
previous paragraph.  So we have to conclude that at some stage a value of m
must be chosen by the FIND step in the Goldfish algorithm.
>
>However, let's consider what this means to the beat path from X to Y.
Remember this path looks like
>X >> C1 >> C2 >> C3 .. >> Y
>where each >> corresponds to a pair-wise victory greater than m.  Which
means that each of C1, C2, C3, .. Y all have pair-wise victories against
them greater than m.  Now, above it was found that the FIND step has to
eventually get down below m.  According to theorem 2 this means that Y must
have been eliminated.
>
>So, from the preceding argument, if X has a greater beat path against every
other candidate, X cannot be eliminated, so X must win over all.
>
>
>
>-----== Sent via Deja News, The Discussion Network ==-----
>http://www.dejanews.com/  Easy access to 50,000+ discussion forums
>