Fundacja Wolność i Pokój

Centrum Informacji

Głosowanie a matematyka

Voting

(Znalezione na Wykopie, niestety nie skopiowałem nicka autora, za co serdecznie Go przepraszam. Wiesław Cupała )

Mamy dzisiaj wybory, więc o polityce ani słowa. Ale to doskonała okazja, żeby pokrótce powiedzieć, co na temat wyborów i sposobu głosowania ma do powiedzenia matematyka. Nie martwcie się, nie będę Was zamęczał dowodami ani zbytecznymi znaczkami, postaram skupić się na sednie sprawy. 🙂

Wybrałem kilka znanych twierdzeń/paradoksów, które doskonale pokazują, że stworzenie dobrego (co to w ogóle znaczy?) systemu głosowania jest wysoce nietrywialnym zadaniem. Pojawia się wiele problemów, z których istnienia większość ludzi nawet nie zdaje sobie sprawy.

1. Paradoks Condorceta, czyli o tym, że z sensownych poglądów jednostek nie wypływa sensowne zdanie grupy.

Załóżmy, że w wyborach startuje iluś kandydatów, a każdy wyborca ustawia ich zgodnie z własnym zdaniem od najlepszego do najgorszego. Na przykład: niech kandydaci to A, B, C, D. Wtedy np. jeden wyborca mówi: moje preferencje to: C>A>B>D; inny wyborca mówi natomiast: a moje to B>A>C>D.

„Głosem” wyborcy jest właśnie takie uszeregowanie wszystkich kandydatów. Więc wyborcy oddają głosy tej postaci i chcemy na ich podstawie wybrać najlepszego kandydata. Gdzie tkwi problem?

W tym, że z sensownych poglądów jednostek nie wynikają sensowne poglądy grupy. Wiadomo, że pojedyncza osoba nie powie np. czegoś takiego: moje preferencje to A > B > C > A. Nie można preferować kandydata nad nim samym, to jest bez sensu.

A o jakich preferencjach powinniśmy mówić w przypadku grupy? Rozwiązanie jest następujące: chcemy móc powiedzieć: większość grupy preferuje kandydata X nad kandydatem Y. Problem w tym, że – jak się okazuje – tutaj preferencje już mogą się zapętlać. Czyli możemy mieć taką sytuację, jaką w poprzednim akapicie nazwaliśmy bezsensowną.

Formalnie rzecz biorąc mówimy, że relacja „większość preferuje X nad Y” nie jest przechodnia. Czyli z tego, że X>Y i Y>Z nie wynika, że X>Z.

Najłatwiej to zrozumieć na prostym przykładzie. Mamy 3 kandydatów (A,B,C) i 3 wyborców (1,2,3). Ich preferencje są następujące:

  1. A > B > C
  2. B > C > A
  3. C > A > B

Łatwo policzyć, że 2/3 wyborców (czyli większość) uważa, że A jest lepszy niż B, 2/3 wyborców, że B jest lepszy niż C i wreszcie 2/3 wyborców, że C jest lepszy niż A. Czyli zdaniem większości: A > B > C > A. Bez sensu.

Dupa. 🙂

2. Paradoks Alabamy, czyli o tym, że większy Parlament nie przekłada się na lepsze odwzorowanie społeczeństwa.

W USA każdy stan dostaje w ichnim Parlamencie liczbę miejsc proporcjonalną do wielkości populacji tego stanu. Ponadto wielkość Parlamentu zależy od wielu czynników i sumaryczna liczba dostępnych miejsc może się łatwo zmienić. Więc przy każdej zmianie wielkości Parlamentu należy przeliczyć liczbę miejsc zarezerwowaną dla każdego stanu.

Czego byśmy oczekiwali przy takiej zmianie? Na przykład tego, że przy zwiększeniu Parlamentu liczba miejsc żadnego stanu nie zmniejszy się. Całkiem naturalne założenie. Problem w tym, że niekoniecznie łatwe do zrealizowania w praktyce. 🙂

