[EM] Re: A Deterministic Version of Rob LeGrand's Ballot by Ballot DSV

[Gervase Lam]

> Date: Thu, 1 Jul 2004 15:52:28 -0700 (PDT)
> From: Forest Simmons <fsimmons at pcc.edu>
> Subject: [EM] A Deterministic Version of Rob LeGrand's Ballot by Ballot
> DSV

> In my humble opinion one of the best methods ever invented is Rob
> LeGrand's Ballot by Ballot DSV based on Approval Strategy A.

On first glance, this method reminded me of Kevin Venzke's Gradual Info 
Approval (GIA) and your Ante Upping (Au!) method.  I initially thought 
this method was as good as those two.

However, the more random thoughts I have about this method, the less I 
like the method.  Nevertheless, there are some very good ideas in the 
method.  Also, the method is more directly amenable to a ranked ballot.

> Here's my rendition of the stochastic version (with apologies to Rob):
>
> 1. Shuffle the ranked ballots (equal rankings allowed) into random
> order.

Probably this is one thing I don't like about the method.  The problem is 
that my ballot has a different effect depending whether it is counted in 
the beginning, middle or end of the whole counting procedure.  I suppose 
it could be said that this is very slightly similar to the "one person, 
one vote" requirement except for the fact that the significance of my 
ballot depends on when it is counted.

This is one reason why I think GIA or Au are better.  However, GIA and Au 
are worse in that all of the ballots need to be counted in several rounds. 
 This method only needs one round.

> 2. [my initialization procedure] Use the Borda Count to initialize
> approvals; each candidate's initial approval is its Borda Count
> normalized by dividing by ten times the largest such count, so all
> initial approvals are decimals with first decimal place occupied by a
> digit less than two.
>
> [From this point on all approval increments will be whole numbers, so
> there will be no tied approvals, assuming there were no tied Borda
> Counts.]

I don't like the idea of using Borda in order to do this.  Borda 
supporters would say why not stick to Borda and forget about the rest?

Instead of Borda to break ties, why not just order the candidates randomly 
or even in alphabetical order?  The only time there is ever going to be a 
large preponderance of ties is near the beginning.  After enough ballots 
are counted, if there is a tie then it could be argued that using anything 
arbitrary to break a tie is reasonable.

> 3. While any ballots are left to be processed,
>
>      Take the next ballot B and increment (by one) the approval of
>      each candidate ranked (on B) above the current approval champion,
> and
>
>        If there is some candidate ranked (on ballot B) below this
> "champ" that has more current approval than any candidate ranked (on B)
> above this champ,
>        Then also increment the approval for the current champ.

This way of finding out whether to vote for the current approval champion 
or not is interesting.

> 4. The winner is the approval champ after all the ballots have been
> processed.
>
>
> This method is stochastic because of the first step, randomization of
> the order of the ballots.

An initial idea I had for randomising the order of ballot papers is to 
actually print them with a sequence number (1, 2, 3, 4, etc...).  After 
being printed, they are then shuffled.  It is probably physically better 
to get the printer to print the numbers in random order.

Then, when the ballots reach the ballot counting station, the ballots are 
sorted in sequence number order.  The process of sorting by sequence 
number actually randomises the order of the ballots.

One way to keep the sequence number secret so that only the voter knows 
what the number is is to give the voter the unfilled ballot in a sealed 
envelope.  The voter then walks to the booth and then opens the envelope.

After filling the ballot, the ballot can then be put into another 
envelope.  The voter then puts this envelope into the ballot box.

Alternatively, the ballot paper could be a self seal type where you fold 
it up along some dotted lines, which makes two self seal surfaces come 
together.  In other words, it is a bit like some of the mailshots you get 
at home that tell you to write your address on a piece of pre-printed 
paper that your fold up into an "envelope", which you then post.

The thing I don't like about this is how would the voter react if the 
voter saw a sequence number of 1 on the ballot paper?  One way around this 
is not to apply the sequence numbers at print time but at count time.

At the counting station is a shuffled pot of decals/stickers.  Each one 
has a peel off which, when torn off, reveals the sequence number.

One of these is stuck on to each filled ballot paper.  After every ballot 
paper has a decal/sticker, the peel offs are torn off.

I am sure there are other ways of giving ballot papers a secret sequence 
number.  If a PIN number or even a pay slip can be sent through the post, 
surely a ballot paper can be given a number?

I don't know whether it is quicker to sort or to randomise.  I think that 
sorting is easier because it is easy to see whether a sort has been done 
correctly or not.  It is harder to check whether something has been 
properly randomised or not.

> But what if we replaced the random shuffle of the ballots by a pseudo
> random shuffle?  Then we would have a deterministic method that would
> be statistically indistinguishable from the stochastic version.
>
> There are two details to worry about.
>
> (1) Given a list L of ballots, how do we do a "deterministic shuffle?"
>
> (2) How do we determine a starting order L to which we may apply our
> shuffle?
>
> The first question is the easiest to answer.  Suppose we have a list L
> of ballots.  We can get a shuffled list L' by the "taffy pull" method of
> folding and blending:
>
> Suppose, for example, that the original list has 100 ballots, then the
> order for L' would be 100, 1, 99, 2, 98, 3, 97, 4, ... 51, 50 .
>
> No matter what deterministic order we start with for L, four
> applications of this shuffle L -> L' -> L'' -> L''' -> L'''' would be a
> pseudo randomization adequate for statistical purposes.

Is "taffy pull" your algorithm or did you get it from somewhere else?  It 
seems to be very neat!  The closest thing I could find on the web was 
something to do with toffee.

The algorithm is a bit like doing a riffle shuffle on a pack of cards.  
Whereas 6 or 7 riffles are needed for sufficient randomisation in a pack 
of cards, I suppose 4 taffy pulls are enough for statistical purposes.

> The second question is a little more difficult, because we want to get
> the same answer no matter the order in which the ballots were cast or
> collected.  We want this to work for secret ballots, and if the names of
> the candidates were permuted, we would want the name of the winner to
> follow the same permutation.
>
> So first we find the Border order of the candidates, and assign to each
> candidate a letter of the alphabet corresponding to his placement by
> Borda.  The candidate with the highest Borda score gets the label A, the
> second highest, B, etc.

As mentioned above, I don't like using Borda here.  I wonder whether 
sorting the candidates alphabetically, by age or by date and month of 
birth would be good enough for an initial list?

> Next encode each ballot by making use of the labels according to our
> our customary usage on the EM list.
>
> For example,  B > A = D > C .
>
> Finally, form the list L by sorting the coded ballots lexicographically
> [using the ASCII order for the blanks and symbols like ">" and "=" ].

Personally, I would either use just ">" or just "=".  Therefore, the 
example would be:

B > A D > C or B A = D C.

I think using ">" is clearer here.

Also, I think it would be best to put "=" before the letter A and ">" 
after the letter Z.

Thanks,
Gervase.