Matematik för fördelning

Matematik för fördelning beskriver matematiska principer och algoritmer för rättvis fördelning av identiska poster mellan parter med olika rättigheter. Sådana principer används för att fördela platser i parlament mellan federala stater eller politiska partier . Se fördelning (politik) för mer konkreta principer och frågor relaterade till fördelning, och fördelning per land för praktiska metoder som används runt om i världen.

Matematiskt är en fördelningsmetod bara en metod för att avrunda bråk till heltal. Hur enkelt det än låter, varje metod för avrundning lider av en eller flera paradoxer . Den matematiska teorin om fördelning syftar till att avgöra vilka paradoxer som kan undvikas, eller med andra ord, vilka egenskaper som kan förväntas av en fördelningsmetod.

Den matematiska teorin om fördelningen studerades redan 1907 av matematikern Agner Krarup Erlang . Det utvecklades senare till stor detalj av matematikern Michel Balinsky och ekonomen Peyton Young . Förutom dess tillämpning på politiska partier, är den också tillämplig på rättvis fördelning av föremål när agenter har olika rättigheter . Det är också relevant i arbetskraftsplanering - där jobb bör fördelas i proportion till arbetskraftspoolens egenskaper, för statistik - där de rapporterade avrundade procenttalen ska summera till 100 %, och för konkursproblem .

Definitioner

Inmatning

Indata till en fördelningsmetod är:

  • Ett positivt heltal som representerar det totala antalet objekt som ska allokeras. Det kallas också husstorleken , eftersom föremålen som ska fördelas i många fall är platser i ett representanthus.
  • Ett positivt heltal som representerar antalet agenter till vilka objekt ska allokeras. Dessa kan till exempel vara federala stater eller politiska partier .
  • En vektor av tal som representerar rättigheter - representerar behörigheten för agent , det vill säga mängden objekt som är berättigad till (av det totala antalet ). Dessa rättigheter är ofta normaliserade så att . Alternativt kan de normaliseras så att deras summa är ; i detta fall kallas rättigheterna kvoter och betecknas med , där och . Alternativt ges en vektor av populationer ; här är rätten för agent .

Produktion

Utdata är en vektor av heltal med , kallad en fördelning av , där är antalet objekt som tilldelats agent i .

För varje agent det reella talet kvoten av i { och anger det exakta antalet objekt som ska ges till . I allmänhet är en "rättvis" fördelning en där varje allokering är så nära kvoten .

En fördelningsmetod kan returnera en uppsättning fördelningsvektorer (med andra ord: det är en funktion med flera värden ). Detta krävs, eftersom det i vissa fall inte finns något rättvist sätt att skilja mellan två möjliga lösningar. Till exempel, om (eller något annat udda tal) och } (50,51) och (51,50) är båda lika rimliga lösningar, och det finns inget matematiskt sätt att välja den ena framför den andra. Även om sådana kopplingar är extremt sällsynta i praktiken, måste teorin ta hänsyn till dem (i praktiken, när en fördelningsmetod returnerar flera utdata, kan en av dem väljas av vissa externa prioriteringsregler eller genom att vända mynt, men detta ligger utanför räckvidden av den matematiska fördelningsteorin).

En fördelningsmetod betecknas med en funktion med flera värden ; en speciell -lösning är en funktion med ett värde väljer en enskild uppdelning från .

En partiell fördelningsmetod är en fördelningsmetod för specifika fasta värden på och ; det är en funktion med flera värden som endast accepterar en -vektorer.

Varianter

Ibland innehåller inmatningen också en vektor av heltal som representerar minimikrav - representerar den minsta antal objekt som agent ska ta emot, oavsett dess berättigande. Så det finns ett ytterligare krav på utgången: för alla .

När agenterna är politiska partier är dessa siffror vanligtvis 0, så denna vektor utelämnas. Men när agenterna är stater eller distrikt är dessa siffror ofta positiva för att säkerställa att alla är representerade. De kan vara lika för alla agenter (t.ex. 1 för USA-stater, 2 för Frankrikes distrikt) eller olika (t.ex. i Kanada eller EU-parlamentet).

Ibland finns det också en vektor med maximala krav , men det är mindre vanligt.

Grundläggande krav

