Indeks siły Shapleya-Shubika

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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łę \frac 2 6 = \frac 1 3.

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: \frac {12}{24} = \frac 1 2 = 50\%
  • Partia Niebieska: \frac {4}{24} = \frac 1 6 = 16.67\%
  • Partia Czerwona: \frac {4}{24} = \frac 1 6 = 16.67\%
  • Partia Żółta: \frac {4}{24} = \frac 1 6 = 16.67\%

Obliczanie[edytuj | edytuj kod]

Już dla 4 uczestników obliczenia stały się dość długie. Dzieje się tak dlatego, że wszystkich uporządkowań n graczy jest n!.

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 c pozostałych graczy
Niech i będzie równe ilości graczy w aktualnie sprawdzanej koalicji c
Jeśli wybrany podzbiór jest przegrywający, ale dołączenie gracza x czyni go wygrywającym, to:
Dodaj do punktacji gracza (i)! (n-i-1)!
Podziel wynik przez liczbę wszystkich możliwych uporządkowań (n!)

Powyższy algorytm jest poprawny, ponieważ uporządkowania występują w grupach. Jeśli koalicja graczy g_1,g_2,...,g_i,x jest wygrywająca, natomiast g_1,g_2,...,g_i nie, to w wykonywanych wedle definicji obliczeniach wystąpią następujące uporządkowania:

g_1,g_2,,..,g_i,x,h_1,h_2,...,h_{n-i-1}
g_2,g_1,...,g_i,x,h_1,h_2,...,h_{n-i-1}
g_1,g_2,...,g_i,x,h_2,h_1,...,h_{n-i-1}
...
Czyli: wszystkie permutacje \{g_1,g_2,,..,g_i\}, gracz x (któremu należy się za to 1 punkt), wszystkie permutacje \{h_1,h_2,,..,h_{n-i-1}\}

Ponieważ dla danego zbioru \{g_1,g_2,,..,g_i\} i gracza x jest takich permutacji (i)! (n-i-1)!, zamiast liczyć je po kolei, wystarczy że sprawdzimy wszystkie zbiory, zamiast wszystkich permutacji.

Złożoność obliczeniowa oryginalnego algorytmu wynosi O(n!), złożoność zmodyfikowanego zaś O(n 2^{n-1}).

Dla 20 graczy w pierwszym algorytmie trzeba wykonać 10^{18.38} operacji, w drugim zaś tylko 10^{7.02}, czyli ponad 200 miliardów razy mniej.