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? > >
