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
