Kod raznih igara često je važno pitanje određivanja pobjedničke strategije. No, vrlo često se razmatraju i problemi računarske složenosti u vezi igara (vidi [2]). U ovom članku se razmatra računarska složenost povezana s igrom Sokoban.

Sokoban je poznata stara računalna igra u kojoj igrač (skladištar) mora odgurati sve kutije u skladištu na odgovarajuće pozicije, s tim da odjednom smije gurati najviše jednu kutiju. Osnovnu verziju igre možete isprobati na sljedećoj poveznici: https://sokoban.info/.

U ovom članku dat ćemo dokaze NP-težine dviju varijanti igre Sokoban. Ti se dokazi svode na to da za svaku instancu 3-SAT problema (ili u drugom slučaju problema P-3-SAT) generiramo početnu konfiguraciju igre koja će biti rješiva ako i samo ako je zadana formula ispunjiva. Većina rezultata u ovom članku dio je članka [5].

Osnovne pojmove teorije složenosti algoritama potrebne za razumijevanje ovog članka predstavit ćemo u točki 2. U točki 3 objasnit ćemo standardnu verziju igre Sokoban te još jednu njenu varijantu. Kao prirodno pitanje nameće se što uopće znači da je igra Sokoban NP-teška. To ćemo objasniti u točki 4.

U točki 5 ćemo dati dokaz NP-težine neklasične varijante igre Sokoban. Po našem mišljenju taj je dokaz nešto jednostavniji od dokaza iste tvrdnje za standradnu verziju igre. Dokaz NP–težine standardne verzije igre dan je u točki 6.

U ovoj točki dati ćemo opise osnovnih pojmova iz teorije složenosti algoritama koje koristimo u ovom članku. Naglašavamo da ćemo dati samo intuitivne opise a ne stroge definicije. Razlog tome je, naravno, veličina teksta članka. Za formalne defincije trebalo bi, primjerice, detaljno definirati Turingove strojeve i sve pojmove u vezi njih. Kolika je to veličina materijala možete vidjeti, primjerice u [12].

U čitavom članku pojam algoritma ćemo koristiti u intutivnom smislu.1

Neka je \Gamma proizvoljan konačan skup. Skup \Gamma ćemo nazivati alfabet. Svaki konačan niz elemenata alfabeta \Gamma nazivamo riječ. Skup svih riječi alfabeta \Gamma označavamo s \Gamma^{*}. Ako je s\in \Gamma^{*} neka riječ tada s |s| označavamo duljinu riječi s. Svaki podskup od \Gamma^{*} nazivamo jezik.

U ovom članku razmatrat ćemo samo algoritme koje imaju jedan ulazni podatak (točnije, za zadani alfabet \Gamma ulazni podatak je neka riječ s\in\Gamma^{*}). Zatim, pretpostavljamo da svaki algoritam za svaki ulazni podatak završi u konačno mnogo koraka te da na kraju kao izlazni podatak daje samo "DA" ili "NE". Razlog takvim ograničenjima je to što promatramo samo tzv. probleme odlučivanja. To su problemi kod kojih nas zanima ima li neki objekt neko zadano svojstvo. Neki primjeri problema odlučivanja su: ispunjivost formula logike sudova, prostost zadanog prirodnog broja i bojanje grafa s tri boje. Problem trgovačkog putnika, problem ruksaka i problem rasporeda su primjeri problema koji nisu problemi odlučivanja. Formalno se problemi odlučivanja definiraju kao odgovarajući jezici. Primjerice, problem PRIMES koji se sastoji od određivanja je li zadani prirodan broj prost, definira se formalno kao \lbrace n\in \mathbb{N}: n je prosti broj\rbrace .

Vremenska složenost nekog algoritma definira se kao funkcija f: \mathbb{N}\to \mathbb{N}, gdje je f(n) maksimalni broj koraka koji algoritam izvrši za svaki ulazni podatak duljine n.2

Sasvim analogno se defnira prostorna složenost nekog algoritma (primijetite da je ovdje nužno imati Turingove strojeve kako bi mogli brojati registre koje algoritam koristi).

Reći ćemo da je neki algoritam vremenski polinoman ili samo kratko da je polinoman, ako je njegova vremenska složenost neki polinom. S P označavamo klasu svih problema odlučivanja za koje postoje polinomni algoritmi koji ih rješavaju. Neki primjeri problema koji pripadaju klasi P su sljedeći: ispitivanje relativne prostosti dva prirodna broja, odre đivanje je li graf povezan i egzistencija rješenja sistema linearnih algebarskih jednad\v zbi. Zanimljivo je da je 2004. godine dokazano da problem PRIMES tako đer pripada klasi P (članak o tome je objavljen u najcjenjenijem matematičkom časopisu Annals of Mathematics).

Sasvim analogno definira se klasa PSPACE koja sadrži sve probleme odlučivanja za koje postoji algoritam koji je polinomno prostorno složen.

Sada ćemo opisati nekoliko pojmova iz logike sudova kako bismo mogli definirati problem SAT. Propozicionalne varijable ovdje označavamo s x_{0}, x_{1}, x_{2}, \ldots Ako je F neka formula logike sudova, tada ćemo s \overline{F} označavati njenu negaciju. Literal je svaka propozicionalna varijabla x_{i} i njena negacija \overline{x}_{i}. Elementarna disjunkcija je disjunkcija literala. Primjerice, x_{2}\vee x_{7} \vee \overline{x}_{33}\vee x_{8} \vee \overline{x}_{201}  i  x_{4}\vee x_{6} su primjeri elementarnih disjunkcija. Konjunktivna normalna forma (ili kratko: knf) je svaka konjunkcija elementarnih disjunkcija. Neki primjeri knf su (x_{8}\vee \overline{x}_{1}\vee x_{4} \vee x_{5})\wedge (x_{1} \vee x_{2})  i  (x_{13}\vee \overline{x}_{23})\wedge x_{33} \wedge (x_{23}\vee \overline{x}_{4} \vee x_{9}). Knf nazivamo 3-knf ako svaka njena elementaran disjunkcija sadrži tri literala. Problem ispunjivosti logike sudova, koji se kratko označava sa SAT, sastoji se određivanja je li zadana knf ispunjiva, tj. postoji li interpretacija propozicionalnih varijabli tako da je za tu interaprtaciju knf istinita, odnosno formalno ovako:

Problem 3-SAT u obzir uzima samo 3-knf. Sasvim analogno se definira problem 2-SAT.
Mi ćemo u ovom članku najviše spominjati klasu problema NP. Jako grubo rečeno klasa NP sadrži sve probleme odlučivanja za koje postoji polinomni algoritam čiji ulazni podatak je par koji uz zadani objekt sadrži i posebni "certifikat". Primjenom "certifikata" algoritam onda odlučuje ima li zadani objekt traženo svojstvo. Pokušat ćemo to objasniti na dva primjera. Problem SAT pripada klasi NP jer očito postoji polinomni algoritam kojemu na ulaz dajemo neku knf F i neku interpretaciju I (to je "certifikat") te onda algoritam određuje vrijedi li I(F)=1 (možete li opisati jedan takav algoritam?). Zatim, problem egzistencije potpuno povezanog podgrafa zadane veličine u nekom grafu također pripada klasi NP. Za taj problem postoji polinomni algoritam koji na ulazu ima zadani graf G, k\in \mathbb{N} i neki podgraf G' od G (ovdje je podgraf "certifikat") te onda algoritam određuje je li G' potpuno povezan i veličine k.

Očito vrijedi P \subseteq NP. Pitanje vrijedi li i obratna inkluzija je centralni problem teorijskog računarstva već više od 50 godina. \v Stovi\v se, problem P vs. NP jedan je od tzv. sedam Milenijskih matemati\v ckih problema.

Neka su \Gamma_{1} i \Gamma_{2} alfabeti. Za neku funkciju g:\Gamma_{1}^{*} \to \Gamma_{2}^{*} kažemo da je vremenski polinomno izračunljiva ako postoji polinom p:\mathbb{N}\to \mathbb{R} i neki algoritam tako da za svaki s\in \Gamma_{1}^{*} algoritam kao izlazni rezulat daje g(s) i za to mu ne treba više od p(|s|) koraka.

Ako imamo dva problema odlučivanja, označimo ih L_{1} i L_{2}, tada je problem L_{1} polinomno reducibilan na problem L_{2} ako možemo svaku instancu problema L_{1} (rješivu i nerješivu) svesti u polinomnom vremenu na neku instancu problema L_{2}. Budući da ovaj pojam polinomne reducibilnosti bitno koristimo u ovom članku, odlučili smo ipak dati nešto formalniju definiciju. Neka su L_{1}\subseteq \Gamma_{1}^{*} i L_{2}\subseteq \Gamma_{2}^{*} dva problema odlučivanja. Kažemo da je problem L_{1} polinomno reducibilan na problem L_{2}, i pišemo L_{1}\leq_{p} L_{2}, ako postoji vremenski polinomno izračunljiva funkcija g tako da za svaki s\in \Gamma_{1}^{*} vrijedi sljedeća ekvivalencija:

U daljnjem tekstu članka dati ćemo primjere polinomne reducibilnosti.
Za neki problem odlučivanja L kažemo da je NP–težak ako za svaki problem L'\in NP vrijedi L'\leq_{p} L. Zatim, govorimo da je neki problem L jedan NP–potpun problem ako je on NP–težak i još vrijedi L\in NP. Cook i Levin su 1970. godine nezavisno dokazali da je SAT jedan NP–potpun problem. Problem 3-SAT je tako đer NP–potpun. (No, vrijedi 2-SAT \in P.)

Označimo s Dif problem odre đivanja ima li zadana diofantska jednadžba cjelobrojnih rješenja. Već smo naveli da za taj problem ne postoji algoritam koji ga rješava. Iz toga posebno slijedi Dif\not\in NP. No, može se pokazati da je Dif jedan NP–težak problem (vidi [12]).

U igri Sokoban igrač upravlja skladištarem koji se može kretati u 4 smjera po pravokutnoj mreži. Na slici 1 prikazan je primjer jednog početnog stanja igre. Skladištar ne može pristupiti poljima na kojima je zid. Može se pomaknuti na slobodno susjedno polje, isto kao i na polje na kojem je kutija (ako je slobodno polje na koje će svojim pomicanjem gurnuti kutiju). U standardnoj verziji igre odjednom može gurnuti najviše jednu kutiju. Zatim, u standardnoj verziji skladištaru nije dozvoljeno vući kutije prema sebi.

U ovom ćemo radu razmatrati još jednu verziju igre. U tom slučaju ćemo pretpostaviti da skladištar istovremeno može gurati do k kutija, gdje je k neki prirodan broj. U toj verziji igre skladišatar smije prema sebi vući najviše jednu kutiju.

Sa Sokoban(k, l) ćemo označiti igru u kojoj skladištar može istovremeno gurati do k kutija i prema sebi vući najviše l kutija, gdje su k i l prirodni brojevi. Tada standardnu verziju igre možemo kratko zapisti kao Sokoban(1, 0), a drugu malo prije opisanu verziju igre možemo kratko označiti sa Sokoban(k, 1), za neki k\geq1.

Slika 1: Prikaz igre Sokoban. Cilj skladištara je sve kutije smjestiti na pozicije označene kružićima.

NP-teški problemi imaju svojstvo da se svaki problem iz klase složenosti NP može polinomno reducirati na njih, dok oni sami ne moraju pripadati klasi NP. Jedan od najpoznatijih načina za dokazivanje da je neki problem NP-težak je polinomno svođenje problema 3-SAT na njega (vidi [12]). To će biti i ideja dokaza u ovome članku. No, prvo moramo objasniti kako uopće neki problem u vezi igre Sokoban možemo promatrati kao problem odlučivanja.

Promatrat ćemo problem odlučivanja SOKOBAN u kojem je pitanje ima li igra Sokoban s nekom početnom konfiguracijom rješenje. Preciznije, za problem SOKOBAN(1, 0) zanima nas možemo li za neku početnu konfiguraciju klasične igre sve kutije staviti na željena mjesta. Za verziju igre Sokoban(k, 1) gledat ćemo nešto lakši problem. U problemu SOKOBAN(k, 1) treba za početnu konfiguraciju odrediti može li skladištar doći do neke određene pozicije (neovisno o pozicijama kutija na kraju igre). Želimo samo spomenuti da je u [5] navedeno da bi se tvrdnja mogla dokazati i za teži problem ali da bi tada alati korišteni u dokazu trebali biti daleko kompliciraniji od ovih koje ćemo mi predstaviti.

U ovoj točki dokazat ćemo sljedeći teorem:

Kao što smo već najavili, za dokaz ovog teorema koristit ćemo činjenicu da je problem 3-SAT jedan NP-potpun problem (to je jedna od posljedica Cook, Levinovog teorema; vidi [12]). Naš cilj je dokazati da je problem 3-SAT polinomno reducibilan na problem SOKOBAN(k, 1), za svaki k\geq 5. To znači da za svaku 3-knf F moramo konstruirati početnu konfiguraciju igre za koju će skladištar moći doći do zadanog polja ako i samo ako je 3-knf F ispunjiva.

U tu svrhu koristit ćemo četiri konstrukcijska elementa: usmjerivač, porednik, prekidač i usmjereno raskrižje.

Ako je I oznaka ulaza a O oznaka izlaza u nekom konstrukcijskom elementu, tada s I\rightarrow O označavamo proizvoljni (usmjereni) put od I do O. Sada redom opisujemo svaki od prije navedena četiri konstrukcijska elementa.

\bullet	usmjerivač je prikazan na slici 2. Primijetimo da je put I \rightarrow O otvoren jer skladištar mora samo dva puta gurnuti tri uzastopne kutije: prvo udesno, nakon čega mora krenuti donjim puteljkom, te nakon toga ulijevo kako bi oslobodio prolaz koji je zatvorio prethodnim guranjem. Nakon izlaska skladištara, konstrukticijski element izgledat će i kao prije njegovog ulaska u koridor. Primijetimo da skladištar ni na koji način ne može proći putem O \rightarrow I (iz tog razloga ovaj konstrukcijski element nazivamo usmjerivač). Slika 2: Usmjerivač i njegov shematski prikaz.
\bullet	porednik je prikazan na slici 3. Kod ovog konstrukcijskog elementa je na početku put I_{1} \rightarrow O_{1} otvoren, a put I_{2} \rightarrow O_{2} je zatvoren. Kako bi skladištar prošao putem I_{2} \rightarrow O_{2}, prvo mora osloboditi prolaz, a to može samo ako prvo uđe u koridor kroz ulaz I_{1}, obje kutije gurne do zida i zatim bližu kutiju povuće prema sebi. Primijetimo kako je usmjerivač sastavni dio ovog konstrukcijskog elementa. Naime, da njega nema na ulazima I_{1} i I_{2}, skladištar bi mogao ući na ulaz I_{1}, osloboditi prolaz I_{2} \rightarrow O_{2} i izaći iz koridora na mjestu gdje je ušao. Slika 3: Porednik i njegov shematski prikaz.
\bullet	prekidač je prikazan na slici 4. Njegova funkcija je da omogući samo jednu vrstu prolaza. U objašnjenju ćemo se fokusirati na slučaj desnog shematskog prikaza sa slike 4. Ako skladištar jednom prođe putem I_{1} \rightarrow O zauvijek će mu se zatvoriti put I_{2} \rightarrow O. Jednako je i obrnutom slučaju. Slika 4: Prekidač i njegova dva shematska prikaza. Konstrukcijski element prikazan desnim shematskim prikazom dobijemo ako izlaze O_{1} i O_{2} sa slike spojimo u jedinstveni izlaz O.
\bullet	usmjereno raskrižje je prikazano na slici 5. U ovom konstrukcijskom elementu skladištar na početku može proizvoljan broj puta proći putem I_{1} \rightarrow O_{1}. Tijekom jednog od prolazaka putem I_{1} \rightarrow O_{1} skladištar može odlučiti osloboditi prolaz I_{2} \rightarrow O_{2} tako da prođe kroz prolaz označen s B, gurne kutije do zida i zatim najbližu kutiju povuće prema sebi. Nakon što prođe putem I_{2} \rightarrow O_{2}, prolaz I_{1} \rightarrow O_{1} ostat će trajno zatvoren. Slika 5: Usmjereno raskrižje

Očito je usmjereno raskrižje najkompliciraniji konstrukcijski element. Kasnije ćemo vidjeti da nam on omogućava da tvrdnju dokažemo i za instance 3-SAT problema čiji inducirani graf nije planaran. O tome ćemo više reći više u dokazu NP-težine standardne verzije igre u kojem nam je planarnost tog grafa ključna.
 

Sada možemo objasniti i zbog čega je u iskazu teorema uvjet k \geq 5. U usmjerenom raskrižju potrebno je da skladištar u jednom trenutku gura barem 5 kutija u nizu. Kada bismo, primjerice, uspjeli konstruirati usmjereno raskrižje u kojem se guraju najviše 4 kutije, tada bi tvrdnja vrijedila i za k = 4.

Koristeći prethodno opisane konstrukcijske elemente prelazimo na glavni dio dokaza teorema 1. Neka je F \equiv C_{1} \bigwedge...\bigwedge C_{m} proizvoljna 3-knf s propozicionalnim varijablama x_{1},..., x_{n}. Ideja konstrukcije prikazana je na slici 6.

Slika 6: Shematski prikaz konstrukcije početnog stanja igre Sokoban(k, 1) za proizvoljnu 3-knf.

Na slici 6 nalazi se m porednika, koje redom pridružujemo elementarnim disjunkcijama, dok prekidače pridružujemo varijablama. Prvi ulaz i-tog prekidača pridružen je literalu x_{i}, a njegov drugi ulaz je pridružen literalu \bar{x_{i}}. Zatim, prvi izlaz i-tog porednika vodi do ulaza prekidača koji je pridružen prvom literalu u elementarnoj disjunkciji C_{i}. Drugi izlaz i-tog porednika pridružen je drugom literalu iz C_{i} te je treći izlaz pridružen trećem literalu. Kao što smo već spomenuli, usmjerena raskrižja imaju među ostalim funkciju da se putevi mogu sijeći (bez ikakvih garancija da je graf induciran početnom konfiguracijom igre planaran).

Skladištar počinje svoje putovanje na poziciji A i cilj mu je doći do pozicije B. Ovdje je ključno primijetiti da skladištar mora redem proći kroz sve porednike kako bi stigao od ulaza A do izlaza B. Nakon prolaska kroz i-ti porednik skladištar mora barem jednom literalu koji se pojavljuju u elementarnoj disjunkciji C_{i} pridružiti vrijednost "istina". Prekidači skladištaru onemogućuju da istovremeno nekom literalu i njegovoj negaciju pridruži vrijednost "istina". Time smo dokazali da vrijedi sljedeća ekvivalencija:

Time je teorem potpuno dokazan.

Slika 7: Graf induciran s 3-knf (x_{1} \lor \bar{x_{1}} \lor \bar{x_{2}}) \land (x_{2} \lor x_{3} \lor \bar{x_{3}}). Ovo je jedan od najjednostavnijih grafova u kojima je barem jedno usmjereno raskrižje.

Sada na jednom primjeru želimo ilustrirati neke detalje iz prethodnog dokaza. Na slici 7 je prikazana početna konfiguracija igre Sokoban(k, 1), k \geq 5, koja je pridružena sljedećoj 3-knf:

Budući da je prva klauzula od F jednaka x_{1} \lor \bar{x_{1}} \lor \bar{x_{2}} tada prvi izlaz prvog porednika vodi k prvom ulazu prekidača varijable x_{1}, a drugi izlaz tog prekidača k njegovom drugom ulazu jer on odgovara literalu \bar{x_{1}}. Isto je tako treći izlaz spojen s prvim ulazom drugog prekidača jer on odgovara literalu x_{2}, a slično je i za drugi porednik.

Put koji spaja treći izlaz prvog porednika i drugi ulaz drugog prekidača siječe se s putem koji povezuje prvi izlaz drugog porednika i prvi ulaz drugog prekidača pa je neophodno korištenje usmjerenog raskrižja.

U ovom poglavlju dokazujemo NP-težinu standardne verzije igre. To iskazujemo u sljedećem teoremu.

U ovoj verziji igre skladištar smije gurati najviše jednu kutiju i zabranjeno mu je vući kutije prema sebi. U ovom ćemo slučaju zahtijevati da na kraju igre sve kutije budu smještene na predviđenim pozicijama. To je različito od prethodno razmatranog slučaja gdje smo samo promatrali može li skladištar doći do svog cilja.

Slično kao i u prethodnom dokazu, ključnu ulogu igraju konstrukcijski elementi koji će biti korišteni prilikom generiranja početne konfiguracije igre. Koristit ćemo dva konstrukcijska elementa: selektor i klauzulu. Za razliku od otvora konstrukcijskih elemenata iz prijašnjeg dokaza, ovi neće biti usmjereni, već je ulazak i izlazak moguć kroz sve njih. Sada redom opisujemo nove konstrukcijske elemente.

