Skip to content

Instantly share code, notes, and snippets.

@asafh
Last active October 5, 2021 23:49
Show Gist options
  • Save asafh/a8e9af7a3e5282cbba27 to your computer and use it in GitHub Desktop.
Save asafh/a8e9af7a3e5282cbba27 to your computer and use it in GitHub Desktop.
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
Copy link

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment