[EM]

[Alex Small]

I want to consider a proof of the Gibbard-Satterthwaite Theorem.  It's
similar to something in Donald Saari's _Basic Geometry of Voting_, but not
exactly the same.  If the proof below is valid then I can use similar
methods to complete my work on strong FBC.  More on that in a later post. 
For now, I need constructive feedback on this proof.

Assume we have 3 candidates and an election method that satisfies the
following reasonable criteria:

1) It is only a function of the number of voters with each preference
order.  (all voters treated equally)
2) Every voter has a strict (no equal rankings or truncation) and
transitive preference order.
3) If candidate A wins, and every voter then swaps A and B in his
rankings, B now wins.  If A wins and every voter swaps B and C in his
rankings, A still wins.  (all candidates treated equally)
4) Evenly Divided Electorate Assumption:  If equal numbers of people hold
each preference order then the election method gives a 3-way tie (this is
a reasonable constraint, and it is helpful for technical purposes).

I will prove that all such methods must give voters incentives to vote
insincerely.


The electorate is represented by a vector in 6-dimensional space, each
direction representing the number of voters with a different preference
order.  To make the presentation more transparent, I won't represent
vectors as ordered lists, e.g. (2,1,9,2,4,6).  You then have to remember
which position in the list corresponds to which type of voter.  Instead, I
will define and use a notation called Dirac Notation.  It's actually quite
convenient, and I hope it catches on here:

A vector V is represented by the symbol |V>.  If I want to represent the
electorate with the vector |E>, I might write:

|E> = 10 |ABC> + 11 |BCA> + 3 |CBA>

to indicate that 10 people have the preference A>B>C, 11 people have the
preference B>C>A, and 3 people have the preference C>B>A.  The
coefficients might of course be fractions rather than integers, or real
numbers between 0 and 100 if they represent percentages.

Obviously, vectors can have negative coefficients.  Such vectors wouldn't
represent electorates, but they might represent changes of opinion, so
that |E> + |ABC> - |CBA> means that a person changed his opinion from
C>B>A to A>B>C.

One particularly important vector is

|I> := |ABC> + |ACB> + |BAC> + |BCA> + |CAB> + |CBA>

Finally, dot products:  Suppose we have a vector |N> and we want to dot it
with the vector |E> (perhaps if |N> dot |E> = 0 we have a tie between two
candidates).  We write the product |N> dot |E> as <N|E> or <E|N>.  The
order doesn't matter unless we use imaginary numbers, which we obviously
won't do here (imaginary numbers don’t belong in politics, except when
politicians are making budget forecasts).

OK, consider the set of all vectors |E> such that
1)  <E|ABC>, <E|ACB>, <E|BAC>, <E|BCA>, <E|CAB>, and <E|CBA> are
non-negative, and
2)  <E|I> = 1 (number of voters is held constant)

All such vectors are valid electorates.  Our election method partitions
this 5-dimensional region into 3 different 5-dimensional regions
corresponding to a victory for each candidate.  It also defines 4D regions
corresponding to 2-way ties, and 3D regions corresponding to 3-way ties.

Suppose that for a particular electorate |E1> candidate B wins, and that
|E> is close to the 4D surface where A and B are tied.  The “tie surface”
may be curved, but we’ll assume that it is locally flat, so that in the
vicinity of |E1> it can be approximately defined by the equation <N1|E> =
0.  (|N1> is the normal to the A-B interface in the vicinity of |E1>.)

Assume further that if <N1|E> > 0 then A wins, and if <N1|E> < 0 then B
wins, so that:

<N1|E1> < 0.

Voters with the preference order |ABC> have an incentive to insincerely
list their preference as x>y>z (where x>y>z is any ranking other than
A>B>C) if

<N1| (|E1> + s |xyz> - s |ABC>)  >= 0               for 0<s<1

We therefore conclude that, to avoid insincere voting by those who prefer
A to B,

<N1| (|E1> + s |xyz> - s |ABC>)  <= 0               for 0<s<1

or

<N1|xyz> <= <N1|ABC>

The same reasoning holds for the factions A>C>B and C>A>B, so we get

<N1|ABC> = <N1|ACB> = <N1|CAB>  >=  <N1|BAC>, <N1|BCA>, <N1|CBA>


Now, consider another electorate |E2> in the vicinity of |E1> so that we
can still approximate the normal to the interface as |N1> but in a region
where A wins, so that

<N1|E2>  >  0

Without going through the algebra again, apply the same reasoning to
ensure that factions preferring B to A have no incentive to vote
insincerely.  We get the conclusion that

<N1|ABC>=<N1|ACB>=<N1|CAB>  >=  <N1|BAC>=<N1|BCA>=<N1|CBA>

Without loss of generality, we conclude that at every point along the
interface between A’s victory region and B’s victory region, the normal
vector is of the form

|N> = (|ABC> + |ACB> + |CAB>) – r*(|BCA> + |BAC> + |CBA>)

where r may vary from point to point.  r must be positive, or else no
electorate can satisfy the condition

<N|E> <= 0.


We can use similar reasoning at the B-C and A-C interfaces.  Indeed, our
symmetry criterion (3) requires this.  Finally, we conclude that in the
vicinity of the electorate specified by

|E> = (|ABC> + |ACB> + |BAC> + |BCA> + |CAB> + |CBA>)/6 = |I>/6

the norms to all interfaces must have r = 1.  This is to satisfy our
assumption (4) concerning evenly divided electorates.

The problem is that, at least when r = 1, the inner products <E|Nij>
(|Nij> is the normal to the boundary between regions where i wins and
regions where j wins) give the margins in pairwise contests, and our
assumptions require us to select a Condorcet winner.  However, there are
cases where no Condorcet winner exists (indeed, all cases in the vicinity
of |I>/6 have no Condorcet winner).

Trying to make an election method non-manipulable and still follow our
assumptions hence leads to a paradox, and so our assumptions preclude
non-manipulable election methods.



Feedback from list members?


Three comments of my own:

1) My criteria are more restrictive than those of Gibbard and
Satterthwaite, and Pareto optimality is not explicitly used.  However, my
criteria seem quite reasonable for public elections, and I never needed to
invoke Pareto.
2) It is interesting to me that the Condorcet paradox lies at the heart of
this proof.  Indeed, it is easy to show that Condorcet Voting would be
strategy-proof if life were such that pairwise preferences couldn’t yield
cycles.
3) It would be easy to extend this proof to arbitrary numbers of
candidates.  For convenience I stuck to three.


Thank-you to those who read all the way through this long post.



Alex



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