Hogyan számítsuk ki az eredményeket?
Ez az oldal még nem teljesen készült el magyarul.
Online számítási eszköz
Egy online eszközt biztosítunk az egyenlő részvétel módszerének eredményeinek kiszámítására. Az eszköz elérhető a https://equalshares.net/tools/compute címen. Az eszköz ingyenesen használható, és nem igényel regisztrációt vagy telepítést.
Nyissa meg az online számítási eszközt →Az eszköz lehetővé teszi a felhasználók számára, hogy egy .pb formátumú fájlt töltsenek fel, amely az összes szavazatot tartalmazza, és a pabulib által használt szabványos formátum.
Ezután kiszámítja az egyenlő részvétel módszerének eredményeit, és táblázatos formában megjeleníti azokat, valamint további statisztikákat és információkat nyújt.
Az eszköz támogatja az egyenlő részvétel módszerének minden szabványos változatát.
Az adatokat nem küldi el semmilyen szerverre; minden számítás a felhasználó böngészőjében történik. A felhasználók leválaszthatják az internetet az oldal betöltése után, és az eszköz továbbra is működni fog.
Az eszköz csak a több X-es szavazást támogatja.
A .pb fájlformátumról
A .pb fájlformátum a közösségi költségvetési adatok tárolásának szabványos formátuma.
A pabulib könyvtár használja.
A formátum egy egyszerű szöveges formátum, amely bármely szövegszerkesztővel szerkeszthető.
Információkat tartalmaz a választási esetről (például a helyszínről, dátumról és a választási költségvetésről),
a projektekről (például azok nevéről és költségeiről), valamint a szavazatokról (például, hogy mely projekteket támogatja minden szavazó).
Íme egy példa egy .pb fájlra:
META
key;value
description;Példa választás
num_projects;3
num_votes;4
budget;100000
vote_type;approval
PROJECTS
project_id;name;cost
1;Projekt 1;5000
2;Projekt 2;10000
3;Projekt 3;85000
VOTES
voter_id;vote
1;1,2
2;1
3;3
4;1,2,3
A pabutools csomag
A pabutools csomag egy ingyenes és nyílt forráskódú Python-csomag, amely számos közösségi költségvetési szavazási szabályt, köztük az egyenlő részvétel módszerét is megvalósítja.
A csomag elérhető a GitHubon.
A csomagot a PyPI segítségével lehet telepíteni pip-pel:
pip install pabutools
A csomag segítségével beolvashat egy pabulib fájlt, és kiszámíthatja az egyenlő részvétel módszerének eredményeit a következő módon:
from pabutools.election import parse_pabulib, Cost_Sat
from pabutools.rules import method_of_equal_shares
instance, profile = parse_pabulib("filename.pb")
winners = method_of_equal_shares(
instance,
profile.as_multiprofile(),
sat_class=Cost_Sat,
voter_budget_increment=1 # a kiegészítési módszer Add1 használata
)
print(winners)
További részletek a csomagdokumentációban érhetők el.
Kódgenerátor
Itt rövid kódrészleteket biztosítunk az egyenlő részvétel módszerének Python vagy JavaScript segítségével történő kiszámításához. Kiválaszthatja a módszer azon változatát, amelyet meg szeretne valósítani.
Language: Python
Ballot type: Approval ballots
Tie breaking: In favor of lower cost, then higher vote count
Completion method: Repeated increase of voter budgets by 1 currency unit
Comparison step: None
Numerical accuracy: Use floating point numbers
def equal_shares(voters, projects, cost, approvers, total_budget):
"""
Computes the Method of Equal Shares for Participatory Budgeting.
Args:
voters (list): A list of voter names.
projects (list): A list of project IDs.
cost (dict): A dictionary mapping project IDs to their respective costs.
approvers (dict): A dictionary mapping project IDs to the list of voters who approve them.
total_budget (int): The total budget available.
Returns:
list: A list of project IDs that are selected by the Method of Equal Shares.
Example:
>>> equal_shares(
>>> voters=["v1", "v2", "v3"],
>>> projects=["p1", "p2", "p3"],
>>> cost={"p1": 100, "p2": 50, "p3": 50},
>>> approvers={"p1": ["v1", "v2"], "p2": ["v1"], "p3": ["v3"]},
>>> total_budget=150)
["p1", "p3"]
"""
mes = equal_shares_fixed_budget(voters, projects, cost, approvers, total_budget)
# add1 completion
# start with integral per-voter budget
budget = int(total_budget / len(voters)) * len(voters)
current_cost = sum(cost[c] for c in mes)
while True:
# is current outcome exhaustive?
is_exhaustive = True
for extra in projects:
if extra not in mes and current_cost + cost[extra] <= total_budget:
is_exhaustive = False
break
# if so, stop
if is_exhaustive:
break
# would the next highest budget work?
next_budget = budget + len(voters)
next_mes = equal_shares_fixed_budget(voters, projects, cost, approvers, next_budget)
current_cost = sum(cost[c] for c in next_mes)
if current_cost <= total_budget:
# yes, so continue with that budget
budget = next_budget
mes = next_mes
else:
# no, so stop
break
return mes
def break_ties(voters, projects, cost, approvers, choices):
remaining = choices.copy()
best_cost = min(cost[c] for c in remaining)
remaining = [c for c in remaining if cost[c] == best_cost]
best_count = max(len(approvers[c]) for c in remaining)
remaining = [c for c in remaining if len(approvers[c]) == best_count]
return remaining
def equal_shares_fixed_budget(voters, projects, cost, approvers, total_budget):
budget = {i: total_budget / len(voters) for i in voters}
remaining = {} # remaining candidate -> previous effective vote count
for c in projects:
if cost[c] > 0 and len(approvers[c]) > 0:
remaining[c] = len(approvers[c])
winners = []
while True:
best = []
best_eff_vote_count = 0
# go through remaining candidates in order of decreasing previous effective vote count
remaining_sorted = sorted(remaining, key=lambda c: remaining[c], reverse=True)
for c in remaining_sorted:
previous_eff_vote_count = remaining[c]
if previous_eff_vote_count < best_eff_vote_count:
# c cannot be better than the best so far
break
money_behind_now = sum(budget[i] for i in approvers[c])
if money_behind_now < cost[c]:
# c is not affordable
del remaining[c]
continue
# calculate the effective vote count of c
approvers[c].sort(key=lambda i: budget[i])
paid_so_far = 0
denominator = len(approvers[c])
for i in approvers[c]:
# compute payment if remaining approvers pay equally
max_payment = (cost[c] - paid_so_far) / denominator
eff_vote_count = cost[c] / max_payment
if max_payment > budget[i]:
# i cannot afford the payment, so pays entire remaining budget
paid_so_far += budget[i]
denominator -= 1
else:
# i (and all later approvers) can afford the payment; stop here
remaining[c] = eff_vote_count
if eff_vote_count > best_eff_vote_count:
best_eff_vote_count = eff_vote_count
best = [c]
elif eff_vote_count == best_eff_vote_count:
best.append(c)
break
if not best:
# no remaining candidates are affordable
break
best = break_ties(voters, projects, cost, approvers, best)
if len(best) > 1:
raise Exception(f"Tie-breaking failed: tie between projects {best} could not be resolved. Another tie-breaking needs to be added.")
best = best[0]
winners.append(best)
del remaining[best]
# charge the approvers of best
best_max_payment = cost[best] / best_eff_vote_count
for i in approvers[best]:
if budget[i] > best_max_payment:
budget[i] -= best_max_payment
else:
budget[i] = 0
return winners
Általános megfontolások
Algoritmikus trükk a számítás gyorsításához
A számítás során az algoritmusnak ismételten ki kell számítania az egyes projektek "effektív szavazatszámát", ami egy költséges lépés. Ez a rész felgyorsítható, ha csak akkor számítjuk újra az effektív szavazatszámot, ha ez lényeges.
A fő megfigyelés az, hogy az effektív szavazatszám csak csökkenhet, ahogy az algoritmus halad előre. Az implementációban a következőt tesszük: az előző körben a legmagasabb effektív szavazatszámú projekttel kezdjük. Újraszámoljuk ennek a projektnek az effektív szavazatszámát. Ezután összehasonlítjuk az új effektív szavazatszámát az előző körben második legmagasabb effektív szavazatszámú projekttel. Ha az új effektív szavazatszám magasabb, mint a második legmagasabb projekté, akkor tudjuk, hogy megtaláltuk a jelenlegi kör legmagasabb effektív szavazatszámú projektjét (mivel az összes többi projekt korábban alacsonyabb effektív szavazatszámmal rendelkezett, amely azóta csak tovább csökkenhetett). Így azonnal kiválaszthatjuk azt.
Ez az optimalizálás minden ezen az oldalon található kódrészletben alkalmazva van.
Numerikus pontosság: lebegőpontos számok vagy törtek?
Az egyenlő részvétel módszerét használó választások nyerteseinek kiszámításakor törtekkel történő számításokat kell végezni. Például egy projekt költségét el kell osztani a támogatói számával, hogy megtudjuk, mennyit kell hozzájárulnia egy-egy támogatónak a projekthez. A számítógépek általában "lebegőpontos számokat" használnak, amelyek nem pontos reprezentációi a valós számoknak (például 1/3 nem ábrázolható pontosan lebegőpontos számmal, mert végtelen tizedes tört). Ez azt jelenti, hogy ha lebegőpontos számokat használunk, ritka esetekben pontatlan eredményeket kaphatunk. Különösen, ha döntetlen van (azaz két projektnek ugyanaz az effektív szavazatszáma), a lebegőpontos implementáció kissé eltérő effektív szavazatszámot rendelhet az egyes projektekhez, és így eltérő nyertest választhat, mint a pontos implementáció.
Ennek a problémának az elkerülése érdekében használhatunk racionális szám implementációt, amely a számokat egész számok törteként ábrázolja.
Az ilyen implementációk általában lassabbak (kb. 4-10x), mint a lebegőpontos implementációk, de pontosak.
A fenti kódegenerátor lehetővé teszi, hogy lebegőpontos vagy racionális szám implementációt válasszon.
Javasoljuk, hogy hivatalos eredmények számításához használja a racionális szám implementációt, míg gyors teszteléshez a lebegőpontos implementációt.
A pabutools csomag alapértelmezés szerint a racionális szám implementációt használja.
Összehasonlítás az akadémiai irodalommal
Az akadémiai irodalomban az egyenlő részvétel módszerét gyakran úgy határozzák meg matematikailag, hogy a projektek kiválasztását a költséghatékonyságuk (azaz a szavazatszám osztva a költséggel) csökkenő sorrendjében részesítse előnyben. Ezzel szemben, a módszer, ahogy ezen a weboldalon le van írva, a projektek kiválasztását a szavazatszám csökkenő sorrendjében részesíti előnyben. A formális irodalomban ezt a módszerváltozatot néha "költség-utilitásokkal" való módszerként említik, mivel az itt tárgyalt változat a projekt költségét proxyként használja a választók által érzett hasznosságára. Fontos ezt a különbséget szem előtt tartani, amikor összehasonlítjuk az akadémiai irodalomban elérhető leírásokat és pszeudokódokat.