[EM] Strong FBC, at last

[Alex Small]

At long last, the proof that satisfying strong FBC requires a method
equivalent to "Top 2 Voting" when we have 3 candidates.  The proof is
lengthy, but here it is.  At the end I mention problems with generalizing
to 4 or more candidates, and also opine that top 2 voting is Approval
Voting if we allow truncation.

Without further ado...

The Strong Favorite Betrayal Criterion:

An election method passes the strong favorite betrayal criterion if a
voter insincerely ranking another candidate ahead of his can never obtain
a better result than he could obtain by either voting sincerely, or
insincerely altering the rankings of candidates lower on his list.

Theorem:  When there are 3 candidates, any election method which meets the
following criteria is equivalent to “top 2 voting”:

1)  Strong Favorite Betrayal
2)  Anonymity:  The method is only a function of the number of voters with
each strict and transitive preference order among the three candidates.
3)  Neutrality:  If candidate A wins, and all voters then swap A and B in
their rankings, candidate B should win.  If candidate C wins, and all
voters then swap A and B in their rankings, candidate C should still win.
4)  Partial Decisiveness:  In the 5 dimensional space of admissible
electorates, the election method returns a decisive result for all
electorates not lying in a 4 dimensional subset of the electorate space.

“Top 2 Voting”, AKA “Negative Voting”, AKA “Anti-Plurality Voting”, gives
a single vote to each of the top 2 candidates on a person’s ballot, and
gives no vote to the bottom candidate on that ballot.


Notation:

I will represent the electorate with a 6-dimensional vector E.  In the
basis normally used, each component of the vector gives the fraction of
the electorate with a particular preference order.  Because the fractions
cannot be negative and must add up to 1, the components of E must also be
non-negative and add up to 1.  This constraint means that the set of
admissible electorates is 5 dimensional.

The normal method of representing vectors as ordered lists of numbers
(e.g. (0.5, 0.3, 0, 0, 0.1, 0.1)) is cumbersome to the extent that it
requires one to remember which preference order corresponds to which
position in the list.  We will instead use Dirac notation.  A vector E is
written as |E>.  To denote an electorate in which half of the voters have
the preference A>B>C and the other half have the preference B>C>A we write

|E> = 0.5 |ABC> + 0.5 |BCA>

Similar notation holds for the 4 other possible preference orders with 3
candidates.

Inner products of vectors, also known as dot products, are written as
<V|E> = <E|V> = |V> dot |E>.  The order of V and E is irrelevant as long
as we’re dealing with real numbers (which we shall obviously do here).

Finally, I will define an “Identity Vector”

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

I call this an identity vector because <E|I> = 1 if |E> is normalized so
that each component is the fraction of the electorate with a given
preference order and the fractions add to 1.



Now, the proof:


An election method partitions the 5D space of electorates into 3 separate
5D regions.  Each region corresponds to the victory of a particular
candidate.  The neutrality requirements put certain constraints on the
boundaries between regions:

Consider the boundary between the A region and the B region.  Call the
normal to the boundary |Nab>.  We can say without loss of generality that:

If <E|Nab> > 0 then A wins.
If <E|Nab> < 0 then B wins.
If <E|Nab> = 0 then there is a tie between A and B.

Note that |Nab> need not be constant throughout electoral space. 
Boundaries can in principle have curves or kinks in them.  However, we can
assume that the boundaries are locally flat except in the vicinity of
kinks.

Now, consider an electorate |E1> in the vicinity of the boundary between
the A and B regions of electorate space.  Suppose that <Nab|E1> < 0, so
that B wins.  We will consider the conditions imposed by
non-manipulability and strong favorite betrayal.

The voters with the preference order A>B>C will obviously be willing to
vote insincerely if they believe that doing so can cause A to win instead
of B.  Suppose that they consider the possibility of insincerely reporting
the preference A>C>B.  This is equivalent to changing the electorate in
the manner represented by

|E2> = |E1> + d*(|ACB> - |ABC>)

where d indicates the (positive) fraction of the electorate insincerely
changing its reported preference.  Note that the same notation could also
be used to denote a fraction d of the electorate sincerely changing its
mind and concluding that C is superior to B.

Suppose that there is no situation for which the voters with preference
A>B>C can cause A to win instead of B by reporting A>C>B.  This means that

<E2|Nab> <= 0

or

< Nab|E1> + d*(<Nab|ACB>-<Nab|ABC>) <= 0.

If <Nab|ACB> - <Nab|ABC> were positive we could pick |E1> to be
arbitrarily close to the A-B boundary, and for some admissible value of d
the above inequality would be violated, so we must conclude that

