Goldfish (single-winner method)

[Blake Cretney]

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