[EM] The Copeland/Borda wv hybrid (fwd)

[Forest Simmons]

I meant to make this information available to the whole EM list.

---------- Forwarded message ----------
Date: Tue, 3 Dec 2002 14:40:05 -0800 (PST)
From: Forest Simmons <fsimmons at pcc.edu>
To: Elisabeth Varin/Stephane Rouillon <stephane.rouillon at sympatico.ca>
Subject: Re: [EM] The Copeland/Borda wv hybrid

Rob liked his method because it beat Black (Borda Completed Condorcet) in
expected utility, and always seemed to pick the CW when there was one.

But I showed by counter-example that Rob's method didn't always pick a
member of the Smith set for the ranked ballots.

My fix was designed to maintain the spirit of Rob's method along with high
expected utility and reverse symmetry criterion satisfaction, while
ensuring that the winner would be a member of the Smith set.

Because of the high expected utility I believe that this method must have
problems similar to those inherited by Black from Borda, namely clone
problems, as well as strategic incentives for insincere ranking.

However, the Stochastic Matrix idea that I used to "fix" Rob's method has
many variations, so perhaps you might find a good way of adapting it ... a
way that doesn't suffer from the above mentioned problems.


In a nutshell here's the stochastic matrix idea:

A stochastic matrix is a matrix of non-negative numbers such that each of
its rows is normalized to have a sum of one.

For each such matrix P there is at least one normalized vector of
non-negative numbers v such that vP=v .  Usually such a vector is
interpreted as an equilibrium vector in a discrete dynamical system called
a Markov Process.

Suppose that P is a stochastic matrix such that each off diagonal entry
Pij (in row i and column j) is greater than zero if and only if candidate
j is preferred over candidate i on more ballots than candidate i is
preferred over candidate j.

Theorem:  Let v be an equilibrium vector satisfying  vP=v .  Then every
non-zero entry in v corresponds to a member of the Smith set.

So every such matrix P gives rise to a Condorcet Method.

Notice that there is a lot of freedom in the choice of the entries Pij, so
there are lots of possible Condorcet Methods here.

Generally, you can use the diagonal elements of P to give the method your
preferred flavor.

If you like Borda, put Borda counts down the main diagonal before
normalizing the row sums.  If you like Approval, put approval counts down
the main diagonal before normalizing the row sums.

The off-diagonal positive elements could all be ones (before the
normalization) or they could be proportional to the corresponding margins
or winning votes. Many other possibilities exist.

Any such method can be modified in a natural way to satisfy reverse
symmetry by constructing the matrix Q for the order reversed ballots,
while letting w be the appropriate normalized equilibrium vector
satisfying wQ=w.

Then (as a corollary to the above theorem) the positive entries of w
correspond to members of the reverse Smith set for the ballots.

To satisfy reverse symmetry, take as the winner for the modified method
the candidate with the largest positive entry in the difference v-w of the
two vectors.

[If v-w has no positive entry, then no element is negative either since
the sum of its elements must be zero, since it is the difference of two
sum normalized vectors.  In this unlikely case, all of the candidates are
tied.  Note that if there is both a Condorcet Winner and a Condorcet Loser
the vector v-w will have exactly two non-zero elements, a 1 and a -1 for
the winner and loser respectively.

For example, let P be the matrix obtained by first putting one in all of
the off diagonal entries Pij for which candidate j beats candidate i.
Then along the main diagonal let Pjj be the percentage of the electorate
that approves of candidate j. Finally, normalize the row sums.

For Q first use ones for the off diagonal entries Qij for which candidate
i beats candidate j.  Then along the main diagonal let Qjj be the
percentage of the ballots that list candidate j below the approval cutoff.
Finally, normalize the row sums.

To find v start with a normalized vector of ones. Multiply it by P and
normalize the result.  Multiply that result by P and normalize the result.
Repeat until no change in the tenth decimal place.

[The repeated normalization is not really necessary, but should be done
occasionally to counter round off error.]

Find w analogously (using Q instead of P).

Suppose that the largest member of v-w is the fifth entry.  Then candidate
number five is the winner of this Approval Flavored Condorcet Method.


Notice that the method is completely deterministic, even though it makes
use of stochastic matrices, which can be given a probabilistic
interpretation if anybody is interested.


I hope that this at least partially answers your question.


Forest






On Tue, 3 Dec 2002, Elisabeth Varin/Stephane Rouillon wrote:

> The one you think is the best.
> I would like to see what are the advantages...
>
> Forest Simmons a écrit :
>
> > Which would you like summarized? [Rob's original or my fix.]
> >
> > On Mon, 2 Dec 2002, Elisabeth Varin/Stephane Rouillon wrote:
> >
> > > Could you summarize the method?
> > >
> > > Steph.
> > >
> > > Forest Simmons a écrit :
> > >
> > > > Rob, remember that method that you proposed that turned out to be a kind
> > > > of Borda/Copeland hybrid that usually picked the CW, but not always?
> > > >
> > > > I have a way to fix it.
> > > >


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