[EM] Re: Arrow and Gibbard-Satterthwaite

[Steve Eppley]

Markus Schulze <schulze at speedy.physik.tu-berlin.de> wrote:
-snip-
> Only dictatorial methods (where one voter always gets his way)
> and random methods (where the probability of being elected is
> proportional to the number of votes) can meet IIAC and
> Gibbard-Satterthwaite.

It's unclear to me why Markus is using that definition of
random methods, but that's probably not an important question
for us.  I don't think any of us in the EM list are advocating
random methods, and I don't think the public would tolerate
much randomness.

Yes, those two are hard criteria to meet.  In other words, 
it would be silly to expect any decision-making method to be
"perfect".  A futile search for perfection shouldn't be allowed
to get in the way of the election reform movement toward methods 
which are much better than commonly used methods.  Don't let 
the "perfect" (a holy grail?) be the enemy of the "good."  Don't 
wait for scientists to develop a truth serum which forces voters 
to vote their true preferences.

The relevant questions for us involve *comparisons* of the
various election methods on the standards and rigorous criteria
which are important to democracy.  Quite a few standards and
criteria have been identified in this maillist, and, unlike
IIAC and the Gibbard-Satterthwaite non-manipulability
criterion, some of those other important criteria actually
serve to inform us about which of the proposed methods are
better than others.  Focussing on IIAC and/or non-manipulability
would be like focussing on "perpetual motion engines" when
shopping for an automobile: an interesting diversion but not 
very useful.

IIAC ("Independence from Irrelevant Alternatives" criterion)
says, among other things, that the removal of a non-winning
candidate from the voters' ballots must NEVER change the
winner.  

To Ken Arrow, all non-winning candidates are "irrelevant".  
Your own definition of "relevance" may not be as strict as
Arrow's.  Bruce Anderson, an EM subscriber, wrote that the
thrust of his research involves relaxing the definition of
"relevance" so it includes all the alternatives in the Smith set
(in other words, all the circularly tied alternatives) and
investigating which methods satisfy this "relaxed IIAC" as well 
as all the rest of Arrow's criteria.  (Any method which always 
elects an alternative from the Smith set meets "relaxed IIAC.")

Gibbard-Satterthwaite says, among other things, that there must
NEVER be a way that any voters can, by misrepresenting their
true preferences in their ballots, change the winner to an
alternative they would prefer more.  It does NOT say that 
there is ALWAYS (or even often) a way some voters can change 
the result.  

Since no decent methods rigorously satisfy Non-Manipulability,
then in order to compare decision-making methods on their 
resistance to manipulability one needs to explore practical 
considerations:  How likely or unlikely are scenarios where it 
is possible for voters to affect the outcome by manipulation?
How feasible would it be for voters to coordinate their 
manipulation tactics?  Can other voters defend the "sincere" 
winner by countering the manipulation with "defensive 
manipulation?"  Etc.

Mike Ossipoff posted an important criterion regarding the
ability of a majority to defend the "sincere" winner without
any of them having to insincerely rank it ahead of or equal to
alternatives they prefer more.  Since it's not possible for any
decent method to satisfy Gibbard-Satterthwaite, a more
informative test for us is to distinguish between methods by
whether or not they satisfy that Ossipoff criterion.  

> Majority criterion:
>   Suppose there is a candidate who is prefered to every
>   other candidate by a majority of the voters. In other words:
>   Suppose there is a candidate who gets an unshared majority
>   of all votes resp. first preferences.
>   Then a voting method meets the "Majority Criterion" if &
>   only if this candidate wins.
> 
> Pairwise Majority Criterion:
>   Suppose there are only two candidates X and Y.
>   Suppose a majority of the voters prefer X to Y.
>   Then a voting method meets the "Pairwise Majority
>   Criterion" (PMC) if & only if X wins.
> 
> Remark:
>   Every method that meets the Majority Criterion also meets PMC.

Those two criteria are very easy to meet.  PMC, for instance,
as defined by Markus only applies to scenarios where there are 
exactly two alternatives, and almost any method will elect the 
one which a majority of the voters indicate they prefer more 
than the other.  Even Instant Runoff meets MC and this narrow 
PMC.  (There's a broader definition of PMC, which Markus appears 
to imply in his proof below, which Instant Runoff fails.)

> A method that meets PMC always fails to meet Arrow's IIAC.
> Proof:
>   Suppose there is a tie between the candidates A, B, and C. 
>   (A>B>C>A)  Suppose the used method meets PMC.

