🔢 mathematics

Counting Votes with Multisets

Diese Arbeit zeigt auf, wie die kategorischen Eigenschaften von Multimengen – insbesondere ihre Struktur als freies kommutatives Monoid, Funktor und Monad – effektiv angewendet werden können, um Ergebnisse in verschiedenen Wahlsystemen, einschließlich Instant-Runoff, De Borda und Single Transferable Vote, abzuleiten und auszudrücken.

Ursprüngliche Autoren: Bart Jacobs, Michael Johnson, Richard Buckland

Veröffentlicht 2026-06-05

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Bart Jacobs, Michael Johnson, Richard Buckland

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie führen eine Wahl durch, aber anstatt Papierstimmzettel einzeln zu zählen, verwalten Sie einen riesigen Beutel mit bunten Murmeln. Dies ist der Kern der Arbeit: Multimengen (Multisets).

Hier ist eine einfache Aufschlüsselung dessen, was die Autoren Bart Jacobs, Michael Johnson und Richard Buckland vorschlagen, unter Verwendung alltäglicher Analogien.

1. Der magische Beutel (Was ist eine Multimenge?)

Normalerweise ist in der Mathematik eine „Menge“ wie eine Liste von einzigartigen Objekten. Wenn Sie eine Menge an Früchten haben, können Sie einen Apfel und eine Banane haben, aber Sie können nicht „zwei Äpfel“ in der Mengendefinition haben; es sind einfach nur „Äpfel“.

Eine Multimenge ist wie ein Beutel voller Murmeln.

Wenn Sie 4 rote, 3 blaue und 2 grüne Murmeln in einen Beutel geben, spielt die Reihenfolge keine Rolle.
Was zählt, ist die Anzahl.
Die Autoren schreiben dies als: 4|R⟩ + 3|B⟩ + 2|G⟩.
Bei einer Wahl repräsentiert dieser Beutel die Stimmen. Es spielt keine Rolle, wer wie viel gestimmt hat oder wann gestimmt wurde; es zählt nur, dass es 4 Stimmen für Rot, 3 für Blau und 2 für Grün gibt.

Warum ist das gut?
Wenn Sie Stimmen in einer Liste führen (wie in einer Tabellenkalkulation), könnte die Reihenfolge der Liste versehentlich verraten, wer für wen gestimmt hat. Aber wenn Sie alles einfach in einen „Multimengen-Beutel“ schütten, verschwindet die Reihenfolge. Sie erhalten eine saubere, anonyme Zählung, die unmöglich auf Einzelpersonen zurückverfolgt werden kann.

2. Die drei Wahlspiele

Das Paper zeigt, wie dieser „Beutel voller Murmeln“-Ansatz drei komplexe Wahlsysteme viel einfacher verständlich und berechenbar macht. Die Autoren verwenden einige schicke mathematische Begriffe (wie „Funktoren“ und „Monaden“), aber betrachten Sie diese als Regeln, um Murmeln im Beutel hin und her zu bewegen.

Spiel A: Instant-Runoff-Voting (Das „Eliminations“-Spiel)

Wie es funktioniert: Wähler ranken Kandidaten (1. Wahl, 2. Wahl, 3. Wahl). Wenn niemand 50 % der Stimmen erhält, wird die Person mit den wenigsten Stimmen eliminiert. Ihre Stimmen werden dann an die zweite Wahl der Wähler übertragen.
Der Multimengen-Trick: Stellen Sie sich vor, Ihr Beutel mit Stimmzetteln ist ein Stapel von Listen.
1. Sie schauen sich die oberste Zeile jeder Liste an (1. Wahl) und zählen die Murmeln.
2. Sie finden den Verlierer (Kandidat C).
3. Sie benutzen ein „magisches Radiergummi“ (einen sogenannten Funktor im Paper), um Kandidat C aus jeder einzelnen Liste im Beutel zu löschen.
4. Nun werden die 2. Wahlen zu den neuen 1. Wahlen. Sie zählen den Beutel erneut.
5. Sie wiederholen dies, bis jemand eine Mehrheit hat.
Der Vorteil: Anstatt tausende Namen auf Papieren manuell durchzustreichen, wenden Sie die „Lösch-Regel“ einfach auf den gesamten Beutel auf einmal an.

