Omröstning med fraktionerad godkännande

Bråkvalsröstning är ett valsystem som använder godkännandeomröstningar (varje väljare väljer ett eller flera kandidatalternativ), där resultatet är bråktal : för varje alternativ j finns det en bråkdel p _j mellan 0 och 1, så att summan av p _j är 1. Det kan ses som en generalisering av godkännandeomröstning : i den senare vinner en kandidat ( p _j = 1) och de andra kandidaterna förlorar ( p _j = 0). Bråken p _j kan tolkas på olika sätt, beroende på inställning. Exempel är:

• Tidsdelning : varje alternativ j implementeras en bråkdel p _j av tiden (t.ex. varje kandidat j tjänstgör en bråkdel p _j av mandatperioden).
• Budgetfördelning : varje alternativ j får en bråkdel p _j av den totala budgeten .
• Sannolikheter : efter att bråkresultaten har beräknats finns det ett lotteri för att välja en enskild kandidat, där varje kandidat j väljs med sannolikhet p _j .
• Rättigheter : de bråkdelar som används som berättigande (även kallade vikter ) i fördelningsregler , eller i algoritmer för rättvis uppdelning med olika berättigande .

Omröstning med fraktionerad godkännande är ett specialfall av fraktionerat socialt val där alla väljare har dikotoma preferenser . Det förekommer i litteraturen under många olika termer: lotteri, delning, portionering, blandning och distribution.

Formella definitioner

Det finns en ändlig uppsättning C av kandidater (även kallad: utfall eller alternativ ), och en ändlig uppsättning N av n väljare (även kallad: agenter ). Varje väljare i specificerar en delmängd A _i av C , som representerar den uppsättning kandidater som väljaren godkänner .

En röstningsregel för bråkdelsgodkännande tar som indata uppsättningen A _i och returnerar som utdata en blandning (även kallad: distribution eller lotteri ) - en vektor p av reella tal i [0,1], ett tal för varje kandidat, t.ex. att summan av siffror är 1.

Ai _Det antas att varje agent i får en nytta av 1 från varje kandidat i hans godkännandeuppsättning , och en nytta på 0 från varje kandidat som inte är _i Ai . Därför vinner agent i från varje blandning p , en nytta av $\sum _{j\in A_{i}}p_{j}$ . Till exempel, om blandningen p tolkas som en budgetfördelning, då är nyttan av i den totala budgeten som allokeras till de resultat han gillar.

Önskade egenskaper

Grundläggande egenskaper

Två grundläggande egenskaper hos röstningsregler i allmänhet, och regler för fraktionerad godkännande-röstning i synnerhet, är:

• Anonymitet – väljarnas namn spelar ingen roll;
• Neutralitet - namnen på kandidaterna spelar ingen roll;

Effektivitetsegenskaper

Pareto-effektivitet (PE) betyder att ingen blandning ger en högre användbarhet för ett medel och minst lika hög användbarhet för alla andra.

Ex-post PE är en svagare egenskap, relevant endast för tolkningen av en blandning som ett lotteri. Det betyder att, efter lotteriet, inget utfall ger en högre nytta för en agent och minst lika hög nytta för alla andra (med andra ord, det är en blandning över PE-utfall). Anta till exempel att det finns 5 kandidater (a,b,c,d,e) och 6 väljare med godkännandeset (ac, ad, ae, bc, bd, be). Att välja ut en enskild kandidat är PE, så varje lotteri är PE i efterhand. Men lotteriet som väljer c,d,e med sannolikhet 1/3 vardera är inte PE, eftersom det ger en förväntad nytta på 1/3 till varje väljare, medan lotteriet väljer a,b med sannolikhet 1/2 vardera ger en förväntad nytta av 1/2 till varje väljare.

PE innebär alltid efterhand PE. Det motsatta är också sant i följande fall:

• När det finns högst 4 väljare, eller högst 3 kandidater.
• När kandidaterna kan beställas på en rad så att varje godkännandeset är ett intervall (analogt med enstaka toppade preferenser) .

Rättvisa egenskaper

Rättvisa krav fångas upp av varianter av begreppet fair share (FS) .