\bullet

selektor je prikazan na slici 8. U ovom konstrukcijskom elementu nalaze se tri kutije i četri pozicije na kojima se na kraju igre moraju nalaziti kutije. Uz ulazni i izlazni otvor u konstrukcijskom elementu se nalaze još dva otvora označena s x i \bar{x} čiju ćemo funkciju objasniti naknadno. Slika 8: Selektor i njegov shematski prikaz. Kružići označavaju mjesta na kojima su pozicionirane kutije, a osjenčana polja predstavljaju pozicije do kojih skladištar mora dogurati kutije.

\bullet

klauzula je prikazana na slici 9. Ovaj konstrukcijski element sadrži tri otvora i jednu poziciju namijenjenu za smještanje kutije. Slika 9: Klauzula i njezin shematski prikaz. Isto kao u prethodnom konstrukcijskom elementu, osjenčani kvadratić predstavlja mjesto do kojeg skladištar mora dogurati točno jednu kutiju. Plavim trokutićima su označeni otvori ovog konstrukcijskog elementa.

Osnovna ideja dokaza teorema 2 je slična dokazu teorema 1 gdje smo dokazali da je problem 3-SAT polinomno reducibilan na svaki problem SOKOBAN(k, 1), gdje je k\geq 5. No, kao što smo već napomenuli, u ovom ćemo slučaju promatrat ćemo samo instance problema 3-SAT čiji je inducirani graf planaran. Prvo ćemo definirati pojam induciranog grafa (sa zadanom formulom), a onda ćemo definirati jednu važnu verziju problema SAT.

Neka je F \equiv C_{1} \bigwedge...\bigwedge C_{m} neka 3-knf s propozicionalnim varijablama x_{1},..., x_{n}. Neka je skup čvorova grafa G_{F} = (V, E), koji je induciran formulom F, jednak sljedećem skupu:

Zatim, neka je skup bridova grafa G zadan ovako:

Dakle, čvorovi grafa su elementarne disjunkcije C_{i} i varijable formule F. Varijable su bridovima spojene u jedan veliki ciklus, a svaka elementarna disjunkcija C_{i} je spojena s onim varijablama koje se, ili njihova negacija, pojavljuju u njima.

Sada želimo na jednom primjeru ilustrirati kako izgleda graf koji je induciran zadanom formulom. Na slici 10 prikazan je planarni graf sljedeće 3-knf:

Slika 10: Graf induciran s 3-knf.

Označimo s P-3-SAT problem u kojem se razmatraju samo instance problema 3-SAT za koje je inducirani graf planaran. Ovaj problem je također NP-potpun (vidi [??]).

Sada dokazujemo da je problem P-3-SAT polinomno reducibilan na problem SOKOBAN(1, 0). U tu svrhu za proizvoljnu 3-knf F čiji je inducirani graf planaran, konstruiramo početnu konfiguraciju igre kao na slici 11. Takva početna konfiguracija sadrži točno n selektora koji redom odgovaraju varijablama formule F. Na slici 11 je m klauzula koje pridružujemo elementarnim disjunkcijama C_{i}.

Selektori su spojeni onim klauzulama u kojima se pripadne varijable ili njihove negacije nalaze. Preciznije, ako je x_{j} \in C_{i} tada će j-ti selektor biti spojen s klauzulom koja odgovara elementarnoj disjunkciji C_{i} kroz otvor x_{j}, a ako je \bar{x_{j}} \in C_{i} biti će spojen kroz otvor \bar{x_{j}}.

Primijetimo da se u danoj početnoj konfiguraciji nalazi još jedan konstrukcijski element koji do sada nismo opisali. Taj novi konstrukcijski element nazivat ćemo rezervoar. U njemu su na početku smještene kutije. Naime, u svakom od n selektora su na početku tri kutije i četiri mjesta namijenjena za kutije, a u svakoj od m klauzula jedno mjesto namijenjeno za kutije, što znači da fali n+m kutija kako bi na kraju igre svaka kutija bila na točno jednom namijenjenom mjestu.

Preostalo je dokazati da je formula F ispunjiva ako i samo ako za početnu konfiguraciju koju smo iz nje izgradili skladištar može smjestiti sve kutije na zadane pozicije. Neka se na početku skladištar nalazi u rezervoaru.

Pretpostavimo prvo da je F ispunjiva formula. Tada postoji interpretacija I za koju je I(F) = 1. Skladištar kreće iz rezervoara i prolazi redom po selektorima. Svaku kutiju koja mu stoji na putu mora staviti u otvor koji pripada literalu l_{i} za koji je I(l_{i}) = 0. Na taj način blokira taj otvor.

Nakon toga mora dogurati kutije do slobodnih mjesta u svakoj od klauzula. To je moguće zbog toga što su otvori selektora koji pripadaju literalima l_{i} za koje vrijedi I(l_{i}) = 1 ostali otvoreni i zato što, zbog ispunjivosti formule F, za svaku klauzulu postoji barem jedan literal za koji je I(l_{i}) = 1. Nakon što popuni tražena mjesta unutar klauzula, skladištar pomoću preostalih kutija iz rezervoara mora blokirati preostale otvore selektora. Tako je uspio sve kutije dovesti na željene pozicije.

Slika 11: Shematski prikaz konstrukcije početnog stanja igre Sokoban(1, 0) za proizvoljnu 3-knf čiji je inducirani graf planaran.

Pretpostavimo sada da igra s početnom konfiguracijom generiranom formulom F rješiva. Cilj nam je pronaći interpretaciju I za koju je I(F) = 1. Kojim god poretkom skladištar smještao kutije na željene pozicije, kroz selektore mora proći redom od prvog do posljednjeg ulazeći u njih kroz glavni ulaz I. Naime, u selektor ne smije ući kroz otvor x_{i} ili \bar{x_{i}} jer bi u tom slučaju kutiju s tog ulaza gurnuo u kut iz kojeg ga više ne može izvaditi. Skladištar također ne smije ući u selektor kroz glavni izlaz O jer bi prije toga morao ući u neki od selektora kroz otvor x_{i} ili \bar{x_{i}}. Prolazeći redom kroz selektore, skladištar mora kutiju koja mu je na putu staviti u neki od otvora x_{i} ili \bar{x_{i}}, jer bi gurajući kutiju prema sljedećem selektoru zablokirao svoj prolaz u trenutku kad kutija koju gura dođe do kutije iz sljedećeg selektora. Ako u i-tom selektoru skladištar prvo blokira otvor x_{i}, definirat ćemo I(x_{i}) = 0, a ako prvo blokira otvor \bar{x_{i}} tada ćemo definirati I(x_{i}) = 1. Očito na taj način dobivamo interpretaciju I za koju je I(F)=1, što smo i trebali pokazati.

Na slici 12 je prikazana početna konfiguracija igre Sokoban(1, 0) pridružena formuli sa slike 10.

