[EM] Uncovered set methods (Re: How close can we get to the IIAC)

[Jobst Heitzig]

Hi again Markus,

it's different. The goldfish winner can be really strange. If the defeat
strength are

   A  B  C  D
A  -  2  3  0
B  0  -  1  4
C  0  0  -  5
D  6  0  0  -

then Beatpath and Tideman give B, River gives C, and Goldfish gives D
since the table evolves like this:


      B  C  D
B     -  1  0
C     0  -  0
D     2  3  -


      B     D
B     -     0
D     2     -


            D
D           -

Yours, Jobst


Am 31.10.2010 18:35, schrieb Jobst Heitzig:
> Hi Markus,
> 
> on 29.04.2010 20:33 you asked:
>> is Jobst Heitzig's river method identical
>> to Blake Cretney's goldfish method?
> 
> I'm sorry that I have not read any list posts for months, so this caught
> my attention just now. I will check the differences! You probably refer
> to the method from Blake's Aug 12, 1998 post I cite below?
> 
> Yours, Jobst
> 
> 
> On Aug 12, 1998, Blake Cretney wrote:
>> Here's my entry for single-winner system of the week. It was motivated
>> by my desire to make a method that would be easy to program. To this
>> end, it does not require cycles or the Smith set to be found.
>> I'll call it "Goldfish" until someone shows me a previous mention
>> under a different name. The idea of goldfish is that the candidates
>> seem to eat each other, becoming bigger and bigger, until
>> only one is left swimming in the electoral fish bowl.
>>
>> Goldfish definition:
>> Successively find the worst defeat and eliminate the pair-wise loser.
>> Any win achieved by the pair-wise loser is now scored as if it was
>> achieved by the pair-wise winner, provided it is larger than the
>> one already scored by him, or he is currently scored a loss.
>>
>> Start by making a "victory" table. For each row, enter the votes
>> against each column's candidate, if the row's candidate wins
>> pair-wise. Otherwise enter a 0.
>>
>> The best way to resolve ties is for a chairman, president, or random
>> voter to enter a special ballot. This ballot must not be truncated.
>>
>> Repeat until only one candidate is left:
>> FIND:
>> Find the highest value in the table. Call this cell i,j. If
>> more than one row share this value, choose the row that is
>> higher in the special ballot.
>> MERGE:
>> Here's where the big fish eats the little one. For each cell
>> in the i row, if there is a higher value for that column in
>> the j row, copy it over. For each cell in the i column, if
>> there is a zero for that row in the j column, copy it over.
>> Do not change the empty cells on the diagonal.
>> ELIMINATE:
>> Remove the j candidate and its row and column from
>> consideration.
>>
>> I'm going to use the word "beats" to mean "defeats pair-wise" and
>> "eats" to mean "is chosen to defeat and merge with".
>>
>> MIIAC -- Candidates outside the Smith set are always beaten by
>> members of the Smith set. When they eat them, the rows and
>> columns are merged, but this provides nothing of use for beating
>> other Smith members, because candidates outside the Smith set only
>> have losing scores against those inside, and the merge rule does
>> not copy losing scores. This is because only 0 values are copied
>> from column to column.
>>
>> GITC -- If someone outside a clone set eats a clone, all the
>> clones will be eaten on successive rounds, just as if there was
>> only one. If a clone eats someone outside, the merge occurs.
>> Because the outsider loses to the clone, it can provide no help in
>> defeating other clones. It does not matter which clone eats an
>> outsider, because eventually all clones will be eliminated, or one
>> will eat all the others, and merge with them.
>>
>> GMC -- Because candidates are removed in order of votes against,
>> and because removal does not eliminate a majority vote against
>> a candidate, but merely copies it, candidates with a majority against
>> will be removed first.
>>
>> Elimination methods frequently have the problem that it is
>> possible to help elect a candidate by ranking it lower. This
>> happens when you can reduce the amount by which a victory is
>> obtained, so that a candidate is not eliminated, and can carry on
>> to defeat your enemies. The merge step in Goldfish makes this
>> strategy unnecessary. The winner ends up beating the same candidates
>> as the loser, and by as much. Lower losing values are not copied,
>> but having another candidate in the race with lower losing values
>> is not helpful.
>>
>> This seems like a pretty good system and is fairly easy to program.
>> With a couple of tweaks, it can be converted to Tideman.
> 
> 
> ----
> Election-Methods mailing list - see http://electorama.com/em for list info