Individuell - FS (även kallad Fair Welfare Share ) innebär att nyttan för varje väljare i är minst 1/ n , det vill säga minst 1/ n av budgeten tilldelas kandidater som godkänts av i .

Individual-Outcome-FS betyder att nyttan för varje väljare i är åtminstone hans nytta i ett lotteri som väljer en kandidat slumpmässigt, det vill säga minst k /| C |, där k är antalet kandidater som godkänts av i .

• Individual-FS och individual-outcome-FS är otillräckliga eftersom de ignorerar grupper av väljare. Till exempel, om 99 % av väljarna godkänner X och 1 % godkänner Y, tillåter båda fastigheterna att ge 1/2 av budgeten till X och 1/2 till Y. Detta är utan tvekan orättvist för gruppen Y-anhängare.

Single-vote-FS (även kallad trofast ) betyder att om varje väljare godkänner en enda kandidat, så är bråkdelen som tilldelas varje kandidat j lika med antalet väljare som godkänner j dividerat med n .

• Enröst-FS är ett grundkrav, men det är otillräckligt eftersom det inte säger något om fallet då väljare kan godkänna två eller flera kandidater.

Enhälligt-FS innebär att, för varje uppsättning S av väljare med identiska preferenser, nyttan för varje medlem i S är minst | S |/ n.

• Enhälligt-FS innebär en röst-FS, men det är fortfarande otillräckligt eftersom det inte säger något om grupper av agenter vars godkännande-uppsättningar överlappar varandra.

Group-FS (även kallad proportionell delning ) innebär att för varje väljaruppsättning S är den totala budgeten som tilldelas kandidater som godkänts av minst en medlem av S , minst | S |/ n.

• Grupp-FS innebär enhälligt-FS, enkelröst-FS och individuellt-FS.
• Group-FS är ekvivalent med en egenskap som kallas nedbrytbarhet : det är möjligt att dekomponera fördelningen till n fördelningar av summan 1/ n , så att fördelningen som rekommenderas till agent i är positiv endast på kandidater godkända av i .

Medel-FS innebär att, för varje väljaruppsättning S med minst en godkänd kandidat gemensam, är den genomsnittliga nyttan av väljare i S minst | S |/ n.

Core-FS betyder att det för varje väljaruppsättning S inte finns någon annan fördelning av deras | S |/ n budget, vilket ger alla medlemmar i S en högre nytta.

• Core-FS innebär Group-FS.

Strategiska egenskaper

Flera varianter av strategisäkerhet (SP) har studerats för röstningsregler:

• Individ-SP innebär att en enskild väljare, som rapporterar oriktiga preferenser, inte kan få en högre nytta.
• Svag-grupp-SP innebär att en väljargrupp, som rapporterar oriktiga preferenser i samordning, inte kan få en högre nytta för dem alla.
• Grupp-SP innebär att en väljargrupp, som rapporterar oriktiga preferenser i samordning, inte kan få högre nytta för minst en av dem och minst lika hög nytta för dem alla.
• Preferens-monotonicitet innebär att om en väljare, som tidigare inte stödde en viss kandidat X, börjar stödja X, så ökar inte de andra kandidaternas andelar. Detta innebär individuell-SP.

En svagare variant av SP är exkluderbar SP . Det är relevant i situationer där det är möjligt att utesluta väljare från att använda vissa kandidatalternativ. Om kandidaterna till exempel är mötestider, så är det möjligt att utesluta väljare från att delta i mötet på tider som de inte godkänt. Detta gör det svårare att manipulera, och därför är kravet svagare.

Deltagande fastigheter

Reglerna bör uppmuntra väljarna att delta i omröstningsprocessen. Flera deltagandekriterier har studerats:

• Svagt deltagande : nyttan av en väljare när han deltar är minst lika stor som hans nytta när han inte deltar (detta är negationen av no show-paradoxen ).
• Strikt deltagande : nyttan av en väljare när han deltar är strikt högre än hans nytta när han inte deltar. Särskilt vinner en väljare på att delta även om han har "kloner" - väljare med identiska preferenser.

En starkare egenskap krävs i deltagande budgeteringsinställningar där budgeten som ska fördelas doneras av väljarna själva:

