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

[Forest Simmons]

Here's the promised heuristic for the convergence of the strategic
utilities to the sincere utilities in the sequence of voting methods M1,
M2, M3, ... described below:

Let's say that b(i,j,k) is the optimal strategic utility of the i_th voter
for candidate j in method k.  In terms of the notation introduced by my
previous posting, b(i,j,k) is the strategic cardinal rating of the j_th
candidate in the i_th member of the ballot set B(M[k],U).

Lemma: If we hold i and j constant, then the sequence b(i,j,1), b(i,j,2),
... b(i,j,k) ... is monotone.

In other words if k2 is between k1 and k3, then b(i,j,k2) is between
b(i,j,k1) and b(i,j,k3).  Here I use "between" inclusively so that we can
say that 0.5 is between 0.7 and 0.5, even though it is not "strictly
between" those two numbers.

I don't have a proof of this lemma, but it seems reasonable, and if it is
true, it easily follows that the sequence converges.

If each such sequence converges, then the sequence of ordered strategic
utility sets  B(M1,U), B(M2,U), ... also converges.

So if the Lemma is true, all that remains is to show that the limit L of
this latter sequence is U.

Suppose that the sequence of methods also converges in the sense that
M1(U), M2(U), ... converges to some outcome (or set of outcomes) M(U).

Then  M(U)=M(L) and B(M,U)=L, and therefore

M(B(M,U))=M(U).

In other words, for this limit method M the oracle optimization yields the
same results as the sincere utilities.

Well there are lots of loose ends in the "proof", but the basic ideas are
there.

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

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