📊 statistics

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

Dit artikel ontwikkelt een theorie van optimale posterieure e-waarden voor sequentiële statistische toetsing met behulp van een efficiënt Frank-Wolfe-algoritme om niet-convexe parametermengels te verwerken, waarbij de superieure kracht en steekproefomvangefficiëntie worden aangetoond door toepassingen op Condorcet-, Borda- en Schulze-stemmechanismen op data van de Franse presidentsverkiezingen van 2022.

Oorspronkelijke auteurs: Adrienne Tuynman, Timothée Mathieu

Gepubliceerd 2026-06-30

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Adrienne Tuynman, Timothée Mathieu

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Het Grote Plaatje: De "Stop-Wanneer-Je-Het-Weet"-Peiling

Stel je voor dat je een politieke peiling uitvoert. Je wilt weten wie de verkiezingen gaat winnen, maar je wilt niet elke individuele kiezer in het land ondervragen. Je wilt net genoeg mensen ondervragen om zeker te zijn van de uitslag, en dan direct stoppen om tijd en geld te besparen.

Het probleem is dat traditionele statistiek je vaak dwingt om vooraf een vast aantal mensen te bepalen die je gaat ondervragen. Als je te vroeg stopt, zijn je resultaten misschien wankel. Als je te veel mensen ondervraagt, heb je middelen verspild.

Dit artikel introduceert een nieuwe, slimmere manier om deze peilingen uit te voeren. Het gebruikt een wiskundig hulpmiddel genaamd een "e-waarde" (denk aan een "vertrouwensmeter") waarmee je de gegevensverzameling kunt stoppen op het exacte moment dat het bewijs sterk genoeg is om een winnaar uit te roepen.

De Stemmechanismen: Drie Verschillende Spellen

De auteurs hebben hun methode getest op drie verschillende manieren om stemmen te tellen:

Condorcet (De "King of the Hill"): Een kandidaat wint als hij van elke andere kandidaat kan winnen in een één-tegen-één confrontatie. Het is simpel, maar soms is er geen duidelijke winnaar (zoals bij Steen-Papier-Schaar waarbij Steen de Schaar verslaat, Schaar het Papier, maar Papier de Steen).
Borda (Het "Puntenstelsel"): Kiezers rangschikken kandidaten. De winnaar is degene met de meeste totale punten. Dit is wiskundig "glad" en gemakkelijk te hanteren.
Schulze (De "Kettingreactie"): Dit is de lastige. Het kijkt naar ketens van overwinningen. Als A van B wint, en B van C wint, dan heeft A een sterke route om van C te winnen. Deze methode is erg populair in echte organisaties (zoals de Wikimedia Foundation), maar is wiskundig rommelig en "hobbelig".

Het Probleem: De "Hobbelige" Kaart

In de statistiek probeer je meestal een kaart te tekenen van alle mogelijke uitkomsten.

Voor Borda is de kaart een mooie, gladde heuvel (convex). Je kunt het hoogste punt gemakkelijk vinden.
Voor Schulze is de kaart een grillig, rotsachtig landschap met veel afzonderlijke pieken en dalen (niet-convex).

Vorige methoden waren als wandelaars die alleen wisten hoe ze op gladde heuvels moesten lopen. Ze konden Borda aan, maar raakten verdwaald of gaven op toen ze het rotsachtige Schulze-terrein probeerden te navigeren.

De Oplossing: De "Rugzaktoerist-Kompas" (POE)

De auteurs hebben een nieuwe methode ontwikkeld genaamd POE (Posterior Optimal E-value).

De Oude Manier: Stel je voor dat je probeert het beste pad een berg op te vinden door naar een statische kaart te kijken. Als de kaart fout is of het terrein vreemd is, raak je verdwaald.
De POE-Manier: Stel je voor dat je een rugzaktoerist bent met een magische kompas dat zichzelf bij elke stap die je zet, opnieuw kalibreert.

*   Terwijl je gegevens verzamelt (stemmen ondervraagt), berekent de kompas het "beste pad" opnieuw op basis van wat je tot nu toe hebt gezien.
*   Het zoekt niet alleen naar *één* specifieke winnaar; het zoekt naar de *best mogelijke verklaring* van de gegevens die je op dit moment hebt.
*   Cruciaal is dat deze kompas werkt, zelfs op het "rotsachtige" Schulze-terrein waar andere methoden falen.

