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:
6 (2) - x
14 - 10
(Bo całkowita populacja to 14 osób, a liczba miejsc w Parlamencie to 10).
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:
a)
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.
b)
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.
c)
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.
d)
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.
e)
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:
a) ma dyktatora
b) nie ma własności suwerenności
c) można go zmanipulować
Dupa. :)
pokaż spoiler 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? :)
pokaż spoiler 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.
Komentarze (65)
najlepsze
Jakiś dowodzik?
Na poważnie, większość z tego można skrócić następująco: nie można zadowolić wszystkich.
W każdym razie, jest wiele dowodów tego twierdzenia, są w Internecie. Ja korzystałem z książki A Primer in Social Choice Theory, tam są 3 dowody twierdzenia Arrowa i dowód twierdzenia Gibbarda-Satterthwaite'a. Nie są jakieś szczególnie trudne,
nie bardzo rozumiem co jest nie tak w ostatnim.
Wyobraź sobie, że np. jest głosowanie nad podziałem budżetu między dzielnice. Można się spodziewać, że wszyscy radni z danej dzielnicy będą głosować w ten sam sposób, na korzyść swojej dzielnicy (a nie np. zgodnie z podziałami partyjnymi).
Czyli tak naprawdę mamy coś takiego: jest 6 wyborców (dzielnice), którzy mają różną siłę
Ale jeszcze jest drugi wniosek: dzielnica z 7 głosami jest tak samo ważna jak
Może teza powinna być inna?
W podanym przykładzie 11 osobowy parlament lepiej odwzorowuje społeczeństwo niż 10 osobowy.
Czy mógłby ktoś wytłumaczyć innymi słowami? Jak to działa?
Absolutnie najprostszy przykład to głosowanie na "mniejsze zło". Czyli np. odnosząc się do aktualnych wyborów: "Wolę Korwina niż Kukiza, ale tylko Kukiz ma szansę wejść do drugiej tury. Zatem zagłosuję na niego, spychając w ten sposób z 2. miejsca Dudę, który jest moim zdaniem jeszcze gorszym wyborem niż Kukiz". Czyli nie głosuję zgodnie z własnymi
ps
poza tym JOW trochę zmienia pojęcie partii - asocjacje w samej partii, brak lidera - tylko raczej arbitrzy
Prawidłowy wniosek: głosy wyborców rozkładają się po 33,3%.
Stracić powinien ten, któremu spadło poparcie, a nie ten, któremu wzrosło ( ͡º ͜ʖ͡º)
Niech żyje Monarchia! Niech żyje Król! Niech żyje Golarka!