Slika 12: Početna konfiguracija dobivena iz 3-knf (x_{1} \lor x_{2} \lor \bar{x_{3}}) \land (x_{3} \lor \bar{x_{1}} \lor \bar{x_{5}}) \land (\bar{x_{4}} \lor \bar{x_{3}} \lor x_{5}), koja je korištena i u slici 10 gdje je pokazano da je inducirani graf te formule planaran. Sve klauzule koje su u planarnom grafu sa slike 10 unutar ciklusa koji povezuje varijable potrebno je staviti s jedne, a one koje su izvan ciklusa s druge strane pravca na kojem su selektori. Tada je moguće spojiti klauzule i selektore linijama koje se ne presjecaju. Skladištar se na početku nalazi u rezervoaru.

U ovom članku dani su dokazi NP-težine dviju verzija igre Sokoban.

Culberson je dokazao da je standardna verzija igre Sokoban PSPACE-potpuna (vidi [3]). To je dokazano i za stratešku društvenu igru Scotland Yard (vidi [10]). Takva, dakako, ne mora biti svaka igra. Primjerice, za problem odlučivanja pobjednika u popularnoj igri GO dokazano je tek da je PSPACE-težak, dok je pripadnost klasi PSPACE otvoren problem. (vidi [8]).

Za neke druge klasične igre kao što su Minesweeper (vidi [6]), potapanje brodova (vidi [9]) i tetris (vidi [4]) je dokazano i da su NP-potpune.

No za razne verzije igre Sokoban je još otvoreno pitanje jesu li NP-potpune.

Ključne riječi: teorija igara, matrične igre, nekooperativne igre s nenul-sumom, Nashova ravnoteža, Pareto optimalnost.

Pod pojmom igra obično mislimo na društvene, kartaške ili računalne igre. Tijekom 20. stoljeća, potaknuta različitim praktičnim problemima, razvila se teorija igara, grana matematičke znanosti koja detaljnije proučava igre uz primjenu teorije vjerojatnosti, linearnog programiranja, kombinatorike i drugih grana matematike. U teoriji igara, igra predstavlja natjecateljsku situaciju u kojoj sudjeluju barem dva igrača, pri čemu svaki ima određenu kontrolu nad ishodom igre. Svaki igrač ima određeni broj mogućih poteza koje može odabrati, a svakom mogućem ishodu igre pridružene su isplate za svakog igrača. Pretpostavljamo da igrači djeluju razumno i žele profitirati.

Proučavat ćemo igre u kojima sudjeluju dva igrača. Nazivamo ih matričnim igrama i prikazujemo matricom isplata P. Redci matrice P označavaju m poteza koje na raspolaganju ima igrač A, a stupci označavaju n mogućih poteza igrača B. Ako igrač A odigra svoj i-ti potez, a igrač B svoj j-ti potez, tada u matrici isplata

promatramo element (isplatu) p_{ij}. Kod igara s nula-sumom, igrači imaju strogo konfliktne interese, odnosno dobitak jednoga jednak je gubitku drugoga pa promatramo isplate samo za jednog igrača. Ako je u matrici P vrijednost p_{ij}\gt 0, igrač A dobiva iznos p_{ij} od igrača B, odnosno igrač B gubi iznos p_{ij}. Ako je p_{ij}=0, niti jedan igrač ne dobiva niti gubi. Ako je p_{ij}\lt 0, igrač B dobiva iznos p_{ij} od igrača A, odnosno igrač A gubi iznos p_{ij}. Napomenimo da je situacija kod igara s nenul-sumom nešto složenija, jer igrači nemaju strogo konfliktne interese te stoga na poziciji p_{ij} navodimo isplate za oba igrača.

Pravila igre unaprijed su poznata svakom igraču, određuju koje poteze on ima na raspolaganju te koje su posljedice pojedinog poteza. Dobitak na kraju igre ovisi i o potezima suparničkog igrača pa u teoriji igara govorimo o konfliktu ili suradnji. Zbog svega toga, svaki igrač mora imati i primjenjivati određenu strategiju tijekom igre. Sljedeće dvije definicije izričemo iz perspektive prvog igrača u igri (igrača A), a analogno se mogu izreći i iz perspektive drugog igrača.

Postoji beskonačno mnogo mješovitih strategija za svakog igrača, a glavni cilj teorije igara je svakom igraču pronaći optimalnu strategiju. Kod igara s nula-sumom, optimalne strategije su najopreznije strategije, u kojima igrač A želi osigurati najveći mogući minimalni dobitak, dok će istovremeno za igrača B maksimalan gubitak biti najmanji mogući, bez obzira na to koji potez suparnički igrač odabrao. Ako jedan od igrača ima na raspolaganju samo dva poteza, optimalnu strategiju moguće je odrediti grafički. Kod matrica isplata većih dimenzija u tome pomaže linearno programiranje, a ovakvi se problemi rješavaju korištenjem računala. Traženjem optimalnih strategija ovdje se nećemo baviti (pogledati, na primjer, u [4] i [6]).

Za daljnju analizu matričnih igara potrebno je uključiti i teoriju vjerojatnosti.

Analogno možemo izračunati i prosječni dobitak igrača B, samo što u tom slučaju moramo uzeti u obzir dobitke igrača B.

Kod igara s nenul-sumom dobitak jednog igrača ne predstavlja direktni gubitak drugog igrača u svakom od mogućih ishoda igre, odnosno zbroj dobitaka oba igrača nije nužno jednak nuli. Kombiniraju se natjecateljski aspekti s mogućnošću suradnje pa analiza ovakvih igara ovisi o tome jesmo li pretpostavili da igrači komuniciraju tijekom igre ili ne. Razlikujemo kooperativne i nekooperativne igre s nenul-sumom. Mi ćemo pretpostaviti da igrači ne komuniciraju, dakle razmatramo nekooperativne igre. Također, uzet ćemo da istovremeno odabiru svoje strategije i da njihov izbor nije poznat drugom igraču, kao što je to kod igara s nula-sumom. Kod igara s nenul-sumom, elementi matrice isplata su uređeni parovi, pri čemu su prve koordinate vrijednosti isplata za prvog igrača, a druge za drugog.

U igri iz Primjera 5, na primjer, ako igrač A odabere potez r_{2}, a igrač B potez s_{2}, kao isplatu dobivamo p_{22}=(8,8), kod koje su oba igrača na dobitku.

Kako i u igrama sa sumom nula nije pristuna suradnja, logično je pogledati koji se termini vezani uz igre s nula-sumom mogu proširiti na igre s nenul-sumom. Krenimo s pojmom dominacije.

Očekuje se da će razuman igrač uvijek igrati dominantnu strategiju. Kod igara sa sumom nula takva je strategija uvijek optimalna i nazivamo je ravnotežna strategija. U Primjeru 5, za igrača A strategija r_{1} dominantna je u odnosu na strategiju r_{2} jer je 0\gt -5 i 10\gt 8. Za igrača B dominantna je strategija s_{1} u odnosu na strategiju s_{2}, jer je 0\gt -8 i 8=8. Dominantne strategije igrača su X=Y=(1,0), a isplata dobivena primjenom principa dominacije p_{11}=(0,0). No, isplata p_{22}=(8,8) je povoljnija pa zaključujemo da kod nekooperativnih igara s nenul-sumom korištenje dominantnih strategija ne rezultira uvijek najboljim ishodom za igrače. Osim toga, kako kod igara s nula-sumom, tako i kod igara s nenul-sumom, dominantne strategije ne moraju postojati u igri.

