📊 statistics

Optimal Posterior E-values with Non-Convex Parameter Sets with Applications to Voting Systems

Diese Arbeit entwickelt eine Theorie optimaler Posterior-E-Werte für sequenzielle statistische Tests unter Verwendung eines effizienten Frank-Wolfe-Algorithmus zur Handhabung nicht-konvexer Parametersätze und demonstriert dessen überlegene Power und Stichprobengrößeneffizienz durch Anwendungen auf Condorcet-, Borda- und Schulze-Wahlsysteme bei den Daten der französischen Präsidentschaftswahl 2022.

Ursprüngliche Autoren: Adrienne Tuynman, Timothée Mathieu

Veröffentlicht 2026-06-30

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Adrienne Tuynman, Timothée Mathieu

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

Das große Ganze: Die „Stopp-wenn-du-es-weißt“-Umfrage

Stellen Sie sich vor, Sie führen eine politische Umfrage durch. Sie möchten wissen, wer eine Wahl gewinnen wird, aber Sie wollen nicht jeden einzelnen Wähler des Landes fragen. Sie wollen gerade so viele Menschen fragen, bis Sie sich des Ergebnisses sicher sind, und dann sofort aufhören, um Zeit und Geld zu sparen.

Das Problem ist, dass die traditionelle Statistik Sie oft dazu zwingt, sich schon vor Beginn festzulegen, wie viele Personen Sie befragen wollen. Wenn Sie zu früh aufhören, könnten Ihre Ergebnisse unzuverlässig sein. Wenn Sie zu viele fragen, haben Sie Ressourcen verschwendet.

Dieses Paper stellt eine neue, intelligentere Art und Weise vor, diese Umfragen durchzuführen. Es verwendet ein mathematisches Werkzeug namens „e-Wert“ (denken Sie an ein „Konfidenz-Meter“), das es Ihnen ermöglicht, die Datenerhebung genau in dem Moment zu stoppen, in dem die Beweislast groß genug ist, um einen Sieger zu verkünden.

Die Wahlsysteme: Drei verschiedene Spiele

Die Autoren testeten ihre Methode bei drei verschiedenen Arten, Stimmen zu zählen:

Condorcet (Der „König des Hügels“): Ein Kandidat gewinnt, wenn er in jedem direkten Duell gegen jeden anderen Kandidaten gewinnt. Es ist einfach, aber manchmal gibt es keinen klaren Sieger (wie bei Schere-Stein-Papier, wo Schere Stein schlägt, Stein Papier schlägt, aber Papier Schere schlägt).
Borda (Das „Punktesystem“): Wähler ranken Kandidaten. Der Gewinner ist derjenige mit den meisten Gesamtpunkten. Dies ist mathematisch „glatt“ und leicht zu handhaben.
Schulze (Die „Kettenreaktion“): Dies ist der knifflige Teil. Es betrachtet Ketten von Siegen. Wenn A gegen B gewinnt und B gegen C gewinnt, dann hat A einen starken Pfad, um C zu schlagen. Diese Methode ist in realen Organisationen (wie der Wikimedia Foundation) sehr beliebt, aber mathematisch „uneben“ und „höckerig“.

Das Problem: Die „unebene“ Landkarte

In der Statistik versucht man normalerweise, eine Karte aller möglichen Ergebnisse zu zeichnen.

Für Borda ist die Karte ein schöner, glatter Hügel (konvex). Man kann das Gipfel leicht finden.
Für Schulze ist die Karte eine zerklüftete, felsige Landschaft mit vielen separaten Gipfeln und Tälern (nicht-konvex).

Frühere Methoden waren wie Wanderer, die nur auf glatten Hügeln wandern konnten. Sie konnten Borda handhaben, aber sie blieben stecken oder gaben auf, wenn sie versuchten, das felsige Schulze-Gelände zu durchqueren.

Die Lösung: Der „Rucksackwanderer-Kompass“ (POE)

Die Autoren entwickelten eine neue Methode namens POE (Posterior Optimal E-value).

Der alte Weg: Stellen Sie sich vor, Sie versuchen, den besten Pfad auf einem Berg zu finden, indem Sie eine statische Karte betrachten. Wenn die Karte falsch ist oder das Gelände seltsam ist, verirren Sie sich.
Der POE-Weg: Stellen Sie sich vor, Sie sind ein Rucksackwanderer mit einem magischen Kompass, der sich jedes Mal selbst aktualisiert, wenn Sie einen Schritt machen.
- Während Sie Daten sammeln (Wähler fragen), berechnet der Kompass den „besten Pfad“ basierend auf dem, was Sie bisher gesehen haben, neu.
- Er sucht nicht nur nach einem spezifischen Gewinner; er sucht nach der bestmöglichen Erklärung für die Daten, die Sie jetzt gerade haben.
- Entscheidend ist: Dieser Kompass funktioniert auch auf dem „felsigen“ Schulze-Gelände, wo andere Methoden scheitern.

