[EM] Simple Election Methods and Geometry

[Alex Small]

The goal of this post is to identify (1) the "simplest" class of ranked methods (in a sense which I will define more precisely) and (2) the "simplest" method for resolving Condorcet cycles.  I don't actuall have answers, but I have conjectures.  Although this involves geometry in higher dimensions I will provide simple examples that you can visualize by drawing lines on a piece of paper.
 
Let's stick to 3 candidates and ignore equal rankings, to keep it simple.  There are 6 possible types of voters, and so there are 6 variables to consider:  The fraction of the electorate with each possible preference order. These variables live in a 6D space, but because the fractions add up to 1 we're dealing with a finite (and 5-dimensional) region of space.  Also, I assume that the method treats all candidates equally, so that if every voter swapped the winner (let's call him candidate A) with the same other candidate (let's call him B) then B would win.
 
Our election method divides this region of space into 3 sub-regions, each corresponding to a different winner.  If you want to go beyond winners and also decide which loser comes in second and which comes in third, we get 6 regions corresponding to different transitive preference orders.  In some sense it is trivial to modify a method to identify a runner-up.  Just eliminate the winner from the ballots and run the method again to see who wins. 
 
Let's stick with the notion that our method will also identify a runner-up, because it means that we just need to make 3 "cuts":  Before I put this in the language of higher dimensions, just consider drawing lines on a piece of paper.  Draw a circle, triangle, or some other convex figure on a piece of paper.  Now draw 3 straight lines (to keep it simple).  You could think of each line as representing a comparison of 2 candidates:  The first line divides the drawing into a region where A beats B in our method and a region where B beats A.  The second line does that for B and C, and the third line does that for A and C.
 
In higher dimensions, we'd draw 4D hypersurfaces (analogous to lines), and each hypersurface divides the space of possible electorates into regions corresponding to how the method ranks 2 candidates relative to each other.
 
Now, one thing to notice is that when you draw lines on a piece of paper you don't usually divided your figure into 6 regions.  Usually you divide your figure into 7 regions.  The lines have to all meet at a single point in order to give exactly 6 regions (i.e. no cycle).  You can't just draw any old lines that you want and still have a transitive outcome.
 
Here's my first proposal:  We're talking about election methods as ways to draw boundaries in space.  The more complicated those boundaries are, the more complicated the method is to figure out, and the more incentives for manipulation there will be (assuming voters have sufficient and accurate information, of course).  So, I propose that the total perimeter of the 3 boundaries (or, in general, N(N-1)/2 boundaries for N candidates) can be used as a way to compare the complexity of different methods.
 
Conjecture #1:  I conjecture that the methods which minimize the total area of the boundaries are those where the boundaries are "straight lines" (formally, 4D hypersurfaces defined by a linear equation, so there aren't any kinks or curves).
 
The assumption of neutrality (treating all candidates equally) is important here, because otherwise you could minimize the total perimeter by drawing 2 of the surfaces to carve out a tiny corner.  One of the candidates would win in most cases, and the other 2 would only win in a handful of cases.

The notion of drawing "straight lines" in 5D might seem complicated, but the methods that correspond to "straight line" boundaries are easy to understand.  They're what Saari would call "positional methods".  Candidates get a certain number of points from each voter depending on how the voter ranked the candidates.  For instance, in plurality a candidate gets 1 point from each voter who ranks him 1st and 0 points from all other voters.  In Borda a candidate gets get 2 points from each voter who ranked him 1st, 1 point from each candidate who ranked him 2nd, and 0 points from voters who ranked him last.  In one of my favorite positional methods (mostly because of its importance in the strong FBC problem that I continue to pursue on the side), a candidate gets 1 point from each voter who ranks him 1st and 2nd, and 0 points from each candidate who ranks him 3rd.  I don't think that all positional methods would yield the same surface area, but there would probably be more than on
 e method
 that does minimize the surface area of the boundaries.
 
Anyway, I'm not saying these are the best methods to use, but simply posing a question as a warm-up for something that people on this list might find more practical:
 
Question:  Which Condorcet completion method minimizes the total area of the boundaries?
 
My hunch is that it would be some sort of positional method, and that there would be more than 1 such positional method.  However, it could just as easily turn out that methods which compare the magnitude of victory minimize the area of the boundaries and are therefore simpler and less prone to manipulation in some sense.

Anybody care to take a stab at these questions?
 
 
 
Alex

		
---------------------------------
Do you Yahoo!?
 Take Yahoo! Mail with you! Get it on your mobile phone.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20050227/2bbcb9ca/attachment-0002.htm>