(1)     <Nab|ACB> - <Nab|ABC>  <=  0.

If we further impose the condition that voters with the preference A>B>C
can NEVER cause A to win instead of B by voting insincerely, we can go
through the same reasoning for any other insincere preference order and
conclude that

(2)     <Nab|ABC>  >=  <Nab|any other preference order>.

We can immediately draw conclusions about <Nab|BAC> by using the result
(proved in Appendix 2) that swapping A and B multiplies |Nab> by -1.  One
consequence is that

(3a)     <Nab|ABC> = - <Nab|BAC>,
or
(3b)     <Nab|BAC>  <=  <Nab|any other preference order>

Alternately, rather than removing any incentive for the faction A>B>C to
vote insincerely, we could simply specify that those voters never have any
incentive to insincerely rank another candidate ahead of their true
favorite, but do have an incentive (in at least some cases) to insincerely
report the ranking A>C>B.  So, if a portion p of the electorate could
cause A to win instead of B by reporting, say, C>A>B rather than A>B>C,
they could also cause A to win instead of B by reporting A>C>B rather than
A>B>C.

Before going through the mathematics, one obvious situation exhibiting the
aforementioned behavior would be “top 2 voting”, which, as mentioned
before, gives one vote each to a voter’s top 2 candidates.  Voters with
the preference A>B>C give equal votes to A and B and hence have no impact
on the outcome of a close contest between A and B.  They have an incentive
to list B in last place and raise C’s ranking (assuming it isn’t a close
3-way contest).  They could deny B a vote by reporting the preference
A>C>B or the preference C>A>B.  Since both strategies accomplish the same
end, there is no incentive to insincerely list another candidate ahead of
A.

The condition that the A>B>C faction can cause A to win instead of B
without ranking another candidate ahead of A can be formulated as:

If <Nab|E>  <=  0 (so that B wins)
and
<Nab|E> + p*( - <Nab|ABC> + <Nab|any ranking with A below 1st place>) >=  0
then
<Nab|E> + p*( - <Nab|ABC> + <Nab|ACB>)  >=  0.

This implies that

(4)     <Nab|ACB>  >=  <Nab|any ranking with A below 1st place>

and using the results of appendix 2 implies that

(5)     <Nab|BCA>  <=  <Nab|any ranking with B below 1st place>


Now, in order for an election method to satisfy Strong FBC, at each
boundary each faction must either have no incentive to vote insincerely,
or be able to obtain a better outcome by insincerely swapping their second
and third choices while leaving their favorite in the top rank.  However,
since we can obtain the normals to the C-A and B-C boundaries from the
normals to the A-B boundary and the neutrality condition it is only
necessary to examine the A-B boundary (see appendix 3).  Also, since the
normal to each boundary has only 3 independent components (see appendix
2), we really need to examine the strategic incentives facing 3 factions. 
This gives 2^3 = 8 cases to consider.

The remainder of the proof proceeds as follows:  We will apply each of the
8 possible combinations of conditions to obtain the normals to the A-B,
B-C, and C-A boundaries.  If the conditions imposed are inconsistent then
there will exist electorates which are on the A side of the A-B boundary,
the B side of the B-C boundary, and the C side of the C-A boundary.  We
will see that the only cases that do not lead to such a cyclic ambiguity
are “top 2 voting” and a method that is strategically equivalent to “top 2
voting.”

We should clarify one point about cyclic ambiguities:  There are
well-defined Condorcet voting methods, which elect the Condorcet Winner
(CW) when one exists, and use an auxillary procedure when no CW exists. 
In those methods the boundaries in electorate space are curved or kinked,
so that the normals can vary from point to point in electorate space. 
However, the conditions that we impose concerning strategic manipulation
will place severe limits on the degree to which the boundaries can be
curved or kinked, so that no auxillary procedure will be admissible to
resolve ambiguities.

The cases are identified in Table 1, where “y” indicates that the faction
can sometimes cause its favorite of {A, B} to win by voting insincerely,
and “n” indicates that the faction has no incentive to vote insincerely,
at least in regards to the choice between A and B.


Table 1:
                                                              Factions
Case      |      A>B>C/B>A>C    |    A>C>B/B>C>A      |     C>A>B/C>B>A

1                  n                       n                      n
2                  n                       n                      y
3                  n                       y                      n
4                  n                       y                      y
5                  y                       n                      n
6                  y                       n                      y
7                  y                       y                      n
8                  y                       y                      y

