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

[Forest Simmons]

Note that the sequence of methods M2, M3, M4, ... can be based on any
initial method M1.  In fact, the whole thing could be done with multi
player games in general, not just election methods.  Because of that I
would be surprised if it hasn't been done already in some other context
where users are unsophisticated and consequently should be able to input
their sincere utilities without worrying about strategic faking.

Perhaps there are already some well established results along these lines.

If so, we'll re-name the machine accordingly.

If the method converges under reasonably general conditions, I would be
tempted to call the resulting limit method the Strategic Closure of the
original.  Is there such a thing as "Strategic Closure" in game theory?

Forest

On Wed, 22 May 2002, Forest Simmons wrote:

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

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