[EM] Strong FBC--This time it's personal! ; )

[Alex Small]

Strong FBC:  Revisited.

I won’t actually prove that strong FBC is impossible, but I will prove
that Approval Voting is superior to any ranked method if your goal is to
let voters defend their interests without betraying their favorite.  I
apologize for the length, but the methods I’m using require some
explanation.  I know that a year ago I posted a retraction of a similar
argument.  I wasn’t sufficiently careful with my use of symmetry
conditions, so my conclusions were nullified.  Here I’m more careful, and
instead of trying to tackle the most ambitious aspect of the problem
(showing that strong FBC is impossible) I just show that any method
satisfying strong FBC would be inferior to Approval Voting.



PRELIMINARIES:

I’ll consider the case of 3 candidates.  I’ll consider a method that uses
ranked ballots.  For simplicity we won’t consider equal rankings.  Since
all voters are treated equally, and since there are 6 possible preference
orders, the space of all possible electorates is 6-dimensional.  We can
think of a ranked voting method as one that partitions the 6-dimensional
space of all possible electorates into 3 regions.  Each region corresponds
to victory for one of the 3 candidates.

I will be considering the properties of the surfaces that separate these 3
regions.  I will usually represent these surfaces with the linear equation
Nxy*E = 0, where Nxy is a vector normal to the boundary between the region
where x wins and the region where y wins, E is a vector representing a
point in the space of all possible electorates, and “*” denotes a scalar
product, AKA dot product, AKA inner product, for those who know linear
algebra.

Say that we’re looking at the boundary between the region where A wins and
the region where B wins.  We’ll call the normal to this boundary Nab.  If
Nab*E >0, A wins.  If Nab*E < 0 B wins.  If Nab*E = 0 then there’s a tie. 
(We’re assuming that in this region of electoral space C cannot win.)  We
won’t require that Nab be the same everywhere.  For instance, consider
Condorcet methods.  In some regions of electoral space the condition
determining whether A or B wins will be that A defeats B pairwise.  In
other regions of electoral space the condition might be that A’s margin of
victory over B exceeds B’s margin of victory over C.  The form of Nab will
depend on which region of electoral space we’re in.

When we actually write down the form of Nab, we’ll use a simple notation: 
The notation “ABC” will denote unit vector pointing in the direction of
adding more voters with the preference A>B>C.  Remember, this is a
six-dimensional space of all possible electorates.  Say we want to
represent an electorate where 30% of the voters have the preference A>B>C,
45% have the preference B>A>C, and 25% have the preference C>A>B.  We
could denote this electorate as

E = 30 ABC + 45 BAC + 25 CAB

Now say that some of the C>A>B voters want to change their ballots to
insincerely say A>B>C, because B is the plurality winner and they would
prefer A over B.  We could denote this change by saying that the change in
the electorate vector is

delta E = 16(ABC – CAB).




THE STRONG FAVORITE BETRAYAL CRITERION:

We know that we can’t stipulate that a method never give a voter an
incentive to vote insincerely.  The Gibbard-Satterthwaite Theorem says
that any non-dictatorial and Pareto efficient ranked method will be
manipulable.  We examine a weaker condition:  The voting method should
never give us an incentive to rank our favorite candidate below first
place, or rank another candidate equal to our sincere favorite.  Or, if
there is an incentive to rank your favorite below the first place, it
should be possible to achieve the same outcome through some other means,
namely by reversing the rankings of your second and third choices, while
leaving your favorite in first place.

We call this criterion “strong FBC” to distinguish it from “weak FBC”,
which stipulates that you should never have an incentive to rank another
candidate ahead of your favorite, but you _might_ have an incentive to
rate another candidate _equal to_ your favorite.  Approval voting
satisfies weak FBC but flunks strong FBC.

(Some might find the condition less than compelling, but other people have
a strong desire to sincerely support their favorite, so the goal is to
find out whether it can be satisfied.)

An example of a method that satisfies strong FBC (the only strictly ranked
method that does for 3 candidates, to the best of my knowledge) is
“Negative Voting”:  You indicate your preference order, and the method
assigns one vote apiece to your favorite and middle candidates, and no
vote to your least favorite.  This still violates the “spirit” of strong
FBC, however, because it doesn’t give any special status to your favorite.
 This method and its various properties will come up throughout this
posting.



SYMMETRY

