I was thinking last night about how an election can fail to have a Condorcet winner, and I wondered what fraction of all possible elections had that property.
Rather than spending half an hour looking up the answer on Google and reading it (finding e.g. http://arxiv.org/abs/math.ST/0511140 for three candidates) I thought it would be fun to spend three hours hacking up some code that wouldn't actually give me an answer, but maybe would give me some feel for the answer. (It turns out that the vague answer is that having no Condorcet winner is a common phenomenon.) So here it is. It, or some later version, is also online at http://pobox.com/~kragen/sw/condorcet.html <html><head><title>Condorcet cycles</title> <script type="text/javascript"> /* TODO: * D create adjustable parameters for voters and candidates * D randomly generate voter prefs with button * D display voter prefs * D display voter prefs in columns of table * D come up with candidate names * D come up with candidate colors * D display candidate/candidate matrix * D compute Condorcet winner * (at this point I only had 70 minutes left before kragen-hacks goes out) * D compute FPTP and Borda count winners * (at this point I had 20 minutes left) * - compute dominant cycle if no winner * - color-code voters on mouseover of candidate comparisons * - support drag-and-drop modification of voter prefs? * D generate candidate colors randomly? */ /* very basic functions needed even for class Candidate */ function map(func, alist) { var rv = [] for (var ii = 0; ii < alist.length; ii++) rv.push(func(alist[ii])) return rv } function tag(tagname) { return function(content) { return '<' + tagname + '>' + content + '</' + tagname + '>' } } function font(color, content) { return tag('font color="' + color + '"')(content) } function all(alist) { for (var ii = 0; ii < alist.length; ii++) if (!alist[ii]) return false return true } function sum(alist) { var rv = 0 for (var ii = 0; ii < alist.length; ii++) rv += alist[ii] return rv } /* class Candidate */ function Candidate(name, color) { this.name = name this.color = color } Candidate.prototype.as_html = function() { return font(this.color, this.name) } Candidate.prototype.compare = function(other_candidate, voters) { var wins = 0 var losses = 0 for (var ii = 0; ii < voters.length; ii++) { if (voters[ii].prefers(this, other_candidate)) { wins++ } else { losses++ } } return [wins, losses] } Candidate.prototype.beats = function(other_candidate, voters) { var comparison = this.compare(other_candidate, voters) return comparison[0] > comparison[1] } Candidate.prototype.beats_all = function(candidates, voters) { var self = this return all(map(function(candidate) { return self.beats(candidate, voters) }, candidates)) } Candidate.prototype.fptp_votes = function(voters) { var self = this return sum(map(function(voter) { return voter.prefs[0] == self ? 1 : 0 }, voters)) } Candidate.prototype.borda_count = function(voters) { var self = this return sum(map(function(voter) { return voter.borda_count(self) }, voters)) } /* end class Candidate */ /* very basic functions needed for class Voter */ function identity(obj) { return obj } function copylist(alist) { return map(identity, alist) } function randrange(max) { return parseInt(Math.random() * max) } function method(methodname) { // XXX should take extra parameters somewhere... return function(obj) { return obj[methodname]() } } function Voter(candidates, voterid) { this.voterid = voterid this.prefs = copylist(candidates) for (var ii = 0; ii < this.prefs.length; ii++) { var pos = randrange(ii+1) var tmp = this.prefs[pos] this.prefs[pos] = this.prefs[ii] this.prefs[ii] = tmp } } Voter.prototype.ballot = function() { return ['Voter #' + this.voterid].concat(map(method("as_html"), this.prefs)) } Voter.prototype.prefers = function(a, b) { for (var ii = 0; ii < this.prefs.length; ii++) { var cand = this.prefs[ii] if (cand == a) return true if (cand == b) return false } throw "candidate not in list" } Voter.prototype.borda_count = function(candidate) { for (var ii = 0; ii < this.prefs.length; ii++) if (this.prefs[ii] == candidate) return this.prefs.length - ii throw "candidate not in list" } /* end class Voter */ /* main program routines, with HTML and so forth */ td = tag('td') tr = tag('tr') th = tag('th') function elem(id) { return document.getElementById(id) } function table_innerHTML(matrix) { var rv = [] for (var ii = 0; ii < matrix.length; ii++) { var row = [] for (var jj = 0; jj < matrix[ii].length; jj++) row.push((ii == 0 ? th : td)(matrix[ii][jj])) rv.push(tr(row.join('\n'))) } return rv.join('\n') } function transpose(matrix) { var rv = [] // XXX does not work for empty matrix for (var jj = 0; jj < matrix[0].length; jj++) rv.push([]) for (var ii = 0; ii < matrix.length; ii++) for (var jj = 0; jj < matrix[0].length; jj++) rv[jj].push(matrix[ii][jj]) return rv } function display_voters(dest, voters) { elem(dest).innerHTML = table_innerHTML(transpose( map(method('ballot'), voters))) } function candidate_row(candidates, voters) { return function(row_candidate) { return tr(th(row_candidate.as_html()) + map( function(column_candidate) { if (row_candidate == column_candidate) return td('') var comp = row_candidate.compare(column_candidate, voters) var color = ((comp[0] > comp[1]) ? row_candidate.color : (comp[1] > comp[0]) ? column_candidate.color : 'grey') return td(font(color, comp[0] + '-' + comp[1])) }, candidates).join('') ) } } function compose(f, g) { return function(obj) { return f(g(obj)) } } function display_pairwise(dest, candidates, voters) { var cand_hdr_top = tr(td('') + map(compose(th, method("as_html")), candidates).join('')) var cand_rows = map(candidate_row(candidates, voters), candidates) elem(dest).innerHTML = cand_hdr_top + cand_rows.join('\n') } function display_winner(dest, candidates, voters) { var winner = "No candidate" for (var ii = 0; ii < candidates.length; ii++) { var cand = candidates[ii] if (cand.beats_all(candidates, voters)) { winner = cand.as_html() } } elem(dest).innerHTML = winner + " is the Condorcet winner." } function update_winner(current, name, score) { if (score > current[1]) { current[0] = name current[1] = score } else if (score == current[1]) { if (current[0]) /* initially null */ current[0] = "tied" } } function display_other_winners(table, fptp, borda, candidates, voters) { var table_headers = [tr(th('Candidate') + th('FPTP') + th('Borda'))] var fptp_winner = [null, 0] var borda_winner = [null, 0] var table_rows = map(function(candidate) { var fptp_votes = candidate.fptp_votes(voters) update_winner(fptp_winner, candidate.as_html(), fptp_votes) var borda_count = candidate.borda_count(voters) update_winner(borda_winner, candidate.as_html(), borda_count) return tr(th(candidate.as_html()) + td(fptp_votes) + td(borda_count)) }, candidates) elem(table).innerHTML = table_headers.concat(table_rows).join('\n') elem(fptp).innerHTML = fptp_winner[0] elem(borda).innerHTML = borda_winner[0] } function candidate_name(ii) { /* http://www.census.gov/genealogy/names/names_files.html */ var candidate_names = [ 'Margaret', 'Dorothy', 'Charles', 'Richard', 'Maria', 'Thomas', 'Jennifer', 'Elizabeth', 'Joseph', 'David', 'James', 'Mary', 'Patricia', 'William', 'John', 'Susan', 'Michael', 'Barbara', 'Linda', 'Robert', ] if (ii < candidate_names.length) return candidate_names[ii] return 'Candidate #' + ii } function randhex() { return ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'][randrange(16)] } var candidate_color = function(ii) { var colors = [ 'black', 'red', 'blue', 'cyan', 'magenta', 'green', 'yellow', 'orange', 'purple', 'bluegreen' ] if (ii < colors.length) return colors[ii] var r = randhex() var g = randhex() var b = randhex() return '#' + r + r + g + g + b + b } function range(n) { var rv = [] for (var ii = 0; ii < n; ii++) rv.push(ii) return rv } /* main program entry point */ function election(form) { var n_voters = form.voters.value var n_candidates = form.candidates.value var candidates = map(function(ii) { return new Candidate(candidate_name(ii), candidate_color(ii)) }, range(n_candidates)) var voters = map(function(ii) { return new Voter(candidates, ii) }, range(n_voters)) display_voters('voterlist', voters) display_pairwise('matrix', candidates, voters) display_winner('winner', candidates, voters) display_other_winners('othervotingsystems', 'fptp-winner', 'borda-winner', candidates, voters) } </script> </head> <body onload="election(document.forms[0])"> <h1>Condorcet winners</h1> <p>The "Condorcet winner" of an election is the candidate that is preferred by a majority of the voters over any other single candidate. The basic idea is that each voter has some order of preference of the available candidates, and you can tell which candidate they prefer out of any pair by comparing their ranks in that list.</p> <p>A well-known problem is that, if there are more than two candidates and more than four voters, there may not be a Condorcet winner in a particular election. The case with three candidates ABC and five voters is as follows: ABC, ABC, CAB, CAB, BCA. A is preferred to B by four out of five; C is preferred to A by three out of five; and B is preferred to C by three out of five. Such examples demonstrate that the idea of a Condorcet winner does not solve the problem of collective choice; it's an interesting question how probable the existence of a Condorcet winner is.</p> <p>So here's a little experimental environment. You can set the number of voters and the number of candidates and randomly generate the preferences for each voter, and see the Condorcet results....</p> <form onsubmit="election(this); return false"> <label for="voters">Voters: </label><input id="voters" name="voters" value="15" size="4" /> <label for="candidates">Candidates: </label><input id="candidates" name="candidates" value="9" size="4" /> <input type="submit" value="Elect!" /> </form> <h2>Individual voter ballots:</h2> <table id="voterlist"> <tr><td>No election yet.</td></tr> </table> <h2>Pairwise matchups:</h2> <table id="matrix"> <tr><td>No election yet.</td></tr> </table> <h2>Condorcet winner</h2> <p>A Condorcet winner will appear in the matrix of pairwise matches with their entire row and their entire column a single solid color: their color.</p> <p id="winner">No election yet.</p> <h2>Other voting systems</h2> <p>In first-past-the-post (used, for instance, in the US presidential election and most other US elections) each voter votes for exactly one candidate, and the candidate with the most votes wins. If we assume "sincere voting" --- each voter votes for their first choice --- we can deduce the FPTP results from the preference orders displayed above; the winner is <span id="fptp-winner">not yet computed</span>. Obviously this is a terrible system, and every other voting system proposed so far has been proposed because its proponents think it is better.</p> <p>In the Borda count, your last choice gets 1 point; your next-to-last choice gets 2 points; and so forth, until your first choice gets as many points as there are candidates. The Borda count winner of this election is <span id="borda-winner">not yet computed</span>. </p> <table id="othervotingsystems"> <tr><td>No election yet.</td></tr> </table> </body></html>