Spiel B: De-Borda-Count (Das „Gewichtete Punkte“-Spiel)

Wie es funktioniert: Wähler ranken Kandidaten. Die 1. Wahl erhält 4 Punkte, die 2. Wahl 3 Punkte, die 3. Wahl 2 Punkte usw. Alle Punkte werden zusammengezählt.
Der Multimengen-Trick:
1. Anstatt nur Stimmen zu zählen, verwandeln Sie jeden einzelnen Stimmzettel in eine Mini-Multimenge gewichteter Murmeln. Ein Stimmzettel mit „A, B, C, D“ wird zu 4|A⟩ + 3|B⟩ + 2|C⟩ + 1|D⟩.
2. Sie schütten all diese Mini-Beutel in einen einzigen riesigen Super-Beutel.
3. Sie nutzen ein „Abflachungs-Werkzeug“ (eine sogenannte Monade), um alle Schichten zusammenzuschlagen.
4. Das Ergebnis ist eine einzige große Zählung der Gesamtpunkte für jeden Kandidaten.
Der Vorteil: Es verwandelt ein komplexes mathematisches Problem in eine einfache „Addiere alles auf“-Operation.

Spiel C: Single Transferable Vote (Das „Überschuss-Sharing“-Spiel)

Wie es funktioniert: Dies wird verwendet, um mehrere Personen zu wählen (z. B. einen Stadtrat). Es gibt ein „Quorum“ (eine Mindestanzahl an Stimmen, die zum Sieg benötigt wird). Wenn ein Kandidat viel mehr Stimmen erhält als nötig, sollten die zusätzlichen Stimmen nicht verschwendet werden; sie sollten an die nächste Wahl der Wähler übertragen werden.
Der Multimellen-Trick:
1. Stellen Sie sich vor, ein Kandidat gewinnt mit 93 Stimmen, aber das Quorum liegt nur bei 63. Er hat also 30 „Überschussstimmen“.
2. Anstatt 30 zufällige Zettel auszuwählen, um sie zu übertragen (was unfair wäre), schlagen die Autoren einen mathematischen Trick vor: Entwerten Sie die Stimmen.
3. Sie nehmen alle 93 Stimmen für diesen Gewinner und schrumpfen sie um einen bestimmten Bruchteil (wie das Verkleinern eines Fotos).
4. Sie „löschen“ dann den Gewinner aus den Listen und übertragen diese „geschrumpften“ Stimmen an die nächsten Kandidaten.
5. Dies ermöglicht es der Mathematik, mit Brüchen von Stimmen perfekt umzugehen, wodurch sichergestellt wird, dass keine Stimmen verschwendet oder doppelt gezählt werden.

3. Warum ist das wichtig?

Die Autoren versuchen nicht, eine neue Art von Mathematik zu erfinden; sie zeigen, dass alte Mathematik (Kategorientheorie) das perfekte Werkzeug für moderne Wahlen ist.

Transparenz: Da Multimengen die Reihenfolge der Stimmen ignorieren, ist der Zählvorgang mathematisch garantiert anonym.
Einfachheit: Komplexe Regeln (wie das Löschen von Verlierern oder das Aufteilen von Überschüssen) werden zu einfachen Operationen auf einem Beutel voller Murmeln.
Korrektheit: Wenn Sie ein Computerprogramm schreiben, um Stimmen mithilfe dieser „Beutel-Regeln“ zu zählen, ist es viel schwieriger, einen Fehler zu machen, als wenn Sie versuchen, durch Stapel von Papier zu sortieren.

Zusammenfassend lässt sich sagen: Das Paper argumentiert, dass wenn wir aufhören, Stimmen als einen unordentlichen Haufen Papier zu betrachten und statbeginnen, sie als einen Beutel bunter Murmeln zu denken, wir einfache, leistungsstarke mathematische Regeln nutzen können, um sie fair, schnell und fehlerfrei zu zählen.

Technisches Resümee: Stimmenzählung mit Multimengen

Problemstellung
Die Arbeit befasst sich mit der Herausforderung, Algorithmen zur Stimmenzählung für komplexe Wahlsysteme zu beschreiben, zu erklären und zu implementieren, insbesondere solche, die präferenzielle Wahlen (Präferenzwahlen) und mehrere gewichtete Optionen beinhalten. Während einfache Wahlen (z. B. zwei Kandidaten, eine Stimme) über Listen oder einfache Zählungen beschrieben werden können, erfordern Mechanismen wie das Instant-Runoff-Voting (IRV), De-Borda-Zählungen und das Single Transferable Vote (STV) die Übertragung von Überschussstimmen, das Ausscheiden von Kandidaten und die Neugewichtung von Präferenzen. Die Autoren argumentieren, dass Standard-Datentypen wie Listen suboptimal für diese Aufgaben sind, da sie eine Ordnung beibehalten (die für das Ergebnis irrelevant ist) und Informationen über die Sequenz der Stimmabgabe preisgeben können, was die Vertraulichkeit gefährden kann. Zudem führt die Implementierung dieser Algorithmen mit Listen oft zu komplexem, ad-hoc-basiertem Code, der schwer auf Korrektheit und Transparenz zu prüfen ist.

Methodik
Die Arbeit schlägt vor, Wahlergebnisse und Stimmenzählungsprozesse unter Verwendung von Multimengen (Mengen, in denen Elemente mehrfach vorkommen können) anstatt Listen zu modellieren. Die Autoren nutzen elementare Techniken der Kategorientheorie, um die Operationen auf diesen Multimengen zu formalisieren. Die Kernmethodik umfasst:

Datentyp-Auswahl: Darstellung einer Sammlung von Stimmen als Multimenge $N(X)$ (oder $M(X)$ für fraktionale Stimmen), wobei die Elemente Kandidaten und die Vielfachheiten die Stimmenanzahl sind. Dies abstrahiert die Reihenfolge der Stimmen weg.
Kategoriale Strukturen: Die Autoren nutzen drei spezifische kategoriale Eigenschaften von Multimengen, um Wahlalgorithmen abzuleiten und auszudrücken:
- Kommutatives Monoid: Multimengen bilden ein freies kommutatives Monoid, was die Addition von Stimmenanzahlen (Vereinigung von Urnen) ermöglicht, bei der die Reihenfolge irrelevant ist.
- Funktorialität: Die Multimengen-Konstruktion $N$ wirkt als Funktor. Dies erlaubt es, auf Kandidaten definierten Funktionen (z. B. „Kopf der Liste“ oder „Kandidat löschen“) auf Multimengen von Listen zu heben. Diese Eigenschaft wird verwendet, um Erstpräferenzen zu aggregieren und Stimmen umzuverteilen, wenn ein Kandidat ausscheidet.
- Monaden-Struktur: Multimengen bilden eine Monade mit unit (Erzeugung einer Einzelelement-Multimenge) und flatten (Kollabieren einer Multimenge von Multimengen). Diese Struktur wird verwendet, um gewichtete Zählungen zu handhaben, bei denen eine einzelne Stimme (eine Liste von Präferenzen) in gewichtete Beiträge zu mehreren Kandidaten zerlegt wird.

Wesentliche Beiträge und Ergebnisse
Die Arbeit demonstriert die Anwendung dieser kategorialen Strukturen durch drei spezifische Wahlmechanismen unter Verwendung kleiner Maßstäbe (verifiziert via Python-Skripten aus der EfProb-Bibliothek), um die Abstraktion zu illustrieren:

