Mechanizm dyktatury

W teorii wyboru społecznego mechanizm dyktatury jest regułą, zgodnie z którą spośród wszystkich możliwych alternatyw wyniki głosowania odzwierciedlają preferencje jednej z góry określonej osoby, bez uwzględnienia innych wyborców. Dyktatura sama w sobie nie jest uważana za dobry mechanizm w praktyce, ale jest teoretycznie ważna: zgodnie z twierdzeniem Arrowa o niemożliwości , gdy istnieją co najmniej trzy alternatywy, dyktatura jest jedynym systemem głosowania rankingowego , który spełnia nieograniczoną domenę , efektywność Pareto i niezależność nieistotne alternatywy . Podobnie, zgodnie z twierdzeniem Gibbarda , gdy istnieją co najmniej trzy alternatywy, dyktatura jest jedyną zasadą uzasadnioną strategią .

Brak dyktatury jest właściwością bardziej powszechnych zasad głosowania , w których na wyniki wpływają preferencje wszystkich jednostek. Ta właściwość jest spełniona, jeśli nie ma jednego wyborcy i z indywidualnym porządkiem preferencji P, tak że P jest zawsze społecznym („zwycięskim”) porządkiem preferencji. Innymi słowy, preferencje jednostki nie zawsze powinny przeważać. Anonimowe systemy głosowania (z co najmniej dwoma wyborcami) automatycznie spełniają własność niedyktatury.

Zasada dyktatury ma warianty, które są przydatne w praktyce: dyktatura seryjna , dyktatura losowa i dyktatura losowa szeregowa (patrz poniżej).

Definicja formalna

Brak dyktatury jest jednym z warunków koniecznych twierdzenia Arrowa o niemożliwości . W książce Social Choice and Individual Values Kenneth Arrow definiuje brak dyktatury jako:

Nie ma wyborcy i w { 1 , ..., n } takiego, że dla każdego zestawu porządków w dziedzinie konstytucji i każdej pary stanów społecznych x i y , x ${\ Displaystyle P_ {i} }$ y implikuje x P y .

Naturalnie, dyktatura jest regułą, która nie zadowala nie-dyktatury.

Seryjna dyktatura

Mechanizm dyktatury jest dobrze zdefiniowany tylko wtedy, gdy dyktator ma jedną preferowaną opcję. Kiedy dyktator jest obojętny na dwie lub więcej preferowanych opcji, możliwe jest wybranie jednej z nich arbitralnie/losowo, ale nie będzie to efektywne w sensie Pareto . Bardziej efektywnym rozwiązaniem jest wyznaczenie drugiego dyktatora, który ma prawo wybrać, spośród wszystkich najlepszych opcji pierwszego dyktatora, tę, którą on najbardziej preferuje. Jeśli drugi dyktator jest również obojętny na dwie lub więcej opcji, wybiera spośród nich trzeci dyktator i tak dalej. Ta zasada nazywa się dyktaturą seryjną . Inna nazwa to mechanizm priorytetowy .

Mechanizm pierwszeństwa jest często stosowany w problemach przydziału domów . Na przykład, przydzielając studentom pokoje w akademiku, często ustala się kolejność studentów według z góry określonej kolejności (np. według wieku, klas, odległości itp.) i pozwala każdemu z nich po kolei wybrać najbardziej preferowane pokoje z dostępne.

Przypadkowa dyktatura i przypadkowa dyktatura szeregowa

Rządy dyktatury są oczywiście niesprawiedliwe, ale mają wariant, który jest sprawiedliwy w oczekiwaniach. W losowej dyktatury (RD) jeden z wyborców jest wybierany jednolicie losowo i wybierana jest alternatywa najbardziej preferowana przez tego wyborcę. Jest to jedna z powszechnych zasad losowego wyboru społecznego . Kiedy jest używany w organach wielookręgowych, jest czasami nazywany głosowaniem losowym .

Podobnie jak dyktatura, także przypadkowa dyktatura powinna uwzględniać możliwość obojętności; powszechnym rozwiązaniem jest rozszerzenie go na losową dyktaturę szeregową (RSD), zwaną także losowym priorytetem . W mechanizmie tym losowa permutacja wyborców, a każdy głosujący po kolei zawęża istniejące alternatywy do tych, które najbardziej mu odpowiadają, spośród tych, które są jeszcze dostępne. Jest to powszechny mechanizm przydzielania niepodzielnych obiektów między agentów; zobacz losowy przydział elementów priorytetowych .