Postavlja se pitanje možemo li odrediti mješovite strategije za oba igrača, takve da odabirom nekih drugih strategija niti jedan od njih neće profitirati. John Forbes Nash Jr. (1928.-2015.) je 1950. godine dokazao da svaka igra za dva igrača ima barem jedan par ravnotežnih strategija, bilo čistih, bilo mješovith (detaljnije opisano u [3]). Nash je bio američki ekonomist i matematičar, koji je dao veliki doprinos teoriji igara. Njemu u čast, ravnotežu u igrama s nenul-sumom nazivamo Nashova ravnoteža. Nashova ravnoteža imala je veliku primjenu kod donošenja poslovnih strategija te je Nash 1994. godine bio nagrađen Nobelovom nagradom za ekonomiju. Njemu u čast, 2001. godine snimljen je film Genijalni um (engl. A Beautiful Mind).

Dakle, ako neki igrač odluči tijekom igre promijeniti svoju strategiju, to mu neće omogućiti veći dobitak, u odnosu na odabir strategije kojom je uspostavljena Nashova ravnoteža, sve dok i drugi igrač ne promijeni svoju strategiju.

Promotrimo li u Primjeru 7 isplate za igrača B kao igru s nula-sumom, kao optimalnu strategiju za igrača A dobit ćemo X_{0}=\big(\frac{3}{7},\frac{4}{7}\big). Zanimljivo je da, bez obzira na to koju strategiju Y odabere igrač B, očekivani ishod igre (2) za njega je E(X_{0},Y)=\frac{32}{7}. Ako promotrimo isplate igrača A kao igru s nula-sumom, kao optimalnu strategiju za igrača B dobit ćemo Y_{0}=\big(\frac{1}{2},\frac{1}{2}\big). Bez obzira na to koju strategiju X odabere igrač A, očekivani ishod igre (2) za njega je E(X,Y_{0})=3. Par ravnotežnih strategija (X_{0},Y_{0}) za uspostavu Nashove ravnoteže pronašli smo tako da je svaki igrač promatrao isplate drugog igrača, a ignorirao svoje. Nashova ravnoteža nije baš u svakoj igri najsretnije rješenje za igrače.

Nashova ravnoteža je uspostavljena ravnotežnim strategijama X_{0}=Y_{0}=(0,1). Dobivamo isplatu p_{22}=(0,0), no isplata p_{11}=(6,6) povoljnija je za igrače. Dakle, opet postoji bolja isplata od one u Nashovoj ravnoteži.

Ako igrač A odabere potez r_{1}, za igrača B je bolje odabrati potez s_{1} te igrač A prolazi bolje, s isplatom p_{11}=(5,1). Imamo ravnotežne strategije X_{0}=Y_{0}=(1,0). Ako igrač A odabere potez r_{2}, igrač B odabire potez s_{2} i s isplatom p_{22}=(1,5) on prolazi bolje. Drugi par ravnotežnih strategija je X'_{0}=Y'_{0}=(0,1). Kada bismo igračima dozvolili komunikaciju, mogli bi se dogovoriti da kod višestrukog ponavljanja igre naizmjenično odaberu parove ravnotežnih strategija te tako oba budu na dobitku. No, u nekooperativnim igrama to ne možemo.

Djelomično rješenje problema u kojima postoje povoljnije isplate od onih dobivenih Nashovom ravnotežom, nudi Vilfredo Federico Pareto (1848.-1923.), talijanski sociolog, ekonomist i filozof.

Paretov se princip temelji na grupnoj racionalnosti, a princip dominacije na individualnoj. Igre mogu imati više Pareto optimalnih isplata, a riječ optimalna znači da nije lošija od neke druge isplate. Paretov princip glasi: Da bi isplata bila prihvatljiva kao rješenje igre, ona mora biti Pareto optimalna.

Radi lakšeg razmatranja, problem prikazujemo u koordinatnoj ravnini, s vrijednostima dobitaka za igrača A na osi apscisa te vrijednostima dobitaka za igrača B na osi ordinata. Točke u koordinatnoj ravnini predstavljaju isplate u matrici isplata, a povezane dužinama tvore mnogokut koji se naziva mnogokut isplata. Križić predstavlja isplatu dobivenu uspostavom Nashove ravnoteže, a isprekidane linije povezuju Pareto optimalne isplate.

Slika 1: Mnogokut isplata za igru iz Primjera 9

U Primjeru 9, isplata p_{22}=(0,0) nije Pareto optimalna, jer isplata p_{11}=(6,6) omogućuje bolje dobitke za oba igrača. Tri preostale isplate su Pareto optimalne.

Slika 2: Mnogokut isplata za igru iz Primjera 7

U Primjeru 7, Nashova ravnoteža ne daje dobru isplatu za igrače. Odabirom isplate p_{11}=(4,8), prikazane vrhom A, oba igrača bi se našla u boljoj situaciji.

Ishodi igara dobiveni uspostavom Nashove ravnoteže su poželjni, jer su stabilni i postoje u svakoj igri, ali često dobivene isplate nisu Pareto optimalne. Zato se javlja potreba za drugim idejama. U igrama sa sumom nula optimalne su strategije najopreznije strategije.

Odabirom vrijednosti maximin igrač A nastoji sebi osigurati najveći minimalni dobitak, a igrač B želi sebi osigurati najmanji maksimalni gubitak odabirom ishoda minimax. Ako postoji sedlo, u igri s nula-sumom za oba je igrača najbolje igrati sedlo.

Pogledajmo ponašanje ovakvih strategija u kontekstu igara s nenul-sumom. Za igru iz Primjera 7, potražimo povoljniji ishod od onog dobivenog uspostavom Nashove ravnoteže. Uzmimo da igrač A želi maksimizirati minimalni dobitak. Gledajući njegove isplate, vidimo da je najmanji element u prvom retku 2, a u drugom 0. Kako je 2\gt 0, igrač A će potezom r_{1} osigurati dobitak vrijednosti najmanje 2.

Dakle, odabirom razborite strategije, igrač A osigurava najmanje onaj dobitak koliko iznosi njegov sigurnosni nivo. U Primjeru 7 razborita strategija igrača A je X=(1,0), a sigurnosni nivo je 2. To je ujedno i sedlo za igru igrača A.

U igri igrača B ne postoji sedlo. Razborita stategija Y=(\frac{4}{7},\frac{3}{7}) za igrača B dobiva se rješavanjem matrične igre s nula-sumom. Njegov sigurnosni nivo iznosi \frac{32}{7}. Ako igrači odigraju svoje razborite strategije, ishod igre (2) je E(X,Y)=\frac{4}{7}(4,8)+\frac{3}{7}(2,0)=(\frac{22}{7},\frac{32}{7}). Taj ishod nije Pareto optimalan, niti dobiven uspostavom Nashove ravnoteže. Isplata p_{11}=(4,8) je bolja za oba igrača. Ukoliko očekuje da će igrač A odigrati svoju razboritu strategiju, igrač B bi odabirom strategije Y=(1,0) sebi osigurao dobit vrijednosti 8. Analogno, ako očekuje da će igrač B odabrati svoju razboritu stretegiju, igrač A odabirom poteza r_{1} dobiva \frac{4}{7}\cdot 4+\frac{3}{7}\cdot 2=\frac{22}{7}, a odabirom poteza r_{2} dobiva \frac{4}{7}\cdot 6+\frac{3}{7}\cdot 0=\frac{24}{7}. Svaki igrač trebao bi potražiti najbolji odgovor na razboritu strategiju drugog igrača.

