Indeks siły Shapleya-Shubika

Z Wikipedii

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 ja 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%.

[edytuj] Prosty symetryczny przykład

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łę .

[edytuj] Przykład dla różnych uczestników

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:

[edytuj] Obliczanie

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

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₁,g₂,...,g_i,x jest wygrywająca, natomiast g₁,g₂,...,g_i nie, to w wykonywanych wedle definicji obliczeniach wystąpią nastepujące uporządkowania:

g₁,g₂,,..,g_i,x,h₁,h₂,...,h_{n − i − 1}

g₂,g₁,...,g_i,x,h₁,h₂,...,h_{n − i − 1}

g₁,g₂,...,g_i,x,h₂,h₁,...,h_{n − i − 1}

...

Czyli: wszystkie permutacje {g₁,g₂,,..,g_i}, gracz x (któremu należy się za to 1 punkt), wszystkie permutacje {h₁,h₂,,..,h_{n − i − 1}}

Ponieważ dla danego zbioru {g₁,g₂,,..,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(n2^{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.