Case 1 can be ruled out by the Gibbard-Satterthwaite Theorem, although we
shall show that the methods of our proof embrace that result.  Indeed, in
regard to 3-candidate elections our result yields more information than
the Gibbard-Satterthwaite Theorem, in that it shows that only one ranked
election method gives no incentives for a particular type of insincere
voting, and that system is also known to be manipulable.

Using (2), (3a), (4), and (5) we get the following inequalities:

Case 1:  <Nab|ABC>, <Nab|ACB>, <Nab|CAB>  >=   <Nab|All other preferences>


Case 2:  <Nab|ABC>, <Nab|ACB>  >=  <Nab|All other preferences>
                    <Nab|CBA>  >=  <Nab|All preferences with C below 1st
                                                                  place>

Case 3:  <Nab|CAB>, <Nab|ABC>  >=  <Nab|All other preferences>

Case 4:             <Nab|ABC>  >=  <Nab|All other preferences>
                    <Nab|CBA>  >=  <Nab|All preferences with C below 1st
                                                                  place>

Case 5:  <Nab|CAB>, <Nab|ACB>  >=  <Nab|All other preferences>

Case 6:             <Nab|ACB>  >=  <Nab|All other preferences>
                    <Nab|CBA>  >=  <Nab|All preferences with C below 1st
                                                                  place>

Case 7:  <Nab|ABC>, <Nab|ACB>, >Nab|CAB>  >=  <Nab|All other preferences>

Case 8:  <Nab|ABC>, <Nab|ACB>  >=  <Nab|All other preferences>
                    <Nab|CBA>  >=  <Nab|All preferences with C below 1st
                                                                  place>

These inequalities, along with the result of appendix 2 concerning
swapping A and B, determine |Nab> up to an irrelevant positive
multiplicative factor, and in some cases a factor -1 <= G <= 1 that can
vary throughout electorate space to give a curved or kinked boundary.  The
neutrality condition allows us to obtain |Nbc> and |Nca> from |Nab>.

Case 1:  |Nab> = |ABC> + |ACB> + |CAB> - |BAC> - |BCA> - |CBA>
         |Nbc> = |BCA> + |BAC> + |ABC> - |CBA> - |CAB> - |ACB>
         |Nca> = |CAB> + |CBA> + |BCA> - |ACB> - |ABC> - |BAC>

Case 2:  |Nab> = |ABC> + |ACB> + |CBA> - |BAC> - |BCA> - |CAB>
         |Nbc> = |BCA> + |BAC> + |ACB> - |ABC> - |CAB> - |CBA>
         |Nca> = |CAB> + |CBA> + |BAC> - |BCA> - |ABC> - |ACB>

Case 3:  |Nab> = |ABC> + |CAB> - |BAC> - |CBA> + Gab*(|ACB> - |BCA>)
         |Nbc> = |BCA> + |ABC> - |CBA> - |ACB> + Gbc*(|BAC> - |CAB>)
         |Nca> = |CAB> + |BCA> - |ACB> - |BAC> + Gca*(|CBA> - |ABC>)

Case 4:  |Nab> = |ABC> + |CBA> - |BAC> - |CAB> + Gab*(|ACB> - |BCA>)
         |Nbc> = |BCA> + |ACB> - |CBA> - |ABC> + Gbc*(|BAC> - |CAB>)
         |Nca> = |CAB> + |BAC> - |ACB> - |BCA> + Gca*(|CBA> - |ABC>)

Case 5:  |Nab> = |CAB> + |ACB> - |CBA> - |BCA> + Gab*(|ABC> - |BAC>)
         |Nbc> = |ABC> + |BAC> - |ACB> - |CAB> + Gbc*(|BCA> - |CBA>)
         |Nca> = |BCA> + |CBA> - |BAC> - |ABC> + Gca*(|CAB> - |ACB>)

Case 6:  |Nab> = |CBA> + |ACB> - |CAB> - |BCA> + Gab*(|ABC> - |BAC>)
         |Nbc> = |ACB> + |BAC> - |ABC> - |CAB> + Gbc*(|BCA> - |CBA>)
         |Nca> = |BAC> + |CBA> - |BCA> - |ABC> + Gca*(|CAB> - |ACB>)

Case 7:  |Nab> = |ABC> + |ACB> + |CAB> - |BAC> - |BCA> - |CBA>
         |Nbc> = |BCA> + |BAC> + |ABC> - |CBA> - |CAB> - |ACB>
         |Nca> = |CAB> + |CBA> + |BCA> - |ACB> - |ABC> - |BAC>