Det finns grundläggande egenskaper som bör tillgodoses med någon rimlig fördelningsmetod. De fick olika namn av olika författare: namnen till vänster är från Pukelsheim; Namnen inom parentes till höger är från Balinsky och Young.

  • Anonymitet (= Symmetry ) innebär att fördelningen inte beror på agenternas namn eller index. Formellt, om är någon permutation av , då är fördelningarna i är exakt motsvarande permutationer av fördelningarna i .
    • Detta krav är vettigt när det inte finns några minimikrav, eller när kraven är desamma; om de inte är desamma bör anonymiteten gälla under förutsättning att kraven är uppfyllda.
  • Balansering (= Balans ) innebär att om två agenter har lika rättigheter, så bör deras tilldelning skilja sig med högst 1: innebär .
  • Överensstämmelse (= Svag populationsmonotoni ) innebär att en agent med en strikt högre berättigande får minst lika många föremål: innebär .
  • Anständighet (= Homogenitet ) innebär att skalning av berättigandevektorn inte ändrar resultatet. Formellt är för varje konstant c ( detta är automatiskt tillfredsställt om input till fördelningsmetoden normaliseras).
  • Exakthet (= Svag proportionalitet ) betyder att om det finns en perfekt lösning så måste den väljas. Formellt, om kvoten för varje agent är ett heltal, då är måste innehålla en unik vektor . Med andra ord, om en h -fördelning är exakt proportionell mot , så bör det vara det unika elementet i .
    • Stark exakthet innebär att exakthet också håller "i gränsen". Det vill säga, om en sekvens av berättigandevektorer konvergerar till en heltalskvotvektor då den enda allokeringsvektorn i alla element i sekvensen är . För att se skillnaden från svag exakthet, överväg följande regel. (a) Ge varje agent sin kvot avrundad nedåt, ; (b) ge de återstående platserna iterativt till de största partierna. Denna regel är svagt exakt, men inte starkt exakt. Anta till exempel att h =6 och betrakta sekvensen av kvotvektorer (4+1/ k , 2-1/ k ) . Ovanstående regel ger allokeringen (5,1) för alla k , även om gränsen när k→∞ är heltalsvektorn (4,2).
    • Stark proportionalitet innebär dessutom att om och , och det finns någon h -fördelning som är exakt proportionell mot , då borde det vara det unika elementet av . Till exempel, om en lösning i är (3,3), då är den enda lösningen i måste vara (2,2). [ varför? ]
  • Fullständighet betyder att, om någon fördelning returneras för en konvergerande sekvens av berättigandevektorer, så returneras också för deras gränsvektor. Med andra ord, mängden vilka är en möjlig uppdelning - är topologiskt stängd . En ofullständig metod kan "fullbordas" genom att lägga till fördelningen till valfri limitberättigande om och endast om den tillhör varje berättigande i sekvensen. Slutförandet av en symmetrisk och proportionell fördelningsmetod är fullständig, symmetrisk och proportionell.
    • Fullständigheten kränks av metoder som tillämpar en extern tie-breaking-regel, vilket många länder gör i praktiken. Den oavgjorda regeln gäller endast i limitfallet, så det kan bryta fullständigheten.
    • Fullständighet och svag-exakthet innebär tillsammans stark-exakthet. Om en fullständig och svagt exakt metod modifieras genom att lägga till en lämplig oavgjort regel, är den resulterande regeln inte längre komplett, men den är fortfarande mycket exakt.

Vanliga fördelningsmetoder

