Diktaturmekanism
I teorin om sociala val är en diktaturmekanism en regel där, bland alla möjliga alternativ, resultatet av omröstningen speglar en enda förutbestämd persons preferenser, utan hänsyn till de andra väljarna. Diktatur i sig anses inte vara en bra mekanism i praktiken, men den är teoretiskt viktig: enligt Arrows omöjlighetsteorem , när det finns minst tre alternativ, är diktatur det enda rangordnade röstningsvalsystemet som tillfredsställer obegränsad domän , Pareto effektivitet och oberoende. irrelevanta alternativ . På liknande sätt, enligt Gibbards teorem , när det finns minst tre alternativ, är diktatur den enda strategisäkra regeln.
Icke-diktatur är en egenskap hos vanligare röstregler , där resultaten påverkas av alla individers preferenser. Denna egenskap är uppfylld om det inte finns någon enskild väljare i med den individuella preferensordningen P, så att P alltid är den samhälleliga ("vinnande") preferensordningen. Med andra ord, preferenserna för individuella i bör inte alltid råda. Anonyma röstsystem (med minst två väljare) tillgodoser automatiskt icke-diktaturens egendom.
Diktaturregeln har varianter som är användbara i praktiken: seriediktatur , slumpmässig diktatur och slumpmässig seriediktatur (se nedan).
Formell definition
Icke-diktatur är ett av de nödvändiga villkoren i Arrows omöjlighetsteorem . I Social Choice and Individual Values definierar Kenneth Arrow icke-diktatur som:
- Det finns ingen väljare i i { 1 , ..., n } så att, för varje uppsättning av ordningsföljder inom konstitutionens domän, och varje par av sociala tillstånd x och y , x y innebär x P y .
Naturligtvis är diktatur en regel som inte tillfredsställer icke-diktatur.
Seriediktatur
En diktaturmekanism är väldefinierad endast när diktatorn har ett enda bäst föredragna alternativ. När diktatorn är likgiltig mellan två eller flera bäst föredragna alternativ är det möjligt att välja ett av dem godtyckligt/slumpmässigt, men detta kommer inte att vara Pareto-effektivt . En mer effektiv lösning är att utse en andra diktator, som har rätt att, bland alla den första diktatorns bästa alternativ, välja den som de mest föredrar. Om den andra diktatorn också är likgiltig mellan två eller flera alternativ, så väljer en tredje diktator bland dem, och så vidare. Denna regel kallas seriediktatur . Ett annat namn för det är prioritetsmekanism .
Prioritetsmekanismen används ofta i problem med husfördelning . Vid tilldelning av studentrum är det till exempel vanligt att man beställer eleverna efter en förutbestämd prioriteringsordning (t.ex. efter ålder, betyg, avstånd etc.), och låter var och en av dem i sin tur välja sina mest föredragna rum från de tillgängliga.
Slumpmässig diktatur och slumpmässig seriediktatur
Diktaturregeln är uppenbarligen orättvis, men den har en variant som är rimlig i förväntan. I slumpmässig diktatur (RD) väljs en av väljarna likformigt slumpmässigt, och det alternativ som väljs mest föredraget av den väljaren. Detta är en av de vanliga reglerna för slumpmässiga sociala val . När det används i organ med flera valkretsar kallas det ibland slumpmässig omröstning .
På samma sätt som diktatur bör även slumpmässig diktatur hantera möjligheten till likgiltighet; den vanliga lösningen är att utöka den till slumpmässig seriediktatur (RSD), även kallad slumpmässig prioritet . I denna mekanism väljs en slumpmässig permutation av väljarna, och varje väljare begränsar i sin tur de befintliga alternativen till de de mest föredrar, från de som fortfarande finns tillgängliga. Det är en vanlig mekanism för att fördela odelbara objekt mellan agenter; se slumpmässig prioritetsfördelning .
Egenskaper
Allan Gibbard bevisade slumpmässig diktatursats . Det står att när preferenser är strikta är RD den enda regeln som uppfyller följande tre egenskaper:
- Anonymitet: lotteriet gör inte skillnad på förhand mellan olika väljare.
- Stark SD-strategisäkerhet: varje falsk rapport från en agent resulterar i ett resultat som är svagt stokastiskt dominerat .
- Ex-post Pareto-effektivitet: resultatet är Pareto-effektivt.
- Faktum är att med strikta preferenser, uppfyller RD en starkare effektivitetsegenskap som kallas SD-effektivitet : det resulterande lotteriet domineras inte stokastiskt. Med svaga preferenser tillfredsställer RSD effektivitet i efterhand, men bryter mot SD-effektivitet.
- Även med strikta preferenser bryter RD mot den starkare egenskapen som kallas PC-effektivitet: det resulterande lotteriet kan domineras i betydelsen parvisa jämförelser (för varje agent är sannolikheten att ett annat lotteri ger ett bättre alternativ än RD-lotteriet större än tvärtom).
RD uppfyller också en egenskap som kallas agendakonsistens. Det är den enda regeln som uppfyller följande egenskaper:
- Stark kontraktionskonsistens ("regelbundenhet"): sannolikheter kan inte minska när godtyckliga alternativ tas bort.
- Effektivitet i efterhand.
- En probabilistisk version av Oberoende av irrelevanta alternativ .
Efterföljande forskning har gett alternativa bevis, såväl som olika förlängningar. Ett omöjlighetsresultat är att utvidga satsen till svaga preferenser. Den säger att, med svaga preferenser, egenskaperna anonymitet, SD-effektivitet och SD-strategisäkerhet är oförenliga när det finns minst 4 agenter och 4 alternativ. Beviset härleddes med hjälp av en SMT-lösare och verifierades av en interaktiv teorembevisare Isabelle/HOL .
RD uppfyller ett axiom som kallas populationskonsistens och ett axiom som kallas kloning-konsistens , men bryter mot sammansättningens konsistens .
Beräkning
Det är lätt att implementera både RD- och RSD-mekanismerna i praktiken: välj bara en slumpmässig väljare, eller en slumpmässig permutation, och låt varje diktator i sin tur välja det bästa alternativet. Men ibland vill man i förväg räkna ut vad är sannolikheten för att ett visst alternativ skulle väljas. Med RD (när preferenserna är strikta) är detta lätt också: sannolikheten för att alternativ x väljs är lika med antalet väljare som rankar x först, dividerat med det totala antalet väljare. Men situationen är annorlunda med RSD (när det finns likgiltigheter):
- Att beräkna sannolikheterna är #P -svårt;
- Det finns en effektiv algoritm för att beräkna stödet (de alternativ som väljs med positiv sannolikhet);
- Det finns algoritmer med hanteringsbar parametriserad komplexitet , där parametrarna är: antal objekt, antal alternativ och antal väljartyper.
- Det finns en exponentiell-tidsalgoritm för att beräkna sannolikheterna i samband med röstning av fraktionerad godkännande .
- ^ Game Theory Second Edition Guillermo Owen Ch 6 pp124-5 Axiom 5 Academic Press, 1982 ISBN 0-12-531150-8
- ^ a b c Felix Brandt (2017-10-26). "Probabilistiskt socialt val" . I Endriss, Ulle (red.). Trender i Computational Social Choice . Lulu.com. ISBN 978-1-326-91209-3 .
- ^ Gibbard, Allan (1977). "Manipulation av system som blandar röstning med chans" . Econometrica . 45 (3): 665–681. doi : 10.2307/1911681 . ISSN 0012-9682 . JSTOR 1911681 .
- ^ Pattanaik, Prasanta K.; Peleg, Bezalel (1986). "Maktfördelning under stokastiska sociala valregler" . Econometrica . 54 (4): 909–921. doi : 10.2307/1912843 . ISSN 0012-9682 . JSTOR 1912843 .
- ^ Brandl, Florian; Brandt, Felix; Eberl, Manuel; Geist, Christian (2018-01-31). "Bevisa inkompatibiliteten av effektivitet och strategisäkerhet via SMT-lösning" . Journal of the ACM . 65 (2): 6:1–6:28. arXiv : 1604.05692 . doi : 10.1145/3125642 . ISSN 0004-5411 . S2CID 1135734 .
- ^ a b Aziz, Haris; Brandt, Felix; Brill, Markus (2013-12-01). "Den slumpmässiga seriediktaturens beräkningskomplexitet" . Ekonomibrev . 121 (3): 341–345. arXiv : 1304.3169 . doi : 10.1016/j.econlet.2013.09.006 . ISSN 0165-1765 . S2CID 14384249 .
- ^ Aziz, Haris; Mestre, Julián (2014-11-01). "Parametriserade algoritmer för slumpmässig seriediktatur" . Matematisk samhällsvetenskap . 72 : 1–6. arXiv : 1403.0974 . doi : 10.1016/j.mathsocsci.2014.07.002 . ISSN 0165-4896 . S2CID 6719832 .
- ^ Bogomolnaia, Anna; Moulin, Hervé; Stong, Richard (2005-06-01). "Kollektivt val under dikotoma preferenser" . Journal of Economic Theory . 122 (2): 165–184. doi : 10.1016/j.jet.2004.05.005 . ISSN 0022-0531 .