31:T573,md`### How to rank lotteries ? Lottery A is considered better or similar to a lottery B if on average i.e. according to the Tournament graph the candidate picked by Lottery A wins over the candidate picked by Lottery B. #### Example Consider the ballot with the Tournament graph and Payoff table above. Compare lottery P = {A: 1/2, B: 1/4, C: 1/4} and Q = {A: 1/2, B: 1/2}. Lotteries P and Q are like to opponents in the a game similar to [Paper-Rock-Scissor](https://en.wikipedia.org/wiki/Rock%E2%80%93paper%E2%80%93scissors). Here the elements in payoff matrix represent the gain for the player associated with first column "Win" and symmetrically the loss for the player associated with first row "Lose". We could run random simulations and count the winners for randomy generated candidates picked by P vs. Q probability distributions. Instead we can simply determine the winning lottery from matrix G and P, Q expressed as corresponding vectors. ${tex.block`\mathbf{P} = \begin{bmatrix} 1/2\\ 1/4\\ 1/4\\ 0 \end{bmatrix}\quad \mathbf{Q} = \begin{bmatrix} 1/2\\ 1/2\\ 0\\ 0 \end{bmatrix}\quad \mathbf{G} = \begin{bmatrix} 0 & -1 & -1 & -1\\ 1 & 0 & 1 & -1\\ 1 & -1 & 0 & 1\\ 1 & 1 & -1 & 0 \end{bmatrix}`} In this case the payoff for player P is ${tex.block`\mathbf{P}^{T} \cdot \mathbf{G}\cdot \mathbf{Q} = -1/8 < 0`} Consequently lottery Q wins over P. `32:T780,md`#### Example: If Player 1 makes move ${tex`i=3`} and Player 2 makes move ${tex`j=2`} then Player 1 wins ${tex`a_{32}`} and Player loses ${tex`a_{32}`}. Now let us assume Player 1 and Player 2 play with respective probabilities ${tex.block`(p_i)_{i=1, 2, 3}`} ${tex.block`(q_i)_{i=1, 2, 3, 4}`} From the point of view of Player 2 ${tex`(q_i)`} must be determined so as to minimize the maximum gain for Player 1: ${tex.block`\min_\mathbf{q} \left \{ \max_i \sum_{j=1}^{4} a_{ij}q_j \right \} \quad subject\ to \quad \sum_{j=1}^{4} q_j = 1, \quad \mathbf{q}\geq 0`} Which is equivalent to: ${tex.block`\min_{\mathbf{q}, v} v \quad subject\ to \quad \forall i \quad \sum_{j=1}^{4} a_{ij}q_j \leq v , \quad \sum_{j=1}^{4} q_j = 1, \quad \mathbf{q}\geq 0`} If ${tex`v>0`} (else add constant to ${tex`a_{ij}`} so that ${tex`v>0`}) and we define ${tex`x_j = q_j/v`} then the problem becomes: ${tex.block`\min_{\mathbf{x}, v} v \quad subject\ to \quad \forall i \quad \sum_{j=1}^{4} a_{ij}x_j \leq 1 , \quad \sum_{j=1}^{4} x_j = 1/v, \quad \mathbf{q}\geq 0`} Which is equivalent to: ${tex.block`\max_\mathbf{x} \sum_{j=1}^{4} x_j \quad subject\ to \quad \mathbf{A}\mathbf{x} \leq \mathbf{1} , \quad \mathbf{x}\geq 0`} Similarly from Player 1 perspective ${tex`(p_i)`} must be determined so as to minimize the maximum gain for Player 2: The reasoning leads to the dual problem, where ${tex`v>0`} (else add constant to ${tex`a_{ij}`} so that ${tex`v>0`}) and ${tex`y_j = p_j/v`} : ${tex.block`\min_\mathbf{y} \sum_{j=1}^{3} y_j \quad subject\ to \quad \mathbf{A}^T\mathbf{y} \geq \mathbf{1} , \quad \mathbf{y}\geq 0`} In this case, which is less general, matrix ${tex`\mathbf{A}`} is symmetric. Thus the solutions of the direct and dual problems must give the same results, which, after normalization, is the **best lottery** i.e. the best probability distribution to select the winner. `33:T1125,buildGraph = params => { const { data, width = 960, height = 400, strength = -1e4, theta = 0.1, radius = 35, linkColor = '#121212', winnerOpacity = 0.4 } = params; const uuid = Math.floor(Math.random() * 1e9); const colors = d3.scaleOrdinal(d3.schemeCategory10); const dataC = clone(data); const dataNodes = dataC.nodes; const dataLinks = dataC.links; console.log(JSON.stringify(data)); const simulation = d3 .forceSimulation(dataNodes) .force("link", d3.forceLink(dataLinks).id(d => d.id)) .force( "charge", d3 .forceManyBody() .strength(strength) .theta(theta) .distanceMin(10) // .distanceMin(height) ) .force("center", d3.forceCenter(width / 2, height / 2)); const svg = d3 .create('svg') .attr('width', width) .attr('height', height); console.log({ radius }); svg .append('defs') .append('marker') .attr('id', `arrowhead-${uuid}`) .attr('viewBox', '-0 -5 10 10') .attr('refX', radius + 0) .attr('refY', 0) .attr('orient', 'auto') .attr('markerWidth', 10) .attr('markerHeight', 10) .attr('xoverflow', 'visible') .append('svg:path') .attr('d', 'M 0,-5 L 10 ,0 L 0,5') .attr('fill', linkColor) .attr('stroke', linkColor); const gLink = svg .append("g") .selectAll(".link") .data(dataLinks) .join("g") .attr("class", 'link'); const link = gLink .append('line') .attr("stroke", linkColor) .attr("stroke-width", 1.5) .attr("stroke-opacity", 0.8) .attr('marker-end', `url(#arrowhead-${uuid})`); const linkLabel = gLink .append('text') .attr("stroke-width", 0) .attr('fill', 'darkgray') .attr('dy', -5) .attr("text-anchor", 'middle') .text(d => d.label); const gNode = svg .append("g") .selectAll(".node") .data(dataNodes) .join('g') .attr("class", 'node') .call(drag(simulation)); const nodeWinner = gNode .append('circle') .attr("r", d => (d.proba > 0 ? radius + 5 : 0)) .attr("opacity", winnerOpacity) .attr("stroke", "red") .attr("stroke-width", 2.0) .attr("fill", 'transparent'); const nodeCondorcetWinner = gNode .append('circle') .attr("r", d => (d.probaStr === '1/1' ? radius + 10 : 0)) .attr("opacity", winnerOpacity) .attr("stroke", "red") .attr("stroke-width", 2.0) .attr("fill", 'transparent'); const node = gNode .append("circle") .attr("r", radius) .attr("stroke", linkColor) .attr("stroke-width", 1.5) .attr("fill", (e, i) => colors(i)); const nodeId = gNode .append("text") .attr("stroke-width", 0) .attr('fill', 'black') .attr("dx", '0em') .attr("dy", '0.25em') .attr("text-anchor", 'middle') .text(d => d.id); const nodeProba = gNode .append("text") .attr("stroke-width", 0) .attr('fill', 'red') .attr("dx", '3.5em') .attr("dy", '0.25em') .attr("text-anchor", 'middle') .text(d => d.probaStr); simulation.on("tick", () => { gNode.attr("transform", d => `translate(${d.x}, ${d.y})`); link .attr("x1", d => d.source.x) .attr("y1", d => d.source.y) .attr("x2", d => d.target.x) .attr("y2", d => d.target.y); linkLabel.attr('transform', (d, i) => { const tx = (d.source.x + d.target.x) / 2; const ty = (d.source.y + d.target.y) / 2; const dx = d.target.x - d.source.x; const dy = d.target.y - d.source.y; const r = Math.atan(dy / dx) * (180 / Math.PI); return `translate(${tx},${ty}) rotate(${r})`; }); }); invalidation.then(() => simulation.stop()); const names = data.nodes.map(e => e.id); let summary = ` Tournament Graph for candidates ${names.join(', ')} - The ratio next to a candidate is their probability of winning for the best lottery - A potential winner (win proba > 0) is circled in red - A Condorcet winner (win proba = 1), if any, is double circled in red - Arrows represent results of 1-1 elections from voters ordered preferences: They are directed from winner to loser`; if (preference) summary += `; the numbers are the winner and loser percentage scores in 1-vs-1 elections.`; return html`

${svg.node()}

${summary}

`; }34:T457,buildGraphData = (sol, payoff, preference = null) => { const names = Object.keys(sol.direct); const nodes = names.map(e => { const proba = sol.direct[e]; const p = new Fraction(proba).toFraction(true); const probaStr = p.includes('/') ? p : p + '/1'; return { id: e, probaStr, proba }; }); const label = (i, j) => { const s = preference[i][j] + preference[j][i]; const p_ij = ((100 * preference[i][j]) / s).toFixed(1); const p_ji = ((100 * preference[j][i]) / s).toFixed(1); return `${p_ij} - ${p_ji}`; }; const links = []; names.forEach((e, i) => names.forEach((f, j) => { if (j > i) { if (payoff[i][j] > payoff[j][i]) { const link = { source: e, target: f }; if (preference) { link.label = label(i, j); } links.push(link); } if (payoff[i][j] < payoff[j][i]) { const link = { source: f, target: e }; if (preference) { link.label = label(j, i); } links.push(link); } } }) ); return { nodes, links }; }35:T46d,solveSimplex = ({ payoff, names }) => { const shift = Math.abs(d3.min(d3.min(payoff))) + 1; const A = payoff.map(e => e.map(f => f + shift)); const prog = { name: 'RCVS', objective: { direction: glpk.GLP_MAX, name: 'lottery', vars: names.map(e => ({ name: e, coef: 1 })) }, subjectTo: A.map((a, i) => ({ name: 'c' + i, vars: a.map((e, j) => ({ name: names[j], coef: e })), bnds: { type: glpk.GLP_UP, lb: 0.0, ub: 1.0 } })) }; const solved = glpk.solve(prog, glpk.GLP_MSG_ALL); console.log(solved); const normDirect = d3.sum(Object.values(solved.result.vars)); const normDual = d3.sum(Object.values(solved.result.dual)); const direct = Object.fromEntries( Object.entries(solved.result.vars).map(([k, v]) => [k, v / normDirect]) ); const dual = Object.fromEntries( Object.entries(solved.result.dual).map(([k, v], i) => [ names[i], v / normDual ]) ); const tol = 1e-6; const equal = names .map(e => Math.abs(direct[e] - dual[e]) < tol) .every(e => e); return { direct, dual, equal, status: solved.result.status }; }36:[{"id":"98b76c4fef22cc8c88c4b40b5f28e07fa558061daab8a8a110c3d71e671fcfbc5684a75417056d05025d75b238136b185197e0b9e025bdecb82afb6d4c272e9d","href":"https://static.observableusercontent.com/files/98b76c4fef22cc8c88c4b40b5f28e07fa558061daab8a8a110c3d71e671fcfbc5684a75417056d05025d75b238136b185197e0b9e025bdecb82afb6d4c272e9d","name":"condorcet-bw.jpg","type":"image/jpeg","lastModified":1613922699078.747,"size":14630}] 2f:{"title":"Randomized Condorcet Voting System","cells":[{"id":0,"value":"md`# Randomized Condorcet Voting System\n\nDescribed and studied by [Lê Nguyen Hoand](https://fr.wikipedia.org/wiki/L%C3%AA_Nguy%C3%AAn_Hoang) in:\n+ this [paper](https://www.gerad.ca/en/papers/G-2014-74/view) from 2014\n+ this [other paper](http://www.science4all.org/wp-content/uploads/RandomizedCondorcet.pdf) from 2017 \n+ this [youtube video](https://www.youtube.com/watch?v=wKimU8jy2a8)\n\nThis mathematically faire voting system is interesting in multi-candidate elections - theoretically. Because it seems *way* too abstract for the Human species to accept !\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1070,"value":"md`## Overview\n\nIn a nutshell the randomized [Condorcet](https://en.wikipedia.org/wiki/Marquis_de_Condorcet) voting system consists in asking each voter their ordered preference for the candidates. These preferences are then converted into a tournament graph. If a candidate beats every other in 1-vs-1 elections, he is a Condorcet winner and wins the elections. In cases where there is no such Condorcet winner, then the (often unique) winning probability distribution (the **\"best lottery\"**) is determined (see section Details below). Then the winner is picked *randomly* based on this probability distribution.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1072,"value":"md`Here are two well-known examples of a tournament graph without Condorcet Winner:\n+ Rock-Paper-Scissors-Well\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1185,"value":"{\n const names = ['Rocks', 'Paper', 'Scissor', 'Well'];\n const payoff = [[0, -1, 1, -1], [1, 0, -1, 1], [-1, 1, 0, -1], [1, -1, 1, 0]];\n const sol = solveSimplex({ payoff, names });\n const data = buildGraphData(sol, payoff, null);\n const g = buildGraph({ data });\n return g;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1216,"value":"md`+ [Rock-Paper-Scissors](https://en.wikipedia.org/wiki/Rock_paper_scissors)\n`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":1139,"value":"{\n const names = ['Paper', 'Scissor', 'Rock'];\n const payoff = [[0, -1, 1], [1, 0, -1], [-1, 1, 0]];\n const sol = solveSimplex({ payoff, names });\n const data = buildGraphData(sol, payoff, null);\n const g = buildGraph({ data });\n return g;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1074,"value":"md`Here is an example of a tournament graph with a Condorcet Winner\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1196,"value":"{\n const names = ['A', 'B', 'C', 'D'];\n const payoff = [[0, -1, 1, -1], [1, 0, 1, 1], [-1, -1, 0, -1], [1, -1, 1, 0]];\n const sol = solveSimplex({ payoff, names });\n const data = buildGraphData(sol, payoff, null);\n const g = buildGraph({ data });\n return g;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":43,"value":"md`## Details\n\nNow let us examine how to determine the best lottery, which fairly captures the aggregate of voters' preferences, as Condorcet devised it.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1241,"value":"md`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":17,"value":"md`### Ballot mechanism\n\n+ It is a **one-round** election. \n+ Each voter casts a ballot where they can **order** all or some of the candidates by decreasing order of preference. \n\nFor example if a voter may vote B>A>D in a election where candidates A, B, C, D run. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":78,"value":"md`### Preference Table\nEach ballot contains one or several preferences. In the example above it contains: \n+ B > A \n+ A > D \n+ B > D \n\nAll such preference are aggregated in a preference table. \nThe first column are the winners and the top row the losers. \n\n| Win \\\\ Lose | A | B | C | D |\n|---|---|---|---|---|\n| A | 0 | 6 | 4 | 2 |\n| B | 9 | 0 | 8 | 3 |\n| C | 5 | 2 | 0 | 10|\n| D | 10| 9 | 8 | 0 |\n\nFor examples Cell(D, A) = (row=4, col=1) = 10 means that the ballots contains 10 instances of D>A.\nConversely Cell(A, D) = (row=1, col=4) = 2 means that the ballots contains 2 instances of A>D. Consequently D>A in a duel. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"md`### Tournement graph\n\nThis preference table can be turned to a Tournament graph i.e. a directed graph where each candidate is a vertex and there is a directed edge from candidate X to candidate Y if and only if X>Y. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":20,"value":"md`### Payoff Table\n\nThis Tournament graph can also be represented by this Payoff table. \n\n| Win \\\\ Lose | A | B | C | D |\n|---|---|---|---|---|\n| A | 0 | -1 | -1 | -1 |\n| B | 1 | 0 | 1 | -1 |\n| C | 1 | -1 | 0 | 1 |\n| D | 1 | 1 | -1 | 0 |\n\nEach directed edge from candidate X to candidate Y is represented by +1 for (row=X, col=Y) and -1 for (row=Y, col=X), or 0 if nobody expressed preference about X relative to B or there is equality between X and Y. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"md`### Condorcet Winner\n\nA Condorcet winner is the candidate who wins in any two-candidate elections (a **duel**).\nIn the Tounament graph this is the candidate who has only outgoing edges. Such a candidate does not always exist. A counter example is a situation where A>B>C>A. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":26,"value":"md`### Lottery\n\nA **lottery** is a probability distribution for choosing a candidate. \n\nExample {A: 1/2, B: 1/4, C: 1/4}. \nIf the probability is 100% for one candidate, e.g. {B: 1} then the lottery is deterministic and picks the Condorcet winner. So a lottery is a natural extension of the Condorcet method to cases where a Condorcet winner does not exist.\n\nAdditionally, contrary to Condorcet winners, there is always **a unique best lottery** as shown in this [paper](http://www.science4all.org/wp-content/uploads/RandomizedCondorcet.pdf) (*) \n\nThus the new objective of the election process is to determine the best lottery from the ballots. \n\n(*) Demonstrated only in the case of a complete Tournament graph i.e. any two candidates are connected. If the number of voters is great and the number of candidates reasonable, this is very likely to be the case. \n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":32,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"md`### How to determine all the possible lotteries ?\nThis is a vast set and obviously sampling it is not the preferred way. \n\nInstead we can determine the **best lottery** by framing the problem as a two person zero sum game. \nBoth players make moves simultaneously and the outcome of the game is given by a payoff matrix. \n\nIn the general case such payoff matrix has the following shape:\n\n${tex.block`\\mathbf{A} = \\begin{bmatrix}\n a_{11} & a_{12} & a_{13} & a_{14}\\\\ \n a_{21} & a_{22} & a_{23} & a_{24}\\\\ \n a_{31} & a_{32} & a_{33} & a_{34}\\\\ \n\\end{bmatrix}`}\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1095,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":4,"value":"md`## Simulation\n\nNow let's see some simulations. \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":195,"value":"md`Pick the number of candidates\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":156,"value":"nbCand = 4","pinned":true,"hidden":false,"mode":"ojs"},{"id":198,"value":"md`Pick the number of voters\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":177,"value":"nbVoters = 1e2","pinned":true,"hidden":false,"mode":"ojs"},{"id":357,"value":"viewof rndDraw = html`