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 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łączaniaUczestnik, po przyłączeniu którego koalicja uzyskuje wymaganą większośćA B CBA C BCB A CAB C ACC A BAC B AB

Ilość punktów każdego uczestnika wynosi więc 2, a zatem każdy uczestnik ma siłę

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 NiebieskaPartia ŻółtaZielona Żółta Niebieska CzerwonaPartia ŻółtaZielona Niebieska Czerwona ŻółtaPartia NiebieskaZielona Niebieska Żółta CzerwonaPartia NiebieskaZielona Czerwona Niebieska ŻółtaPartia CzerwonaZielona Czerwona Żółta NiebieskaPartia CzerwonaŻółta Niebieska Czerwona ZielonaPartia CzerwonaŻółta Niebieska Zielona CzerwonaPartia ZielonaŻółta Czerwona Zielona NiebieskaPartia ZielonaŻółta Czerwona Niebieska ZielonaPartia NiebieskaŻółta Zielona Czerwona NiebieskaPartia ZielonaŻółta Zielona Niebieska CzerwonaPartia ZielonaNiebieska Żółta Czerwona ZielonaPartia CzerwonaNiebieska Żółta Zielona CzerwonaPartia ZielonaNiebieska Czerwona Zielona ŻółtaPartia ZielonaNiebieska Czerwona Żółta ZielonaPartia ŻółtaNiebieska Zielona Żółta CzerwonaPartia ZielonaNiebieska Zielona Czerwona ŻółtaPartia ZielonaCzerwona Żółta Niebieska ZielonaPartia NiebieskaCzerwona Żółta Zielona NiebieskaPartia ZielonaCzerwona Niebieska Zielona ŻółtaPartia ZielonaCzerwona Niebieska Żółta ZielonaPartia ŻółtaCzerwona Zielona Niebieska ŻółtaPartia ZielonaCzerwona Zielona Żółta NiebieskaPartia 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 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.

Kategoria:Teoria gier