[EM] Random and reproductible tie-breaks

[Steve Eppley]

Hi again,

I believe Stephane has erred below where he wrote that Condorcet methods 
ensure a clone independent resolution.  Perhaps his definitions of 
Condorcet methods and/or clone independence and/or resolution differ 
from what I believe are the standard definitions? 

Condorcet methods are not necessarily independent of clone 
alternatives.  Some Condorcet methods are vulnerable to clones even when 
no pairings are ties or have equal majorities, for examples Minmax 
(which elects the candidate whose largest pairwise opposition in his/her 
pairwise "defeats" is smallest) and Copeland (which elects the candidate 
with the smallest number of pairwise "defeats").  Other Condorcet 
methods, for examples MAM and Beatpathwinner, are clone independent when 
no tiebreaking is needed and for complete clone independence rely on a 
tiebreaker that is also clone independent.

(Briefly going off on a tangent...  A simpler Minmax that is nearly 
Condorcetian is the one that elects the candidate whose largest pairwise 
opposition is smallest.  It doesn't strictly satisfy the Condorcet 
criterion if votes may be weak orderings, but it's simpler than the 
Minmax defined in the previous paragraph and has similar properties.)

It matters that the tiebreaker be clone independent when the probability 
of a tie is not negligible--in other words when the number of voters is 
small--because otherwise there could *routinely* be farces where 
factions nominate a huge number of clones in order to win if there is a tie.

I agree with Stephane about the desirability of being able to produce 
the same winner each time the votes are tallied.  From the standpoint of 
electing the "best" alternative according to the votes, it doesn't 
matter, since tied alternatives are equally good.  But it may be 
important in many circumstances for the outcome to be stable with 
respect to recounts and verification tallies.  It's a plus if every 
voter can reach the actual outcome when s/he tallies the votes 
independently.

I'm not sure what Stephane means when he says the tiebreaker should be 
"equiprobable."  I see nothing unfair about randomly picking a ballot 
and using it to break ties.  Yet it's possible that a majority of the 
ballots rank one of the tied alternatives over the other, and in such a 
case the two alternatives would not have an equal chance of being 
selected by the random ballot tiebreaker.  Why be concerned?  According 
to the votes the tied alternatives are equally good, so it doesn't 
matter if one has an advantage in the tiebreaker.

Here's a reproducible way to "randomly" choose a tiebreaking ballot:  
Keep track of when each vote is cast, and combine the tracked times to 
make a seed to be used by a pseudorandom number generator. (My apologies 
if this has already been proposed, or if a simpler/better technique has 
already been proposed.)

I think Stephane's concern about influencing the chairperson is 
overstated, since in the case of a tie every member is subject to influence.

Let's not forget how desirable it is that the tiebreaker (and voting 
method) be fairly easy to understand by the voters.  That's more 
important than some of the criteria being discussed.

