[EM] Strong FBC and the SVM

[Alex Small]

A few months ago we discussed the SVM and the Strong Favorite Betrayal
Criterion.  I haven't solved the problem of Strong FBC, but I have some
thoughts on the matter that might help us answer the question.

(As a reminder, the SVM is a machine that takes each voter's preference
order as input, assigns to each voter an optimal strategy given everybody
else's preferences, to achieve a Nash equilibrium, where no voter has an
incentive to change his strategy.  The question is whether one ever has an
incentive to rank somebody equal to his favorite candidate when giving
input to the machine.  If so then it violates the Strong Favorite Betrayal
Criterion.  The weak criterion is that you should have no incentive to
rank another candidate above your favorite.)

First, must the machine be deterministic?  Yes.  We already have a
non-deterministic election method that satisfies strong FBC:  Random
ballot.  If we’re going to admit non-deterministic election methods to
satisfy strong FBC then there’s really no point in building the machine. 
However, I don’t know anybody (except maybe Alan Natapoff, who likes the
Electoral College because it increases your odds of casting the deciding
vote) who wants a method where you gamble on having the deciding vote.

Second, in general, a game can have more than one Nash equilibrium.  If
for a given voting method and electorate there are two or more different
outcomes that correspond to Nash equilibria the machine has a decision to
make.  There are two ways to resolve this:

The first is to first figure out what all possible Nash equilibria are,
given an electorate and election method.  If more than one outcome is
possible then we need to choose among those equilibria.  We can’t use the
strategies assigned to the voters because the machine HASN’T assigned any
strategies yet.  It has looked at our preferences and all possible
strategies, sincere or insincere, that could be assigned to us, and
figured out what the equilibria might be.

The machine must therefore use some criteria to choose the winner from the
set of outcomes possible with Nash equilibria.  We’ve already ruled out a
random selection.  The criteria must therefore be based on our inputs. 
All that the machine has done is eliminate those candidates who can never
win under the circumstances of Nash equilibria.

By applying criteria based on the entire electorate, however, it no longer
performs its function of assigning us strategies that are in our own best
interests.  It is formally equivalent to an election method without the
intermediary of this machine that assigns us strategies.

The other way for the machine to operate is to start from an initial
condition (presumably the ballots we inputted), find a winner according to
whatever method it’s using, and then modify our strategies in light of
what everybody else is doing.  Continue until we reach an equilibrium and
then stop.

(In principle it could find more than one equilibrium, but not necessarily
all equilibria, and then choose among the equilibria already identified. 
However, that also places us in a situation formally equivalent to an
election without the intermediary of the machine.)

Operating by sequential adjustments may not find equilibria, but instead
produce periodic behavior.  (See Brams and Fishburn for a discussion of
how polls can produce such outcomes in Approval Voting.)  For instance,
under sincere voting the winner might be candidate A.  Those who dislike A
might then make adjustments which result (wittingly or unwittingly) in the
election of B.  Those who dislike B can then make adjustments that lead to
the election of C.  Those who dislike C might make adjustments leading to
the election of A.

This periodic problem can be fixed by introducing "damping":  If cyclical
behavior ensues the machine could randomly assign a certain fraction of
the voters to stop making adjustments after each step.  (This might
emulate a real-life situation, where people tire of responding to
ever-changing polls during the campaign and finally decide they'll just
vote sincerely on election day and take their chances).  Continue until we
reach a point where no voter has any incentive to change his strategy,
even if he hadn't already given up in disgust.  (The damping can be
deterministic, since the machine can have a pre-determined rule for which
fraction of voters will keep their previous strategies after each step,
and for how to round numbers.)

THE QUESTION:  Will a machine that operates via sequential adjustments,
with damping thrown in to get rid of oscillations, give voters an
incentive to lie to the machine?

MY ANSWER:  Yes.  The final outcome produced by such a voting machine
depends deterministically on the initial conditions.  Consider the vector

(N(input 1), N(input 2).....) where each element of the vector is the
integer number of voters who gave the machine each input.  This vector
contains all possible information on the initial state of the machine. 
With n candidates we can divide the input space into n regions, each
region corresponding to all possible inputs that will result in the
election of a particular candidate (the regions need not be connected or
simply connected).

If the initial condition is near the boundary of two different regions,
such that there is at least one voter who can change his ballot and move
to a different region of input space, then in general there can arise
situations where one of those swing-voters has an incentive to vote
insincerely.

What I have not demonstrated is that the incentive to vote insincerely can
include an incentive for a voter to rank somebody greater than or equal to
his first choice.  Let's assume that the input consists of cardinal
utilities, with a scale that has an arbitrarily large number of levels
(e.g. 0 to 10, 0 to 100, 0 to 6*10^23, whatever you like).

Consider two adjacent points on opposite sides of a boundary (adjacent
meaning that we can move from one to the other if a single voter changes
his ballot).  If at one of those points a particular voter distinguishes
between his first and second choices, and at the other point the voter
gives 2 candidates a tie for 1st place, AND the voter in question prefers
the outcome that occurs with a tie, then strong FBC is violated.

The whole problem comes down to how the input space is partitioned.  The
election method used by the SVM determines which strategies will improve
the outcome for a voter or group of voters, and hence which strategies the
machine will assign to voters and what the final outcome will be given
inputs.  We need to find a voting method that partitions input space in
such a way that strong FBC can never be violated.

I don't know whether this gets us anywhere, or whether it merely restates
the problem, but it's something to think about.  I do know that I’ve
narrowed down the number of ways in which the machine can operate, and
given a geometric criterion for strong FBC violations.

Actually, if we limit ourselves to a deterministic machine, then doesn’t
the Gibbard-Sitherwaite (spelling?) theorem hold?  If so, then the only
real question is whether it’s reasonable for me to limit the machine to a
deterministic mode of operation, which amounts to asking whether I was
right to argue that we might as well use random ballot once we admit
non-deterministic strategies.

Incidentally, if the SVM can't satisfy strong FBC then this suggests that
it is impossible for parties to always give good advice to their members. 
By affiliating with a party you reveal by implication information on your
preferences and utilities.  However, the impossibility of always
satisfying strong FBC means that even if the party had perfect info on the
other voters (via polling) it couldn't give you good advice.  Parties then
have no choice but to compromise on some issues.  By coming up with
policies that aren't in perfect harmony with the preferences of their core
supporters they essentially force their supporters to vote somewhat
insincerely.  However, the compromises help parties win by bringing in
swing voters, similar to reeling in voters to cross from one region of
input space to another.  Maybe not a perfect analogy, but interesting....



Anyway, that’s all for now, folks.




Alex


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