[EM] R.I.P. SVM?

[Alex Small]

While waiting for my car to be worked on yesterday I pulled out a notepad
and worked on the (theoretical) possibility of a machine that

1)  Looks at each voter's preference order
2)  Assigns each group of voters with identical preference orders an
optimal (possibly mixed) strategy given the election method being used and
the strategies assigned to all other voters3)  Picks the winner based on the assigned strategies and the election
method designated by the engineer designing the machine.

The question is, do you have an incentive to submit an insincere
preference order to this machine?

A few months ago, some people invoked the Gibbard-Saitherwaite (sp?)
Theorem to say that it's impossible to do this with a non-dictatorial
machine (a "fair" but dictatorial machine would be one that conducts a
lottery and the winning ballot picks the elected official, AKA Random
Ballot.  I say "fair" because all voters have an equal chance of being the
dictator).

Forest argued that since the GS Theorem doesn't consider probabilistic
strategies it doesn't necessarily apply, since this machine could either
include a stochastic element in its design, or assign some members of a
faction to follow one strategy (the proportion being equal to the
probability if we were using mixed strategies) and the rest to follow
another.  He further argued that if the optimal mixed strategy requires
some fraction (e.g. 25%, or 1/4) of a bloc to follow a particular
strategy, and that fraction of the bloc's membership is not an integer
number of voters (e.g. a bloc of 17 voters, not divisible by 4), then some
probabilistic method is needed to handle rounding.

Here's what I came up with:


In designing such a machine, the task of "assigning each faction an
optimal strategy given the designated election method AND THE STRATEGIES
OF THE OTHER FACTIONS" amounts to finding a Nash Equilibrium.  There may
be many such equilibria.  This is not necessarily a problem, if all
equilibria elect the same person.  As a simple example, suppose that we
use plurality voting and the electorate is as follows:
6%  A>B>C
49% B>A>C
45% C>B>A

We could have a situation where the B and C factions vote for their
respective favorites, and the A faction follows a mixed strategy.  As long
as the mixed strategy involves the A faction giving at least 2 votes to B
we have a Nash equilibrium electing B.

In the above case, as long as the A faction uses the strategy of voting
for B with a probability p>1/3 we have a Nash equilibrium electing B.  If
it is true that for any Nash equilibrium which requires pursuing strategy
S with a probability p, pursuing S with a probability p+delta is also a
Nash equilibrium (for delta smaller than some bound) then Forest's concern
doesn't matter (for sufficiently large electorates).  I don't know whether
game theorists have tackled this question.

However, in general we can have more than one outcome corresponding to a
Nash equilibrium.  In tackling that case, the machine has to use some
criteria to select among the possible outcomes.  Assigned strategies can't
be used, since none have been assigned yet.  Regardless of the method used
by the machine, there will always be a faction which preferred a different
Nash equilibrium, and there will always be close elections where a single
unhappy faction can change the outcome by changing strategies.  If we
assume that they started with a sincere strategy then any strategic
adjustments to protect their interests will be insincere and hence we
can't design a machine that never gives you an incentive to lie (if it
operates deterministically).

The only remaining question is whether you can design an election method
such that all equilibrium strategies give the same outcome.  (The outcome
cannot be the same for all electorates, but for a given electorate with a
particular set of preference orders all equilibria must yield the same
outcome.)

This isn't quite the same as the GS theorem, since I haven't asserted that
all equilibria must involve sincere strategies.  We could take a method
where all equilibria yield the same result, some of them using insincere
strategies, and couple it to an SVM (Small Voting Machine, Super Voting
Machine, Simmons Voting Machine, whatever) and make it into a method where
all equilibrium strategies are sincere, since now your "strategy" is your
(sincere) input to the machine, which in turns assigns a (possibly
insincere) ballot.

However, while I haven't thought carefully about it I suspect that such a
method would be dictatorial.  Once that question is answered, and the
technical matter about whether pursuing the same mixed strategy with a
slightly different probability is still an equilibrium, we can say goodbye
to this theoretical machine.
Comments?



Alex Small


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