Hoe Ze Het Werkend Kregen: Het "Frank-Wolfe" Algoritme

Om deze kompas werkend te krijgen op het rotsachtige Schulze-terrein, moesten de auteurs een nieuwe manier uitvinden om de wiskunde te doen. Ze gebruikten een techniek genaamd het Frank-Wolfe algoritme.

De Analogie: Stel je voor dat je probeert het laagste punt in een vallei te vinden, maar je kunt de hele vallei niet zien. Je kunt alleen kleine stapjes zetten.
- Oude methoden probeerden grote, complexe stappen te zetten die vaak vastliepen in de rotsen.
- De Frank-Wolfe methode is als het nemen van kleine, slimme stappen in de richting die op dit moment het steilst lijkt. Het is efficiënt en raakt niet in de war door de grillige randen van de Schulze-methode.

De Praktijktest: De Franse Verkiezingen van 2022

Om te bewijzen dat hun methode werkt, gebruikten ze niet alleen fictieve cijfers. Ze gebruikten echte gegevens van de Franse presidentsverkiezingen van 2022.

De Vraag: "Als de Franse kiezers het huidige systeem hadden vervangen door het Borda-systeem, wie zou er dan gewonnen hebben?"
Het Resultaat: Ze simuleerden een peiling. Terwijl ze meer stemmers "ondervraagden" (gesimuleerd door hun algoritme), konden ze kandidaten één voor één elimineren.
De Winnaar: Het algoritme stopte vol vertrouwen en riep Yannick Jadot uit als de Borda-winnaar.
De Efficiëntie: Ze ontdekten dat ze veel minder "stemmers" nodig hadden om zeker te zijn van de uitslag vergeleken met oudere statistische methoden. Sterker nog, hun methode was zo efficiënt dat het een conclusie had kunnen bereiken met slechts een fractie van de mensen die normaal gesproken bij politieke peilingen worden ondervraagd.

Samenvatting van Claims

Nieuw Hulpmiddel: Ze hebben een nieuw statistisch hulpmiddel (POE) gecreëerd dat "optimaal" is, wat betekent dat het het antwoord zo snel mogelijk vindt zonder fouten te maken.
Hanteert Complexiteit: In tegenstelling tot eerdere tools, werkt deze zelfs wanneer de regels van het spel (zoals het Schulze-stemmechanisme) wiskundig "hobbelig" en complex zijn.
Efficiëntie: In tests stopte hun methode eerder met het verzamelen van gegevens dan andere top-tier methoden, terwijl het nog steeds 100% betrouwbaar was.
Echte Toepassing: Ze hebben dit succesvol toegepast op echte verkiezingsgegevens om een hypothetische winnaar te bepalen, wat bewijst dat het in de echte wereld werkt en niet alleen in theorie.

Kortom: Ze hebben een slimmere, snellere en flexibelere manier gebouwd om peilingen uit te voeren die complexe stemregels kunnen verwerken en precies kunnen stoppen op het moment dat het antwoord duidelijk is, wat tijd en geld bespaart.

Technische Samenvatting: Optimale Posteriore E-waarden met Niet-Convexe Parameterverzamelingen met Toepassingen op Stemmenstelsels

Probleemstelling
Het artikel behandelt de uitdaging van het uitvoeren van sequentiële hypothesetests op voorkeurgegevens, specifiek binnen de context van politieke peilingen en stemmenstelsels. Het doel is om de winnaar van een verkiezing te bepalen (onder Condorcet-, Borda- of Schulze-regels) door sequentieel gegevens over paargewijze vergelijkingen te verzamelen en te stoppen zodra er statistisch significante resultaten zijn verkregen.

De kern van de statistische moeilijkheid ligt in de aard van de hypotheseverzamelingen. Terwijl de parameterruimte voor paargewijze voorkeuren (multivariate Bernoulli-gegevens) goed gedefinieerd is, zijn de verzamelingen parameters die corresponderen met specifieke stemwinnaars ( $H_0$ en $H_1$ ) complex.