Det finns många fördelningsmetoder, och de kan klassificeras i flera tillvägagångssätt.

  1. De största restmetoderna börjar med att beräkna vektorn av kvoter avrundade nedåt, det vill säga . Om summan av dessa avrundade värden är exakt , returneras denna vektor som den unika fördelningen. Vanligtvis är summan mindre än . I det här fallet fördelas de återstående föremålen mellan agenterna enligt deras rester : agenten med den största återstoden får en plats , sedan får agenten med den näst största återstoden en plats, och så vidare, tills alla föremål är tilldelade. Det finns flera varianter av LR-metoden, beroende på vilken kvot som används:
    • Den enkla kvoten, även kallad Hare-kvoten , är . Att använda LR med Hare-kvoten leder till Hamiltons metod .
    • Hagenbach -Bischoff-kvoten , även kallad den exakta Droop-kvoten, är . Kvoterna i denna metod är större, så det finns färre kvarvarande poster. I teorin är det möjligt att summan av avrundade kvoter skulle vara vilket är större än , men detta händer sällan i praktiken.
    • Imperiali -kvoten är . Denna kvot är mindre vanlig, eftersom det finns större chanser att summan av nedrundade kvoter är större än .
  2. Divisormetoder , istället för att använda en fast multiplikator i kvoten (som eller ), välj multiplikatorn så att summan av avrundade kvoter är exakt lika med , så det finns inga återstående objekt att tilldela. Formellt är . Divisormetoder skiljer sig åt beroende på vilken metod de använder för avrundning. En divisormetod parametriseras av en divisorfunktion som specificerar, för varje heltal ett reellt tal i intervallet . Det betyder att alla tal i ska avrundas nedåt till , och alla tal i ska avrundas uppåt till . Avrundningsfunktionen betecknas med , och returnerar ett heltal så att . Själva talet kan avrundas både uppåt och nedåt, så avrundningsfunktionen är flervärdig. Till exempel använder Adams metod , vilket motsvarar avrundning uppåt; D'Hondt/Jefferson-metoden använder vilket motsvarar avrundning nedåt; och Webster/Sainte-Laguë-metoden använder vilket motsvarar avrundning till närmaste heltal. En divisormetod kan också beräknas iterativt: initialt sätts Sedan, vid varje iteration, tilldelas nästa plats till ett parti som maximerar förhållandet t .
  3. Rank-index-metoder parametriseras av en funktion som minskar i . Fördelningen beräknas iterativt. Inledningsvis ställer du in till 0 för alla parter. Sedan, vid varje iteration, allokera nästa plats till en agent som maximerar . Divisormetoder är ett specialfall av rank-index-metoder: en divisormetod med divisorfunktion är ekvivalent med en rank-index-metod med rank-index .
  4. Optimeringsbaserade metoder syftar till att för varje instans uppnå en tilldelning som är "så rättvis som möjligt" för denna instans. En tilldelning är "rättvis" om för alla agenter i ; i detta fall säger vi att tilldelningens "orättvisa" är 0. Om denna jämlikhet kränks kan man definiera ett mått på "total orättvisa", och försöka minimera den. Man kan minimera summan av orättvisa nivåer, eller den maximala orättvisa nivån. Varje optimeringskriterium leder till en annan regel.

Att hålla sig inom kvoten

Den exakta kvoten för agent är . Ett grundläggande krav från en fördelningsmetod är att den allokerar till varje agent dess kvot om det är ett heltal; annars bör den tilldela det ett heltal som är nära den exakta kvoten, det vill säga antingen dess nedre kvot eller dess övre kvot . Vi säger att en fördelningsmetod -

  • Uppfyller lägre kvot om för alla (detta gäller iff ).
  • Uppfyller den övre kvoten om för alla (detta gäller om ).
  • Uppfyller båda kvoterna om båda ovanstående villkor gäller (detta gäller iff ).

Hamiltons metod med största resterande tillfredsställer både lägre kvot och övre kvot efter konstruktion. Detta gäller inte för divisormetoderna:

  • Alla divisormetoder uppfyller båda kvoterna när det finns 2 agenter;
  • Websters metod är den enda divisormetoden som uppfyller båda kvoterna för 3 agenter;
  • Adams metod är den enda divisormetoden som uppfyller den övre kvoten för ett valfritt antal agenter;
  • Jeffersons metod är den enda divisormetoden som uppfyller lägre kvoter för ett valfritt antal agenter;
  • Ingen divisormetod bryter samtidigt mot den övre kvoten för en agent och bryter mot den lägre kvoten för en annan agent.

Därför uppfyller ingen divisormetod både den övre kvoten och den lägre kvoten för ett valfritt antal agenter. Det unika med Jefferson och Adams gäller även i den mycket större klassen av rangindexmetoder.

Detta kan ses som en nackdel med divisormetoder, men det kan också betraktas som en nackdel med kvotkriteriet:

" Till exempel, att ge D 26 istället för 25 platser i Tabell 10.1 skulle innebära att man tar en plats från en av de mindre staterna A, B eller C. En sådan överföring skulle straffa representationen per capita i den lilla staten mycket mer - i både absoluta och relativa termer - än att stat D straffas genom att få en mindre än sin lägre kvot. Liknande exempel kan uppfinnas där någon stat rimligen kan få mer än sin övre kvot. Det kan hävdas att det inte är riktigt att hålla sig inom kvoten. överhuvudtaget förenlig med proportionalitetstanken, eftersom den tillåter en mycket större varians i representationen per capita för mindre stater än vad den gör för större stater. "