Wie sie es zum Laufen brachten: Der „Frank-Wolfe-Algorithmus“

Um diesen Kompass auf dem felsigen Schulze-Gelände funktionsfähig zu machen, mussten die Autoren eine neue Art der Mathematik erfinden. Sie verwendeten eine Technik namens Frank-Wolfe-Algorithmus.

Die Analogie: Stellen Sie sich vor, Sie versuchen, den tiefsten Punkt in einem Tal zu finden, aber Sie können das ganze Tal nicht sehen. Sie können nur kleine Schritte machen.
- Alte Methoden versuchten, riesige, komplexe Schritte zu machen, die oft in den Felsen stecken blieben.
- Die Frank-Wolfe-Methode ist wie das Machen kleiner, kluger Schritte in die Richtung, die jetzt gerade am steilsten erscheint. Sie ist effizient und lässt sich nicht von den zerklüfteten Kanten des Schulze-Verfahrens verwirren.

Der Praxistest: Die französische Wahl 2022

Um zu beweisen, dass ihre Methode funktioniert, haben sie nicht nur fiktive Zahlen verwendet. Sie nutzten reale Daten aus der Präsidentschaftswahl in Frankreich 2022.

Die Frage: „Wenn die französischen Wähler das Borda-System anstelle des aktuellen Systems genutzt hätten, wer wäre der Gewinner gewesen?“
Das Ergebnis: Sie simulierten eine Umfrage. Während sie immer mehr „Wähler“ befragten (simuliert durch ihren Algorithmus), konnten sie Kandidaten einen nach dem anderen eliminieren.
Der Sieger: Der Algorithmus stoppte selbstbewusst und erklärte Yannick Jadot zum Borda-Sieger.
Die Effizienz: Sie fanden heraus, dass sie weit weniger „Wähler“ brauchten, um sich des Ergebnisses sicher zu sein, als bei älteren statistischen Methoden. Tatsächlich war ihre Methode so effizient, dass sie das Ergebnis mit einem winzigen Bruchteil der Menschen hätte erreichen können, die normalerweise in politischen Umfragen befragt werden.

Zusammenfassung der Behauptungen

Neues Werkzeug: Sie haben ein neues statistisches Werkzeug (POE) geschaffen, das „optimal“ ist, was bedeutet, dass es die Antwort so schnell wie möglich findet, ohne Fehler zu machen.
Bewältigung von Komplexität: Im Gegensatz zu bisherigen Werkzeugen funktioniert dieses auch dann, wenn die Regeln des Spiels (wie das Schulze-Wahlsystem) mathematisch „uneben“ und komplex sind.
Effizienz: In Tests stoppte ihre Methode die Datenerhebung früher als andere erstklassige Methoden, während sie gleichzeitig zu 100 % zuverlässig blieb.
Reale Anwendung: Sie haben dies erfolgreich auf reale Wahldaten angewendet, um einen hypothetischen Sieger zu ermitteln, was beweist, dass es in der realen Welt funktioniert und nicht nur in der Theorie.

Kurz gesagt: Sie haben eine intelligentere, schnellere und flexiblere Art und Weise entwickelt, Umfragen durchzuführen, die komplexe Wahlregeln handhaben und genau dann aufhören können, wenn die Antwort klar ist, wodurch Zeit und Geld gespart werden.

Technische Zusammenfassung: Optimale posteriore E-Werte mit nicht-konvexen Parameterbereichen mit Anwendungen auf Wahlsysteme

Problemstellung
Die Arbeit adressiert die Herausforderung der Durchführung sequentieller Hypothesentests auf Präferenzdaten, speziell im Kontext von politischem Polling und Wahlsystemen. Das Ziel besteht darin, den Gewinner einer Wahl (unter Condorcet-, Borda- oder Schulze-Regeln) zu bestimmen, indem paarweise Vergleichsdaten sequentiell gesammelt werden und der Prozess stoppt, sobald statistisch signifikante Ergebnisse vorliegen.

Die zentrale statistische Schwierigkeit ergibt sich aus der Natur der Hypothesenmengen. Während der Parameterraum für paarweise Präferenzen (multivariate Bernoulli-Daten) wohldefiniert ist, können die Parameterbereiche, die zu spezifischen Wahlsiegern gehören ( $H_0$ und $H_1$ ), komplex sein.

