Indeks siły Shapleya-Shubika
Indeks siły Shapleya-Shubika – jeden z dwóch najważniejszych indeksów siły (obok indeksu siły Banzhafa).
Indeksu tego używa się do określenia względnej siły graczy w danym systemie wyborczym.
System wyborczy jest tu opisywany w następujący sposób:
- podajemy zbiór uczestników,
- podajemy, które koalicje wyborcze (podzbiory zbioru uczestników) są wygrywające.
Taki system musi spełniać pewne dodatkowe założenia:
- koalicja wszystkich graczy jest wygrywająca (jest możliwe wygranie głosowania),
- koalicja pusta nie jest wygrywająca (jest możliwe przegranie głosowania),
- jeśli koalicja już jest wygrywająca, to dołączenie do niej dodatkowych graczy nie spowoduje jej przegranej,
- jeśli jakaś koalicja już jest wygrywająca, to z pozostałych uczestników nie da się zbudować innej koalicji wygrywającej (w systemach wyborczych „każdy gracz ma jeden głos” oznacza to, że próg zwycięstwa nie może być niżej niż 50% + jeden głos).
Indeks liczy się następująco:
- Bierze się wszystkie możliwe uporządkowania uczestników. Każde takie uporządkowanie przedstawia możliwa kolejność przyłączania się graczy do koalicji. Gracz, po przyłączeniu którego budowana właśnie koalicja stanie się koalicją wygrywającą dostaje jeden punkt.
- Indeks siły gracza jest równy ilości takich punktów podzielonej przez ilość wszystkich uporządkowań, tak żeby suma indeksów siły wszystkich graczy wynosiła 100%.
Prosty symetryczny przykład
[edytuj | edytuj kod]Na przykład jeśli jest 3 graczy, i dowolnych 2 potrzeba do wygrania głosowania, ich punktacja wygląda następująco:
Kolejność przyłączania | Uczestnik, po przyłączeniu którego koalicja uzyskuje wymaganą większość |
---|---|
A B C | B |
A C B | C |
B A C | A |
B C A | C |
C A B | A |
C B A | B |
Ilość punktów każdego uczestnika wynosi więc 2, a zatem każdy uczestnik ma siłę
Przykład dla różnych uczestników
[edytuj | edytuj kod]Rozważmy 9-osobową radę gminy, gdzie poszczególne partie mają 4, 2, 2 i 1 radnego, a do podjęcia decyzji potrzebnych jest 5 głosów. Nazwijmy te partie: Zieloną, Niebieską, Czerwoną i Żółtą.
Są aż 24 możliwe uporządkowania:
Kolejność przyłączania | Uczestnik, po przyłączeniu którego koalicja uzyskuje wymaganą większość |
---|---|
Zielona Żółta Czerwona Niebieska | Partia Żółta |
Zielona Żółta Niebieska Czerwona | Partia Żółta |
Zielona Niebieska Czerwona Żółta | Partia Niebieska |
Zielona Niebieska Żółta Czerwona | Partia Niebieska |
Zielona Czerwona Niebieska Żółta | Partia Czerwona |
Zielona Czerwona Żółta Niebieska | Partia Czerwona |
Żółta Niebieska Czerwona Zielona | Partia Czerwona |
Żółta Niebieska Zielona Czerwona | Partia Zielona |
Żółta Czerwona Zielona Niebieska | Partia Zielona |
Żółta Czerwona Niebieska Zielona | Partia Niebieska |
Żółta Zielona Czerwona Niebieska | Partia Zielona |
Żółta Zielona Niebieska Czerwona | Partia Zielona |
Niebieska Żółta Czerwona Zielona | Partia Czerwona |
Niebieska Żółta Zielona Czerwona | Partia Zielona |
Niebieska Czerwona Zielona Żółta | Partia Zielona |
Niebieska Czerwona Żółta Zielona | Partia Żółta |
Niebieska Zielona Żółta Czerwona | Partia Zielona |
Niebieska Zielona Czerwona Żółta | Partia Zielona |
Czerwona Żółta Niebieska Zielona | Partia Niebieska |
Czerwona Żółta Zielona Niebieska | Partia Zielona |
Czerwona Niebieska Zielona Żółta | Partia Zielona |
Czerwona Niebieska Żółta Zielona | Partia Żółta |
Czerwona Zielona Niebieska Żółta | Partia Zielona |
Czerwona Zielona Żółta Niebieska | Partia Zielona |
Partie powodują uzyskanie większości w radzie gminy w:
- Partia Zielona – 12 przypadkach na 24,
- Partia Niebieska – 4 przypadkach na 24,
- Partia Czerwona – 4 przypadkach na 24,
- Partia Żółta – 4 przypadkach na 24,
co daje indeksy siły:
- Partia Zielona:
- Partia Niebieska:
- Partia Czerwona:
- Partia Żółta:
Obliczanie
[edytuj | edytuj kod]Już dla 4 uczestników obliczenia stały się dość długie. Dzieje się tak dlatego, że wszystkich uporządkowań graczy jest
Ale można te obliczenia znacznie uprościć korzystając z prostej matematycznej właściwości: to czy przyłączenie się danego uczestnika umożliwi uzyskanie większości nie zależy od kolejności w jakiej przyłączali się pozostali uczestnicy, ani tym bardziej od kolejności w jakiej przyłączaliby się kolejni.
Zamiast więc sprawdzać wszystkie permutacje wystarczy, że sprawdzimy wszystkie zawierające gracza.
- Wybieramy gracza x, dla którego będziemy liczyć indeks siły.
- Sprawdzamy po kolei wszystkie możliwe podzbiory pozostałych graczy.
- Niech będzie równe ilości graczy w aktualnie sprawdzanej koalicji
- Jeśli wybrany podzbiór jest przegrywający, ale dołączenie gracza x czyni go wygrywającym, to:
- Dodaj do punktacji gracza
- Podziel wynik przez liczbę wszystkich możliwych uporządkowań
Powyższy algorytm jest poprawny, ponieważ uporządkowania występują w grupach. Jeśli koalicja graczy jest wygrywająca, natomiast nie, to w wykonywanych wedle definicji obliczeniach wystąpią następujące uporządkowania:
- Czyli: wszystkie permutacje gracz (któremu należy się za to 1 punkt), wszystkie permutacje
Ponieważ dla danego zbioru i gracza jest takich permutacji zamiast liczyć je po kolei wystarczy, że sprawdzimy wszystkie zbiory, zamiast wszystkich permutacji.
Złożoność obliczeniowa oryginalnego algorytmu wynosi złożoność zmodyfikowanego zaś
Dla 20 graczy w pierwszym algorytmie trzeba wykonać operacji, w drugim zaś tylko czyli ponad 200 miliardów razy mniej.