Skip to content

Instantly share code, notes, and snippets.

@ibeauregard

ibeauregard/exhaustive-ballot.ipynb

Created October 31, 2020 17:27
Show Gist options
  • Save ibeauregard/ab34af2936428ffc40d055e6ddad9832 to your computer and use it in GitHub Desktop.
Save ibeauregard/ab34af2936428ffc40d055e6ddad9832 to your computer and use it in GitHub Desktop.
Download ZIP
Exhaustive Ballot.ipynb
Display the source blob
Display the rendered blob
Raw
exhaustive-ballot.ipynb
{
"nbformat": 4,
"nbformat_minor": 0,
"metadata": {
"colab": {
"name": "Exhaustive Ballot.ipynb",
"provenance": [],
"collapsed_sections": [],
"authorship_tag": "ABX9TyMz0BT0sU1yWH8yOPxPKcw+",
"include_colab_link": true
},
"kernelspec": {
"name": "python3",
"display_name": "Python 3"
}
},
"cells": [
{
"cell_type": "markdown",
"metadata": {
"id": "view-in-github",
"colab_type": "text"
},
"source": [
"<a href=\"https://colab.research.google.com/gist/ibeauregard/ab34af2936428ffc40d055e6ddad9832/exhaustive-ballot.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "dLSSUmd2vq5l"
},
"source": [
"# Exhaustive Ballot vote"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "52DW_EePaLU6"
},
"source": [
"The function `exhaustive_ballot` outputs the result of an [exhaustive ballot](https://en.wikipedia.org/wiki/Exhaustive_ballot) vote, given a `votes` matrix. At each round, the candidate with the least number of votes is eliminated, with their votes being redistributed to the remaining candidates in accordance with the voters' choices. The first candidate to reach an absolute majority of votes is the winner.\n",
"\n",
"- The input parameter `votes` is an ndarray of shape(`number_of_voters`, `number_of_candidates`). The `i`th row contains a permutation of [0, 1, 2, ..., `number_of_candidates - 1`], reflecting the `i`th voter's choices, from favorite candidate to least favorite candidate.\n",
"\n",
"- The function returns an ndarray of shape (`number_of_rounds`, `number_of_candidates`), with `number_of_rounds` being the number of rounds necessary to designate a winner with an absolute majority of the votes. The `i`th row of the ndarray contains the number of votes assigned to each of the candidates after round `i`."
]
},
{
"cell_type": "code",
"metadata": {
"id": "TewOMfAH8UMY"
},
"source": [
"import numpy as np\n",
"\n",
"def exhaustive_ballot(votes):\n",
" voter_axis = 0\n",
" first_choice_index = 0\n",
" def one_hot(votes, num_candidates):\n",
" return np.eye(num_candidates, dtype=bool)[votes]\n",
" num_voters, num_candidates = votes.shape\n",
" aggregate_results = []\n",
"\n",
" while True:\n",
" results = np.sum(\n",
" one_hot(votes[:, first_choice_index], num_candidates),\n",
" axis=voter_axis)\n",
" aggregate_results.append(results)\n",
" \n",
" out = np.flatnonzero(results == np.min(results[results > 0]))\n",
" votes = votes[~np.isin(votes, out)].reshape(num_voters, -1)\n",
" if results.max() * 2 > num_voters or votes.size == 0:\n",
" break\n",
" \n",
" return np.vstack(aggregate_results)"
],
"execution_count": 1,
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {
"id": "q67wVzBeg3rR"
},
"source": [
"Let's now try this function! First, we need to generate a `votes` matrix. Here is a function that does that.\n",
"\n",
"First, we assign to each candidate a probability `p` of being chosen. The probabilities are taken from a loguniform distribution, which roughly means that just a few candidates will receive a lot of 1st choice votes.\n",
"\n",
"For each voter, we generate a permutation of [0, 1, 2, ..., `number_of_candidates - 1`], reflecting the voter's choices, from favorite to least favorite candidate.\n",
"\n",
"The numbers are picked without replacement from [0, 1, 2, ..., `number_of_candidates - 1`], in accordance with the probabilities defined beforehand."
]
},
{
"cell_type": "code",
"metadata": {
"id": "ZVdVufWNhPuI"
},
"source": [
"from scipy.stats import loguniform\n",
"\n",
"def random_vote(num_voters, num_candidates):\n",
" a, b = 1, 100\n",
" p = loguniform.rvs(a, b, size=num_candidates)\n",
" p = p / np.sum(p)\n",
" return np.array(\n",
" [np.random.choice(\n",
" num_candidates, size=num_candidates, replace=False, p=p)\n",
" for _ in range(num_voters)])"
],
"execution_count": 2,
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {
"id": "P9fj8JuFkZfP"
},
"source": [
"Let us now call our `exhaustive_ballot` function, with a `votes` matrix of shape (`number_of_voters=10000`, `number_of_candidates=10`)."
]
},
{
"cell_type": "code",
"metadata": {
"id": "bG23U0Nfkovm",
"outputId": "37ccf4c1-6efe-4e68-8a8c-2ba90226d28a",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"source": [
"num_voters, num_candidates = 10000, 10\n",
"exhaustive_ballot(random_vote(num_voters, num_candidates))"
],
"execution_count": 3,
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"array([[1039, 390, 122, 4036, 119, 600, 571, 642, 1107, 1374],\n",
" [1057, 391, 124, 4084, 0, 609, 574, 648, 1119, 1394],\n",
" [1073, 395, 0, 4136, 0, 613, 585, 655, 1131, 1412],\n",
" [1120, 0, 0, 4315, 0, 640, 605, 677, 1174, 1469],\n",
" [1208, 0, 0, 4577, 0, 677, 0, 717, 1259, 1562],\n",
" [1283, 0, 0, 4909, 0, 0, 0, 779, 1338, 1691],\n",
" [1398, 0, 0, 5316, 0, 0, 0, 0, 1457, 1829]])"
]
},
"metadata": {
"tags": []
},
"execution_count": 3
}
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "FnbM0PM6lCli"
},
"source": [
"Let us now define a few functions to pretty print those results. First, a function to print the results from a single round."
]
},
{
"cell_type": "code",
"metadata": {
"id": "ltp7L9uflJ9s"
},
"source": [
"def print_results(round, results, names):\n",
" result_dict = {result: np.flatnonzero(result == results)\n",
" for result in sorted(results, reverse=True)\n",
" if result > 0}\n",
" print(f'RESULTS AFTER ROUND {round + 1}\\n')\n",
" print(' ' * 4 + f'{\"Candidate\":<25}{\"Votes\":>7}{\"%\":>9}')\n",
" print('-' * 45)\n",
" position = 1\n",
" for result, candidate_ids in result_dict.items():\n",
" for id in candidate_ids:\n",
" print((f'{f\"{position}.\":<4}'\n",
" f'{names[id]:<25}{result:>7}'\n",
" f'{result / num_voters * 100:>8.2f}%'))\n",
" position += len(candidate_ids) \n",
" print('\\n\\n')"
],
"execution_count": 4,
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {
"id": "c4SF0eqalRzU"
},
"source": [
"And then a function that prints the aggregate results. First, this function calls the previous function for each round, and then it announces the winner (or declares that the vote ended up in a tie)."
]
},
{
"cell_type": "code",
"metadata": {
"id": "PK6YscUdlpS8"
},
"source": [
"def print_aggregate_results(results, names):\n",
" for round, result in enumerate(results):\n",
" print_results(round, result, names)\n",
"\n",
" winner_result = result.max()\n",
" winners = np.flatnonzero(result == winner_result)\n",
" print('FINAL RESULT\\n')\n",
" if len(winners) == 1:\n",
" print((f'{names[winners[0]]} '\n",
" f'wins after Round {round + 1} '\n",
" f'with {winner_result} votes '\n",
" f'({winner_result / num_voters * 100:.2f}%).'))\n",
" else:\n",
" print((f'{\", \".join(names[winner] for winner in winners[:-1])} '\n",
" f'and {names[winners[-1]]} finish ex æquo '\n",
" f'with {winner_result} votes each.'))"
],
"execution_count": 5,
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {
"id": "EIkNTNR8oAfj"
},
"source": [
"In order the use the printing functions, let us define an arbitrary list of candidates."
]
},
{
"cell_type": "code",
"metadata": {
"id": "3fEQDA9mobyf"
},
"source": [
"CANDIDATES = ['Cathy Bowler',\n",
" 'Ava Rodrigues',\n",
" 'Romeo Estrada',\n",
" 'Tamanna Emery',\n",
" 'Katie-Louise Wickens',\n",
" 'Tony Hester',\n",
" 'Katelyn Barry',\n",
" 'Fabien Burn',\n",
" 'Conor Coffey',\n",
" 'Kenzie Paul']"
],
"execution_count": 6,
"outputs": []
},
{
"cell_type": "markdown",
"metadata": {
"id": "v2Y0JG7VpTbW"
},
"source": [
"Finally, let us generate a random exhaustive ballot vote with these candidates, and 10,000 voters. We will print the results with the function defined above."
]
},
{
"cell_type": "code",
"metadata": {
"id": "VhX-UdFLhakP",
"outputId": "922bc50c-2728-4409-b25d-88cee114c0b9",
"colab": {
"base_uri": "https://localhost:8080/"
}
},
"source": [
"num_voters, num_candidates = 10000, len(CANDIDATES)\n",
"\n",
"results = exhaustive_ballot(random_vote(num_voters, num_candidates))\n",
"print_aggregate_results(results, CANDIDATES)"
],
"execution_count": 7,
"outputs": [
{
"output_type": "stream",
"text": [
"RESULTS AFTER ROUND 1\n",
"\n",
" Candidate Votes %\n",
"---------------------------------------------\n",
"1. Ava Rodrigues 3612 36.12%\n",
"2. Conor Coffey 2968 29.68%\n",
"3. Katelyn Barry 1535 15.35%\n",
"4. Tamanna Emery 681 6.81%\n",
"5. Fabien Burn 485 4.85%\n",
"6. Kenzie Paul 266 2.66%\n",
"7. Tony Hester 133 1.33%\n",
"8. Romeo Estrada 130 1.30%\n",
"9. Katie-Louise Wickens 96 0.96%\n",
"10. Cathy Bowler 94 0.94%\n",
"\n",
"\n",
"\n",
"RESULTS AFTER ROUND 2\n",
"\n",
" Candidate Votes %\n",
"---------------------------------------------\n",
"1. Ava Rodrigues 3648 36.48%\n",
"2. Conor Coffey 2993 29.93%\n",
"3. Katelyn Barry 1546 15.46%\n",
"4. Tamanna Emery 686 6.86%\n",
"5. Fabien Burn 493 4.93%\n",
"6. Kenzie Paul 272 2.72%\n",
"7. Tony Hester 134 1.34%\n",
"8. Romeo Estrada 131 1.31%\n",
"9. Katie-Louise Wickens 97 0.97%\n",
"\n",
"\n",
"\n",
"RESULTS AFTER ROUND 3\n",
"\n",
" Candidate Votes %\n",
"---------------------------------------------\n",
"1. Ava Rodrigues 3680 36.80%\n",
"2. Conor Coffey 3024 30.24%\n",
"3. Katelyn Barry 1563 15.63%\n",
"4. Tamanna Emery 695 6.95%\n",
"5. Fabien Burn 498 4.98%\n",
"6. Kenzie Paul 275 2.75%\n",
"7. Tony Hester 134 1.34%\n",
"8. Romeo Estrada 131 1.31%\n",
"\n",
"\n",
"\n",
"RESULTS AFTER ROUND 4\n",
"\n",
" Candidate Votes %\n",
"---------------------------------------------\n",
"1. Ava Rodrigues 3735 37.35%\n",
"2. Conor Coffey 3062 30.62%\n",
"3. Katelyn Barry 1585 15.85%\n",
"4. Tamanna Emery 705 7.05%\n",
"5. Fabien Burn 503 5.03%\n",
"6. Kenzie Paul 276 2.76%\n",
"7. Tony Hester 134 1.34%\n",
"\n",
"\n",
"\n",
"RESULTS AFTER ROUND 5\n",
"\n",
" Candidate Votes %\n",
"---------------------------------------------\n",
"1. Ava Rodrigues 3780 37.80%\n",
"2. Conor Coffey 3115 31.15%\n",
"3. Katelyn Barry 1604 16.04%\n",
"4. Tamanna Emery 712 7.12%\n",
"5. Fabien Burn 510 5.10%\n",
"6. Kenzie Paul 279 2.79%\n",
"\n",
"\n",
"\n",
"RESULTS AFTER ROUND 6\n",
"\n",
" Candidate Votes %\n",
"---------------------------------------------\n",
"1. Ava Rodrigues 3895 38.95%\n",
"2. Conor Coffey 3196 31.96%\n",
"3. Katelyn Barry 1644 16.44%\n",
"4. Tamanna Emery 740 7.40%\n",
"5. Fabien Burn 525 5.25%\n",
"\n",
"\n",
"\n",
"RESULTS AFTER ROUND 7\n",
"\n",
" Candidate Votes %\n",
"---------------------------------------------\n",
"1. Ava Rodrigues 4109 41.09%\n",
"2. Conor Coffey 3363 33.63%\n",
"3. Katelyn Barry 1748 17.48%\n",
"4. Tamanna Emery 780 7.80%\n",
"\n",
"\n",
"\n",
"RESULTS AFTER ROUND 8\n",
"\n",
" Candidate Votes %\n",
"---------------------------------------------\n",
"1. Ava Rodrigues 4479 44.79%\n",
"2. Conor Coffey 3625 36.25%\n",
"3. Katelyn Barry 1896 18.96%\n",
"\n",
"\n",
"\n",
"RESULTS AFTER ROUND 9\n",
"\n",
" Candidate Votes %\n",
"---------------------------------------------\n",
"1. Ava Rodrigues 5552 55.52%\n",
"2. Conor Coffey 4448 44.48%\n",
"\n",
"\n",
"\n",
"FINAL RESULT\n",
"\n",
"Ava Rodrigues wins after Round 9 with 5552 votes (55.52%).\n"
],
"name": "stdout"
}
]
}
]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment