[EM] Two Theorems: Please criticize or point out errors

[Alex Small]

I was thinking about a statement that Mike has made:  That with Approval
Voting there is always a Nash equilibrium where the Condorcet Winner wins
the election and every voter votes sincerely.  Here's what I came up with:

First, definitions:


Definition:  A Nash equilibrium for an election is a situation in which
each group of voters with identical preference orders follows the same
(possibly mixed) strategy and no faction has any incentive to pursue a
different strategy when all other factions keep to the same strategies.

(This definition has already been defended by me and others in many
previous posts.)

Definition:  A Sincere Approval Ballot is one on which if a voter approves
candidate j he also approve all candidates whom he preferes to j.

Theorem:  If a Condorcet Candidate exists and the electorate uses Approval
Voting then there is always at least one Nash Equilibrium in which all
voters cast sincere ballots and the Condorcet Winner is elected.

(Note that there may also be sincere Nash equilibria in which the CW
loses.  For an example, seehttp://groups.yahoo.com/group/election-methods-list/message/9351)


Proof:  I will construct a particular set of sincere ballots that elect
the Condorcet Candidate and prove that it is a Nash Equilibrium.  By doing
so I will prove that at least one such equilibrium exists.

Suppose that all voters who do not rank the CW last approve him and any
other candidate whom they prefer to him.  All voters are casting sincere
ballots.  The CW is approved by a majority of the voters, and all other
candidates are approved by a minority of the voters (because a candidate
is approved by whatever fraction of the electorate prefers him to the
Condorcet Candidate).  The CW wins.  Those blocs which prefer the CW to
all others obviously have no incentive to change strategies.

Suppose that bloc X decides to withdraw support for the CW (and possibly
other candidates) in hopes that candidate j (whom they prefer to the CW). 
The CW is still approved by the majority of voters who prefer him to
candidate j (and possibly some from blocs other than X who prefer j to the
CW).  No other candidate is approved by a majority so the CW still wins
and the bloc X has failed to obtain a better outcome.

The only remaining possibility is that a bloc votes for ADDITIONAL
candidates to change the outcome, but this might elect somebody whom the
bloc considers inferior to the CW, and hence the bloc would obtain a worse
outcome.  This completes the proof.


Are there any holes?



Second Theorem:


Definition:  Majority Choice Approval Voting (MCA).  All voters rate each
candidate as Preferred, Acceptable, or Unacceptable.  The candidate
Preferred by the most voters wins if he is Preferred by a majority. 
Otherwise the candidate rated unacceptable by the fewest voters
(equivalently, the candidate rated Preferred or Acceptable by the most
voters) wins.

Theorem:  Suppose that in a race with 3 candidates voters cast ordinary
Approval ballots and the Condorcet Winner is elected with a majority,
while the runner-up also has a majority.  If we switch to Majority Choice
Approval, and all voters who approved two candidates rate one candidate as
Preferred and the other as Acceptable, the CW will still win.

Proof:  If the CW is Preferred by a majority then he still wins. 
Otherwise, if no candidate is Preferred by a majority, the inclusion of
Acceptable votes makes this election equivalent to the previous Approval
election and the CW will win as before.


The motivation for this theorem is to prove that Majority Choice Approval
is just as good as Ordinary Approval (OA) in electing Condorcet
candidates, assuming that all voters take advantage of the increased
flexibility offered by MCA.  Obviously there are situations in which MCA
will not elect a CW but OA will.  Example:

Bloc 1:  40:  A>B>C
Bloc 2:  20:  B>A>C
Bloc 3:  40:  C>B>A


Ballots cast:


Bloc 1:  AB:  40
Bloc 2:  BA:  40
Bloc 3:  CB:  10
          C:  10

(here's an example of a mixed strategy for bloc 3)


Now switch to MCA:


Bloc 1:  40 Prefer A and Accept B
Bloc 2:  20 Prefer A and B
Bloc 3:  20 Prefer C, 10 also Accept B

A is the only candidate Preferred by a majority and wins.


Now, my proof is only guaranteed to work for 3 candidates.  Can my theorem
by generalized to 4 or more candidates?  Or can we restrict it to say
something like the following?

Conjecture:  Suppose that in an election with 3 or more candidate and
Ordinacy Approval Voting the CW is elected with a majority, and at least
one other candidate is also approved by a majority.  If voters cast
identical ballots with MCA, except that some voters indicate distinctions
among those whom they approved, AND ALL VOTERS WHO APPROVED BOTH THE CW
AND THE OTHER CANDIDATE(S) APPROVED BY THE MAJORITY DISTINGUISH AMONG THEM
WITH THE PREFERRED AND ACCEPTABLE RATINGS then the CW will still win.


Thoughts?



Alex


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