We’ll assume and require that our election method treats all candidates
equally.  (Sorry, Florida... ;)  Say that we’re near the A-B boundary in
voter space.  It’s possible that that one of the factions (e.g. A>C>B)
might have no incentive to vote insincerely for the purpose of helping A
win instead of B.  It’s possible that another faction (e.g. A>B>C) might
have an incentive to vote insincerely for the purpose of helping A defeat
B.  It all depends on the details of our ranked method.  However, symmetry
makes the following demands on us:

1)  If a faction with a given preference order (e.g. A>C>B) has no
incentive to vote insincerely for the purpose of helping A defeat B, then
a faction that reverses A and B in its preference order (e.g. B>C>A)
should likewise have no incentive to vote insincerely.  The method should
not treat A’s supporters any differently from B’s supporters.

2)  Conversely, if a given faction (e.g. A>B>C) has an incentive to
insincerely swap its second and third choices to help A defeat B (e.g.
insincerely report A>C>B) then a faction that has the reverse opinion of A
and B (e.g. B>A>C) should also have an incentive to insincerely swap its
second and third choices (e.g. report B>C>A) to help B defeat A.

3)  If a faction with a given preference order (e.g. A>C>B) has no
incentive to vote insincerely to help A defeat B, then when we permute the
candidates (e.g. A->B, B->C, C->A) the statement should still be true.
(e.g. voters with the preference B>A>C should have no incentive to vote
insincerely to help B defeat C.)

4)  If a faction with a given preference order (e.g. A>B>C) has an
incentive to insincerely swap its second and third candidates to help A
defeat B, then when we permute the candidates (e.g. A->B, B->C, C->A) the
statement should still be true.  (e.g. voters with the preference B>C>A
should have an incentive to swap C and A to help B defeat C.)

These symmetry conditions greatly simplify our analysis.  Instead of
considering the strategic incentives faced by all 6 factions at the 3
different boundaries, we only need to consider the strategic incentives
faced by 3 factions at a single boundary, and everything else followed
from symmetry.



MORE ON THE GEOMETRY OF ELECTORATE SPACE:

Let’s consider the A-B boundary.  Say that a XYZ faction prefers A to B. 
The condition for A to win is Nab*E > 0.  If that faction has no incentive
to vote insincerely for the purpose of helping A defeat B, then XYZ*Nab
must be greater than or equal to RST*Nab, where RST is any other faction. 
Otherwise, voters from the faction XYZ could increase E*Nab by reporting
their preference as RST.  Likewise, if XYZ preferred B to A, and we
stipulated that XYZ never have an incentive to vote insincerely to help B
defeat A, then we’d require that XYZ*Nab be less than or equal to RST*Nab,
where RST is any other preference order.

On the other hand, suppose that XYZ has an incentive to help A defeat B by
reporting the (insincere) preference X>Z>Y.  Then Nab*XZY must be less
than or equal to Nab*RST, where RST is any other preference order.  Or,
suppose that XYZ prefers B to A, and that it has incentive to help B
defeat A by reporting the (insincere) preference X>Z>Y.  Then Nab*XZY must
be less than or equal to Nab*RST, where RST is any other preference.

In both cases where a faction XYZ has an incentive to vote insincerely,
the strong FBC criterion tells us absolutely nothing about Nab*XYZ, but it
does tell us something about Nab*XZY.  It is in the cases where a faction
has an incentive to vote insincerely that we have some freedom in
specifying the form of Nab.  The form of Nab can then vary from place to
place in electoral space, as it does in many methods.  (e.g. in IRV the
form of Nab depends on whether a candidate won with an outright majority
of first-place votes, or if instead an elimination had to be held.  In
Condorcet it depends on whether or not there’s a cycle to be resolved.)

So, strong FBC tells us something about which components of Nab must be a
maximum or minimum.  We’ll assume that the maximum and minimum components
of Nab are +1 and -1.  One of those components can be chosen completely
arbitrarily.  The other one requires careful consideration, because it is
NOT necessarily true that Nab will change sign if we swap A and B.  (To
persuade yourself of this, consider any method that selects the first
choice of a majority when such a candidate exists.  If we’re testing to
see whether A is the first choice of the majority, then Nab will be ABC +
ACB – BAC – BCA – CAB – CBA.)  However, we will impose the reasonable
requirement that if one person’s vote helps A defeat B, there should
always be a way for another person to vote so that he or she cancels out
the first person’s vote, at least with regard to the choice between A and
B.  In that case, if the maximum component of Nab is +1, then the minimum
component must be -1.



ANALYSIS  Here’s where the good stuff begins.

