[EM] I've begun writing a paper on the Favorite Betrayal Criterion
Alex Small
alex_small2002 at yahoo.com
Tue Jun 12 19:58:37 PDT 2007
Hello, everyone. A long time ago I used to be active on this list, and as some of you may recall I was working on the problem of the "Favorite Betrayal Criterion": Can you create voting methods in which you never have an incentive to insincerely rank somebody other than your favorite in first place?
We knew that you could do it with Approval Voting, and we had figured out that you could do it with point systems that give equal points to the first and second choice. However, the question always loomed whether there were other ranked voting methods that could satisfy the criterion. A few times I posted and then retracted a proof that it could only be done with point systems.
Well, I've fallen out of contact with the list, but I have continued working on the problem at times. I now have a complete result. I am working on the paper now, but I will post a very brief outline of the result, and as I work on the paper I will post more of the proof. I will also include here a link to the very beginning of the paper. It's only an introduction, but I would appreciate any feedback people might have. I want this paper to be readable.
The link is on this page:
http://physicistatlarge.googlepages.com/electionmathematics
Outline of result:
You can categorize FBC-compliant methods into 3 groups. The methods are characterized by the types of boundaries that they draw in the space of electorates, if you use a geometric approach:
Imagine that you represent the set of ballots cast with a point in some high dimensional space. Each coordinate or direction in that space represents the number of people submitting ballots with a particular ranking of the candidates. In different regions of space different candidates win, and the election method determines where those regions lie, and hence the boundaries between regions.
Now, the rules defining the election method consist of a series of statements involving linear inequalities, i.e. ballot tallies. e.g. "If the number of ballots listing candidate 1 in first place plus the number of ballots listing candidate 1 in second place minus the number of ballots listing candidate 2 in first place minus the number of ballots listing candidate 2 in second place is greater than zero, and..."
These rules could be expressed with symbols and formal linear inequalities rather than long and convoluted sentences. These linear inequalities can be rewritten in the form N dot p > 0, where N is a vector of coefficients and p is a "profile vector" (in Saari's terminology), with each element indicating the number of ballots of a given type. The coefficient vectors N defining the rules also define the boundaries between victory regions.
Saari showed that you can analyze the strategic incentives facing voters by analyzing the boundaries between victory regions, or by analyzing the vectors normal to those boundaries. The first thing I did was use the same analysis for FBC-compliant methods. FBC imposes certain constraints on the normal vectors. If a boundary separates regions in which candidates 1 and 2 win, then the normal vector N_{1,2} (I'm using LaTex notation for math) must satisfy a certain condition.
You can categorize a voting method by how many conditions the coefficient vectors satisfy:
1) If each of the normal vectors satisfies only one condition (e.g. the condition for N_{1,2} or the condition for N_{1,3} or the condition for N_{2,3}, etc.) then the voting method can only be a "point system" (what Saari calls a "positional method") in which first and second choice candidates are given equal points.
This was the hard part of the work.
2) If some of the normal vectors satisfy multiple conditions (e.g. N_{1,2} and N_{1,3} and N_{1,4} and so forth, so that the first subscript is always the same, but never N_{1,2} and N_{2,3}) then (under a few simple assumptions) the method belongs to a family similar to Bucklin:
In the first round of the election you calculate point totals by some method that treats first and second choices equally (and assigns whatever point value to 3rd, 4th, etc. places). If the candidate with the most points also exceeds some threshold of points, he wins. Otherwise, you assign points by some other method, and again check to see if the candidate with the most points exceeds some threshold (not necessarily the same threshold as the first round). You can have as many or as few steps as you like, but at some point you have to call it quites.
I don't know that I would recommnd such a method, but the mathematical task was to figure out which methods satisfy FBC and which ones don't. Well, these methods do satisfy FBC.
Note also that when there's only 3 candidates there's only one point system (positional method) that treats first and second choices equally, so this category is redundant with the first one.
This was easier, because I imposed a few additional conditions on the geometry.
3) Some of the coefficient vectors (and hence normal vectors) satisfy all of the conditions, i.e. they satisfy the condition for N_{i,j} for ALL i and for ALL j.
It's easy to show that these methods make no practical sense. Mathematically they work, but they are not of any political interest. Conceptually, you could define a condition of that form and declare that it's a victory condition for ANY candidate. (I'll try to make this clearer in the paper when I get into all of the math.)
This part was easiest, because I didn't really pursue it. I just defined the category, observed that it was uninteresting, and moved on, rather than trying to figure out exactly which methods are included in this category.
Anyway, that's the sketch of the result. It will make more sense as I write more of the paper. All I have posted right now is the intro section, but as I said, I'd appreciate feedback. In the next week I'll write the section on my geometric formalism and notation. Then I'll start deriving conditions, at which point I can delineate the 3 categories of methods, and then prove some theorems concerning methods in each category.
Alex
---------------------------------
Yahoo! oneSearch: Finally, mobile search that gives answers, not web links.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.electorama.com/pipermail/election-methods-electorama.com/attachments/20070612/76c1358a/attachment-0002.htm>
More information about the Election-Methods
mailing list