Skip to content

Instantly share code, notes, and snippets.

@asafh asafh/pairs.js
Last active Feb 24, 2019

Embed
What would you like to do?
Ranked Pair voting
/**
* Runs electSingle until at least *wanted* winners are elected, returns the first *wanted* winners.
* @param candidates see electSingle
* @param getScore see electSingle
* @param ballots see electSingle
* @param wanted the number of wanted winners
* @returns [candidate] Array of candidates of size *wanted* (given that there are enough candidates)
*/
function elect(candidates, getScore, ballots, wanted) {
if(typeof wanted !== "number") {
wanted = 1;
}
var winners = [];
while (winners.length < wanted) {
var thisElection = electSingle(candidates, getScore, ballots);
if (!thisElection.length) {
console.log("Could not elect enough?");
break;
}
winners.push.apply(winners, thisElection);
if (winners.length == wanted) {
break;
}
else if (winners.length > wanted) {
console.log("Too many winners, removing extras");
winners.splice(wanted, winners.length);
break;
}
candidates = candidates.filter(function (candidate) {
return thisElection.indexOf(candidate) === -1;
});
}
return winners;
}
/**
* Runs the a Ranked Pairs vote, and returns an array of winners (which is usually single, unless the graph has more than
* one source)
* @param candidates An array of strings, each representing a candidate
* @param getScore function(candidate, ballot) => preference # (i.e. lower is preferred)
* @param ballots array of <any>, each is a ballot that is passed to getScore
* @returns [candidate] Array of candidates which are the sources of the locked-in graph.
*/
function electSingle(candidates, getScore, ballots) {
if (!candidates.length) {
return [];
}
console.log(ballots.length + " Ballots:")
console.log(candidates.join("\t"));
ballots.forEach(function (ballot) {
var scores = candidates.map(function (cid) {
return getScore(cid, ballot);
});
console.log(scores.join("\t"));
});
var V = {};
var majorities = [];
candidates.forEach(function (xCID) {
var Vx = V[xCID] = {};
candidates.forEach(function (yCID) {
if (yCID == xCID) {
return;
}
Vx[yCID] = ballots.reduce(function (count, ballot) {
return count + (getScore(xCID, ballot) < getScore(yCID, ballot) ? 1 : 0);
},0);
majorities.push({x: xCID, y: yCID, Vxy: Vx[yCID]});
});
});
majorities.sort(function (m1, m2) {
var x = m1.x, y = m1.y, z = m2.x, w = m2.y;
var diff = m1.Vxy - m2.Vxy //Vxy - Vzw
if (diff > 0) { //Vxy > Vzw
return 1;
}
if (diff == 0) {
return V[w][z] - V[y][x]; // Vwz > Vyx Smaller minority opposition (now wz and yz)
}
return -1;
}).reverse();
console.log("Majorities:\n", majorities);
//Lock in:
var G = {};
candidates.forEach(function (candidate) {
G[candidate] = [];
});
function reachable(from, to) {
var nFrom = G[from];
//Can be reached from one of my connections:
return nFrom.some(function (neighbor) {
return neighbor == to || reachable(neighbor, to);
});
}
majorities.forEach(function (m) {
if (reachable(m.y, m.x)) { //if x is accessible from y, then x->y would create a circle
return;
}
(G[m.x] = G[m.x] || []).push(m.y);
});
console.log("Locked Graph:\n", G);
var sources = candidates.filter(function (candidate) {
return candidates.every(function (neighbor) { //not reachable from every candidate.
return G[neighbor].indexOf(candidate) === -1;
});
});
console.log("Graph Sources:", sources);
return sources;
}
//Wikipedia example, working:
var cities = ["Memphis","Nashville", "Chattanooga","Knoxville"];
var ballots = Array.apply(null, {length: 100}).map(Number.call, Number).map(function(i) {
i -= 42;
if(i<0) { //mem
return ["Memphis","Nashville","Chattanooga", "Knoxville"];
}
i -= 26;
if(i<0) { //nash
return ["Nashville","Chattanooga", "Knoxville", "Memphis"];
}
i -= 15;
if(i< 0) { //chat
return ["Chattanooga", "Knoxville", "Nashville", "Memphis"];
}
//kno
return ["Knoxville", "Chattanooga", "Nashville", "Memphis"];
})
winners = elect(cities, function(city, ballot) {
return ballot.indexOf(city);
}, ballots, 2);
console.log("Winners:");
winners.forEach(function (winner, i) {
console.log("Winner #", i + 1, winner);
});
@Doogiemuc

This comment has been minimized.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.