Now, let’s consider the boundary between the A region of electorate space
and the B region.  We’ll start with the faction C>A>B.  If this faction
never has an incentive to vote insincerely (for the purposes of helping A
defeat B) then Nab*CAB = 1 and Nab*CBA = -1.  On the other hand, if the
faction C>A>B sometimes has an incentive to vote insincerely to help A
defeat B then CBA*Nab = +1, and CAB*Nab = -1.  Either way, those two
components of Nab will be constant rather than varying.  We have no
freedom to pick them except for choosing their signs.  For convenience, we
will confine our attention to the case where Nab*CAB = +1 and Nab*CBA =
-1.  This also implies Nbc*ABC = +1, Nbc*ACB = -1, Nca*BCA = +1, and
Nca*BAC = -1.  We will see below that this convention does not undermine
our main argument.

Next consider the factions A>B>C and A>C>B (as well as the other two
factions with opposite opinions of A and B).  If neither faction can help
A defeat B by voting insincerely, then Nab*ABC and Nab*ACB will both be
+1, and Nab*BAC and Nab*BCA will both be -1.  The same form of Nab would
obtain if ABC and ACB both had an incentive to help A defeat B by voting
insincerely.  ABC’s incentive would imply that Nab*ACB = +1, and ACB’s
incentive would imply that Nab*ABC = +1.  Leave aside the logical
inconsistency there, the point is that the same form would obtain.

It is straightforward to obtain the forms of Nbc and Nca as well, and see
that Nbc, Nca, and Nab will be linearly independent because they are
constant rather than variable.  Linear independence leads to paradoxes,
because we can have an electorate that’s 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.  This paradox occurs regardless of which convention we pick with
regard to Nab*CAB.  So it is clear that either ABC or ACB (but not both)
must, at least sometimes, have an incentive to help A defeat B by
insincerely swapping the second and third candidates.

We will limit ourselves to the case where the A>B>C faction has an
incentive to vote insincerely, but not the A>C>B faction.  By following
this convention, as well as our convention for Nab*CAB, we have a
monotonic method.  Monotonicity may or may not be a crucial feature for a
voting rule, but we will see later that it does not undermine our basic
argument.  Since it does not undermine our results, and since many people
consider it desirable, we will for now stick to monotonic methods.

The form of Nab is therefore:

Nab = ACB + CAB – BCA – CBA + g1(E)*ABC – g2(E)*BAC

g1(E) and g2(E) are functions of E, our vector in electorate space.  The
signs in front of g1 and g2 are arbitrary and chosen for convenience.  To
find Nbc and Nca, one would permute A, B, and C in the components of Nab,
and also permute A, B, and C in E (the argument of g1 and g2).  We note
that if g1 and g2 are identically zero then we have Negative Voting.

Instead of exploring the properties of g1(E) and g2(E) to determine
whether these functions can ever be non-zero without producing a paradox,
we will explore how voters will act when faced with an election using a
method from the family proposed here.

Suppose that the electorate is in a region of electorate space close to
the A-B boundary.  This amounts to a race with 2 chief contenders. 
Anybody who has the preference A>B>C will insincerely vote A>C>B when
g1<1, and anybody who has the preference B>A>C will insincerely vote B>C>A
when g2<1.  The result is de facto Negative Voting.

Of course, the problem with Negative Voting is that everybody voting
against either A or B is obliged to vote for C.  This is fine for those
who consider C their favorite, but not for those who consider A or B their
favorites, and even worse for those who consider C their least favorite. 
It is obvious that Approval Voting and other rated methods, which give the
option of equal rankings for first place, are superior to any ranked
method that attempts to satisfy Strong FBC.  Personally, my favorite such
method is Majority Choice Approval, since it gives voters a way to make
support for their second choice contingent on how other people vote.




Final Thoughts:

1)  Can we go beyond my analysis and actually prove that paradoxes are
inevitable if g1 and g2 are non-zero in a region of electorate space with
non-zero measure?

2)  Would anybody here be interested in helping me clean up these results
and make it more readable for publication?  I’m looking for a co-author. 
Surely there must be a few people here who are accustomed to publishing
scholarly papers and interested in adding to the literature a convincing
case that Approval Voting is superior to any ranked method when one
considers strategy and sincerity.

3)  Does anybody have ideas for how to extend these results to 4 or more
candidates?  It’s difficult because right off the top of my head I can
think of numerous methods that satisfy strong FBC (albeit in the
disappointing way that Negative Voting does):  Vote for the top 2, or vote
for the top 3, or give 1 vote apiece to the top 2 and a half vote to the
third-choice candidate on your ballot, etc.  With a little thought I could
probably come up with variants on other methods as well.