Instant-Runoff-Voting (IRV):
- Mechanismus: Kandidaten mit den wenigsten Erstpräferenzen werden iterativ ausgeschieden, und ihre Stimmen werden an die nächste Präferenz übertragen.
- Anwendung: Die Autoren nutzen die Funktorialität von Multimengen. Die head-Funktion (Auswahl der Erstpräferenz) und die delete-Funktion (Entfernen eines ausgeschiedenen Kandidaten) werden auf die Multimenge der Präferenzlisten gehoben. Dies ermöglicht es, die Aggregation der Erstpräferenzen und die anschließende Umverteilung der Stimmen als einfache funktionale Kompositionen ( $N(\text{hd})$ und $N(\text{del } c)$ ) auszudrücken, wodurch komplexe iterative Listenverarbeitung vermieden wird.
De-Borda-Zählung:
- Mechanismus: Wähler ranken Kandidaten, und Punkte werden basierend auf dem Rang vergeben (z. B. 1. Platz erhält $n$ Punkte, 2. Platz $n-1$ usw.).
- Anwendung: Die Monaden-Struktur wird genutzt. Jede Präferenzliste wird auf eine Multimenge gewichteter Kandidaten abgebildet (via unit und Punktvergabe). Die Sammlung aller solcher gewichteten Multimengen bildet eine Multimenge von Multimengen. Die flatten-Operation kollabiert diese Struktur dann in eine einzige Multimenge der Gesamtpunktzahlen, was die Summation der gewichteten Beiträge effizient durchführt.
Single Transferable Vote (STV):
- Mechanismus: Wird für Mehrpersonenwahlkreise verwendet. Kandidaten, die ein Quorum (Droop-Quota) überschreiten, werden gewählt, und ihr Überschuss wird an die nächste Präferenz übertragen.
- Anwendung: Die Autoren erweitern den Datentyp zu fraktionalen Multimengen ( $M(X)$ ), um den „Übertragungswert“ (einen Bruchteil einer Stimme) zu handhaben. Sie nutzen die Monoid-Struktur für die Subtraktion (Entwertung von Stimmen, die zur Wahl eines Kandidaten verwendet wurden) und die Funktorialität für die Umverteilung. Der Prozess wird als iterativer Subtraktionsprozess der quotengewichteten Stimmen eines gewählten Kandidaten von der Gesamtmengengefolgt durch das Entfernen des gewählten Kandidaten und die Übertragung der verbleibenden fraktionalen Gewichte an die nächste Präferenz modelliert.

Bedeutung und Ansprüche
Die Arbeit erhebt den bescheidenen Anspruch, dass ihr primärer Beitrag nicht in tiefer Kategorientheorie liegt, sondern in der Erkennung und Nutzung bestehender kategorialer Strukturen (Funktoren, Monaden, Monoide) innerhalb der Domäne der Wahlsysteme. Die Autoren argumentieren, dass:

Abstraktion: Die Beschreibung dieser Algorithmen in Form von Multimengen macht sie „abstrakt“, wodurch komplexe Mechanismen in wenigen Zeilen mathematischer Notation beschrieben werden können.
Korrektheit und Transparenz: Der Multimengen-Ansatz gewährleistet inhärent die Stabilität unter der Permutation von Stimmen (Reihenfolgeunabhängigkeit), eine grundlegende Anforderung für faires Zählen. Er trennt die Logik der Zählung von der physischen oder sequentiellen Repräsentation der Stimmzettel.
Implementierung: Die Abstraktion erleichtert die Erstellung korrekter Implementierungen in funktionalen Programmiersprachen (z. B. Haskell), die Multimengen unterstützen.
Zugänglichkeit: Die Arbeit zielt darauf ab, diese kategorialen Techniken für Nicht-Experten zugänglich zu machen, indem sie zeigt, dass sie praktische Werkzeuge zur Sicherstellung der Transparenz und Genauigkeit von Wahlergebnissen sind und keine rein theoretischen Konstrukte.

Die Arbeit schließt mit dem Hinweis, dass vereinfachende Annahmen getroffen wurden (z. B. gleich lange Listen), der Multimengen-Ansatz jedoch einen robusten Rahmen für zukünftige Referenzimplementierungen und die Analyse von Wahlalgorithmen bietet, der über die historische Abhängigkeit von der Sortierung physischer Stimmzettel hinausgeht.