Condorcet- en Borda-winnaars komen overeen met convexe of eenvoudige parameterverzamelingen.
Schulze-winnaars komen overeen met niet-convexe parameterverzamelingen die bestaan uit een unie van vele convexe componenten (gedefinieerd door strikte ordeningen van voorkeuren).
Bestaande methoden voor het construeren van optimale sequentiële tests, zoals Growth Rate Optimal (GRO) e-waarden, vertrouwen vaak op de convexiteit van de nulhypotheseverzameling ( $H_0$ ) om Reverse Information Projections (RIPr) te berekenen. Dit artikel beoogt een theorie en algoritme te ontwikkelen dat in staat is om algemene samengestelde hypothesen aan te pakken, inclusief niet-convexe verzamelingen zoals die van de Schulze-stemmethode.

Methodologie
De auteurs stellen een raamwerk voor gebaseerd op Posteriore Optimale E-waarden (POE).

Theoretisch Raamwerk (POE):
- Gebouwd op het GRO-criterium, dat de verwachte logaritmische groei van een e-waarde onder een specifieke alternatieve hypothese maximaliseert, breiden de auteurs dit uit naar samengestelde alternatieven vanuit een Bayesiaans perspectief.
- Ze definiëren een nutfunctie voor een e-waarde $E$ op basis van een prior $\pi$ over de alternatieve parameterverzameling $\Phi_1$ . Het doel is om een test-supermartingaal te vinden die de geïntegreerde nutfunctie $G_t(E, \pi, \tau)$ maximaliseert voor elke stoptijd $\tau$ .
- Stelling 2 stelt vast dat de optimale e-waarde (POE) het product is van één-stap optimale e-waarden. Elke stap omvat het berekenen van een likelihood ratio waarbij de teller de posterieure predictieve distributie is en de noemer de projectie van deze posterieure distributie op de nulverzameling $H_0$ .
- In tegenstelling tot eerdere benaderingen (bijv. Turner en Grunwald, 2022) die vertrouwen op specifieke vereenvoudigingen voor convexe verzamelingen of vaste dimensies, is de POE-formulering algemeen en toepasbaar op elke $H_0$ en $H_1$ die gedefinieerd zijn door parameterverzamelingen, mits de KL-divergentie eindig is.
Algoritmische Implementatie (Frank-Wolfe voor RIPr):
- Het berekenen van de POE vereist het oplossen van een Reverse Information Projection (RIPr) probleem in elke tijdstap: het vinden van een distributie in $H_0$ die de KL-divergentie van de huidige posterieure predictieve distributie minimaliseert.
- Standaardalgoritmen (zoals Li's algoritme) zijn computationeel zeer zwaar voor hoogdimensionele multivariate Bernoulli-gegevens.
- De auteurs passen het Frank-Wolfe-algoritme aan voor dit probleem. Door gebruik te maken van de eindige ondersteuning van de distributies (de ruimte van $2^D$ mogelijke uitkomsten), herformuleren ze de optimalisatie in $\mathbb{R}^{2^D}$ .
- Lemma 5 bewijst dat de extreme punten van de verzameling distributies over een parameterverzameling $\Phi'$ Dirac-distributies ( $P_{\delta_\phi}$ ) zijn. Dit stelt het Frank-Wolfe-algoritme in staat om de optimale projectie te zoeken door te itereren over de extreme punten (Dirac-maten) van de parameterverzameling.
- Deze aanpak maakt de berekening van RIPr mogelijk, zelfs wanneer $H_0$ een niet-convexe unie is van convexe verzamelingen (zoals in de Schulze-methode), een scenario waar eerdere GRO-gebaseerde methoden faalden.
Testprocedures:
- Capped Sample Size Test: Een test met een vast budget die stopt als de e-waarde $1/\alpha$ overschrijdt of een vooraf berekende maximale steekproefomvang $T$ bereikt.
- Fixed Confidence Test (PPOE): Een parallelle test die twee sequenties van e-waarden gebruikt (één voor $H_0$ vs $H_1$ , en één voor $H_1$ vs $H_0$ ). Deze stopt wanneer een van beide sequentieses drempelwaarden overschrijdt, wat garanties biedt op fout-positieve verhoudingen en power zonder een harde limiet op de steekproefomvang.

Belangrijkste Bijdragen

Posteriore Optimale E-waarden (POE): Een nieuw criterium voor e-waarde optimaliteit dat GRO generaliseert naar samengestelde hypothesen met behulp van een Bayesiaanse prior. Er wordt aangetoond dat dit het product is van één-stap optimale e-waarden geconditioneerd op de posterieure verdeling.
Afhandeling van Niet-Convexe Verzamelingen: Het artikel biedt de eerste statistische behandeling van het Schulze-stemstelsel, dat berucht is vanwege zijn niet-convexe parameterruimte.
Efficiënt RIPr-algoritme: De auteurs introduceren een Frank-Wolfe-gebaseerd algoritme om Reverse Information Projections voor multivariate Bernoulli-gegevens te berekenen. Deze methode is efficiënt genoeg om de niet-convexe unies van convexe verzamelingen vereist voor Schulze-stemmen te verwerken, waarmee de beperkingen van eerdere methoden die beperkt zijn tot convexe $H_0$ worden overwonnen.
Theoretische Garanties: De auteurs leiden concentratie-ongelijkheden af voor POE en bieden grenzen voor de verwachte stoptijd voor zowel vaste steekproefomvang als fixed-confidence tests, waarbij zij optimaliteit tonen in termen van steekproefcomplexiteit.

Experimentele Resultaten
De auteurs valideren hun methode via simulaties en real-world data:

Synthetische Data: Vergelijkingen met state-of-the-art methoden (Universal Inference, GLRT, Turner-Grunwald e-waarden en GRO) voor Condorcet-, Borda- en Schulze-stemscenario's met 3 kandidaten.
- POE en de parallelle variant (PPOE) vertonen competitieve power en steekproefcomplexiteit.
- Er wordt aangetoond dat POE essentieel is voor Schulze-stemmen (niet-convexe $H_0$ ), waar convexe-beperkte methoden niet direct kunnen worden toegepast.
- De methode profiteert van "prior data" (het voorbereiden van de prior $\pi$ ), waarbij de prestaties convergeren naar die van een oracle GRO-test naarmate de informatie over de prior toeneemt.
Toepassing op Real-world Data: De methode wordt toegepast op gegevens over paargewijze voorkeuren van de Franse presidentsverkiezingen van 2022.
- Het doel was om de Borda-winnaar te bepalen met behulp van sequentiële testen.
- Door gebruik te maken van de Turner-Grunwald (TG) estimator (voldoende voor de convexe Borda-gevallen), elimineerde de test sequentieel kandidaten.
- Het experiment concludeerde dat Yannick Jadot de Borda-winnaar zou zijn geweest. De test had aanzienlijk minder steekproeven nodig (171 kiezers, 4.721 paargewijze vergelijkingen) dan traditionele politieke enquêtes (bijv. IPSOS gebruikte 7.321 kiezers) om tot een definitieve conclusie te komen.

Betekenis en Claims
Het artikel claimt een algemeen raamwerk te bieden voor sequentiële testen in voorkeursstemmen dat niet beperkt wordt door de convexiteit van de hypotheseverzamelingen.

Het is de eerste statistische benadering om het Schulze-stemstelsel aan te pakken, dat door zijn niet-convexe parameterruimte zeer moeilijk te behandelen is.
Het voorgestelde Frank-Wolfe-algoritme biedt een praktische manier om Reverse Information Projections voor distributies met eindige ondersteuning te berekenen, wat potentieel de reikwijdte vergroot van stemmen naar andere omgevingen met niet-convexe restricties.
De auteurs merken op dat hoewel POE en de eenvoudigere TG-estimator vergelijkbaar presteren in convexe settings (zoals Borda), POE noodzakelijk is voor niet-convexe settings. Ze erkennen dat de computationele kosten van POE (door Frank-Wolfe updates) hoger zijn dan die van TG, maar dat deze afweging noodzakelijk is voor niet-convexe problemen.
Het werk benadrukt de haalbaarheid van sequentiële testen in hoogdimensionele real-world scenario's, waarbij wordt aangetoond dat statistisch significante conclusies kunnen worden getrokken met minder steekproeven dan traditionele opiniepeilingen.

De auteurs blijven bescheiden over toekomstige richtingen en wijzen op openstaande vragen over de convergentiesnelheden van hun Frank-Wolfe implementatie, de noodzaak van de $\epsilon$ -slack voor gladheid, en de potentie voor meer efficiënte methoden om het explosieve aantal convexe componenten in hoogdimensionele Schulze-stemmen aan te pakken.