Goldfish (single-winner method)

[Blake Cretney]

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.




-----== Sent via Deja News, The Discussion Network ==-----
http://www.dejanews.com/  Easy access to 50,000+ discussion forums