# Condorcet winners in DHTML

I was thinking last night about how an election can fail to have a
Condorcet winner, and I wondered what fraction of all possible

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

<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))
}
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 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(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>
<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>