Ključne riječi: sustavi glasovanja da-ne, indeksi snage, Shapley-Shubik indeks, Banzhaf indeks, Johnston indeks, Deegan-Packel indeks

Jedan od vrlo važnih pojmova političke znanosti jest snaga. Promotrimo snagu glasovanja u sustavima glasovanja da-ne, gdje glasači (tj. "igrači") imaju određeni utjecaj na donošenje nekih odluka. U smislu formalnog glasovanja, smatra se da je potrebna apsolutna većina za donošenje odluka odnosno određena kvota. Stoga, za prihvaćanje odluka (zakona) treba promatrati pobjedničke koalicije.

Radi kvantitativnog mjerenja snage glasovanja odgovarajućih igrača (primjerice, stranaka u skupštini), predloženi su određeni indeksi glasačke ili političke snage (http://homepages.warwick.ac.uk/~ecaae/links.html, http://powerslave.utu.fi/ ). Neki poznati indeksi snage su Shapley-Shubik indeks, Banzhaf indeks, Johnston indeks, Deegan-Packel indeks (Taylor1995, Cortona1999, Matsui2000, Marosevic2016). Opišimo glavna svojstva ovih indeksa.

Neka je X=\lbrace p_{1}, p_{2}, \ldots, p_{n}\rbrace skup od n igrača u težinskim sustavima glasovanja da-ne, gdje su dane pripadne težine s_{k} igrača p_{k}, k=1,\ldots,n, tako da je s_{k} broj glasova igrača p_{k}. Koalicija C jest bilo koji podskup skupa X. Također, pretpostavimo da je dana kvota q koja je potrebna da bi koalicija pobijedila. Ako je ispunjena nejednakost \sum_{p_{k}\in C} s_{k} \geq q, onda se koalicija C\subseteq X naziva pobjednička koalicija.

Predložen je 1954. god. ([5]). Tu se gleda uređaje (permutacije) igrača. Za uređaj p_{\sigma_{1}}p_{\sigma_{2}}\ldots p_{\sigma_{n}}, jedan od igrača p_{\sigma_{k}} naziva se pivot (tj. pivotni igrač), ako koalicija koja nije pobjednička, p_{\sigma_{1}}p_{\sigma_{2}}\ldots p_{\sigma_{k-1}}, pripajanjem igrača p_{\sigma_{k}} postaje pobjednička koalicija p_{\sigma_{1}}p_{\sigma_{2}}\ldots p_{\sigma_{k-1}}p_{\sigma_{k}}.

Shapley-Shubik indeks igrača p_{k} jest udio permutacija za koje je p_{k} pivotni igrač ([7]), odnosno definira se na sljedeći način.

Primijetimo da je nazivnik u gornjem izrazu jednak n!. Opišimo izračunavanje indeksa SSI jednim primjerom.

Primjer 2. Neka četiri stranke \lbrace p_{1}, p_{2}, p_{3}, p_{4}\rbrace =\lbrace A,B,C,D\rbrace čine skupštinu, sa sljedećim brojem njima pripadnih zastupnika (tj. težinama glasovanja) redom: s_{A}=40, s_{B}=30, s_{C}=20, s_{D}=10. Neka je kvota q=51, što ovdje predstavlja nadpolovičnu većinu. Stoga, da bi koalicija stranaka bila pobjednička, mora ukupno imati barem 51 glasova ili više.

Stranka A ne može biti pivotni element kada je u permutacijama na prvom mjestu, jer s_{A}=40\lt 51. Također, A ne može biti pivotni element kada je u permutacijama na četvrtom mjestu, jer s_{B}+s_{C}+s_{D}=60\gt 51. No, stranka A je pivotni element na drugom mjestu u permutacijama oblika: B A . . ;  C A . . , kojih ima 2!\cdot 2. Nadalje, stranka A je pivotni element na trećem mjestu u permutacijama oblika: . . A B ;  . . A C ;  . . A D , kojih ima 2!\cdot 3. Stoga, po izrazu (1) dobivamo SSI(A)=\frac{2!\cdot 5}{4!}=\frac{5}{12}.

Za stranku B analogno se zaključuje. Ona također ne može biti pivotni element kada je u permutacijama na prvom mjestu, niti kada je u permutacijama na četvrtom mjestu. B jest pivotni element na drugom mjestu u permutacijama oblika: A B . . , kojih ima 2!\cdot 1, te B jest pivotni element na trećem mjestu u permutacijama oblika: . . B A ;  . . B C , kojih ima 2!\cdot 2. Stoga, SSI(B)=\frac{2!\cdot 3}{4!}=\frac{3}{12}.

Za stranku C analogno se zaključuje kao za B i dobiva SSI(C)=\frac{2!\cdot 3}{4!}=\frac{3}{12}.

Stranka D je pivotni element jedino na trećem mjestu u permutacijama oblika: . . D A, pa je SSI(D)=\frac{2!\cdot 1}{4!}=\frac{1}{12}.

Dobivene SSI indekse snage stranaka navodimo i u Tablici 1, a ilustriramo na Slici 1. Vidimo da su vrijednosti tih SSI indeksa stranaka različiti od udjela zastupnika stranaka u skupštini.

Slika 1: Grafički prikaz SSI indeksa snage stranaka iz Primjera 1.

 

Predložen je 1965. god. ([5]). Prvo se definira ukupna Banzhaf snaga igračap_{k}, s oznakom TBP(p_{k}), kao broj koalicija C koje ispunjavaju sljedeće uvjete:

a) p_{k}\in C;  b) C je pobjednička koalicija;  c) C\setminus\lbrace p_{k}\rbrace nije pobjednička koalicija.

U tom slučaju uklanjanje p_{k} dovodi do toga da koalicija C\setminus \lbrace p_{k}\rbrace nije pobjednička, odnosno kaže se da izlazak p_{k} iz koalicije C jest kritičan ([7]). Stoga imamo sljedeću definiciju.

Kod Banzhaf indeksa snage uzimaju se u obzir kritični izlasci iz pobjedničkih koalicija. Opišimo izračunavanje indeksa BI primjerom.

Kod pobjedničkih koalicija može se promatrati ukupan broj igrača čiji izlazak iz dane koalicije je kritičan. Uzimajući to u obzir, Johnston indeks snage definira se ovako ([7]).

Pretpostavimo da su C_{1}, \ldots,C_{m} one pobjedničke koalicije kod kojih je igrač p_{k} kritičan. Neka je n_{1} broj onih igrača čiji izlazak iz C_{1} je kritičan, n_{2} je broj onih igrača čiji izlazak iz C_{2} je kritičan, i tako dalje, n_{m} je broj onih igrača čiji izlazak iz C_{m} je kritičan, Tada se definira ukupna Johnston snaga igračap_{k}} ovako:

