Comment calculer les résultats du vote?
Le paquet Python pabutools
Le paquet pabutools est un paquet Python gratuit et open-source qui
contient des implémentations de plusieurs règles de vote pour le budget participatif, y compris la méthode des parts égales.
Il est disponible sur GitHub.
Le package peut être installé via PyPI en utilisant pip:
pip install pabutools
Extraits de code
Nous présentons ci-dessous de courts extraits de code pour calculer les résultats de la méthode des parts égales dans plusieurs langages de programmation.
Astuce générale pour accélérer le calcul
Pendant le calcul, l'algorithme doit calculer à plusieurs reprises le "nombre de votes pondéré" de chaque projet, ce qui est une étape coûteuse en temps de calcul. Cette partie peut être accélérée en ne recalculant le nombre de votes pondéré que si cela est nécessaire.
L'observation principale est que le nombre de votes pondéré ne peut que diminuer à mesure que l'algorithme progresse. Dans notre implémentation, nous commençons par le projet qui avait le nombre de votes pondéré le plus élevé lors du tour précédent. Nous recalculons le nombre de votes pondéré de ce projet. Ensuite, nous comparons son nouveau nombre de votes pondéré avec le nombre de votes pondéré du projet avec le deuxième plus grand nombre de votes pondéré lors du tour précédent. Si le nouveau nombre de votes pondéré est supérieur au nombre de votes pondéré du deuxième projet, alors nous savons que nous avons trouvé le projet avec le nombre de votes pondéré le plus élevé au tour actuel (parce que tous les autres projets avaient auparavant un nombre de votes pondéré inférieur, qui dans l'intervalle n'a pu que diminuer encore davantage). Ainsi, nous pouvons le sélectionner immédiatement.
Cette optimisation est utilisée dans tous les extraits de code sur cette page.
Python
def equal_shares_fixed_budget(N, C, cost, u, initial_budget):
# u[i,c] = utility of voter i for candidate c
budget = {i : initial_budget/len(N) for i in N}
committee = []
total_utility = {c : sum(u[i,c] for i in N) for c in C}
remaining = {c for c in C if cost[c] > 0 and total_utility[c] > 0} # throw away dummy candidates
approvers = {c : [i for i in N if u[i,c] > 0] for c in C}
previous_rho = {c : cost[c] / total_utility[c] for c in remaining}
while True:
best = None
best_rho = float('inf')
for c in sorted(remaining, key=lambda c : previous_rho[c]):
if previous_rho[c] > best_rho: # best possible rho for this round still isn't good enough
break
if sum(budget[i] for i in approvers[c]) < cost[c]: # unaffordable, can delete
remaining.remove(c)
continue
approvers[c].sort(key=lambda i : budget[i] / u[i,c])
paid_so_far = 0
denominator = total_utility[c]
for j in range(len(approvers[c])):
rho = (cost[c] - paid_so_far) / denominator
if rho * u[approvers[c][j], c] <= budget[approvers[c][j]]:
# found best rho for this candidate
previous_rho[c] = rho
if rho < best_rho:
best_rho = rho
best = c
break
paid_so_far += budget[approvers[c][j]]
denominator -= u[approvers[c][j],c]
if not best:
break
committee.append(best)
remaining.remove(best)
for i in approvers[best]:
budget[i] -= min(budget[i], best_rho * u[i,best])
return tuple(sorted(committee))
def equal_shares(N, C, cost, u, budget):
"Equal Shares with budget completion"
committee = equal_shares_fixed_budget(N, C, cost, u, budget)
for percent in range(101, 400):
new_committee = equal_shares_fixed_budget(N, C, cost, u, budget * percent / 100)
if sum(cost[c] for c in new_committee) > budget + 0.001:
break
committee = new_committee
return committee
Javascript
function sum(xs) {
return xs.reduce((a, b) => a + b, 0);
}
function equal_shares_fixed_budget(N, C, cost, approvers, B) {
let budget = {};
for (let i of N) {
budget[i] = B / N.length;
}
let remaining = new Map(); // remaining candidate -> previous effective vote count
for (let c of C) {
if (cost[c] > 0 && approvers[c].length > 0) {
remaining.set(c, approvers[c].length);
}
}
let committee = [];
while (true) {
let best = null;
let best_eff_vote_count = 0;
let best_max_payment = Infinity;
// go through remaining candidates in order of decreasing previous effective vote count
let remaining_sorted = [...remaining.keys()];
remaining_sorted.sort((a, b) => remaining.get(b) - remaining.get(a));
for (let c of remaining_sorted) {
let previous_eff_vote_count = remaining.get(c);
if (previous_eff_vote_count < best_eff_vote_count) {
// c cannot be better than the best so far
break;
}
if (sum(approvers[c].map(i => budget[i])) < cost[c]) {
// c is not affordable
remaining.delete(c);
continue;
}
// calculate the effective vote count of c, which involves splitting the cost of c as equally as possible among its approvers
approvers[c].sort((a, b) => budget[a] - budget[b]);
let paid_so_far = 0;
let denominator = approvers[c].length; // this will be the number of approvers who can afford the max payment
for (let j = 0; j < approvers[c].length; j++) {
let i = approvers[c][j];
let max_payment = (cost[c] - paid_so_far) / denominator; // payment if remaining approvers pay equally
let eff_vote_count = cost[c] / max_payment;
if (max_payment > budget[i]) {
// i cannot afford the max payment, so pays entire remaining budget
paid_so_far += budget[i];
denominator -= 1;
} else {
// i (and all later approvers) can afford the max payment; stop here
remaining.set(c, eff_vote_count);
if (eff_vote_count > best_eff_vote_count) {
best_eff_vote_count = eff_vote_count;
best_max_payment = max_payment;
best = c;
}
break;
}
}
}
if (!best) {
break;
}
committee.push(best);
for (let i of approvers[best]) {
budget[i] = budget[i] - Math.min(budget[i], best_max_payment);
}
remaining.delete(best);
}
return committee;
}
function equal_shares(N, C, cost, approvers, B) {
// Method of Equal Shares with Add1U completion
// Input:
// N: list of voters
// C: list of candidates
// cost[c]: cost of candidate c
// approvers[c]: list of voters who approve candidate c
// B: budget
// Output:
// committee: list of candidates
let mes = equal_shares_fixed_budget(N, C, cost, approvers, B);
let budget = B;
while (true) {
// is current outcome exhaustive?
let is_exhaustive = true;
for (let extra of C) {
if (!mes.includes(extra) && sum(mes.map(c => cost[c])) + cost[extra] <= B) {
is_exhaustive = false;
break;
}
}
if (is_exhaustive) {
break;
}
// would the next highest budget work?
let new_budget = budget + N.length;
let next_mes = equal_shares_fixed_budget(N, C, cost, approvers, new_budget);
if (sum(next_mes.map(c => cost[c])) <= B) {
budget = new_budget;
mes = next_mes;
} else {
break;
}
}
// in case there is remaining budget, add the next most popular projects
let sorted_C = [...C];
sorted_C.sort((a, b) => approvers[b].length - approvers[a].length);
for (let extra of sorted_C) {
if (!mes.includes(extra) && sum(mes.map(c => cost[c])) + cost[extra] <= B) {
mes.push(extra);
}
}
return mes;
}