Goldfish (single-winner method)
Norman Petry
npetry at sk.sympatico.ca
Thu Aug 13 10:45:57 PDT 1998
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
>
More information about the Election-Methods
mailing list