[EM] PLEASE consider: More non-deterministic methods

[Forest Simmons]

On Sun, 20 Jun 2004, wclark at xoom.org wrote:

[...]

> One major problem with non-deterministic methods is, well, the fact that
> they're non-deterministic.  That means you have to trust whoever is in
> charge of declaring a winner (or providing your source of randomness).
> Non-deterministic methods are generally very highly deficient in
> procedural fairness, even though they often produce fair outcomes in the
> long run (assuming they're not corrupted).
>
> So basically, non-deterministic methods are the exact opposite of
> deterministic methods.  Just like you'd expect.
>
> But I think you're right in saying that this area needs more research.
> For instance, hybrid methods that are deterministic under certain
> conditions (such as when there's a majority winner) and non-deterministic
> at other times may end up striking a better balance between procedural and
> substantive fairness than non-hybrid methods alone.
>
> You could even use non-deterministic procedures to "blend" different
> methods together:  When both methods agree on a winner, use either IRV or
> Condorcet.  When they disagree, use either method with likelihood
> proportional to the number of voters ranking its winner as their first
> choice.  (Or something similar.)
>
> Non-deterministic methods look like they could be a lot of fun.


The other solution is to use pseudo random methods.  Pseudo random methods
are absolutely deterministic and the results are completely reproducible
given the same set of anonymous ballots, yet in spirit they are
probabilistic.

For example, here's how to make Random Ballot into a pseudo random method:

List the candidate names in order of number of (top choice) votes,
breaking ties by alphabetical order of their names.  Replicate each name
as many times as votes received by that candidate, so that the length of
the list is equal to the number N of voters.

Let K be the number of candidates and N be the number of voters.

Let  L = 10^(K+6)  or some other suitably large number that is much larger
than the number N of voters, but otherwise has no particular relationship
with N.

Let M = (L mod N) + 1 .

The M_th name down the list is the name of the winner.


Here's another probabilistic method that is easily converted into a
deterministic method that is (for all intents and purposes) equivalent to
it:

(1) Voters rank the candidates.  They may duplicate ranks and they may
skip several ranks to reflect their feelings about gaps in worthiness for
office.  Unranked candidates are considered equally ranked one rank below
the lowest ranked candidate.

(2) After the ballots have been submitted, each candidate's weight is
initialized at the value one.

(3) For J from one to 100 ...

     (3a)  On each ballot using the current candidate weights
           find the weighted average of the ranks on that ballot.

     (3b)  Use this weighted average rank as an approval cutoff rank.

     (3c)  Tally over all ballots the candidate approvals using the
           current approval cutoffs.

     (3d)  Increment the weight of the candidate with the greatest
           approval tally.

    Next J

(4) Put marbles into a bag so that each candidate corresponds to a
different color of marble, and the number or marbles for a candidate is
that candidate's final weight.

(5) Draw a marble at random from the bag.  The candidate to whom that
marble belongs is the winner.

To convert this to a pseudo random method, eliminate steps (4) and (5) and
simply take the approval winner from the last pass through the For loop.

It would be impossible to distinguish the candidate winning probabilities
of the two methods based on pre-election polls.

Note that the deterministic version fails participation in one sense:
adding ballots favorable to the winner could change the value of J for
which the winner wins to J=99, and then some other candidate wins
on the 100th pass.

However, the total weight of the winner would not be decreased by the
added favorable ballots, so the his winning probability (in the
non-deterministic version) would not decrease, and hence the prior
probability of winning in the deterministic case would not decrease
either.

So the spirit of Participation is met: you don't decrease the prior
probability of your candidate's winning by participating.

Forest