Regards,
Steve
----------------------------------------------
Stéphane Rouillon wrote:
> I erred if I wrote it is ridiculous to nominate clones unless one can 
> predict before the election that a
> tie will occur.
>
> What I tough I wrote is : it is ridiculous to bother with an clone 
> independent tie-breaker if one considers a clone dependent electoral 
> system.
>
> Using a Condorcet method for example ensures a clone independent 
> resolution, thus different computers should always end up to the same 
> winner despite ties if they both use the same reproductible (but 
> equiprobable or fair) tie-breaker.
>
> Although I have a lot of admiration for Forest and Jobst work, I 
> cannot accept the use of random non-reproductible ballot selection for 
> tie-breakers (or for winner designation even more) because it kills 
> the validation of the process. If the process of designation of the 
> winner can be repeated ad nauseam, fraud can be achieved only by 
> corrupting the ballots database. It then becomes a lot easier for 
> electoral managers to ensure an honest result.
>
> In the other case, anyone should be able to know in advance how the 
> random ballot is selected to thrust the electoral process. If it uses 
> a definite predictible and reproductible method, frauders will try to 
> get several favorable ballots as the tie-breaking numbered ballot.  If 
> it uses a non-reproductible method, frauders will try to taint that 
> one time process. Thus I favor unpredictible but reproductible (but 
> still equiprobable) tie-breakers as the one presented previously, 
> which works for small groups and without any opportunity to influence 
> a chairperson. It is random only because it uses the election data 
> which nobody should know in advance.
>
>> From: Steve Eppley <SEppley at alumni.caltech.edu>
>> To: election-methods at electorama.com
>> Subject: Re: [EM] Random and reproductible tie-breaks
>> Date: Mon, 29 Sep 2008 06:36:50 -0700
>>
>> Hi,
>>
>> Raph Frank wrote:
>>> Stéphane Rouillon <stephane.rouillon at sympatico.ca> wrote:
>>>
>> -snip-
>>>>  Tie-breakers have no need to be clone-independent. You cannot 
>>>> predict a tie
>>>> will occur
>>>>  before the election and it would be ridiculous to strategize on this
>>>> hypothesis.
>>>>
>>>
>>> In fairness, tie breaks are a low probability issue in any case.  If
>>> you are going to do them right, you might as well do them fully right.
>>>
>>
>> Raph seems to be saying it's just an aesthetic value for the 
>> tiebreaker to be independent of clones.  I believe it's not just 
>> aesthetic.  Stephane erred when he wrote it is ridiculous to nominate 
>> clones unless one can predict before the election that a tie will 
>> occur.  All that's needed for nominating clones to be strategically 
>> sensible, assuming the cost of nominating clones is low, is that the 
>> probability of a tie is not negligible.  The probability of a tie is 
>> typically not negligible when voting within small groups (committees, 
>> councils, legislatures, etc.) and the cost of nominating clones in 
>> small groups is typically tiny, which means it can be strategically 
>> sensible to nominate clones if the tiebreaker is not independent of 
>> clones.  It's a form of insurance against a low probability undesired 
>> event.
>>
>> Even if one's focus is on large public elections, before asking the 
>> public to adopt the method in public elections it may be crucial for 
>> the voting method to first develop a track record of satisfaction 
>> among many small groups.  Hence the tiebreaker ought to be 
>> independent of clones (or should be close enough to independent that 
>> the probability of gaining by nominating clones is negligible).
>>
>> I don't know that the tiebreaker used within small groups must be 
>> identical to the tiebreaker that would be advocated for large 
>> elections.  For example, in small groups a seniority system is 
>> common; typically a chairperson casts the tiebreaking vote.  
>> Fortunately for us, that tiebreaker provides clone independence with 
>> repeatability and no randomness.
>>
>> Here's another tiebreaking option.  It's typical for groups to choose 
>> the status quo alternative when it's tied.  Perhaps it would be 
>> acceptable to break ties based on the order of nomination (treating 
>> the status quo as first nominated, when it's an alternative).  This 
>> tiebreaker wouldn't provide a strict independence of clones, I think, 
>> but it may be near enough to clone independent to make it 
>> strategically hard or pointless to nominate clones.  It too has the 
>> desirable attributes of repeatability and non-randomness.
>>
>> In a more recent message in this thread, Raph wrote:
>>> Also, if there was a tie, then odds are that there is only 2 people
>>> involved, so it doesn't really matter about clones.
>>>
>>
>> I don't understand why Raph wrote that.  Assume a tie involves two 
>> alternatives, and assume the voting method (up to but not including 
>> the tiebreaker) is independent of clones.  By nominating clones of 
>> one (or both) of the two tied alternatives, the tie can be changed so 
>> it involves more than two.  It follows that it can matter whether the 
>> tiebreaker is independent of clones.
>>
>> Regards,
>> Steve
>> ----
>> Election-Methods mailing list - see http://electorama.com/em for list 
>> info
>
>
>