Since PMC, as Markus defined it, doesn't apply to scenarios
involving more than two choices, presumably "meeting PMC" here
means this: 
   If C were removed from the ballots then the method would 
   elect A.  (A>B)
   If A were removed from the ballots then the methods would 
   elect B.  (B>C)
   If B were removed from the ballots then the method would 
   elect C.  (C>A)

Maybe it would be better to redefine PMC as follows:

   Pairwise Majority Criterion (revised)
   -------------------------------------
   Suppose all alternatives but X and Y are removed from the
   voters' ballots.  Suppose a majority of the voters prefer X   
   to Y, given these modified ballots.   
   Then a voting method meets the "Pairwise Majority Criterion"  
   (PMC) if & only if X wins.

Instant Runoff fails this multi-candidate definition of PMC.  
Here's an example:

   35 voters: ABC
   16 voters: BAC
   16 voters: BCA
   33 voters: CBA

B is preferred to A by a (landslide) majority: 65>35.  And B 
is preferred to C by a (landslide) majority: 67>33.  So to 
satisfy PMC, B must be elected.  But Instant Runoff elects A.
And to further insult the supermajority which prefers B to A,  
Instant Runoff declares B the biggest loser, having eliminated 
B first.

>   Case 1: Suppose, A is elected. Then candidate B changes the
>   result of the elections without being elected, because:
>   If B hadn't run, then C would have been elected, because 
>   the method meets PMC.
-snip-

Looks like a proof to me.

>   Thus: If there is a tie, then independently on who is elected
>   [that means: independently on which tie breaker is used]
>   there is always a candidate who changes the result of the
>   election without being elected.

Of course, there won't always be a circular tie.  So Markus'
use of the word "always" here, added for emphasis, may be 
slightly misleading.  

When there isn't a circular tie--in other words, when one of
the alternatives beats all the others pairwise--then IIAC is
satisfied by most methods which tally preferences pairwise.  
If A>B and A>C, then the removal of B or C from the ballots
doesn't affect the result.  (The winner is still A.)

Furthermore, violating IIAC isn't necessarily a problem for
society.  When there is a sincere circular tie (i.e., the 
tie was not caused by some voters misrepresenting their true
preferences in order to change the result away from electing
the "beats all others pairwise" winner) then it's not as clear
which of the tied alternatives would be the best winner.  So 
the fact that the result can be changed in some cases doesn't 
imply that the method produces the "wrong" outcome in those 
cases.  (See my comment above about Bruce Anderson's "relaxed 
IIAC" and methods which always elect one of the circularly tied 
candidates.)

> Remarks:
>   My only supposition is that the method meets PMC.
> 
>   When I wrote that there is a tie between A, B, and C,
>   I didn't suppose that there is a tie due to the votes.
>   I only supposed that there is a tie due to the opinions
>   of the voters. Thus, I didn't have to suppose that
>   a ranking method is used.
> 
>   The incompatibility between PMC and IIAC is also true for
>   every other method (e.g. Approval voting, methods with
>   additional ballotings). Even Borda methods fail to meet IIAC,
>   because (although Borda methods don't meet the Majority
>   criterion) even Borda methods meet PMC.

Here's an example which shows that Borda doesn't meet the 
Majority Criterion:
   51 voters:  ABCDEF
   49 voters:  BCDEFA

Choice A is the first choice of a majority, yet Borda elects B. 
Borda's method scores each alternative in proportion to the 
number of other alternatives the voters ranked it ahead of: 
   A's Borda score = (51 x 5) + (49 x 0) = 255 +   0 = 255
   B's Borda score = (51 x 4) + (49 x 5) = 204 + 245 = 449
It's arguable that B is the better winner here, since A is the 
last choice of so many voters while B is the first or second 
choice of all the voters.  Which means that the Majority 
Criterion isn't necessarily the most important criterion...

Of course, it's fallacious to read too much into preference
orders.  Just because A is the last choice of some voters
doesn't imply that those voters think A is really much worse 
than their first choice.  People who prefer Borda's method more 
than all other preference order methods seem to assume that it 
does, even though such "preference magnitude" information isn't 
contained in preference order ballots.  (Unfortunately, methods
which allow voters to express magnitude expression in addition
to their orders have a slew of their own well-known problems.)

-snip-
>   Again, I want to mention that the incompatibility between
>   PMC and Gibbard's and Satterthwaite's Non-Manipulability
>   Criterion is valid for each method (e.g. Borda methods,
>   Approval voting, methods with additional ballotings).

Yes.  We don't need to worry about rigorously satisfying
Non-Manipulability or IIAC when we search for methods better
than the ones in common usage. 

---Steve     (Steve Eppley    seppley at alumni.caltech.edu)