I Monte-Carlo-simuleringar uppfyller Websters metod båda kvoterna med mycket hög sannolikhet. Dessutom är Wesbters metod den enda divisionsmetoden som uppfyller nästan kvoten : det finns inga agenter så att flytta en plats från till skulle ge både av dem närmare sina kvoter:

.

Jeffersons metod kan modifieras för att uppfylla båda kvoterna, vilket ger Quota-Jefferson-metoden. Dessutom vilken delningsmetod som helst ändras för att uppfylla båda kvoterna. Detta ger Quota-Webster-metoden, Quota-Hill-metoden, etc. Denna familj av metoder kallas ofta för quatatone-metoderna , eftersom de uppfyller både kvoter och hus-monotonicitet .

Minimera parvis ojämlikhet

Ett sätt att utvärdera fördelningsmetoder är huruvida de minimerar mängden ojämlikhet mellan par av agenter. Klart att ojämlikhet bör ta hänsyn till de olika rättigheterna: om så är agenterna behandlas "lika" (med hänsyn till deras rättigheter); annars, om favoriseras agent favoriseras agent Men eftersom det finns 16 sätt att ordna om likheten finns det motsvarande många sätt på vilka ojämlikhet kan definieras.

  • . Websters metod är den unika fördelningsmetoden där, för varje par av agenter och , denna skillnad minimeras (det vill säga att flytta en plats från till eller vice versa skulle inte göra skillnaden mindre).
  • för Detta leder till Adams metod.
  • för . Detta leder till Jeffersons metod.
  • . Detta leder till Deans metod.
  • . Detta leder till Huntington-Hill-metoden.

Denna analys gjordes av Huntington på 1920-talet. Vissa av möjligheterna leder inte till en stabil lösning. Till exempel, om vi definierar ojämlikhet som då finns det tillfällen där, för varje tilldelning, flytta en plats från en agent till en annan kan minska deras parvisa ojämlikhet . Det finns ett exempel med 3 stater med befolkningar (737 534 329) och 16 platser.

Bias mot stora/små agenter

När agenterna är federala stater är det särskilt viktigt att undvika partiskhet mellan stora stater och små stater. Det finns flera sätt att mäta denna bias formellt. Alla mätningar leder till slutsatsen att Jeffersons metod är partisk till förmån för stora stater, Adams metod är partisk till förmån för små stater, och Websters metod är den minst partiska divisormetoden.

Konsistensegenskaper

Konsistensegenskaper är egenskaper som kännetecknar en fördelningsmetod snarare än en viss fördelning. Varje konsistensegenskap jämför resultaten av en viss metod på olika indata. Flera sådana egenskaper har studerats.

Statlig befolkningsmonotonitet innebär att om rätten till ett ombud ökar, bör dess fördelning inte minska. Namnet kommer från den miljö där agenterna är federala stater , vars rättigheter bestäms av deras befolkning. En kränkning av denna egenskap kallas befolkningsparadoxen . Det finns flera varianter av denna fastighet. En variant - det parvisa PM - tillgodoses uteslutande med divisormetoder. Det vill säga, en fördelningsmetod är parvis PM om-och-bara-om det är en divisormetod.

När och , uppfyller ingen partiell fördelningsmetod parvis-PM, lägre kvot och övre kvot. I kombination med de tidigare påståendena, innebär det att ingen divisormetod uppfyller båda kvoterna.

Husmonotonicitet innebär att när det totala antalet platser ökar, förlorar ingen agent en plats. Överträdelsen av denna egenskap kallas Alabama-paradoxen . Det ansågs särskilt viktigt i USA:s tidiga dagar, då kongressstorleken ökade vart tionde år. Hus-monotonicitet är svagare än parvis-PM. Alla rangindexmetoder (därav alla divisormetoder) är husmonotona - detta följer tydligt av den iterativa proceduren. Förutom divisormetoderna finns det andra hus-monotone metoder, och några av dem uppfyller också båda kvoterna. Till exempel uppfyller Balinskys och Youngs Quota-metoden hus-monotonicitet och övre kvot genom konstruktion, och det kan bevisas att den också uppfyller lägre kvoter. Det kan generaliseras: det finns en generell algoritm som ger alla fördelningsmetoder som både är husmonotona och uppfyller båda kvoterna. Men alla dessa kvotbaserade metoder (Quota-Jefferson, Quota-Hill, etc.) kan bryta mot parvis-PM: det finns exempel där en agent vinner i befolkning men förlorar platser.

