[EM] My Matrix for Kemeny's Rule, n=3
Forest Simmons
fsimmons at pcc.edu
Thu Jan 2 17:31:24 PST 2003
The matrix in your method is not the pairwise matrix that is used in most
Condorcet methods.
Your matrix shows the distance between pairs of preference orders.
So the rows and columns are both indexed by preference orders. The
complete Kemeny matrix has (N!)*(N!) entries.
The usual pairwise matrix is merely an N*N matrix which has one row and
one column for each candidate, and the entry in the (i,j) position is the
number of ballots that show a preference for candidate i above candidate
j.
You can see that (N!)*(N!) grows much faster than N*N as the number of
candidates N increases.
Also, since Kemeny satisfies the Reinforcement Criterion, while Ranked
Pairs does not, we can be sure that the Kemeny order is not the same as
the Ranked Pairs order. [Apply both methods to Blake's example of Ranked
Pairs failure of Reinforcement to see the difference.]
Forest
On Thu, 2 Jan 2003, barnes99 wrote:
> Forest:
>
> Thanks for confirming that my matrix for determining the Kemeny outcome for 3
> candidates is correct. Now, is Kemeny's Rule, as defined by my matrix for 3
> candidate tallies, the same as the Condorcet method which is described on the
> EM website <http://electionmethods.org/>?
>
> SB
>
> --- In election-methods-list at yahoogroups.com, Forest Simmons <fsimmons at p...>
> wrote:
> > Your example is correctly done.
> >
> > Despite the intractability of the method for large numbers of candidates,
> > it seems like an ideal method for some situations.
> >
> > One application could be in choosing between several orders that have been
> > found by other means.
> >
> > [The main computational difficulty of finding the Kemeny order is not in
> > calculating the mean Kemeny distance to any particular order, but in the
> > sheer magnitude of the number of possible orders.]
> >
> > Here's a homely example:
> >
> > Start with the candidates ranked by Approval, Borda, Ranked Pairs, etc.
> >
> > Do both a sink sort and a bubble sort to each of these preliminary orders.
> >
> > [These sortings are ways of achieving "local Keminization." Ranked Pairs
> > is already locally Kemeny optimal.]
> >
> > See which of the resulting locally optimum orders is best (among those
> > considered) globally by calculating the mean distance of each to the
> > preference orders on the ballots.
> >
> > Forest
> >
> > On Fri, 20 Dec 2002, barnes99 wrote:
> >
> > > Here is my matrix for Kemeny's Rule with 3 candidates. Please let me know
> if I
> > > got it right or wrong.
> > >
> > > Here is an example of a Kemeny Rule tally for profile p, p=(1,1,0,0,0,0),
> > > where the first thru sixth columns represent, respectively, the number of
> ABC,
> > > ACB, CAB, CBA, BCA, and BAC voters.
> > >
> > > Voting Vector:
> > >
> > > p=[ 1 1 0 0 0 0 ]
> > >
> > > Matrix (M) for Kemeny's Rule:
> > >
> > > [[ 0 1 2 3 2 1 ]
> > > [ 1 0 1 2 3 2 ]
> > > [ 2 1 0 1 2 3 ]
> > > [ 3 2 1 0 1 2 ]
> > > [ 2 3 2 1 0 1 ]
> > > [ 1 2 3 2 1 0 ]]
> > >
> > >
> > > The KR tally is:
> > >
> > > p(M)=[ 1 1 3 5 5 3 ], where
> > >
> > > ABC=[0+1+0+0+0+0]=1
> > > ACB=[1+0+0+0+0+0]=1
> > > CAB=[2+1+0+0+0+0]=3
> > > CBA=[3+2+0+0+0+0]=5
> > > BCA=[2+3+0+0+0+0]=5
> > > BAC=[1+2+0+0+0+0]=3
> > >
> > >
> > > This is the measure of the "distance" from unanimity, so the lower the
> score
> > > the better. In this example, we have a tie between the ABC and ACB
> outcomes,
> > > in which case I guess the final outcome must be A>B~C. This may not be a
> very
> > > interesting example, but the point is that I believe this is how to do a
> KR
> > > tally with 3 candidates. Please correct me, if I'm wrong.
> > >
> > >
> > >
> > > Thank you,
> > > SB
>
> Steve Barney
>
> Richard M. Hare, 1919 - 2002, In Memoriam: <http://www.petersingerlinks.com/hare.htm>.
>
> Did you know there is an web site where, if you click on a button, the advertisers there will donate 2 1/2 cups of food to feed hungry people in places where there is a lot of starvation? See:
> <http://www.thehungersite.com>.
>
> ----
> For more information about this list (subscribe, unsubscribe, FAQ, etc),
> please see http://www.eskimo.com/~robla/em
>
>
----
For more information about this list (subscribe, unsubscribe, FAQ, etc),
please see http://www.eskimo.com/~robla/em
More information about the Election-Methods
mailing list