Jak można się domyślić po nazwie paradoksu, po raz pierwszy ten problem zauważono na przykładzie Alabamy. W 1880 r. zastanawiano się, jaka powinna być wielkość Parlamentu. W szczególności przeliczono podział miejsc dla Parlamentu wielkości 299 i 300. Okazało się, że w Parlamencie 299-osobowym Alabama ma 8 miejsc, natomiast w Parlamencie 300-osobowym… tylko 7.

Znów: najłatwiej ten problem zobrazować na przykładzie. Załóżmy, że mamy trzy stany: A, B, C. Populacja A i B to 6 osób, a populacja C to 2 osoby. Przyjmijmy też, że w Parlamencie jest 10 miejsc. Liczymy „sprawiedliwy” udział każdego stanu z prostej proporcji:

W ten sposób dochodzimy do wniosku, że udział stanów A i B to 4.29, a stanu C to 1.43. Co (bez wchodzenia w szczegóły) przekłada się na odpowiednio 4, 4, i 2 miejsca w Parlamencie.

A co się stanie, gdy zwiększymy Parlament do 11 miejsc? Licząc jak poprzednio, wyjdzie nam, że sprawiedliwy udział stanów A i B to 4.71, a stanu C to 1.57. To przekłada się odpowiednio na liczbę miejsc: 5, 5, 1. Zatem Parlament jest większy, a mimo to stan C stracił jedno miejsce.

Dupa. 🙂

3. Twierdzenie Arrowa, czyli o tym, że nie istnieje dobry system głosowania.

Wyobraźmy sobie, że projektujemy wybory. Niezależnie od szczegółów chcielibyśmy, żeby procedura głosowania spełniała pewne bardzo naturalne założenia:

  1. Uniwersalność – wybór kandydata zależy wyłącznie od preferencji wyborców. Mówiąc inaczej: preferencje wyborców ściśle determinują konkretny wybór. Nie ma miejsca na losowość, a przy takich samych preferencjach wyborców wynik zawsze powinien być ten sam.
  2. Suwerenność – każdy kandydat powinien móc być wybrany, jeśli preferencje wyborców odpowiednio się ułożą. Mówiąc inaczej: nie ma kandydata z zasady niewybieralnego.
  3. Brak dyktatora – wynik głosowania zależy od woli co najmniej dwóch wyborców, tzn. zdanie jednego wyborcy nie może zdeterminować wyniku całego głosowania.
  4. Monotoniczność – jeśli jakiś wyborca preferował kandydata X nad kandydatem Y (X>Y) i zmienił zdanie (czyli teraz Y>X), to ta zmiana nie może zmniejszyć szans kandydata Y. Innymi słowy, jeśli Y nagle u kogoś awansował, to jego szansa na wygraną powinna się zwiększyć lub pozostać bez zmian.
  5. Niezależność nieistotnych alternatyw – to jest trochę bardziej zagmatwane i martwcie się, jeśli nie zrozumienie definicji; najłatwiej to zrozumieć na przykładzie, który jest poniżej. Definicja jest następująca: jeśli ograniczymy się do dowolnego podzbioru kandydatów, to ich względna kolejność w wyniku musi pozostać taka sama jak w pełnym zbiorze.

Przykład do punktu e): załóżmy, że nasi kandydaci to A, B, C, D, E, a wynikiem glosowania okazała się (w jakiś sposób – nieważne jaki) kolejność C > D > E > A > B. Wtedy względna kolejność np. kandydatów C > A > B musi zostać taka sama niezależnie od tego jak zmieniałyby się preferencje dla D i E.

Po tym przydługim wstępie możemy przejść do treści twierdzenia Arrowa. Która jest bardzo krótka:

 

Nie istnieje żadna procedura głosowania, która by jednocześnie spełniała wszystkie warunki a-e.

Dupa. 🙂

4. Twierdzenia Gibbarda-Satterthwaite’a, czyli o tym, że wciąż nie istnieje dobry system głosowania.

O tym, czym jest suwerenność i brak dyktatora pisałem wyżej. Teraz wprowadzimy pojęcie głosowania taktycznego.