Uniformitet (även kallad koherens ) betyder att om vi tar någon delmängd av agenterna , och tillämpar samma metod på deras kombinerade allokering , då blir resultatet vektorn . Alla rangindexmetoder (därav alla divisormetoder) är enhetliga, eftersom de tilldelar platser till agenter i en förutbestämd metod - bestäms av , och denna ordning gör det inte beror på närvaron eller frånvaron av andra medel. Dessutom måste varje enhetlig metod som också är anonym och balanserad vara en rangindexmetod.

Varje enhetlig metod som också är anonym , svagt exakt och konkordant (= innebär ) måste vara en divisormetod. Dessutom, bland alla anonyma metoder:

  • Jeffersons metod är den enda enhetliga metoden som uppfyller lägre kvoter;
  • Adams metod är den enda enhetliga metoden som uppfyller den övre kvoten;
  • Websters metod är den enda enhetliga metoden som är nära kvotering;
  • Ingen enhetlig metod uppfyller båda kvoterna. Framför allt är Hamiltons metod och Quota-metoden inte enhetliga. Kvotmetoden är dock den unika metoden som tillfredsställer både kvoter utöver husmonotonicitet och "kvotkonsistens", vilket är en svagare form av enhetlighet.

Uppmuntrande koalitioner

När agenterna är politiska partier splittras eller går de ofta samman och det är intressant att kolla hur en sådan splittring/sammanslagning påverkar fördelningen. Antag att en viss fördelningsmetod ger två agenter några respektive platser, och sedan bildar dessa två agenter en koalition, och metoden återaktiveras.

  • En fördelningsmetod uppmuntrar koalitioner om koalitionen får minst mandat (med andra ord, den är splittrad - ett parti kan inte få en plats genom att splittra) .
  • En fördelningsmetod uppmuntrar till schismer om koalitionen får högst mandat (med andra ord, den är fusionssäker - två partier kan inte få en plats genom att slå samman) .

Bland divisormetoderna:

  • Jeffersons metod är den unika divisormetoden som uppmuntrar koalitioner;
  • Adams metod är den unika divisormetoden som uppmuntrar schismer.
  • Websters metod är varken splitsäker eller fusionssäker, men den är "koalitionsneutral": när rösterna fördelas slumpmässigt är det lika troligt att en koalition vinner en plats som att förlora en plats.

Eftersom dessa är olika metoder ger ingen divisormetod varje koalition av exakt platser. Dessutom kan denna unikhet utökas till den mycket större klassen av rangindexmetoder.

En svagare egenskap, kallad "koalitionell stabilitet", är att varje koalition av bör ta emot mellan och platser; så ett parti kan få högst en mandat genom att slå samman/dela.

  • Hamiltonmetoden är koalitionsstabil.
  • En divisormetod med divisor är koalitionellt stabil iff ; detta gäller för alla fem standarddelarmetoderna.

Dessutom är varje metod som uppfyller båda kvoterna "nästan koalitionellt stabil" - den ger varje koalition mellan och platser.

Översiktstabell

Metod Lägre kvot Övre kvot Nära Quota Husets monotoni Enhetlighet Parvis

Befolkning

Monotonicitet

Uppmuntrande

koalitioner

Uppmuntrande

schismer

Koalition

neutralitet

Positiva resultat:

Divisor metoder [Endast Jefferson] [Bara Adams] [Endast Webster] Ja Ja Ja [Endast Jefferson] [Bara Adams] [Endast Webster]
Rank-index metoder [Endast Jefferson] [Bara Adams] [Endast Webster] Ja Ja [Endast divisormetoder] [Bara Jefferson?] [Bara Adams?] [Bara Webster?]
Hamilton Ja Ja Ja Nej Nej Nej ? ? ?
Kvotbegränsade delaremetoder Ja Ja Ja Ja Nej Nej ? ? ?

Omöjlighetsresultat:

- Ja Ja Ja
- Ja Ja Ja
- Ja Ja Ja Ja
- Ja Ja Ja Ja

Se även