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
