[EM] Quantifying manipulability

[Forest Simmons]

Alex makes a good point below about the lack of uniqueness of the (poorly
defined) function F.  So let's see if we can bypass the function F, and
just define G directly:

Let G(V1,V2,M) be the expected utility of the the winner under method M
when the true distribution of voter utilities for the candidates is given
by V1, but each voter is led to believe that the distribution of voter
utilities is V2.

To clarify what I mean by "distribution of utilities" consider the
following example:

There are three candidates: C1,C2, and C3.

Each voter has a utility vector u=[u1,u2,u3] whose three components, u1,
u2, and u3 express the respective relative benefits (whether physical or
psychological) that the voter believes would result from the respective
candidate's election victory.

The distribution of utilities is the multiset of the voters' utility
vectors, i.e. the function V from the set of all possible utility vectors
into the whole numbers, such that V(u) is the number of voters that
subscribe to vector u.

Suppose that there are seven voters and the true distribution V1 is given
by the table:

utility  number of
vector   voters

[0,1,9]   2
[3,0,9]   1
[9,5,0]   3
[1,9,0]   1

In other words, V1 is the multiset

        {([0,1,9],2),([3,0,9],1),([9,5,0],3),([1,9,0],1)} .


Suppose that V2 were  {([0,1,9],3),([2,9,0],4)} .  This might fool the
voters subscribing to the vector [0,1,9], but not the others, because they
could see that their utility vectors were unreported.

In a larger example, the distribution V2 is reported in the form of a
summary of a statistical (supposedly random) sample, so it would be harder
to detect fraud.

Now that we understand what the V's are, we can make use of the function G
of V1, V2, and M.

Restated, G(V1,V2,M) is the expected winner utility under method M when
the true utility distribution is V1, but the voters have been led to
believe (despite their stubborn adherence to their individual utility
vectors) that the distribution of utilities among their fellow voters is
given by V2.

Now let E1(V1) be the social expectation of the candidate with the highest
total utility according to the distribution V1.  In this example E1 would
be 31/7 since the highest utility total is 31 and there are 7 candidates.

Notice that E1(V1) depends only on V1, not on the method M.

Let E2(V1,M) be the average over all possible distributions V2 of the
expectation G(V1,V2,M).

[It may be worthwhile to restrict the possible range of V2 relative to V1
by limiting some norm |V2-V1| to a believable value.  Voters have limits
to their gullibility.]

The larger E2 relative to E1, the better the method M relative to the
distribution V1.

Finally, let E be the average of E2(V1,M)/E1(V1) over all possible V1.

Notice that the number 1 is an upper bound for E, no matter what the
method M may be.

Is there a smaller upper bound?  If so, it would be a kind of Plank's
constant for voting methods.

What is E for the (non-manipulable) random ballot method?

Does it depend on the number of candidates?  If so, perhaps that should be
factored into the formula.

Forest


On Wed, 4 Dec 2002, Alex Small wrote:

> Forest Simmons said:
> > Let F(V,M) represent the set of voter ballots that are optimal for the
> > voters with utility set V under method M.
>
> For whatever it's worth, I don't think F(V,M) is in general unique.
>
> F(V,M) must be a Nash equilibrium.  If any voter can get a better outcome
> by voting a different way then it is not optimal for him.
>
> Now, depending on V there may be more than one Nash equilibrium.  There
> must be some V for which there is more than one Nash equilibrium.
> Otherwise I could build the machine that I talked about several months
> ago, assign every voter his single optimal strategy given everybody else's
> assigned strategies, and pick the winner that way.  The voters would have
> no incentive to falsify their preferences, but that would violate the
> Gibbard-Satterthwaite Theorem.
>
> So, there must be some V for which there is more than one Nash
> equilibrium.  The machine is then impossible to build because we must now
> find a procedure for selecting among the equilibrium outcomes, which gets
> us back to our original problem.
>
> Anyway, I don't know how important this is, but the non-uniqueness of
> (V,M) may be relevant.
>
>
>
> Alex
>
>
> ----
> 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