[EM] election strategy paper, alternative Smith, web site relaunch
Hello. This is James Green-Armytage, replying to Chris Benham. I focus on the nine single-winner voting rules that I consider to be the most widely known, the most widely advocated, and the most broadly representative of single-winner rules in general: these are plurality, runoff, alternative vote, minimax, Borda, Bucklin, Coombs, range voting, and approval voting8. I would think that Schulze(Winning Votes) is more widely advocated than minimax, aka MinMax(Margins). Well, I analyze the vulnerability of beatpath (and ranked pairs) to a simple burying-and-compromising combination strategy, but so far I haven't written an algorithm to exhaustively determine when it is and isn't vulnerable to strategic voting. Perhaps I should say that I'm focusing on minimax because it's one of the simplest and most obvious Condorcet methods. To me, this is somewhat implied by saying that I'm focusing on 'broadly representative' methods, as minimax is probably the most 'generic' Condorcet method around. The exhaustive voting analysis code for minimax is already very complicated. (Have a look at section 4.1 in general and 4.1.9 in particular, and then the minimax code at http://www.econ.ucsb.edu/~armytage/codes.pdf ). I'm sure that it's possible to do the same thing for beatpath, but I'm guessing that it would be a headache, and judging by the results of simple strategy analysis, it would end up in a very similar result anyway. (That is, we know from this analysis that beatpath and ranked pairs aren't substantially less vulnerable than minimax, and I see no reason to think that they would be substantially more vulnerable.) I really don't think that using winning votes rather than symmetric completion would make a substantial difference to my analysis. Just about any group of votes that a strategic coalition can produce given symmetric completion, can also be produced given winning votes. Likewise, I don't think that casting truncated ballots as allowed by winning votes opens up any useful strategic possibilities. I've written in the past about the advantage of winning votes Condorcet methods over margins methods in allowing for more stable counter-strategies. As far as I know, that analysis is still valid, but it doesn't apply here, because I don't get into counter-strategy in this paper. I'm trying to answer the question of which methods allow people to simply not worry about strategy at all, with the greatest frequency. I find these assumptions about ballots that are truncated or have equal-ranking to be very unsatisfactory. It means that the version of Bucklin you are considering is a strange one (advocated by no-one) that fails the Favorite Betrayal criterion. It would also fail Later-no-Help, which is met by normal Bucklin. I make that assumption as a way of treating the different methods equally. It makes little to no difference for most of the methods that I look at. It makes a very tiny difference for Borda, and it makes coding substantially more straightforward. It actually does make a major difference for Bucklin, as I note in subsection 4.1.8. Bucklin without symmetric completion is strictly more vulnerable to strategy (and I'd imagine, by a noticeable amount) than the version I use in the paper. I can run some simulations on the other version for you, if you like (the version without symmetric completion) -- actually, the coding for this version is monumentally easier than the coding for the version I used. I'm quite sure that it would be bad to put two Bucklin versions in the paper, because people don't care that much about Bucklin to begin with. It's possible that I chose the symmetrically completed Bucklin in part because I didn't want to shrink away from the intellectual challenge involved. Have a look at 4.1.8 and the Bucklin code -- it's tricky! Coombs Surely this is a museum curiosity that no-one currently advocates? Yeah, I don't know anyone who advocates Coombs, but it appears quite often in the academic literature on voting strategy and comparative voting systems in general. It also generates some interesting comparisons, and rounds out the group a bit, so I'm glad that it's in there. Sincerely, James Election-Methods mailing list - see http://electorama.com/em for list info
[EM] election strategy paper, alternative Smith, web site relaunch
From James Green-Armytage's paper on election strategy: I focus on the nine single-winner voting rules that I consider to be the most widely known, the most widely advocated, and the most broadly representative of single-winner rules in general: these are plurality, runoff, alternative vote, minimax, Borda, Bucklin, Coombs, range voting, and approval voting8. I would think that Schulze(Winning Votes) is more widely advocated than minimax, aka MinMax(Margins). 2. Preliminary definitions 2.1. Voting rule definitions In this paper, I analyze nine single-winner voting methods. I follow Chamberlin (1985) in including plurality, Hare (or the alternative vote), Coombs, and Borda, and to these I add two round runoff, minimax (a Condorcet method), Bucklin, approval voting, and range voting. My assumption about incomplete ranked ballots is that candidates not explicitly ranked are treated as being tied for last place, below all ranked candidates. My assumption about votes that give equal rankings to two or more candidates is that they are cast as the average of all possible orders allowed by the rankings that they do specify. http://www.econ.ucsb.edu/~armytage/svn2010.pdf I find these assumptions about ballots that are truncated or have equal-ranking to be very unsatisfactory. It means that the version of Bucklin you are considering is a strange one (advocated by no-one) that fails the Favorite Betrayal criterion. It would also fail Later-no-Help, which is met by normal Bucklin. It means that the only version of minimax you can consider is Margins, and you can't consider Schulze(Winning Votes). Unlike minimax(margins), Schulze(WV) meets the Plurality, Smith and Minimal Defense criteria. Alternative vote, or Hare: Each voter ranks the candidates in order of preference. The candidate with the fewest first choice votes (ballots ranking them above all other candidates in the race) is eliminated. The process repeats until one candidate remains. Coombs12: This method is the same as Hare, except that instead of eliminating the candidate with the fewest first-choice votes in each round, it eliminates the candidate with the most last-choice votes in each round. Surely this is a museum curiosity that no-one currently advocates? This fails Majority Favourite, but I think there is another version with a 'majority stopping rule'. http://wiki.electorama.com/wiki/Coombs%27_method http://en.wikipedia.org/wiki/Coombs'_method http://www.fact-index.com/c/co/coombs__method.html 6.2.2. Compromising strategy results Tables 9-11 and figures 10-12 show the voting rules‘ vulnerability to the compromising strategy, given various specifications. As shown in proposition 4, Coombs is immune to the compromising strategy Of course the version with the majority stopping rule isn't immune to that strategy (Compromise). Chris Benham Election-Methods mailing list - see http://electorama.com/em for list info
[EM] election strategy paper, alternative Smith, web site relaunch
Hello. This is James G-A, responding to the following post by Chris Benham: http://lists.electorama.com/pipermail/election-methods-electorama.com/2010-November/026954.html Chris and I have had a good discussion about this since his post, which has enabled me to get back up to speed on some of the things he mentioned. So, to summarize, there are at least two distinct approaches to creating Smith/Hare hybrid single winner election methods. One approach is to first eliminate the candidates outside the Smith set, and then to hold an IRV tally among remaining candidates. Nic Tideman's 'alternative Smith' method is a variation on this, which provides for further elimination of extra-Smith candidates in between IRV counting rounds. Another approach is to successively eliminate the plurality loser until there is a Condorcet winner among remaining candidates. An equivalent method to this is to do an IRV tally, give each candidate a score according to the number of candidates eliminated before them, and then choose the Smith set candidate with the highest score. Douglas Woodall seems to have proposed this in 2003 or earlier, though I'm not sure if he has done so in any published forum. In our discussion, Chris Benham and I resolved that the former approach has the advantage of satisfying the 'local IIA' criterion (which states that adding a candidate outside the Smith set should not affect an election result), while Woodall's approach has the advantage of satisfying the 'mono-add-plump' and 'mono-append' criteria (which are defined, for example, in Woodall's Properties of Preferential Election Rules, Voting Matters December 1994). Chris feels that the monotonicity criteria are more important, but I remain undecided about that. My conclusion at this point is that neither approach entirely dominates the other. One thing that I will say in favor of Woodall's approach is that it has the simplest definition, which suggests a certain elegance, and which means that it would probably be easier to sell to a skeptical public. I've run a few of my election strategy simulations on Woodall's method, and so far I've found no difference between its performance and that of the other approach. So, both approaches seem to share these three highly desirable properties: (1) Smith efficiency, (2) minimal vulnerability to strategic voting, and (3) minimal voting to strategic nomination. In my opinion, this combination is a really big deal, and I look forward to further discussion of these methods. Sincerely, James Election-Methods mailing list - see http://electorama.com/em for list info
[EM] election strategy paper, alternative Smith, web site relaunch
James Green-Armytage wrote (20 Nov 2010):
snip
In addition to the nine methods listed above, I tried some of my
analyses with six other Condorcet methods: beatpath, ranked pairs,
Smith/Hare, alternative Smith, and two versions of cardinal pairwise.
Beatpath and ranked pairs generally seem to perform like minimax, and
cardinal pairwise usually but not always performs somewhat better than
these, but the really striking news in my opinion is how well the
Hare-Condorcet hybrids perform.
That is, given a preliminary analysis, they seem to be as resistant to
strategic voting as Hare (and possibly slightly more resistant), and
they are distinctly less vulnerable to strategic nomination (because
they are Smith efficient, and therefore only vulnerable to strategic
nomination when there is a majority rule cycle). So, for single-winner
public elections, alternative Smith and Smith/Hare seem to have a lot
to recommend them, i.e. the combination of Smith efficiency with
strong resistance to both types of election strategy.
I should define these methods here, for clarity. Smith/Hare eliminates
all candidates not in the Smith set (minimal dominant set, i.e. the
smallest set of candidates such that all members in the set pairwise
beat all members outside the set), and then holds an IRV tally among
remaining candidates. This method has been floating around this list
for a while, yes? Does anyone know of an academic publication that
mentions it? I seem to remember reading something that said that it
had been named after a person at some point, but I no longer know
where I read that.
Alternative Smith is a closely related method, which Nic Tideman made
up when he was writing Collective Decisions and Voting. It (1)
eliminates all candidates not in the Smith set, then (2) eliminates
the candidate with the fewest top-choice votes. Steps 1 and 2
alternate until only one candidate remains. (See page 232 of the
book.) I focus on this rule rather than Smith/Hare in the paper,
because I find it marginally more elegant, but the difference between
the two is very minor.
James,
We discussed these Hare-Condorcet hybrids on EM in the months of
October and
November 2005. Then I quoted Douglas Woodall's demonstration that both
the versions
you discuss fail Mono-add-Plump and Mono-append.
abcd 10
bcda 6
c 2
dcab 5
All the candidates are in the top tier, and the AV winner is a. But
if you add two extra ballots that plump for a, or append a to the two
ballots, then the CNTT becomes {a,b,c}, and if you delete d from all
the ballots before applying AV then c wins.
Translating to a more familiar EM format:
10: ABCD
06: BCDA
02: C
05: DCAB
All candidates are in the Smith set (Woodall's Condorcet-Net Top
Tier), and the Hare
(aka Alternative Vote, aka IRV) winner is A.
But if you add 2 ballots that bullet-vote (plump) for A, or change the
two C ballots to CA,
the Smith set becomes {A B C}, and if you delete D from all the ballots
from all the ballots before
applying Hare (i.e. properly eliminate D and not just disqualify D
from winning) then C wins.
Smith,Hare (which Woodall called CNTT,AV) meets those criteria and has
a simpler algorithm:
Begiinining with their most preferred candidate, voters strictly rank
however many candidates they wish.
Before each (and any) elimination, check for a candidate X that
pairwise beats all (so far uneliminated)
candidates. Until such an X appears, one-at-a-time eliminate the
candidate that is voted favourite
(among uneliminated candidates) on the fewest ballots. As soon as an X
appears, elect X.
So why put up with failures of mono-add-plump and mono-append? What
advantage (if any) do you think
the two versions you discuss have over Smith,Hare to compensate for that?
Chris Benham
Election-Methods mailing list - see http://electorama.com/em for list info
[EM] election strategy paper, alternative Smith, web site relaunch
quoting Jameson Quinn: These two facts seem somewhat contradictory, since in order for Hare to elect the Condorcet winner, voters must frequently use strategy. Are you saying that strategy is even more frequent in other methods? My reply: You're correct that if the sincere Condorcet winner is not also the sincere Hare winner, then sincere voting will not be a core equilibrium in Hare. However, I find that the sincere Condorcet winner usually is the sincere Hare winner, in most of my specifications. Further, when the two sincere winners are the same, the result is highly unlikely to be manipulable in Hare. quoting Jameson Quinn: Also, what's your voter model? All possible sets of voter preferences? Real elections, of course, frequently have much lower entropy than such a model; but any other model involves questionable assumptions. My reply: Right. Well, the simplest and most complete answer to your question is to refer you to section 3 of my paper, but I don't see the harm in giving a short explanation here as well. First, for any of this to make sense, I should mention that my measure of 'how vulnerable' a method is to manipulation is just the fraction of trials in which manipulation that benefits all manipulators is logically possible. Of course there are other ways to measure it, but this method requires the fewest assumptions, so I think that it's a good place to start. (Also, it's the most common approach used in the literature, as I discuss briefly in the introduction.) Now, about the models. I actually use three distinct models, and several specifications within each of these. The first is a spatial model, in which both candidates and voters are randomly placed in an S-dimensional issue space according to a multivariate normal distribution, with variances of 1 and covariances of 0. Voters prefer candidates who are closer to them in this space. The second is an impartial culture model, in which each voter's utility from each candidate is an independent random variable. (I use a uniform distribution for this, but this is irrelevant where ranking-based methods are concerned, because only the preference ordering matters to the analysis.) My third data generating process is derived from political survey data, specifically the American National Election Studies. You can download the data set for free at http://www.electionstudies.org/studypages/download/datacenter_all.htm (I used the June 2010 time series cumulative data file.) Since the 60's, this survey has been asking people to rate various politicians on a scale from 0 to 100; since there's no actual election attached to this, it seems fair to treat these as sincere cardinal ratings. For a given number of candidates C, and a given year, I find all the C-candidate subsets of the rated candidates for that year, and analyze them as separate elections. I take a simple average over the years to get an overall percentage for each given number of candidates. Actually, the idea to use the ANES data in this way comes from Nic Tideman and Florenz Plassman, who do something pretty similar in an as-yet unpublished paper called The Structure of the Election-Generating Universe. You can find their working draft of that paper at http://bingweb.binghamton.edu/~fplass/papers/ElectionGeneratingUniverse.pdf So, there are three models. One of the things that makes this paper relatively strong, in my opinion, is that it produces a set of results that are supported by all three models, which is cool, because they're really very different from each other. For example, have a look at the graphs in section 6 (which are between pages 23 and 28 of the current version). I show results from the three models side by side, and although of course they're not identical, there are very strong patterns that are immediately apparent. The raw percentage of elections in which manipulation is possible is of course highly sensitive to the specification used, but there are a set of comparative relationships between the voting rules that seem to be remarkably stable across models and specifications. In terms of overall strategic voting vulnerability, as I said, Hare and runoff are usually the least manipulable in general, minimax, plurality, and Bucklin are usually intermediate (and minimax is usually best among these), and range, approval, Borda, and Coombs are generally most manipulable. Also, these differences tend to be quite large -- not just a matter of a few percentage points here and there. When we look at just compromising strategies, plurality is the most vulnerable in just about every specification, minimax is consistently second-best (after Coombs, which is immune), and Borda, range, Bucklin, and approval are generally worse than runoff and Hare. When it comes to burying, the plurality-based methods (plurality, runoff, and Hare) are immune, and
Re: [EM] election strategy paper, alternative Smith, web site relaunch
Kristofer Munsterhjelm wrote: James Green-Armytage wrote: So, the nomination results are a little less robust, but many of them seem pretty intuitive. For example, it makes perfect sense to me that plurality would be most vulnerable to strategic exit, and that minimax would be minimally vulnerable to strategic nomination. It also makes sense that Borda would be highly vulnerable to strategic entry (I give some intuition for this in proposition 21), but I'm not as yet able to give a good explanation for why Bucklin seems to be even more vulnerable to strategic entry. Does anyone here want to try their hand at that? I added Bucklin and Coombs to the paper at kind of the last minute (September), so there's at least some possibility of a programming glitch, but I've checked through several examples, and it seems to be working properly, as far as I can tell. Perhaps adding allied candidates in Bucklin delays the point at which other candidates can get a majority. Say you have some friendly voters who votes A first, as well as a bunch of other voters who may vote another candidate B in any position. B wins. Then the friendly voters turn A into A1, A2, A3, etc. On every ballot that votes A ahead of B, this will push B further away so that the voters who do vote B ahead of A don't get their contribution to B aligned with the AB voters' contribution to B until much later, at which point A might already have won. To be a little more precise, I mean that A1, A2, A3 etc. enter, as in strategic nomination, and that all voters, not just the friendly ones, rank them. Election-Methods mailing list - see http://electorama.com/em for list info
[EM] election strategy paper, alternative Smith, web site relaunch
James Green-Armytage wrote ... snip I should define these methods here, for clarity. Smith/Hare eliminates all candidates not in the Smith set (minimal dominant set, i.e. the smallest set of candidates such that all members in the set pairwise beat all members outside the set), and then holds an IRV tally among remaining candidates. This method has been floating around this list for a while, yes? Does anyone know of an academic publication that mentions it? I seem to remember reading something that said that it had been named after a person at some point, but I no longer know where I read that. Was the name Loring? I think Loring is an Hare-Condorcet hybrid that doesn't restrict to the Smith set. Election-Methods mailing list - see http://electorama.com/em for list info
[EM] election strategy paper, alternative Smith, web site relaunch
Dear election methods fans,
I recently completed a much higher-quality version of my 2008 election
strategy paper. I'm using this as an academic job market paper, so if
you do see an error in it, I'd definitely like to know. Here is a link:
http://www.econ.ucsb.edu/~armytage/svn2010.pdf
I'd also love it if one or two people would take a look at the codes
for the primary voting strategy analysis, which can be found at
http://www.econ.ucsb.edu/~armytage/codes.pdf They're for matlab, and
they should start to make sense if you read section 4.1. of the paper.
A quick summary:
I focus primarily on 9 methods: plurality, runoff, Hare (IRV), minimax
('plain Condorcet'), Borda, approval, range, Bucklin, and Coombs.
In my computer simulations, I find that Hare and runoff are least
frequently vulnerable to strategic voting, and that Borda, approval,
Coombs, and range are most frequently vulnerable to strategic voting.
I find that plurality is most vulnerable to strategic exit, and that
Borda and Bucklin are most vulnerable to strategic entry. I assume
that approval and range are minimally vulnerable to strategic
nomination, and aside from these two methods I find that minimax is
the next least vulnerable.
In addition to the computer simulations, I construct 22 relevant
proofs, some of which may be of interest to some of you. For example,
leaving aside the possibility of pairwise ties, I find that the
existence of a sincere Condorcet winner is a necessary and sufficient
condition for the existence of a core equilibrium in 8 of these 9
methods, but that in the Borda count, it is necessary but not
sufficient. The sufficient condition is for the Condorcet winner to
have supermajority beats against all candidates, with sizes of at
least [(2C-2)/(3C-2)]*V, where C is the number of candidates, and V is
the number of voters.
In addition to the nine methods listed above, I tried some of my
analyses with six other Condorcet methods: beatpath, ranked pairs,
Smith/Hare, alternative Smith, and two versions of cardinal pairwise.
Beatpath and ranked pairs generally seem to perform like minimax, and
cardinal pairwise usually but not always performs somewhat better than
these, but the really striking news in my opinion is how well the
Hare-Condorcet hybrids perform.
That is, given a preliminary analysis, they seem to be as resistant to
strategic voting as Hare (and possibly slightly more resistant), and
they are distinctly less vulnerable to strategic nomination (because
they are Smith efficient, and therefore only vulnerable to strategic
nomination when there is a majority rule cycle). So, for single-winner
public elections, alternative Smith and Smith/Hare seem to have a lot
to recommend them, i.e. the combination of Smith efficiency with
strong resistance to both types of election strategy.
I should define these methods here, for clarity. Smith/Hare eliminates
all candidates not in the Smith set (minimal dominant set, i.e. the
smallest set of candidates such that all members in the set pairwise
beat all members outside the set), and then holds an IRV tally among
remaining candidates. This method has been floating around this list
for a while, yes? Does anyone know of an academic publication that
mentions it? I seem to remember reading something that said that it
had been named after a person at some point, but I no longer know
where I read that.
Alternative Smith is a closely related method, which Nic Tideman made
up when he was writing Collective Decisions and Voting. It (1)
eliminates all candidates not in the Smith set, then (2) eliminates
the candidate with the fewest top-choice votes. Steps 1 and 2
alternate until only one candidate remains. (See page 232 of the
book.) I focus on this rule rather than Smith/Hare in the paper,
because I find it marginally more elegant, but the difference between
the two is very minor.
my best,
James
P.S. My web site is back, mostly. The Antioch address got unplugged
because of the split between Antioch College and Antioch University,
so I've set up a new version of the site at
http://www.econ.ucsb.edu/~armytage/voting/
I've taken down several of the peripheral articles, though if anyone
wants to see them (unlikely, I assume), I still have them on my
computer. Comments on my most recent proxy voting paper (which is on
the site) are still quite welcome, by the way.
Election-Methods mailing list - see http://electorama.com/em for list info
Re: [EM] election strategy paper, alternative Smith, web site relaunch
A quick summary: Quick reaction: ... I find that Hare and runoff are least frequently vulnerable to strategic voting, ... ... leaving aside the possibility of pairwise ties, I find that the existence of a sincere Condorcet winner is a necessary and sufficient condition for the existence of a core equilibrium in 8 of these 9 methods... These two facts seem somewhat contradictory, since in order for Hare to elect the Condorcet winner, voters must frequently use strategy. Are you saying that strategy is even more frequent in other methods? Also, what's your voter model? All possible sets of voter preferences? Real elections, of course, frequently have much lower entropy than such a model; but any other model involves questionable assumptions. I'll read the paper and give further comments when I can. JQ but that in the Borda count, it is necessary but not sufficient. The sufficient condition is for the Condorcet winner to have supermajority beats against all candidates, with sizes of at least [(2C-2)/(3C-2)]*V, where C is the number of candidates, and V is the number of voters. In addition to the nine methods listed above, I tried some of my analyses with six other Condorcet methods: beatpath, ranked pairs, Smith/Hare, alternative Smith, and two versions of cardinal pairwise. Beatpath and ranked pairs generally seem to perform like minimax, and cardinal pairwise usually but not always performs somewhat better than these, but the really striking news in my opinion is how well the Hare-Condorcet hybrids perform. That is, given a preliminary analysis, they seem to be as resistant to strategic voting as Hare (and possibly slightly more resistant), and they are distinctly less vulnerable to strategic nomination (because they are Smith efficient, and therefore only vulnerable to strategic nomination when there is a majority rule cycle). So, for single-winner public elections, alternative Smith and Smith/Hare seem to have a lot to recommend them, i.e. the combination of Smith efficiency with strong resistance to both types of election strategy. I should define these methods here, for clarity. Smith/Hare eliminates all candidates not in the Smith set (minimal dominant set, i.e. the smallest set of candidates such that all members in the set pairwise beat all members outside the set), and then holds an IRV tally among remaining candidates. This method has been floating around this list for a while, yes? Does anyone know of an academic publication that mentions it? I seem to remember reading something that said that it had been named after a person at some point, but I no longer know where I read that. Alternative Smith is a closely related method, which Nic Tideman made up when he was writing Collective Decisions and Voting. It (1) eliminates all candidates not in the Smith set, then (2) eliminates the candidate with the fewest top-choice votes. Steps 1 and 2 alternate until only one candidate remains. (See page 232 of the book.) I focus on this rule rather than Smith/Hare in the paper, because I find it marginally more elegant, but the difference between the two is very minor. my best, James P.S. My web site is back, mostly. The Antioch address got unplugged because of the split between Antioch College and Antioch University, so I've set up a new version of the site at http://www.econ.ucsb.edu/~armytage/voting/ I've taken down several of the peripheral articles, though if anyone wants to see them (unlikely, I assume), I still have them on my computer. Comments on my most recent proxy voting paper (which is on the site) are still quite welcome, by the way. Election-Methods mailing list - see http://electorama.com/em for list info Election-Methods mailing list - see http://electorama.com/em for list info