Case 8:  |Nab> = |ABC> + |ACB> + |CBA> - |BAC> - |BCA> - |CAB>
         |Nbc> = |BCA> + |BAC> + |ACB> - |ABC> - |CAB> - |CBA>
         |Nca> = |CAB> + |CBA> + |BAC> - |BCA> - |ABC> - |ACB>


Given these normals, how do we determine if they give rise to a paradox? 
If the electorate |E> has positive projection onto |Nab>, |Nbc>, and |Nca>
then we clearly have a paradox.  As long as the 3 normal vectors are
linearly independent it is possible to find a vector |E> with non-negative
projections onto the normals.  If the vector does not represent an
admissible electorate with non-negative numbers of voters in each
category, we can always multiply |E> by some small positive number, add to
that |I>/6, and then multiply by another positive number to satisfy our
normalization condition.  So, linear independence of the normals is
necessary.

Since cases 1, 2, 7, and 8 all have uniquely specified normals that do not
admit curved or kinked boundaries, it is easy to show that the normals are
linearly independent and cycles are possible.  Note in particular that in
cases 1 and 7 the products <E|Nxy> just correspond to x’s margin of
victory over y in a pairwise contest, and a candidate must win all
pairwise contests to win the election.  Since this is not always possible,
cases 1 and 7 are excluded by Condorcet’s paradox.

Cases 3 through 6 require more careful consideration.  Since the factor g
can vary throughout electorate space, when we compute <E|Nab> to determine
the electorate’s position relative to the A-B boundary, what value of g do
we use?

It turns out that this issue is irrelevant in cases 3 and 6.  We can
construct an electorate of the form

(6)     |E> = |I>/6 + q*(|Nab> + |Nbc> + |Nca>)

where q is some constant, and since the normals are orthogonal to |I> this
electorate has the necessary normalization <E|I>.  In cases 3 and 6, we
get

<E|Nab> = q*(8 - 2Gca - 2Gbc + Gab(Gab-2))

which is positive when Gab, Gbc, and Gca are between -1 and 1.  Permuting
the indices gives us the values of <E|Nbc> and <E|Nca>, so we see that
case 3 gives rise to paradoxes regardless of how we construct the
boundaries.

Now we come to cases 4 and 5.  Once again, construct an electorate of the
form (6), and we get

<E|Nab> = q*(Gab)^2

with similar relations for <E|Nbc> and <E|Nca>.  Since all of the products
will be positive, we hence have a cyclic paradox unless Gab, Gbc, and Gca
are identically zero.

So, what are the voting systems that we have in cases 4 and 5?  How do we
interpret the normals?  Well, case 5 is just “Top 2 voting”, the method
described earlier.  Case 4 is a bizarre system known as “Top and Bottom
Voting” which gives a vote to a person’s favorite and least favorite
candidates, and no vote to a person’s middle candidate.  Strategically
this is just the converse of “Top 2 Voting.”  Whenever a person’s optimal
strategy is to vote sincerely in top 2, he will insincerely swap his
second and third choices in Top and Bottom.  Likewise, a person who would
insincerely swap his second and third choices in Top 2 will vote sincerely
in Top and Bottom.

We can hence say that, with 3 candidates, any ranked election method that
satisfies strong FBC, anonymity, neutrality, and partial decisiveness is
equivalent to Top 2 Voting.  This satisfies strong FBC only in a very weak
sense, since the method makes no actual distinction between a voter’s
first and second choices.

However, without contradicting the above results, we can augment the
method to make a meaningful distinction between first and second place
when there is an exact tie between 2 candidates.  When there is an exact
tie, we can stipulate that the tie shall be broken by a pairwise
comparison of the top 2 candidates.  (If there is also a pairwise tie, or
a 3-way tie, then we must still determine the winner by a 5-4 Supreme
Court ruling.)  There is no contradiction of our result because we never
addressed who will win if the electorate falls exactly on a boundary.

Generalizing this result to 4 or more candidates would be a formidable
challenge.  One problem is that there are plenty of methods that satisfy
strong FBC with 4 or more candidates.  Top 2 Voting, Top 3 Voting, etc.
all satisfy strong FBC.  A modified Borda Count that gives equal points to
the top 2 candidates and successively fewer points for each candidate
lower on the list also satisfies Strong FBC.  And then there are perverse
generalizations of “Top and Bottom” which no reasonable person would ever
propose, but which the math requires us to nonetheless consider when
enumerating all possible cases.  Moreover, there are many more ways to
vote insincerely without betraying your favorite, and we have to consider
the possibility that one of those strategies will protect a voter’s
interests.  Clearly, some different approach is needed to handle 4 or more
candidates.  I would observe, however, that if this result for 3
candidates is rigorous then it is certainly interesting negative evidence
against the possibility of ever satisfying Strong FBC and making a
meaningful distinction between first and second place.