• Poolande deltagande : nyttan av en väljare när han donerar genom mekanismen är minst lika stor som hans nytta när han donerar på egen hand.

Regler

Utilitariskt styre

Den utilitaristiska regeln syftar till att maximera summan av verktyg, och därför fördelar den hela budgeten mellan de kandidater som godkänts av det största antalet väljare. I synnerhet, om det finns en kandidat med det största antalet röster, får den här kandidaten 1 (det vill säga hela budgeten) och de andra får 0, som vid omröstning om godkännande av en vinnare . Om det finns några k kandidater med samma största antal röster, fördelas budgeten lika mellan dem, vilket ger 1/ k till varje sådan kandidat och 0 till alla andra. Den utilitaristiska regeln har flera önskvärda egenskaper: den är anonym, neutral, PE, individuell-SP och preferens-monotone. Det är också lätt att beräkna.

Det är dock inte rättvist mot minoriteter – det bryter mot Individual-FS (liksom alla starkare varianter av FS). Till exempel, om 51 % av väljarna godkänner X och 49 % av väljarna godkänner Y, så ger den utilitaristiska regeln all budget till X och ingen budget alls till Y, så de 49 % som röstar på Y får en nytta på 0. Med andra ord tillåter det majoritetens tyranni .

Den utilitaristiska regeln är inte heller svag-grupp-SP (och därmed inte grupp-SP). Anta till exempel att det finns 3 kandidater (a,b,c) och 3 väljare, var och en av dem godkänner en enda kandidat. Om de röstar uppriktigt så är den utilitaristiska blandningen (1/3,1/3,1/3) så varje agents nytta är 1/3. Om en enda väljare röstar ouppriktigt (säg, den första röstar på både a och b), så är blandningen (0,1,0), vilket är sämre för den ouppriktiga väljaren. Men om två väljare samarbetar och röstar ouppriktigt (säg att de två första väljarna röstar för de två första resultaten), så är den utilitaristiska blandningen (1/2, 1/2, 0), vilket är bättre för båda ouppriktiga väljarna.

Nash-optimal regel

Den Nash-optimala regeln maximerar summan av logaritmer för verktyg. Den är anonym och neutral och uppfyller följande ytterligare egenskaper:

• PE;
• Group-FS (nedbrytbarhet), Average-FS, Core-FS;
• Poolande deltagande (och strikt deltagande);
• Ingen annan strategisäkerhetsegenskap (misslyckas även exkluderbar-SP);

Den Nash-optimala regeln kan beräknas genom att lösa ett konvext program . Det finns en annan regel, som kallas fair utilitarian , som uppfyller liknande egenskaper (PE och group-FS) men är lättare att beräkna.

Jämlikt styre

Den egalitära (leximin) regeln maximerar den minsta nyttan, sedan den näst minsta, etc. Den är anonym och neutral och uppfyller följande ytterligare egenskaper:

• PE;
• Individuell-FS, men inte enhällig-FS;
• Exkluderbar-individ-SP, men inte individuell-SP;
• Svagt deltagande, men inte strikt deltagande (eftersom "kloner" - väljare med identiska preferenser - behandlas som en enda väljare).

Andra välfärdsregler

För varje monotont ökande funktion f kan man maximera summan av f ( u _i ). Den utilitaristiska regeln är ett specialfall där f( x )= x , och Nash-regeln är ett specialfall där f( x )=log( x ). Varje f -maximerande regel är PE och har följande ytterligare egenskaper:

• Om f är någon konkav funktion av log, garanterar det Individual-FS.
• Om-och-bara-om f är själva loggfunktionen, då garanterar den grupp-FS och enhällig-FS (detta motsvarar den Nash-optimala regeln).
• Om-och-bara-om f är en linjär funktion, så är den individuell-SP (detta motsvarar den utilitaristiska regeln).
• Om-och-bara-om det är den utilitaristiska eller den egalitära regeln, tillfredsställer den uteslutande SP;
• Om-och-bara-om det INTE är den utilitaristiska eller den jämlika regeln, tillfredsställer det strikt deltagande.

Prioritetsregler

