[EM] Generalized Condorcet Scores

[Hugo Harth]

I start with a definition of the "Condorcet score"
(see for example: "Equity, In Theory and Practice" , H. Peyton Young, 
Princeton University Press )

Given an ordering of candidates, the Condorcet score is simply the sum of 
the elements of the vote-matrix that are also contained in that order in the 
given permutation.

Example (Young)

Vote matrix :

    A     B     C
_________________
A   0    23    29
B  37     0    29
C  31    31     0

BCA : Condorcet-score : 29 + 31 + 37 = 97
CBA : Condorcet-score : 31 + 31 + 37 = 99

We may look at all the possible permutations, determine the ranking with the 
highest Condorcet score, and declare the first element of this permutation 
the winner.

Now, if we think of the numbers used for a particular permutation as a 
vector [31,31,37] and the Condorcet-score as a vector-norm, we may also 
consider other vector-norms.
One, is selecting the largest element, maybe not directly usable, but it 
hints a little bit towards Tideman's method (which will certainly introduce 
the link BA in its first step).

The idea is to generalize this Condorcet score.
An EM such as Tideman's may be thought being equivalent to finding a 
permutation with the highest generalized Condorcet score using a (probably 
complex) function (of the applicable elements) of the vote matrix.
Here the attempt is to start with simple functions and see how they relate 
to good EM's.

It may simplify things if we normalize the vote matrix : divide all the 
elements by half the number of voters.
The average is 1 then and an element is in any case in [0 , 2].

There is an infinity of functions, but we may start with a simple but 
flexible approach :
a broken line or spline-function of degree 1 to be applied to each element 
that enters in
the scoring-function (given a permutation).
F(x) = x-1 for x in [1-e , 1+e] where e>0 determines the position of two 
knots.
F(x) = e + a . (x-1-e) for x in [1+e , 2] and a >= 0
if a is > 1 , high scores weigh more, which I suspect to be more Tideman 
like.
Similar for x in [0 , 1-e]  F(x) = -e + a . (x-1+e)
It is a simple function with 2 degrees of freedom, antisymmetric (x=1) , 
gives finite results,
and with suitable e and a may be made to produce rational numbers, given 
that all x will
also be rational numbers. Not important now, but if it leads to a usable EM, 
then all calculations
may be performed exactly using integer-arithmetic.

Another important extension is that we may weigh the function results 
differently, depending on the distance of the two elements in the 
permutation.

Example : In the permutation CBA, we may weigh f(x[C,A]) by 2 since C and A 
are distant of 2 positions.
f(x[C,B]) and f(x[B,A]) would be premultiplied by 1 (only rank different).

Generally, if j and i are the ranks of two elements in a permutation ( j > 
i),
we may try premultiplying f(x) by j-i , 1 or perhaps 1 / (j-i) or some 
combinations
thereof such as k + (j-i) with k >=0
The weighting of f(x[i,j]) as a function G(j-i) is a third parameter.

Example 2 : e=1/5 a=2 , use 1/(j-i) and take the example of Young and 
permutation CBA
The scores are 31/30 =x[C,B]
31/30 = x[C,A]
37/30 = x[B,A] which is > than 1+1/5, f(x[B,A]) = 1/5 + 2*(37/30-1-1/5)
The generalized score is then 1/(2-1) * 1/30 + 1/(3-1)*1/30 + 1/(3-2)*
{6/30 + 2*1/30} = 1/30 + 1/60 + 8/30 = 19/60


A way to explore and learn EM's may be

1) trying to approximate excellent EM's by fitting e, a and (j-i) to some 
power (-1,0,1)
2) learning from these approximations (What do they suggest?)
3) perhaps trying to improve on it, using these continuous functions
4) Are interactions essential in a good approximation? Are terms like 
f(x[i,j]).f(x[p,q]) necessary in a good EM ?

yours sincerely,

Hugo Harth

_________________________________________________________________________
Get Your Private, Free E-mail from MSN Hotmail at http://www.hotmail.com.