Nieruchomości

Allan Gibbard udowodnił twierdzenie o przypadkowej dyktaturze . Mówi, że gdy preferencje są ścisłe, RD jest jedyną regułą, która spełnia następujące trzy właściwości:

Anonimowość: loteria nie dyskryminuje z góry różnych wyborców.
Silna odporność na strategię SD: każdy fałszywy raport agenta skutkuje wynikiem, który jest słabo zdominowany stochastycznie .
Efektywność Pareto ex post: wynik jest efektywny Pareto.
- W rzeczywistości, przy ścisłych preferencjach, RD spełnia silniejszą właściwość wydajności zwaną wydajnością SD : wynikowa loteria nie jest zdominowana stochastycznie. Przy słabych preferencjach RSD spełnia efektywność ex-post, ale narusza efektywność SD.
- Nawet przy ścisłych preferencjach RD narusza silniejszą właściwość zwaną wydajnością PC: wynikowa loteria może być zdominowana w sensie porównań parami (dla każdego agenta prawdopodobieństwo, że inna loteria daje lepszą alternatywę niż loteria RD jest większe niż inna droga naokoło).

RD spełnia również właściwość zwaną spójnością programu. Jest to jedyna reguła spełniająca następujące własności:

Silna spójność skurczu („regularność”): prawdopodobieństwa nie mogą się zmniejszyć po usunięciu dowolnych alternatyw.
Efektywność ex-post.
Probabilistyczna wersja niezależności nieistotnych alternatyw .

Późniejsze badania dostarczyły alternatywnych dowodów, a także różnych rozszerzeń. Jeden wynik niemożliwości dotyczy rozszerzenia twierdzenia na słabe preferencje. Mówi, że przy słabych preferencjach właściwości anonimowości, efektywności SD i odporności na strategię SD są niekompatybilne, gdy istnieje co najmniej 4 agentów i 4 alternatywy. Dowód został wyprowadzony przy użyciu solvera SMT i zweryfikowany przez interaktywny program do udowadniania twierdzeń Isabelle/HOL .

RD spełnia aksjomat zwany spójnością populacji i aksjomat zwany spójnością klonowania , ale narusza spójność składu .

Obliczenie

W praktyce łatwo jest wdrożyć zarówno mechanizmy RD, jak i RSD: wystarczy wybrać losowego wyborcę lub losową permutację i pozwolić każdemu dyktatorowi po kolei wybrać najlepszą opcję. Czasami jednak chce się z góry obliczyć, jakie jest prawdopodobieństwo, że wybrano by określoną alternatywę. W przypadku RD (gdy preferencje są ścisłe) jest to również łatwe: prawdopodobieństwo wybrania alternatywy x równa się liczbie wyborców, którzy zajmują x pierwsze miejsce, podzielonej przez całkowitą liczbę wyborców. Ale sytuacja jest inna w przypadku RSD (gdy występują obojętności):

Obliczanie prawdopodobieństw jest #P -trudne;
Istnieje wydajny algorytm obliczania wsparcia (alternatywy wybrane z dodatnim prawdopodobieństwem);
Istnieją algorytmy o możliwej do opanowania złożoności sparametryzowanej , gdzie parametrami są: liczba obiektów, liczba alternatyw i liczba typów wyborców.
Istnieje algorytm czasu wykładniczego do obliczania prawdopodobieństw w kontekście ułamkowego głosowania zatwierdzającego .

