[EM] Matrix Representation of Election Methods

[Alex Small]

I'm homing in on a strategy for figuring out if strong FBC can ever be
satisfied (aside from Random Ballot).  At least initially, it's easiest if
I restrict the class of methods under consideration, and also restrict the
number of candidates to 3.

All methods will be ranked methods.  The electorate can be specified by a
vector

E = [N(A>B>C), N(A>C>B), N(B>A>C), N(B>C>A), N(C>A>B), N(C>B>A)]

where each element specifies the number of voters with a particular
preference order.  It is convenient, but not necessary, to impose the
condition

E*[1,1,1,1,1,1] = 1

All ranked election methods that I'm aware of can be reduced to a set of
linear inequalities involving the elements of E.  For instance, in
plurality voting the criteria for A's victory are

[1,1,-1,-1,0,0]*E > 0    (A gets more first-place votes than B)
[1,1,0,0,-1,-1]*E > 0    (A gets more first-place votes than C)


This can be expressed in matrix form.



   | 1  1  -1 -1  0  0 |     | x |
E* |                   |  =  |   |
   | 1  1   0  0 -1 -1 |     | y |


where x>0, y>0.  More generally, we can always require that E*(specified
matrix) gives a vector with all elements greater than zero.


The victory conditions for B and C can be obtained by multiplying the 6x2
matrix above by a 6x6 matrix (which I won't write out) that "swaps" A and
B or A and C.  Some methods might require more matrices.  For instance,
Condorcet methods would have two possible victory conditions for A:  A is
the CW, or A satisfies some condition for breaking cyclic ambiguities (we
might need two conditions for ambiguities, one for the case A>B>C>A and
the other for C>B>A>C, but that's a minor point).

Restricting my attention to such "linear" methods, which can be expressed
in matrix form, will make life much easier.  It will allow me to use
linear algebra to explore strong FBC, and physics grad students know
linear algebra like the back of our teeth (not willingly, but it's beaten
into our brains during Quantum Mechanics).  Obviously this simplification
comes at the expense of generality, but it's a starting point.  In
particular, it gives an easy formalism for discussing favorite betrayals:

Insincere voting can be represented by adding to E some vector d with only
two non-zero elements, both elements having equal magnitude and opposite
sign.  For instance, if some people in the A>B>C faction switch to the
B>A>C faction for strategic advantage, we can express this as

E(new) = E + [-n,0,n,0,0,0]

Not all such representations of insincere voting are favorite betrayals,
of course.

I want to end this brain-dump session with a question:


Can anybody think of ranked election methods that can't be expressed in
matrix form, i.e. with linear inequalities?  I'd think that such methods
are rather absurd, but I'm not sure that they can be ruled out.



Alex


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