En prioritetsregel (även kallad seriediktatur ) parametriseras av en permutation av väljarna, som representerar en prioritetsordning. Den väljer ett resultat som maximerar användbarheten för den högst prioriterade agenten; med förbehåll för det, maximerar användbarheten av agenten med näst högst prioritet; och så vidare. Varje prioritetsregel är neutral, PE, svag grupp-SP och preferens-monotone. Den är dock inte anonym och tillfredsställer inte någon rättviseuppfattning.

Regeln för slumpmässig prioritet väljer en permutation av väljarna likformigt slumpmässigt och implementerar sedan prioritetsregeln för den permutationen. Den är anonym, neutral och uppfyller följande ytterligare egenskaper:

• PE i efterhand, men inte (ex-ante) PE.
  • Med analogen av entoppade preferenser (kandidater ordnas på en rad och varje väljare godkänner ett intervall), är slumpmässig prioritet PE.
• Svag-grupp-SP.
• Grupp-FS.

En nackdel med denna regel är att det är beräkningsmässigt svårt att hitta de exakta sannolikheterna (se Diktaturmekanism#Computation ) .

Villkorligt utilitaristiskt styre

I den villkorliga utilitaristiska regeln får varje agent 1/ n av den totala budgeten . Varje agent hittar, bland de kandidater som han godkänner, de som stöds av det största antalet andra agenter och delar sin budget lika mellan dem. Den är anonym och neutral och uppfyller följande ytterligare egenskaper:

• Individuell-SP;
• Grupp-FS;
• PE i efterhand men inte (ex-ante) PE.
  • Det är mer effektivt än slumpmässigt prioriterat, både i teorin och i simuleringar.
  • Den hittar alltid en fördelning som är PE bland delmängden av grupp-FS-distributioner.

Majoritärt styre

Majoritärstyret syftar till att koncentrera så mycket makt som möjligt i händerna på få kandidater, samtidigt som det garanterar rättvisa . Det fortsätter i omgångar. Till en början är alla kandidater och väljare aktiva. I varje omgång väljer regeln en aktiv kandidat c som godkänns av den största uppsättningen aktiva väljare, N _c . Sedan "tilldelar" regeln dessa väljare N _c till c , det vill säga den antar att väljare i N _c röstade endast på c , och tilldelar c bråkdelen |N _c |/n. Sedan blir kandidaten c och väljarna i Nc _. inaktiva, och regeln går vidare till nästa omgång Observera att den betingade utilitaristiska regeln är liknande, förutom att väljarna i N _c inte blir inaktiva.

Majoritetsregeln är anonym, neutral, garanterar individ-FS och en röst-FS.

Omöjlighetsresultat

Vissa kombinationer av egenskaper kan inte uppnås samtidigt.

• Ex-post PE och grupp-SP är oförenliga (för ≥3 väljare och ≥3 kandidater).
• Anonymitet, neutralitet, ex-post PE och svag-grupp-SP är oförenliga (för ≥4 väljare och ≥6 kandidater).
  • Om vi ​​tar bort en av dessa egenskaper kan de återstående tre uppnås.
• Ex-post PE, individual-SP och individual-outcome-FS är inkompatibla (för ≥3 väljare och ≥3 kandidater).
  • Om vi ​​tar bort en av dessa egenskaper kan de återstående två uppnås.
  • Men om vi försvagar individuellt utfall-FS genom att tillåta att ge varje agent endast ε gånger hans rättvisa utfallsandel, för vissa ε >0, kvarstår omöjligheten.
• Anonymitet, neutralitet, PE, individ-SP och individ-FS är oförenliga (för ≥5 väljare och ≥17 kandidater).
  • Om vi ​​tar bort antingen PE eller individual-SP eller individual-FS, så kan de återstående fyra egenskaperna uppnås.
  • Om vi ​​tar bort anonymitet och neutralitet så gäller fortfarande omöjligheten, men är mycket svårare att bevisa.
  • I motsats till analogen av entoppade preferenser (kandidater ordnas på en rad och varje väljare godkänner ett intervall), uppnås alla egenskaper genom slumpmässig prioritet.
  • Om vi ​​försvagar individ-SP till exkluderbart-SP, tillfredsställs egenskaperna av den jämlikhetsregel.
  • Det är öppet om PE och exclusable-SP är kompatibla med strikt deltagande och/eller enhälligt-FS.
• PE, preferens-monotonicitet och positiv-andel (en egenskap som är svagare än individ-FS) är oförenliga (för ≥6 väljare och ≥6 kandidater).
• Anonymitet, neutralitet, PE, individ-SP och grupp-FS är oförenliga (för ≥5 väljare och ≥4 kandidater).
  • Om vi ​​tar bort antingen PE eller individuell-SP eller grupp-FS, så kan de återstående fyra egenskaperna uppnås.
  • Om vi ​​tar bort anonymitet och neutralitet så gäller fortfarande omöjligheten, men är mycket svårare att bevisa.
  • När det finns högst 4 väljare eller högst 3 kandidater, uppnår en enkel variant av slumpmässig diktatur alla 5 egenskaper: en diktator väljs ut slumpmässigt, och det populäraste resultatet han gillar väljs. Denna regel är anonym, neutral, ex-post PE, individual-SP, Group-FS och ex-post PE; men med högst 4 väljare eller högst 3 kandidater, innebär efterhand PE PE.
• PE, individ-SP och positiv-andel är oförenliga (för ≥6 väljare och ≥4 kandidater). Detta bevisades med hjälp av en SAT Solver som använde 386 olika profiler - förmodligen det längsta beviset i sociala val.
  • Med anonymitet och neutralitet som ytterligare egenskaper gäller inkompatibiliteten redan för ≥5 väljare och ≥4 kandidater, och bevisningen är mycket enklare.

Översiktstabell

I tabellen nedan representerar siffran i varje cell egenskapens "styrka": 0 betyder ingen (egenskapen är inte uppfylld); 1 motsvarar den svaga varianten av fastigheten; 2 motsvarar en starkare variant; etc.

	Anon.	Neut.	Effektivitet	Rättvis andel	Strategisäkerhet	Deltagande	Monotonicitet	Beräkning
	0=nej 1 = ja	0=nej 1 = ja	0=ingen 1=ex-post 2=ex ante	0=ingen 0,5=positiv 1=individ 2=enhälligt 3=grupp 4=kärna	0=ingen 1=exkluderas 2=individ 3=svag grupp 4=grupp	0=ingen 1=svag 2 = strikt 3=poolning	0=ingen 1=preferens
Regler
Utilitarist:	1	1	2	0	2	1	1	Polynom
Jämlikhetskämpe:	1	1	2	1	1	1	0	Polynom
Nash:	1	1	2	4 (+genomsnitt)	0	3	0	?
Prioritet:	0	1	2	0	3	1	1	Polynom
Slumpmässig prioritet:	1	1	1	3	3	2 (3?)	0	NP-Hård
Rättvis utilitaristisk:	1	1	2	3	0	1 (2? 3?)	0	Polynom
Villkorlig- utilitarist	1	1	1	3	2 (3?)	2 (3?)	1	Polynom
Majoritär:	1	1	?	1 (2? 3?)	?	?	?	Polynom
Sekvens- utilitarist:	1	1	2	1?	0?	0?	1	Polynom
Omöjliga kombinationer
n≥3, c≥3:			1		4
n≥4, c≥6	1	1	1		3
n≥3, c≥3:			1	1[utfall]	2
n≥5, c≥17:	1	1	2	2	2
n≥6, c≥6:			2	0,5			1
n≥6, c≥4:			2	0,5	2
n≥5, c≥4:	1	1	2	3	2
Öppna kombinationer
			2	2	1
			2		1	2

Se även

• Berättigad representation - en egenskap som liknar fair-share, men för diskreta resultat.
• Omröstning om partigodkännande - kandidaterna är partier, och den bråkdel som tilldelas varje parti motsvarar den bråkdel av mandat det borde få i parlamentet.
• Deltagande budgeteringsalgoritmer - andra tillvägagångssätt för att fördela en budget rättvist.
• Vissa författare studerade priset för rättvisa för olika distributionsregler.
• Distributionsproblemet har studerats även i den mer utmanande miljön där agenter har tillsatsverktyg .