[EM] The Small Voting Machine (was Strong FBC)

[Forest Simmons]

Here's the promised second installment on this topic containing my version
of the Small Voting Machine, as well as a fix that addresses Adam's
concern:

First some notation:

For each election method M, and (ordered) set of voted ballots B, let M(B)
represent the outcome of the election under the rules of method M applied
to the set of ballots B.

For each method M and each set of utilities U, let B(M,U) be the (ordered)
set of respective ballots that a game theoretic oracle would prescribe as
optimal for method M given the (ordered) set of respective utilities U.

In all of the methods treated below the ballot style will be Cardinal
Ratings, and all utilities are taken as normalized on a scale of zero to
100 percent.

Let M1 be standard Cardinal Ratings; the candidate with the greatest
average rating (averaged over all ballots) is the winner.

Define M2 by setting M2(U)=M1(B(M1,U)).

This means that the input for method M2 is the set of voter utilities, and
that the oracle uses these utilities to calculate optimum Cardinal Rating
ballots B(M1,U) from those utilities, and that the results are fed into
the Cardinal Rating method M1 to determine the winner M1(B(M1,U)).

This method M2 is the Cardinal Ratings analogue of the Small Voting
Machine, which was based on ordinal ballots, i.e. ranked preference
ballots.

As Adam Tarr would point out, it may be that this method M2 is
manipulable, i.e. some voter or group of voter might gain some strategic
advantage by submitting false utilities to the method, even though the
oracle is giving the best possible advice assuming true utility
information.

So we define method M3 by the equation

M3(U)=M2(B(M2,U)),

and then method M4 by the equation

M4(U)=M3(B(M3,U)),

etc.

The "n plus first" method uses the voter utilities to determine the
optimal strategic utilities for use as input into the n_th method.

If for some number n the method Mn satisfies B(Mn,U)=U, then method Mn is
non-manipulable, and all subsequent methods in the sequence will be
identical to Mn.

It may be that this equation B(Mn,U)=U is never satisfied exactly for any
method Mn in the sequence.  In that case I believe that the difference
in the two sides of the equation can be made as close to zero as desired
by choosing n large enough.

I cannot prove this convergence, but I can give heuristic arguments for
it, which I will do in a later installment if there is enough interest.

The biggest questions for me are these:

What does the average voter's voting power under method Mn approach as n
approaches infinity?

Is this limit on power an upper bound for non-manipulable methods?

I believe that the answer to the first question is on the order of the
reciprocal of the square root of the number of voters, and that the answer
to the second question is, "Yes."

Anybody else have any ideas along these lines?

Forest


On Wed, 8 May 2002, Forest Simmons wrote:

> Alex Small has resurrected the idea of an ideal voting machine that would
> be the election method equivalent of the Carnot Engine of thermodynamics
> or the Universal Turing machine of computer science.
>
> He suggested as input the (nominally) sincere, ranked preference ballots
> of the voters.
>
> The machine invokes a game theory oracle to supply the best approval
> strategy for each player based on a complete knowledge of all the
> submitted ballots.  Then the machine implements these optimal strategies
> on behalf of the players (voters) to see who wins.
>
> Rob LeGrand's citing of a version of the dictator theorem led to a
> reminder that in general we can expect the optimal strategies to be
> stochastic mixtures of pure strategies, so that the SVM would not be a
> deterministic machine, i.e. repeating the input rankings will not always
> yield a repetition of the winning candidate.
>
> At first this might seem like a big defect, but if you just consider it as
> a kind of temporal version of proportional representation for supporters
> of the Smith set candidates, it doesn't seem like such a bad feature after
> all.
>
> Adam pointed out that this composite game might still require strategy to
> optimize one's expected utility. In other words, it might not always be
> best to input your sincere ranking into the Small Voting Machine.
>
> At first I thought I could prove otherwise. Consider the following
> (defective) heuristic argument, and see if you can spot the biggest hole:
>
> Suppose I submit an insincere ranking with hopes of getting better
> results.  The oracle supplies the best strategy for that fake ranking, and
> the SVM implements it on my behalf.
>
> Since this strategy is optimal for my fake ranking, it is probably
> sub-optimal for my true ranking. I cannot intervene with some other
> strategy based on my true preferences, because the SVM implements the
> oracle supplied strategies automatically.
>
> It's like trying to fake left, when I intend to throw right, and then
> being constrained to throw left, after all.
>
> Well, the main hole that I see in this argument is that it doesn't take
> into account the changed strategies that the oracle will supply for the
> other voters.
>
> In the analogy, perhaps my strongest throw is to the right, but it is
> better to throw left, because that plays on a big weakness of my
> opponents.
>
> Admittedly, the difference between my true and my fake preferences
> shouldn't affect the other voters' optimal strategies very much if there
> are lots of voters, but remember, the SVM is supposed to be an ideal
> machine.
>
> Furthermore, the effect could be multiplied by block voting of large
> factions.  In particular, if an approximation to the SVM were used in a
> proxy runoff, there would be one voting block per candidate.
>
> So Adam's concern is valid both theoretically and practically.
>
> I don't want to make this installment too long, so I will give my proposed
> modification of Alex's machine in another message.
>
> Forest
>
>
>
>
> ----
> For more information about this list (subscribe, unsubscribe, FAQ, etc),
> please see http://www.eskimo.com/~robla/em
>
>

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