Prikažimo izračunavanje indeksa JI primjerom.

Godine 1978. Deegan and Packel ([5, 7]) uveli su indeks snage vrlo sličan kao Johnston indeks, ali zasnovan na minimalnim pobjedničkim koalicijama. (Minimalna pobjednička koalicija jest ona pobjednička koalicija koja neće više biti pobjednička koalicija, ako bilo koji njezin član izađe iz nje). Stoga, Deegan-Packel indeks snage definira se na sljedeći način.

Neka su C_{1}, \ldots,C_{j} minimalne pobjedničke koalicije kojima pripada igrač p_{k}. Neka je |C_{1}| broj članova C_{1}, |C_{2}| broj članova C_{2}, \ldots ,|C_{j}| broj članova C_{j}. Tada se definira ukupna Deegan-Packel snaga igračap_{k} ovako:

Prikažimo izračunavanje indeksa DPI primjerom.

Iz prethodnih definicija očito jest da indeksi snage imaju vrijednosti između 0 i 1. Te indekse može se izraziti i u postotcima.

Na slici 2 ilustriramo navedene indekse snage u slučaju četiri stranke iz prethodnih Primjera 1 - 4.

Slika 2: Grafički prikaz indeksa političke snage iz Primjera 1 - 4.

Izračunavanje indeksa snage u složenijim slučajevima je komplicirano, što ovdje nećemo razmatrati. Postoje brojne metode za izračunavanje pojedinih indeksa snage, pomoću algoritama prebrojavanja ([2, 5]). Također, na internetskim stranicama može se naći "online" kalkulator raznih indeksa snage (primjerice, [6, 3], http://powerslave.utu.fi/calculate.html, http://homepages.warwick.ac.uk...).

U drugom dijelu opisujemo indekse snage još na nekim primjerima i u slučaju Europskog parlamenta.

Slika 3: Grafički prikaz indeksa snage stranaka A, B i C u Primjeru 5.

Na slici 4 prikazani su navedeni indeksi snage u slučaju tri stranke iz Primjera 6.

Slika 4: Grafički prikaz indeksa snage stranaka A, B i C u Primjeru 6.

Napomena. Spomenuti indeksi snage stranaka ovise o kvoti q. Primjerice, ako se za podatke iz Primjera 6. definira da je kvota q=67 (to je dvotrećinska većina), dobit će se drugačije vrijednosti indeksa snage, koje navodimo u Tablici 3a.


 

Primjer 11.

Promotrimo osmi saziv Europskog parlamenta, koji se sastoji od 751 članova. Stoga, kvota q=376 predstavlja nadpolovični broj glasova. U ovom primjeru pogledajmo podjelu zastupnika po državama koje predstavljaju, odnosno na n=28 europskih držžava iz kojih dolaze ([8]). Odgovarajući brojevi zastupničkih mjesta s_{k} u Europskom parlamentu koje pripadaju pojedinim državama-članicama (k=1,\ldots,n=28) dani su u Tablici 4 (s pripadajućim postotcima).

Nadalje, u Tablici 4 navedeni su i pripadni indeksi snage tih država, izračunati pomoću [6] (bez Johnston indeksa). To su formalni indeksi snage država-članica, jer zastupnici u Europskom parlamentu pripadaju pojedinim političkim skupinama ovisno o svjetonazoru (npr. pučani, socijalisti, liberali, slobodnjaci, ...), a ne ovisno o državama.

Tablica 4. Sastav 8. saziva Europskog parlamenta po državama-članicama u 2015. god., te pripadni indeksi snage.

 

država	broj zastupnika (\%)	indeks SSI	indeks BI	indeks DPI
1 Njemačka	96 (12.78\%)	0.13724	0.13656	0.03873
2 Francuska	74 (9.85\%)	0.10183	0.10017	0.03748
3: Italija	73 (9.72\%)	0.10031	0.09868	0.03746
Velika Britanija	73 (9.72\%)	0.10031	0.09868	0.03746
4 Španjolska	54 (7.19\%)	0.07211	0.07132	0.03673
5 Poljska	51 (6.79\%)	0.06782	0.06709	0.03659
6 Rumunjska	32 (4.26\%)	0.04147	0.04171	0.03607
7 Nizozemska	26 (3.46\%)	0.03343	0.03377	0.03593
8: Belgija	21 (2.80\%)	0.02683	0.02721	0.03568
Češka	21 (2.80\%)	0.02683	0.02721	0.03568
Grčka	21 (2.80\%)	0.02683	0.02721	0.03568
Mađarska	21 (2.80\%)	0.02683	0.02721	0.03568
Portugal	21 (2.80\%)	0.02683	0.02721	0.03568
9 Švedska	20 (2.66\%)	0.02553	0.02592	0.03567
10 Austrija	18 (2.40\%)	0.02293	0.02331	0.03559
11 Bugarska	17 (2.26\%)	0.02162	0.02200	0.03553
12: Finska	13 (1.73\%)	0.01645	0.01681	0.03542
Danska	13 (1.73\%)	0.01645	0.01681	0.03542
Slovačka	13 (1.73\%)	0.01645	0.01681	0.03542
13: Irska	11 (1.465\%)	0.01389	0.01422	0.03533
Hrvatska	11 (1.465\%)	0.01389	0.01422	0.03533
Litva	11 (1.465\%)	0.01389	0.01422	0.03533
14: Latvija	8 (1.065\%)	0.01006	0.01033	0.03491
Slovenija	8 (1.065\%)	0.01006	0.01033	0.03491
15: Cipar	6 (0.80\%)	0.00752	0.00775	0.03406
Estonija	6 (0.80\%)	0.00752	0.00775	0.03406
Luksemburg	6 (0.80\%)	0.00752	0.00775	0.03406
Malta	6 (0.80\%)	0.00752	0.00775	0.03406

Na slici 5 prikazana su tri indeksa snage za slučaj 28 država članica u Europskom parlamentu razdijeljenih u 15 skupina po broju svojih zastupnika, iz Primjera 7.

Slika 5: Grafički prikaz indeksa političke snage u Primjeru 7.

 

Iz navedenih primjera može se zamijetiti da su Shapley-Shubik indeks (SSI), Banzhaf indeks (BI) i Johnston indeks (JI) monotone funkcije ovisne o broju mjesta (glasova) koje pojedina stranka ima, no nisu linearne funkcije. Napomenimo da Deegan-Packel indeks (DPI) općenito ne mora biti monotona funkcija od broja mjesta, jer kod DPI indeksa uzimaju se u obzir jedino minimalne pobjedničke koalicije.

Spomenimo da se indeksi snage stranaka mogu modificirati, tako da se ne uzimaju u obzir sve pobjedničke koalicije, već samo suženi skup politički mogućih pobjedničkih koalicija ([1]). Kod takvih modifikacija indeksa snage gledaju se samo pobjedničke koalicije sastavljene od onih stranaka koje nisu politički i svjetonazorski udaljene.{10}