^ Teoria gier wydanie drugie Guillermo Owen Ch 6 pp124-5 Axiom 5 Academic Press, 1982 ISBN 0-12-531150-8
^ ^a ^b ^c Felix Brandt (2017-10-26). „Probabilistyczny wybór społeczny” . W Endriss, Ulle (red.). Trendy w obliczeniowym wyborze społecznym . Lulu.com. ISBN 978-1-326-91209-3 .
^ Gibbard Allan (1977). „Manipulowanie schematami, które łączą głosowanie z szansą” . Ekonometria . 45 (3): 665–681. doi : 10.2307/1911681 . ISSN 0012-9682 . JSTOR 1911681 .
^ Pattanaik, Prasanta K.; Peleg, Becalel (1986). „Dystrybucja władzy zgodnie ze stochastycznymi regułami wyboru społecznego” . Ekonometria . 54 (4): 909–921. doi : 10.2307/1912843 . ISSN 0012-9682 . JSTOR 1912843 .
^ Brandl, Florian; Brandt, Feliks; Eberl, Manuel; Geist, chrześcijanin (2018-01-31). „Udowodnienie niezgodności wydajności i odporności na strategię poprzez rozwiązanie SMT” . Dziennik ACM . 65 (2): 6:1-6:28. ar Xiv : 1604.05692 . doi : 10.1145/3125642 . ISSN 0004-5411 . S2CID 1135734 .
^ ^a ^b Aziz, Haris; Brandt, Feliks; Brill, Markus (2013-12-01). „Złożoność obliczeniowa losowej dyktatury szeregowej” . Listy ekonomiczne . 121 (3): 341–345. ar Xiv : 1304.3169 . doi : 10.1016/j.econlet.2013.09.006 . ISSN 0165-1765 . S2CID 14384249 .
Bibliografia _ Mestre, Julián (2014-11-01). „Sparametryzowane algorytmy dla losowej dyktatury szeregowej” . Matematyczne nauki społeczne . 72 : 1–6. ar Xiv : 1403.0974 . doi : 10.1016/j.mathsocsci.2014.07.002 . ISSN 0165-4896 . S2CID 6719832 .
^ Bogomolnaja, Anna; Moulin, Hervé; Stong, Richard (2005-06-01). „Zbiorowy wybór w ramach dychotomicznych preferencji” . Dziennik teorii ekonomii . 122 (2): 165–184. doi : 10.1016/j.jet.2004.05.005 . ISSN 0022-0531 .

[1] Teoria gier wydanie drugie Guillermo Owen Ch 6 pp124-5 Axiom 5 Academic Press, 1982 ISBN 0-12-531150-8

[:0-2] Felix Brandt (2017-10-26). „Probabilistyczny wybór społeczny” . W Endriss, Ulle (red.). Trendy w obliczeniowym wyborze społecznym . Lulu.com. ISBN 978-1-326-91209-3 .

[3] Gibbard Allan (1977). „Manipulowanie schematami, które łączą głosowanie z szansą” . Ekonometria . 45 (3): 665–681. doi : 10.2307/1911681 . ISSN 0012-9682 . JSTOR 1911681 .

[4] Pattanaik, Prasanta K.; Peleg, Becalel (1986). „Dystrybucja władzy zgodnie ze stochastycznymi regułami wyboru społecznego” . Ekonometria . 54 (4): 909–921. doi : 10.2307/1912843 . ISSN 0012-9682 . JSTOR 1912843 .

[5] Brandl, Florian; Brandt, Feliks; Eberl, Manuel; Geist, chrześcijanin (2018-01-31). „Udowodnienie niezgodności wydajności i odporności na strategię poprzez rozwiązanie SMT” . Dziennik ACM . 65 (2): 6:1-6:28. ar Xiv : 1604.05692 . doi : 10.1145/3125642 . ISSN 0004-5411 . S2CID 1135734 .

[:1-6] Aziz, Haris; Brandt, Feliks; Brill, Markus (2013-12-01). „Złożoność obliczeniowa losowej dyktatury szeregowej” . Listy ekonomiczne . 121 (3): 341–345. ar Xiv : 1304.3169 . doi : 10.1016/j.econlet.2013.09.006 . ISSN 0165-1765 . S2CID 14384249 .

[7] Bibliografia _ Mestre, Julián (2014-11-01). „Sparametryzowane algorytmy dla losowej dyktatury szeregowej” . Matematyczne nauki społeczne . 72 : 1–6. ar Xiv : 1403.0974 . doi : 10.1016/j.mathsocsci.2014.07.002 . ISSN 0165-4896 . S2CID 6719832 .

[:02-8] Bogomolnaja, Anna; Moulin, Hervé; Stong, Richard (2005-06-01). „Zbiorowy wybór w ramach dychotomicznych preferencji” . Dziennik teorii ekonomii . 122 (2): 165–184. doi : 10.1016/j.jet.2004.05.005 . ISSN 0022-0531 .