Goldfish (single-winner method)

[Norman Petry]

Blake,

I've got to examine your implementation of Tideman more closely before
commenting on it (I haven't tried devising an algorithm for it myself, yet),
but I did have a couple of comments which I thought I'd toss out right away.
You wrote:

>I'm interested to here what people think of using a tie-breaker ballot as
described above.  I think that this allows GITC, and it seems to me the only
way to accomplish GITC for all cases in a pairwise system.

As far as I know, the only decisive, pairwise methods which fully satisfy
GITC are: (1) Schulze's method, and (2) Tideman's _improved_ method, which
uses a tiebreaker ballot, probably in the manner you describe (see "Complete
Independence of Clones in the Ranked Pairs Rule", Soc Choice Welfare (1989)
6:167-173).  Schulze's method seems to be better in this respect, since a
special tiebreaker isn't required under any circumstances we've yet
discovered.  This seems to me to be a definite advantage of Schulze, since
adding special tiebreaker-ballot rules to other methods increases
complexity, and may be unintuitive to voters.  At first glance, it might
seem unfair to allow one particular voter to affect the election outcome.
If you've discovered any GITC violations for Schulze that we don't know
about, I'd be interested in seeing them!

FWIW, the reason that Schulze's method satisfies GITC is probably related to
the fact that it can be defined as the successive application of the
Schwartz set to the pairwise matrix, after replacing weak defeats with ties,
as Markus explained on August 10th.  Tideman claims that Schwartz's method
(the "General Optimal Choice Algorithm" or GOCHA rule) also satisfies GITC,
but is unacceptable because it doesn't resolve ties.  The Schulze method is
able to resolve those ties in such a way that GITC is still preserved,
without having to resort to particular tiebreaker ballots.

Sequential Dropping seems to be _mostly_ clone independent, but not
entirely, as Mike demonstrated on August 9th ("Maybe None
Clone-Independent").  Perhaps a slightly relaxed version of the GITC
criterion could be defined which SD _does_ satisfy.  That would allow us to
get around the all or nothing nature of criteria compliance -- even though
SD is probably much better than most methods at providing clone
independence, it can't be differentiated using GITC from inferior methods
which violate GITC routinely, since it fails the criterion in rare cases.

***

You also wrote:

>[...].  Of course, there seems to be some debate about what original
Tideman is.

I thought I'd post Tideman's method (in his own words) from his original
paper ("Independence of Clones as a Criterion for Voting Rules", Soc Choice
Welfare (1987) 4: 185-206) so that those on the list can come to a clear
understanding of what he intended.  Tideman wrote:

"An Algorithm"

"Start with the pairings decided by the largest and second largest
majorities, and require that the orderings they specify be preserved in the
final ranking of all candidates. (Require that the ordering of the
candidates be such that when the rows and columns of the matrix of
majorities are so ordered, the positive expressions of these majorities are
in the upper triangle of the matrix, and the negative expressions in the
lower triangle.)  Seek next to preserve the pair-ordering decided by the
third largest majority, and so on.  When a pair-ordering is encountered that
cannot be preserved while also preserving all pair-ordering with greater
majorities, disregard it and go on to pair-orderings decided by smaller
majorities.  Stop when a unique ranking of all candidates is determined, and
declare as the winner the candidate at the top of that ranking." -- Tideman,
"Independence of Clones", p.199.

To me, this sounds like the simple "locking" and "skipping" of defeats that
has been shown by Mike to have serious problems (GMC violations, in
particular).

In his second paper ("Complete Independence of Clones in the Ranked Pairs
Rule", Soc Choice Welfare (1989) 6:167-173), Tideman provides two things:
(1) a special tiebreaker-ballot rule to provide _complete_ clone
independence, and (2) a new definition of Tideman's method, based on his
idea of "Stacks".  On January 6, 1998, David Marsay claimed ("Re: Condorect
sub-cycle rule") that this new definition is the same as Markus' beat-path
method (what we now call the Schulze method).  Yet, I don't think this can
be correct.  In the paper, Tideman provides a proof that his two methods are
identical:

"[...] Hence, if a candidate wins according to the definition of the ranked
pairs rule in terms of stacks, then it also wins under the algorithmic
definition.  Thus the two definitions are equivalent."

To be honest, I don't entirely follow the "stack" definition of Tideman's
method, and he gives no examples.  Yet, we've seen cases where Tideman's
(algorithmic) method provides different (and inferior) results to Schulze,
even when there is no problem with ties.  Therefore, rather than try to
fully decipher Tideman's formulese, I'll just assume the assessment above is
correct, in which case his stack definition *cannot* be the same as
Schulze's beat-path method.

I'd be interested in hearing what others on this list (particularly David
and Markus) have to say about this (who's method is it, anyway?!)


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 23, 1998 2:35 PM
Subject: Re: Goldfish (single-winner method)


>
>--
>
>On Thu, 13 Aug 1998 01:32:01   Mike Ositoff wrote:
>>
>>I don't know if Goldfish 0.2 is different from Tideman's original
>>wording, which I've just received, and haven't completely
>>figured out yet.
>>
>>When you eliminate the loser of a pairwise comparison, then,
>>as far as that candidate is concerned, that's a lot like locking
>>in his defeat.
>>
>>But the copying of his victories from his row into the row
>>of the candidate who beats him seems different from Tideman,
>>and original. The consequences aren't obvious to me without
>>trying it out in examples.
>
>After some thought, I think that original Tideman can be described in the
same algorithm friendly way as Goldfish, and is superior to it in results.
If the following algorithm holds out as original Tideman, then I withdraw
Goldfish.  Of course, there seems to be some debate about what original
Tideman is.
>
>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.
>As well, we will mark every row as "active" initially, but some will be
marked "passive" by the algorithm.
>
>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 row is marked "active"
>    FIND:
>    Find the highest value in active rows of 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:
>    For each cell in the i row, if there is a higher value for that column
in the j row, copy it over.
>Do not change the empty cells on the diagonal.
>    MARK PASSIVE:
>    Mark the j row as "passive".  Set cell (i,j) to be -1, so it doesn't
get chosen again.
>
>The copying of rows may seem different from Tideman, but I don't think it
is.  In Tideman, when a victory is locked in,  the effect is that the
pair-wise loser can no longer win over all, but can help the pair-wise
winner.  The merge step accomplishes the same thing.
>
>The difference between this algorithm and my Goldfish
>algorithm is that in Goldfish, a candidate could only
>be defeated once, and was eliminated.  Here, it is only marked passive, and
may be defeated multiple times, as in Tideman.  The effect of this is that a
decision between candidate X and Y is more likely to be determined by the
majority preference between them, and less likely to be based on which of
them manages to beat candidate Z by a greater amount.  This is why I now
prefer original Tideman to Goldfish.
>
>I'm interested to here what people think of using a tie-breaker ballot as
described above.  I think that this allows GITC, and it seems to me the only
way to accomplish GITC for all cases in a pairwise system.
>
>
>-----== Sent via Deja News, The Discussion Network ==-----
>http://www.dejanews.com/  Easy access to 50,000+ discussion forums
>