[EM] 'More often' (was: IRV and Condorcet operating identically)

[Alex Small]

Jan Kok said:
> I'm curious if anyone can mathematically justify such statements as
> "Voting method A exhibits property P 'more often' than method B"?

Well, for methods that use strictly ranked ballots to pick among N
candidates I would represent all possible electorates with an N!
dimensional vector space.  Each direction would correspond to the number
of voters with a given (sincere, normally) preference order.

I'd look at an N!-1 dimensional "slice" of that vector space given by the
constraint that

Sum(j=1,N!)V(j)=1 and V(j)>=0

where V(j) is the percentage of voters with preference order j.

Within this region, I'd identify the areas in which property P is
satisfied by a particular method and use standard integration to compute a
volume, and divide that volume by the total volume of the region in
question.

I don't think that this method could be interpreted as giving a
probabilistic answer to the question "how often" because it assumes that
all possible scenarios are equally probable.  Still, it allows transitive
comparisons, i.e. if property P1 occurs more often than property P2, and
P2 occurs more often than P3, then P1 occurs more often then P3.

One easy application of this method is to figure out "how often" there
will be a Condorcet winner.  With N candidates we have N(N-1)/2 pairwise
contests.  Since each contest has 2 possible outcomes (ignoring ties)
there are 2^(N(N-1)/2) possible breakdowns for the pairwise results.  Each
combination of pairwise results covers a fraction 2^(-N(N-1)/2) of the
total electoral space.

Now, say that we have a Condorcet winner.  Among the other N-1 candidates
there are (N-1)(N-2)/2 pairwise contests and 2^((N-1)(N-2)/2) possible
ways that the pairwise contests among them could break down.  Each of
those outcomes covers a fraction 2^(-N(N-1)/2) of the total volume of
electoral space (for a fixed number of voters).  A little algebra shows
that the region in which candidate A is the Condorcet winner covers a
fraction
2^(1-N) of electoral space.

Finally, since there are N possible Condorcet winners, the fraction of
electoral space in which a Condorcet winner exists is N*2^(1-N).

A quick sanity check indicates that for 2 candidates, the above formula
says that 100% of electoral space has a Condorcet winner, as we'd expect.

The interpretation is that as we add more candidates, to be a CW one must
win more and more pairwise contests.  This becomes harder and harder to
do, so the fraction of electoral space in which a CW exists becomes
smaller and smaller as we add more candidates.



Alex


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