Jak obliczyć, które projekty wygrały?
Pakiet oprogramowania pabutools
Pakiet pabutools to darmowy i open-source'owy pakiet w języku Python, który zawiera implementację kilku metod liczenia głosów dla budżetów obywatelskich, w tym metody równych udziałów.
Jest on dostępny na GitHub.
Pakiet można zainstalować za pośrednictwem PyPI używając komendy pip:
pip install pabutools
Możesz użyć tego pakietu do odczytywania plików pabulib i obliczania wyników Metody Równych Udziałów, stosując poniższy kod w języku Python:
from pabutools.election import parse_pabulib, Cost_Sat
from pabutools.rules import method_of_equal_shares
instance, profile = parse_pabulib("nazwa_pliku.pb")
wygrani = method_of_equal_shares(
instance,
profile.as_multiprofile(),
sat_class=Cost_Sat,
voter_budget_increment=1 # użyj metody uzupełniania Add1
)
print(wygrani)
Więcej szczegółów można znaleźć w [dokumentacji pakietu]](https://pbvoting.github.io/pabutools/usage.html#method-of-equal-shares-mes).
Fragmenty kodu
Poniżej przedstawiamy krótkie fragmenty kodu służące do obliczania wyników za pomocą metody równych udziałów.
Pomysł, który może znacząco przyspieszyć obliczenia
Algorytm musi wielokrotnie obliczać „efektywną liczbę głosów" dla każdego projektu. Jest to kosztowna operacja. Tę część można przyspieszyć, przeliczając efektywną liczbę głosów tylko w określonych przypadkach.
Główną obserwacją jest to, że efektywna liczba głosów może się tylko zmniejszać w kolejnych rundach algorytmu. Możemy zatem zastosować następującą technikę: zaczynamy od projektu, który miał największą efektywną liczbę głosów w poprzedniej rundzie. Ponownie obliczamy efektywną liczbę głosów dla tego projektu. Następnie porównujemy jego nową efektywną liczbę głosów z drugą co do wielkości efektywną liczbą głosów z poprzedniej rundy. Jeśli nowa efektywna liczba głosów jest wyższa niż efektywna liczba głosów drugiego w kolejności projektu, to wiemy, że znaleźliśmy projekt z najwyższą efektywną liczbą głosów w obecnej rundzie (ponieważ wszystkie inne projekty miały wcześniej niższą efektywną liczbę głosów, która w międzyczasie mogła się jeszcze zmniejszyć). Dlatego możemy taki projekt od razu wybrać.
Ta optymalizacja jest stosowana we fragmentach kodu przedstawionych poniżej.
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;
}