Condorcet- und Borda-Gewinner entsprechen konvexen oder einfachen Parameterbereichen.
Schulze-Gewinner entsprechen nicht-konvexen Parameterbereichen, die aus einer Vereinigung vieler konvexer Komponenten bestehen (definiert durch strikte Ordnungen von Präferenzen).
Bestehende Methoden zur Konstruktion optimaler sequentieller Tests, wie etwa Growth Rate Optimal (GRO) E-Werte, beruhen oft auf der Konvexität der Nullhypothese ( $H_0$ ), um Reverse Information Projections (RIPr) zu berechnen. Die Arbeit zielt darauf ab, eine Theorie und einen Algorithmus zu entwickeln, der allgemeine zusammengesetzte Hypothesen, einschließlich nicht-konvexer Mengen wie jener der Schulze-Wahlmethode, handhaben kann.

Methodik
Die Autoren schlagen ein Framework vor, das auf Posterior Optimal E-values (POE) basiert.

Theoretisches Framework (POE):
- Aufbauend auf dem GRO-Kriterium, welches den erwarteten Log-Wachstumsraten eines E-Wertes unter einer spezifischen Alternativhypothese maximiert, erweitern die Autoren dies auf zusammengesetzte Alternativen aus einer bayesianischen Perspektive.
- Sie definieren eine Nutzenfunktion für einen E-Wert $E$ basierend auf einem Prior $\pi$ über den alternativen Parameterbereich $\Phi_1$ . Das Ziel ist es, eine Test-Supermartingal zu finden, die den integrierten Nutzen $G_t(E, \pi, \tau)$ für jede Stoppzeit $\tau$ maximiert.
- Theorem 2 etabliert, dass der optimale E-Wert (POE) das Produkt von Ein-Schritt-optimalen E-Werten ist. Jeder Schritt beinhaltet die Berechnung eines Likelihood-Verhältnisses, wobei der Zähler die posteriore prädiktive Verteilung und der Nenner die Projektion dieser posterioren Verteilung auf die Nullmenge $H_0$ ist.
- Im Gegensatz zu früheren Ansätzen (z. B. Turner und Grunwald, 2022), die auf spezifischen Vereinfachungen für konvexe Mengen oder feste Dimensionen beruhen, ist die POE-Formulierung allgemein und anwendbar auf beliebige $H_0$ und $H_1$ , sofern die KL-Divergenz endlich ist.
Algorithmische Implementierung (Frank-Wolfe für RIPr):
- Die Berechnung des POE erfordert das Lösen eines Reverse Information Projection (RIPr) Problems zu jedem Zeitschritt: das Finden einer Verteilung in $H_0$ , die die KL-Divergenz von der aktuellen posterioren prädiktiven Verteilung minimiert.
- Standardalgorithmen (wie Li's Algorithmus) sind für hochdimensionale multivariate Bernoulli-Daten rechenintensiv.
- Die Autoren passen den Frank-Wolfe-Algorithmus an dieses Problem an. Durch die Nutzung des endlichen Supports der Verteilungen (den Raum der $2^D$ möglichen Ausgänge) formulieren sie die Optimierung in $\mathbb{R}^{2^D}$ neu.
- Lemma 5 beweist, dass die Extremalpunkte der Menge der Verteilungen über einen Parameterbereich $\Phi'$ Dirac-Verteilungen ( $P_{\delta_\phi}$ ) sind. Dies ermöglicht es dem Frank-Wolfe-Algorithmus, die optimale Projektion durch Iteration über die Extremalpunkte (Dirac-Maße) des Parameterbereichs zu suchen.
- Dieser Ansatz ermöglicht die Berechnung der RIPr selbst dann, wenn $H_0$ eine nicht-konvexe Vereinigung konvexer Mengen ist (wie beim Schulze-Verfahren), ein Szenario, in dem bisherige GRO-basierte Methoden scheiterten.
Testverfahren:
- Capped Sample Size Test: Ein Test mit festem Budget, der stoppt, wenn der E-Wert $1/\alpha$ überschreitet oder eine vordefinierte maximale Stichprobengröße $T$ erreicht.
- Fixed Confidence Test (PPOE): Ein paralleler Test, der zwei Sequenzen von E-Werten verwendet (einen für $H_0$ vs. $H_1$ , einen für $H_1$ vs. $H_0$ ). Er stoppt, wenn eine der Sequenzen ihren Schwellenwert überschreitet, was Garantien für die Falsch-Positiv-Raten und die Power liefert, ohne eine harte Obergrenze für die Stichprobengröße vorzugeben.

Wesentliche Beiträge

Posterior Optimal E-values (POE): Ein neues Kriterium für die Optimalität von E-Werten, das GRO für zusammengesetzte Hypothesen unter Verwendung eines bayesianischen Priors generalisiert. Es wird gezeigt, dass es das Produkt von ein-schritt-optimalen E-Werten ist, die auf die Posterior verteilt sind.
Handhabung nicht-konvexer Mengen: Die Arbeit liefert die erste statistische Behandlung des Schulze-Wahlsystems, welches nicht-konvexe Parameterbereiche beinhaltet.
Effizienter RIPr-Algorithmus: Die Autoren führen einen auf Frank-Wolfe basierenden Algorithmus zur Berechnung von Reverse Information Projections für multivariate Bernoulli-Daten ein. Diese Methode ist effizient genug, um die nicht-konvexen Vereinigungen konvexer Mengen zu handhaben, die für die Schulze-Wahl erforderlich sind, und überwindet damit die Einschränkungen früherer Methoden, die auf konvexe $H_0$ beschränkt waren.
Theoretische Garantien: Die Autoren leiten Konzentrationsungleichungen für POE her und liefern Schranken für die erwartete Stoppzeit sowohl für Fixed-Sample- als auch für Fixed-Confidence-Tests, wodurch sie hinsichtlich der Stichprobenkomplexität optimal sind.

Experimentelle Ergebnisse
Die Autoren validieren ihre Methode durch Simulationen und reale Daten:

Synthetische Daten: Vergleiche mit State-of-the-Art-Methoden (Universal Inference, GLRT, Turner-Grunwald E-Werte und GRO) für Condorcet-, Borda- und Schulze-Wahlszenarien mit 3 Kandidaten.
- POE und seine parallele Variante (PPOE) zeigen eine wettbewerbsfähige Power und Stichprobenkomplexität.
- Es wird gezeigt, dass POE für die Schulze-Wahl (nicht-konvexes $H_0$ ) essenziell ist, da konvex eingeschränkte Methoden hier nicht direkt angewendet werden können.
- Die Methode profitiert von "Prior-Daten" (Vor-Training des Priors $\pi$ ) und konvergiert mit zunehmender Information gegen die Performance eines optimalen Oracle-GRO-Tests.
Anwendung auf Realdaten: Die Methode wird auf paarweise Präferenzdaten der französischen Präsidentschaftswahl 2022 angewendet.
- Das Ziel war es, den Borda-Gewinner mittels sequentieller Tests zu bestimmen.
- Unter Verwendung des Turner-Grunwald (TG) Schätzers (ausreichend für den konvexen Borda-Fall) eliminierte der Test sukzessive Kandidaten.
- Das Experiment kam zu dem Schluss, dass Yannick Jadot der Borda-Gewinner gewesen wäre. Der Test benötigte signifikant weniger Stichproben (171 Wähler, 4.721 Paarvergleiche) als traditionelle politische Umfragen (z. B. IPSOS mit 7.321 Wählern), um zu einem definitiven Ergebnis zu gelangen.

Bedeutung und Ansprüche
Die Arbeit beansprucht, ein allgemeines Framework für sequentielles Testen in Präferenzwahlen bereitzustellen, das nicht durch die Konvexität der Hypothesenmengen begrenzt ist.

Es ist der erste statistische Ansatz, um das Schulze-Wahlsystem anzugehen, das aufgrund seines nicht-konvexen Parameterraums als besonders schwierig gilt.
Der vorgeschlagene Frank-Wolfe-Algorithmus bietet einen praktischen Weg zur Berechnung von Reverse Information Projections für Verteilungen mit endlichem Support, was potenziell über Wahlen hinaus auf andere Settings mit nicht-konvexen Beschränkungen übertragbar ist.
Die Autoren merken an, dass POE und der einfachere TG-Schätzer in konvexen Settings (wie Borda) ähnlich performen, POE jedoch für nicht-konvexe Settings notwendig ist. Sie räumen ein, dass die Rechenkosten von POE (aufgrund der Frank-Wolfe-Updates) höher sind als bei TG, dieser Trade-off jedoch für nicht-konvexe Probleme notwendig ist.
Die Arbeit unterstreicht die Machbarkeit von sequentiellen Tests in hochdimensionalen realen Szenarien und zeigt auf, dass statistisch signifikante Schlussfolgerungen mit weniger Stichproben als traditionelle Umfragemethoden gezogen werden können.

Die Autoren bleiben bescheiden hinsichtlich zukünftiger Richtungen und weisen auf offene Fragen hin, wie etwa die Konvergenzraten ihrer Frank-Wolfe-Implementierung, die Notwendigkeit des $\epsilon$ -Slack für die Glattheit sowie das Potenzial für effizientere Methoden zur Handhabung der explodierenden Anzahl konvexer Komponenten in der hochdimensionalen Schulze-Wahl.