Strong FBC

[Forest Simmons]

The Gibbard-Satterthwaite result doesn't rule out Alex's SVM (Small Voting
Machine) when you take into account that the voting machine is supposed to
apply the OPTIMAL strategy, which is sometimes a probabilistic mixture of
pure strategies requiring coin tosses, die throwing, or needle spinning.

In other words, in voting methods optimal strategies sometimes require
randomization, so the G-S theorem doesn't apply to the SVM, unless Alex
wanted to rule out stochastic strategies, in which case he would be ruling
out optimal strategies for some of the ballot sets that could be input
into his machine.

Think of the scissors, rock, and paper game.  The optimal strategy is to
spin a needle that has equal chance of landing on each of the three
possible choices.  Any other "system" can be thwarted.

Suppose that we had a Small Rock Scissors Paper Machine (SRSPM).  What
would it do?

The input could be the sincere preferences of the two players say R>P>S
and S>P>R.  Implementing the optimal strategy the SRSPM would (unlike the
SVM) ignore the inputs, throw a die, and assign R, S, or P for the first
player depending on whether the die came up 0, 1, or 2 mod 3.  Then it
would throw the die again to determine R, S, or P for the second player.
Then it would compare the two results to determine which of the two
players won.

Put the same input in again, and the machine will probably pick a
different winner.

The SVM would also give different winners sometimes when the same ballot
set was used as input, though the input would generally influence the
expected output (except in cases of complete symmetry like cyclic tie with
equal size factions).

Most voters don't like randomization in voting rules.  That's one of the
reasons that Lorrie Cranor's Declared Strategy Voting idea didn't appeal
to polled students (or Polled Herefords, for that matter).

The beauty of Cumulative Repeated Approval Balloting is that the
randomness required for non-manipulability is approximated by the pseudo
randomness inherent in the chaos of the cyclic patterns.  So the method is
absolutely deterministic, but random enough to thwart insincere voting.

How can something be absolutely deterministic but approximately random?

Think of "random number generators" in general; they usually implement
relatively simple deterministic procedures to generate a sequence of
numbers.  Only the most sophisticated of them take a random number from
nature (like the current temperature, humidity, or time) as a "seed" for
the generator.

As an aside, if you ask a mathematician how to get a sequence of random
numbers, he/she will say, "Go ask a physicist, all we can do is give you
pseudo random sequences based on generators of various complexity."  In
the days before quantuum mechanics, most physicists would reply that
nothing is random in nature. Einstein's famous quote on the matter was,
"God doesn't throw dice."

Cumulative Repeated Approval Balloting has a kind of built in random
number generator for which the seed is the set of voted CR ballots. To
know how to falsify your utilities to exploit this system, you would have
to know all the other CR ballots in detail, i.e. know which seed was used.

Guess wrong on one rating of one candidate on one ballot by just one CR
level, and you have a different seed, so the sequence goes nothing like
you expect it to, so you have no chance of intelligently thwarting it by
falsifying your ratings.

All random number generators take advantage of this "sensitivity to
initial conditions" which means that if you change the seed ever so
slightly, then you change the sequence beyond recognition in a few steps.

So if the repeated balloting requires winning candidates to accumulate
approval of at least a dozen times the number of voters, it will take
enough steps to make the sequence unpredictable for practical purposes.

In any case, I believe that Alex's basic idea is true. But you just have
to remember that feeding the same ballot set X into the Small Voting
Machine more than once may yield different winners from time to time,
because the SVM uses optimal strategies, which are in general stochastic
mixtures of pure strategies.

In a way this result can be thought of nature's way of giving the other
members of the Smith set their due.  In fact it can be thought of as a
temporal version of Proportional Representation.

Suppose that a group of children are trying to decide whether to play
baseball, kickball, football, basketball, jumprope, etc.

They are smart enough to use Paper Scissors Rock to make these kinds of
decisions even when there is a majority in favor of one course of action,
because it yields proportional representation over time, i.e. TPR
(Temporal Proportional Represention).


Forest


On Thu, 2 May 2002, Rob LeGrand wrote:

> Alex wrote:
> > Question:  Can we come up with a voting method such that you never have an
> > incentive to lie to the computer?  If so, then it doesn't matter if your
> > assigned strategy is insincere, we still satisfy strong FBC.
>
> See my post on the Gibbard-Satterthwaite theorem at:
>
> http://groups.yahoo.com/group/election-methods-list/message/8793
>
> Basically, the only way to take ranked ballots as input and choose a winner so
> that no voter would ever have reason to vote insincerely is to choose the
> winner according to *one* of the ballots, in effect giving dictator powers to
> that voter.  If it's acceptable for the election method to be that random, then
> it's a perfect system.  Otherwise, nothing will do.  Even if a Small Voting
> Machine were carefully formulated and built, it would still be possible for a
> voter to gain by voting insincerely.  I gave a lot of thought to a similar idea
> a while ago, but I gave up on it when I realized that the G-S theorem would
> still apply no matter what went on inside the SVM black box.  I imagine that an
> SVM or Cumulative Repeated Approval Balloting would remove incentive for
> insincerity about as much as would be practical, but of course the public would
> be unlikely to support such complicated systems.  At least with Approval, you
> never have reason not to vote for your favorite, even if you can't express
> every single preference.  I love Richard's explanation for why the Approval
> winner could be seen as preferable to the Condorcet winner when the two are
> different.
>
> I also like the revised Bucklin idea, the one that allows multiple levels and
> multiple candidates at each level.  I guess revised Bucklin is to regular
> Bucklin as CR is to Borda.  More investigation of this idea . . . ?
>
> --
> Rob LeGrand
> honky98 at aggies.org
> http://www.aggies.org/honky98/

----
For more information about this list (subscribe, unsubscribe, FAQ, etc), 
please see http://www.eskimo.com/~robla/em