[EM] Another 20 years of the EM list

[Buddha Buck]

Craig Carey <research at ijs.co.nz> writes:

> Subject was: Re: [EM] CR style ballots for Ranked Preferences
> 
> 
> At 01.09.26 11:06 -0700 Wednesday, Forest Simmons wrote:
>  >
>  >
>  >On Tue, 25 Sep 2001, Richard Moore wrote in part:
>  >
>  >> .................. what is Approval but Condorcet forced into
>  >> two levels?
>  >>
>  >
>  >Mike Ossipoff was the first to point out this useful fact to me.  That's
>  >one of the things that got me to thinking about the possibility of methods
>  >that would naturally connect Approval and Condorcet.  Martin Harper saw
>  >the connection more clearly than I, so his was the honor of discovering
>  >Universal Approval.
> 
> Please define "two levels". Since Mr Harper was previously at an utter loss
> to find the facts behind a mistake he made over the meaning of the symbol
> "P", that he was using, we might as well get the exacting details,
> 
> For a moment, I thought that Mr Ossipoff was being honoured.
> 
> I don't believe that the two of you are able to see much at all since both
> do not post up algebra.

I don't do algebra, but I do do logic and combinatorics, combined with
formal proof.  Will that meet what you are looking for?

An Approval Ballot allows the voter to arbitrarily partition the
candidates into two sets A and B, such that if candidate X is in A,
and candidate Y is in B, we know that candidate X is preferred by the
voter to candidate Y.  We cannot tell from an Approval Ballot which of
two candidates chosen from the same partition is preferred.

In an election with N voters, I'll define the A-count of candidate X
(represented by A(X)) as the number of ballots that include candidate
X in set A.  the B-count (B(X)) is defined similarly.  Note that for
any candidate X, A(X) + B(X) = N.

The Approval election method selects the candidate with the highest
A-count as the winner.

The "expressed Condorcet Winner" is the candidate W who, based on the
preferences expressed in the ballot, for every candidate X who is not
W, more voters expressed a preferrence for W over X than expressed a
preferrence for X over W.

Lemma> If for two candidates X and Y, A(X) > A(Y), then more voters
expressed a preference for X over Y than expressed a preference for Y
over X.

Proof of Lemma>  The voters can be partitioned into 4 sets:

V1 = { voters who put X in A and put Y in A }
V2 = { voters who put X in A and put Y in B }
V3 = { voters who put X in B and put Y in A }
V4 = { voters who put X in B and put Y in B }

By the definition of A(X) and A(Y), we have A(X) = |V1| + |V2| and
A(Y) = |V1| + |V3|.

The hypothesis of the lemma is that A(X) > A(Y), 
so |V1| + |V2| > |V1| + |V3|.

Therefore, |V2| > |V3|.

But V2 is exactly those voters who expressed a preference of X over Y
and  V3 is exactly those voters who expressed a preference of Y over
X.  Therefore, if A(X) > A(Y), more voters prefer X to Y than prefer
Y to X.  QED.

Theorem>  The winner of an Approval election is the expressed
Condorcet Winner.

Proof of Theorem> Let candidate X be the winner of an Approval
election.  Therefore, for every candidate Y who is not X, A(X) >
A(Y).  By the lemma, that means that more voters expressed a
preference for X over Y than vice versa.  This is the definition of
the expressed Condorcet Winner.

Is that sufficient for you?