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

[Forest Simmons]

On Sun, 4 Jul 2004, Gervase Lam wrote:

> > 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.

True.  However, every ballot has an equal chance of being first, and every
ballot has an equal chance of being last, (not to mention an equal chance
of being anywhere in between) so it has the same kind of fairness that
random ballot has.

If you belong to a faction of significant size, ballots similar to
yours will be scattered randomly throughout the list.

Furthermore, it's hard to say in general if the first ballot or the last
ballot has more influence on the outcome. Would you rather have your
ballot serve to set the pace or to make one last ditch effort to "save"
the election?

Another way to "unrandomize" Rob's method would be to skip the taffy pull,
and go with the order of the list L (see below.)  Then the voters that
agreed the most with the Borda Count (assuming we stick with Borda as the
initializer) would be the trend setters, but sufficiently many voters at
the other end of the spectrum would have time to overcome high ranking
Borda candidates' approval buildup.

If we replace Borda Count by "number of first place votes," then the
supporters of the candidate with the greatest number of first place votes
would have their ballots counted first, so by the time their ballots were
all counted, no other candidate would have more than a fraction of an
approval vote.  So if this faction was more than fifty percent of the
voting population, no other candidate could possibly overtake this
majority winner.

Still another defense of the ballot-by-ballot approach is to point out
that at least it isn't as bad as the East to West progression of the U.S.
presidential election: exit polls on the East coast influence voters on
the West coast.

But which voters have the greatest advantage?

>
> 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?

Using Borda to get started in this way is like adding one tenth of a voter
whose preference order happens to be the Borda order.

Think of this influence as a transient input that will quickly dampen out
as the system approaches steady state.

The sooner the transient is introduced (in this case at the beginnning)
the sooner opposing forces will be marshalled in opposition. So does this
favor the Borda folks, or does it work against them?

True, it works for them at near ties, but does this advantage overcome the
"early target" disadvantage?

If this transient is deemed to be too influential, you could divide by a
thousand instead of ten to make it more like a thousandth of a ballot.
Ultimately it makes no difference.

For another approach, one might use the number of first rank votes
(divided by ten times the total number of ballots) to initialize the
approvals. Another possibility would be the number of non-truncations
(divided by ten times the total number of ballots).

>
> Instead of Borda to break ties, why not just order the candidates randomly
> or even in alphabetical order?

That would certainly be adequate for the random version (Rob's version).
But I'm aiming at a version that isn't random. And I don't want the result
to depend on how you label the candidates.


> The only time there is ever going to be a
> large preponderance of ties is near the beginning.

Actually, every time one candidate overtakes another there will be a tie
if the approvals are all whole numbers.  When there is a Condorcet cycle,
this can happen frequently throughout the procedure from beginning to end.

> 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.

Flipping a coin would be reasonable in the random case, but we're working
towards a non-random version.

Another approach would be to always break the tie in favor of the "rising
candidate" since that's the one who is most likely to be the next target
anyway.

>
> > 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.

It's the natural extension of "Approval Strategy A" to the case when
equal rankings are allowed.

>
> > 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.
>

That would be adequate for the random method, and would make the result
verifiable, while retaining the randomness.

Rob probably uses some variant of your idea.


[...]

>
> > 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.


I've never seen it elsewhere, but it is analogous to the process of
creating Smale's "horse shoe attractor" with one of Michael Barnsley's
Iterated Function Systems.  [Before the advent of chaos theory this point
set was known as "Knaster's bucket handles."]

Go to the town of Seaside on the Oregon coast and you can see one of these
taffy pull machines in operation in the store window where they make
saltwater taffy.

>
> 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?

For our deterministic method we want something that satisfies both
symmetry with respect to voters and symmetry with respect to candidates,
i.e. neither permuting the names of the candidates or their positions on
the ballot, nor permuting the order of voting or collecting the ballots
from the voters ... (I maintain that) neither of these permutatins should
change the outcome of the election. [The same candidate wins even if under
a different name.]

>
> > 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.

Good suggestion.

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

So "=" is more like a blank.  That makes sense.

Forest

> ----
> Election-methods mailing list - see http://electorama.com/em for list info
>