Despite the lack of generality, there is one very interesting consequence.
 When using Top 2 Voting, the most natural way to interpret a truncated
ballot (A ballot that only lists a first choice) is to give the first
choice a single vote and give no vote to either of the other candidates. 
By allowing truncation in this manner we end up with Approval Voting.  In
some sense I have derived Approval Voting from the simple requirement that
voters never have an incentive to betray their favorite candidate when
there are 3 candidates and we use ranked ballots.


Appendix 1:  Proof that the swap operator S(A, B) is Hermitian:

Consider the basis vectors correspond to each preference order.  Call two
such vectors |pqr> and |ijk>.  The swap operator S(A, B), acting on the
electorate represented by the vector |E>, exchanges candidates A and B in
each voter’s preference order.  It acts component-by-component, so that
S(A, B)|ABC> = |BAC>, and similar relations hold for the other preference
orders.

The inner product of |pqr> and S(A, B)|ijk> is written as

<pqr|S(A, B)|ijk>

where it is understood that S(A, B) acts on the vector to its right.  The
above inner product is equal to zero unless |pqr> and |ijk> differ only by
the exchange of candidates A and B, in which case the inner product is 1. 
Since this is true for <pqr|S(A, B)|ijk> and <ijk|S(A, B)|pqr>, it
therefore follows that S(A, B) is Hermitian.



Appendix 2:  Normals to interfaces

Consider the normal to the A-B interface, |Nab>.  We know that if <Nab|E>
> 0 then A wins, and if <Nab|E> < 0 B wins.  Moreover, if <Nab|E> > 0 then
<Nab|S(A, B)|E> < 0 so that B wins when we swap A and B (as required by
the neutrality condition).  Likewise, if <Nab|E> < 0 then <Nab|S(A, B)|E>
> 0.  We hence get that

(A2.1)     <Nab|S(A, B)|E> = -<Nab|E>

However, because S(A, B) is Hermitian, we can reverse the order of
operations and get

(A2.2)     <E|S(A, B)|E> = - <E|S(A, B)|Nab>

Since this holds for any |E> we can conclude that

(A2.3)     S(A, B) |Nab> = - |Nab>.

It is straightforward to see that this condition is satisfied by any
vector of the form

(A2.4)     |Nab> = x*(|ABC> - |BAC>) + y*(|BCA> - |ACB>) + z*(|CAB> - |CBA>).

If we take the 3 vectors in parenthesis as part of our basis, we can
construct 3 other basis vectors to form a complete set:

(|ABC> + |BAC>), (|BCA> + |ACB>),  and (|CAB> + |CBA>)

We see that the vectors above are eigenvectors of S(A, B) with eigenvalue
+1, while |Nab> is a superposition of eigenvectors of S(A, B) having
eigenvalue -1.  Since the eigenvectors of S(A, B) form a complete set, and
since only three of those correspond to the eigenvalue -1, it follows that
the form given for |Nab> is completely general, and dictated solely by the
condition of neutrality.

Note that |Nab> can vary from point to point on a curved or kinked
surface, but at every point on that surface it must be an eigenvector of
S(A, B) with eigenvalue -1.

One practical consequence for the proof above is that |Nab> has only 3
independent components.  Also, <Nab|I> = 0.  Although the condition
<Nab|I> is not sufficient to implement the neutrality condition, it is a
useful took for checking results, and can be useful for ruling out
possibilities.



Appendix 3:  Obtaining the normals to the B-C and C-A boundaries from the
normals to the A-B boundary.

Suppose we have an electorate |E> such that <Nab|E>  >  0, so that A wins.
 Applying the swap operator S(A, C) to |E> causes C to win.  We see
immediately that if for any |E> such that

(A3.1)     <Nab|E>  >  0

it follows that

(A3.2)     <Nbc|S(A, C)|E>  =  <E|S(A, C)|Nbc>  >  0

(where |Nbc> is the normal to the boundary between the B and C regions of
electorate space)

then

(A3.3)     S(A, C)|Nbc>  =  |Nab>

Operating on both sides of (A3.3) with S(A, C) gives

(A3.4)     |Nbc>  =  S(A, C)|Nab>.

This result enables us to obtain the normals to all other boundaries in
electorate space if we have specified the A-B boundary.



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