[EM] My re-entry?

[Forest Simmons]

Here's another idea or two stimulated by David Catchpole's posting below:

Suppose someone believed that all of the relevant information for making
the "fairest" choice in an N candidate single winner election resided in
the N by N pairwise matrix. 

In other words, suppose someone believed that if two elections gave rise
to the same pairwise matrix, then they should yield the same winner (or
more generally) the same expectations for the respective candidates.

Suppose further that it were always possible, given a set S of ballots,
to find another simpler set S' of ballots that generated the same pairwise
matrix.

For example, the ballots in set S' might be partitioned into only N+1 or
fewer factions in each of which all of the ballots are identical. 

[Remember that N is the number of candidates, and in general there are N
factorial possible distinct preference order factions, so this would
represent a drastic simplification.]

I don't know when a reduction like this is possible, but the following
analogous situation suggests that something similar may be possible with
some degree of generality.

Any three dimensional rigid body with arbitrary distribution of mass (i.e.
arbitrary density function) is equivalent to some rigid tetrahedron with
all of the mass concentrated at the vertices.

By "equivalent" I mean this: assuming the vertex masses are chosen
properly, and that the vertices are correctly placed, the resulting
tetrahedron will have the same moment of inertia tensor, as well as the
same center of gravity as the original rigid body.

This means that the principal axes of rotation would be the same, and the
corresponding radii of gyration would be the same. In other words, if the
two rigid bodies were enclosed in identical black shells, there would be
no way of distinguishing one body from the other by any inertial effects
(whether linear or rotational). 

If ballots are CR style (to which ordinal ballots can be transformed via
conversion of ranks to rates), then each ballot can be thought of as the
position vector of a point mass of one unit.  Then the average of these
ballot vectors represents the center of mass.  The moment of inertia
tensor is represented by the Covariance Matrix. The covariance matrix is
an N by N matrix that is formed by summing various products over all
ballots, so the method would be summable in 2nd order polynomial (in the
number of candidates) complexity (as with pairwise methods). 

Since an N dimensional tetrahedron has N+1 vertices, this transformation
would reduce the number of factions to N+1 from a potential of R^N where R
is the resolution (i.e. number of distinguishable levels) of the CR
ballot. 

What does all of this mean?

Well, suppose that you have collected the kind of information summary you
believe in (say the pairwise matrix or the covariance matrix plus mean
values) from a set S of ballots, and then you figure out a way to generate
the same information summary from a much simpler set S' of ballots. 

This would open up all kinds of possibilities.  For example, non-summable
methods that would have been too complex to apply to S could be applied to
S'. If the complex method gives the "right" outcome for the ballot set S',
then that outcome should be "right" for the equivalent ballot set S.

In particular, sophisticated game theoretic methods that are too complex
to be applied to R^N or N! factions may be more applicable to a mere N+1
factions.

This approach is in line with the following general strategy of problem
solving: 

Find a way of transforming a difficult problem into an equivalent simpler
problem. Solve the simpler problem. Use your solution (whether exact or
approximate) to the simpler problem as a solution for the more difficult
problem. 

I believe that this general approach has potential for devising methods
that are relatively immune to manipulation.

According to the experts, methods that are completely immune to
manipulation require some randomization in one form or another.. 
[Lorrie Cranor alludes to this in her thesis. I haven't seen the proof,
but I believe it.]

There are ways around this. Many of them boil down to making effective
manipulation strategies NP hard. Game theoretic defenses against
manipulation applied to the ballot set S' might have this effect. 

Another way is making implicit use of some kind of pseudo randomization
based on the number of ballots cast.  In order to manipulate the election,
the manipulator would have to know (among other things) the exact
number of qualified voters, and predict the exact number of abstentions. 

Declared Strategy Voting methods can be made virtually immune to
manipulation without actual randomization.  Such a method applied to the
equivalent ballot set S' would yield the desired non-manipulability. 

Lorrie's thesis discusses several approaches to DSV.  One of these
processes the ballots in random order, where different orders of
processing (in some elections) give different outcomes. A survey of
college students said they didn't like this aspect of that version of DSV.

Another approach she used was iterative. That approach was deterministic,
but Lorrie had no theorem guaranteeing convergence of the iterative
process, although it did converge in all of the field trials. 

I don't believe that her iterative method always converges.

Here's where the implicit pseudo randomness can do its job (in the
context of appropriate iterative methods): 

Just say that if N is the number of candidates, and M is the number of
ballots cast, then K=2*3*5*7*11*13*M*N+1 is the number of iterations. The
winner after K iterations is the winner period, with or without
convergence. 

[Note that the smallest prime factor of K is larger than 13, so that even
if patterns in the iteration sequence could be predicted, it would be
virtually impossible to know with any certainty where in that pattern the
K_th iteration would be before knowing the exact value of M.]

Well, there's a lot of room for exploration, and some good thesis
opportunities in there for those willing to dive in and sort things out.

Forest




On Sat, 29 Dec 2001, David Catchpole wrote:

> Hey kids, it's been a long time!
> 
> I'm paddling around in my own uninteresting eddy in voting theory still. I
> was wandering if anyone on this list knows of any articles about the
> conditions for an election system / game to be adequately informed by
> ordinal preferences - that is, the conditions such that the
> optimal strategy of the voters/players can be determined simply by their
> ordinal preferences, rather than needing their cardinal
> preferences/utilities?
> 
>