Co to jest? Ano, po prostu manipulacja :). Załóżmy, że znamy preferencje wszystkich pozostałych wyborców (zdefiniowane jak wyżej, czyli uszeregowanie wszystkich kandydatów od najlepszego do najgorszego). Wtedy mówimy, że głosowanie można zmanipulować (lub „zagłosować taktycznie” :P), jeśli zafałszowując swoje preferencje możemy doprowadzić do zwycięstwa osoby, którą cenimy. Innymi słowy, celowo kłamiemy w głosowaniu, żeby jego ostateczny wynik był zgodny z naszymi prawdziwymi preferencjami.

Jak pewnie już się domyślacie, twierdzenie Gibbarda-Satterthwaite’a orzeka, iż:

Każdy system głosowania spełnia co najmniej jeden z poniższych warunków:

  1. ma dyktatora,
  2. nie ma własności suwerenności,
  3. można go zmanipulować.

Dupa. 🙂

Uwaga dla informatyków: jednym z kierunków badawczych w Obliczeniowej Teorii Wyboru Społecznego jest projektowanie takich systemów głosowania, którymi teoretycznie da się manipulować, ale w praktyce byłoby to bardzo wymagające obliczeniowo, np. NP-zupełne lub jeszcze gorzej. Wtedy możemy zrezygnować z warunku c) na rzecz warunków a) i b), ale w zastosowaniach praktycznych warunek c) i tak będzie spełniony, pomimo że w teorii dany system głosowania nie ma tej własności.

5. Hrabstwo Nassau, Nowy Jork, czyli o tym, że politycy niekoniecznie znają się na matematyce, a powinni.

To jest autentyczny przykład. W radzie hrabstwa Nassau jest 30 miejsc, a do przegłosowania ustawy potrzeba 16 głosów (czyli 50% + 1). Poszczególne części hrabstwa (nie wiem, jak to się nazywa – dzielnice?) mają następujące liczby miejsc w radzie:

  • Hempstead 1: 9 miejsc,
  • Hempstead 2: 9 miejsc,
  • North Hempstead: 7 miejsc,
  • Oyster Bay: 3 miejsca,
  • Glen Cove: 1 miejsce,
  • Long Beach: 1 miejsce.

Czy widzicie w tych liczbach coś niepokojącego? Dupa? 🙂

Owszem, dupa :). Ale pytanie dla Was: dlaczego?

Wniosek

A na poważnie: oczywiście matematyka to tylko matematyka i teoria nie w każdym przypadku dokładnie przekłada się na prawdziwe życie. Np. trudno mówić o możliwości zmanipulowania wyników głosowania na prezydenta w sensie twierdzenia GS, bo skąd mielibyśmy znać preferencje wszystkich głosujących Polaków? Ale już w mniejszych grupach (np. wybory do samorządu studenckiego) można mieć wątpliwości, czy takie coś byłoby niemożliwe.

W każdym razie chciałbym, żebyście z tego tekstu wyciągnęli następujący wniosek: nawet za tak (zdawałoby się) prostymi kwestiami jak głosowanie stoją poważne matematyczne teorie ujawniające poważne problemy, które czasami są po prostu nie do przeskoczenia.”

Advertisements

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

Information

This entry was posted on 3 Czerwiec 2015 by in Co piszą inni..., Społeczeństwo and tagged .

Zasady kopiowania z witryny FWiP

Wszelkie materiały publikowane w Centrum Informacji FWiP publikowane są na zasadach licencji Creative Commons 3.0 BY-NC (Uznanie Autorstwa - Użycie Niekomercyjne) chyba, że jest zaznaczone inaczej.

Odpowiedzialność za treść artykułów

Artykuły są wyrazem poglądów ich Autorów. Za treść przedruków, ogłoszeń itp., jeśli nie jest zaznaczone inaczej, odpowiada redaktor odpowiedzialny. Dokumenty i stanowisko Fundacji Wolność i Pokój muszą być sygnowane przez władze Fundacji zgodnie z jej Statutem

Kontakt z redakcją witryny FWiP

%d bloggers like this: