Goldfish (single-winner method)

[Norman Petry]

Blake,

You wrote, in reference to Goldfish:

>Once again, my motivation is to find an algorithm that
>can be easily implemented.  An easy implementation of
>Sequential dropping could make this all moot.

Sequential Dropping is easily implemented.  Here is my algorithm (using SD
as a tiebreaker), followed by an example:

***

Algorithm for Sequential Dropping (with SD tiebreaker):

Given:

1) N candidates
2) NxN Pairwise Matrix P, where P(i,j) contains the number of voters
preferring candidate i to candidate j (visually, i is rows, j is columns)
3) I'll use '*' (an asterisk) to represent positive infinity (use a constant
called 'MaxInt' or similar if implementing with integer arithmetic).  Also
means "unbeaten"

(Note that this algorithm is destructive of P, so you should apply it to a
copy unless you have another way of recovering the pairwise wins.)

Step 1:

For each candidate who hasn't been disqualified,
Repeat
   Find the fewest votes-against (Lowest[j]) for each candidate.
   Calculate the minimum and maximum of these low values (Lo, Hi)
   If Hi is less than '*', no candidate is yet unbeaten, so
      Replace weakest defeats (P[i,j] = Lo) with '*'
Until Hi = '*' (unbeaten candidate(s) found)

Step 2:

For each unbeaten candidate,
   Check that they beat something & disqualify those who don't.
If all the unbeaten candidates are disqualified, goto step 1.

Step 3:

If more than one unbeaten candidate remains,
   Rebuild P using only unbeaten candidates.  Goto step 1.

***

Example:

(note that you should view this using a mono-spaced font, for it to be
legible).

Initial Matrix P:

(be sure to initialise P(i=j) with '*').

 A   B   C   D   E
 *  25  33  17  17
23   *  33  17  17
18  18   *  32  32
31  31  16   *  25
31  31  16  23   *

Lowest[j]            Lo   Hi
18  18  16  17  17   16   18
18  18  33  17  17   17   33
18  18  33  23  25   18   33
23  25  33  23  25   23   33
31  25  33  32  25   25   33
31  31  33  32  32   31   33
 *   *  33  32  32   32    *

Potential Winners: {A,B}

Check potential winners to see that
they still beat something:

Final Matrix P:

 A   B   C   D   E
 *   *  33   *   *
 *   *  33   *   *
 *   *   *  32  32
 *   *   *   *   *
 *   *   *   *   *

Disqualify any potential winners who
beat nothing.  Since A beats C (by 33),
and so does B, the winners are: {A,B}.
A tiebreaker is therefore required.

We can use Sequential Dropping as the
tiebreaker method.  Eliminate all
non-winning candidates {C,D,E} and
re-start the algorithm.

The final winner is A.


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 12, 1998 11:31 PM
Subject: Re: Goldfish (single-winner method)


>I just thought of a way to make my Goldfish method get closer to GMC.
>The Goldfish algorithm I originally gave I now call Goldfish 0.1.
>Here is Goldfish 0.2.
>
>1.  Make a victory matrix.  This is a matrix where every cell contains
>the votes for that row, against that column if the row beats the column.
>Otherwise zero.
>
>2.  Successively find the largest value in the matrix.  The row is the
>pair-wise winner, the column is the pair-wise loser.  Copy all the
>values from the loser's row to the winner's row, when they are
>greater.  Eliminate the loser's row and column.
>
>3.  The last candidate left wins.
>
>The change from Goldfish 0.1 to Goldfish 0.2 is the removal of
>the column copy rule.  So if B is eliminated in favor of A, and
>C beats A, B beats C, the B beats C score and the C beats A score
>will coexist in the matrix until the higher one is picked and wins
>out.
>
>This brings Goldfish closer to GMC and Tideman.
>
>I believe it satisfies the criterion that
>If Y has a majority against X equal to q, X will not win unless there
>are C1, C2, ... Cn such that
>X >> C1 >> C2 ... >> Cn >> Y
>where >> stands for has a majority greater than or equal to q.
>Once again, my motivation is to find an algorithm that
>can be easily implemented.  An easy implementation of
>Sequential dropping could make this all moot.
>
>
>-----== Sent via Deja News, The Discussion Network ==-----
>http://www.dejanews.com/  Easy access to 50,000+ discussion forums
>