Radman Matricne Igre.doc

Univerzitet u Novom Sadu Tehnički fakultet „Mihajlo Pupin“ u Zrenjaninu

Proste Matricne Igre (seminarski rad iz Finasijske matematike)

Pofesor:

Ime studenta, smer i broj indeksa

Prof. dr Momčilo Bjelica

Marica Radman Odevne tehnologije 19/10-04

Zrenjanin, Jul 2013. god.

PROSTE MATRIČNE IGRE APSTRAKT Postoji više različitih klasifikacija igara zavisno od kriterijuma koji je uzet u obzir. Međutim, razmatranje suštine teorije igara najčešće počinje razmatranjem prostih matričnih igara odnosno strogo determinisanih igara. Proste matrične igre su igre u kojima postoje dva igrača (to su, dakle, parne igre) koji raspolažu sa nekoliko različitih strategija. Interakcija između strategija dva igrača data je preko takozvane matrice plaćanja koja determiniše dobitke odnosno gubitke igrača zavisno od izabrane strategije. Matrična igra je u potpunosti određena matricom plaćanja. Ključne reči matrica plaćanja, optimalna strategija, matricne igre

UVOD Pretpostavimo da u igri učestvuju igrač P i igrač Q. Ako igrač P raspolaže sa m različitih strategija, a igrač Q sa n različitih strategija, onda će pravila igre biti određena sledećom matricom:

Ova se igra realizuje u uslovima kada igrači prilikom izbora bilo koje od strategija ne znaju koju će strategiju izabrati protivnik. Igrač A želi da izabere strategiju koja će mu doneti maksimalno mogući dobitak. Pri tome, svaki od igrača podrazumeva racionalno ponašanje svog protivnika, tj. njegovo stremljenje da u uslovima igre definisanim datom matricom plaćanja ostvari za sebe najpovoljniji rezultat (Branović, 2006). Svaki od igrača, ne znajući izbor protivnika, vrši prethodnu analizu mogućih dobitaka, odnosno gubitaka. Igrač A, zbog toga, za svaku čistu strategiju A i (i=1,2,...,m) određuje minimalan dobitak koji će ostvariti bez obzira na izbor strategije igrača B, tj. opredeljuje minimalan elemenat svake od vrsta matrice plaćanja u obliku αi = min aij i = 1,2,...,m j

Između svih ovako određenih minimalnih dobitaka za pojedine strategije, igrač A bira maksimalni element u obliku

α = max ai = max min aij i

i

j

koji predstavlja tzv. maksimin vrednost, odnosno donju granicu vrednosti igre, koja pokazuje garantovani dobitak koji će igrač A ostvariti. Ova donja granica određuje i optimalnu strategiju za igrača A , čijim izborom dobitak od α jedinica za njega ne može biti umanjen bez obzira na izbor strategije od strane njegovog protivnika (igrača B). Prema Branović, 2006, slična analiza izbora pojedinih strategija se može izvršiti i za igrača B, koji nastoji da odabere takve strategije koje mu obezbeđuju ninimalizaciju gubitaka. Zbog toga on, za svaku od svojih strategija koje su predstavljene kolonama matrice plaćanja, izračunava maksimalne gubitke, tj. određuje vrednosti βj = max aij

j = 1,2,...,n

i

Minimalan od ovako određenih elemenata, odnosno vrednost: β = min βj = min max aij j

j

i

predstavlja gornju granicu vrednosti igre, odnosno minimaks vrednost za igrača B. Kao racionalan učesnik u igri, on će ovu vrednost smatrati optimalnom strategijom, jer mu ona obezbeđuje poziciju u kojoj nikakav izbor strategije od strane igrača A ne može povećati njegov gubitak iznad vrednosti β. Izborom optimalnih strategija od strane oba igrača oni obezbeđuju najpovoljniji rezultat i opredeljuju se za način igre u kome će rizik usled različitog broja strategija od strane protivnika svesti na minimum.■

Primer: Neka je igra predstavljena sledećom matricom plaćanja: 2 -3 P= 7

5 2 4

4 6 3

0 1 8

4

2

1

5

Na osnovu sledeće tabele:

sledi da igrač A treba da odabere svoju treću strategiju kao optimalnu, jer mu ona obezbeđuje

α = max αi = max min aij = 3, dok je za drugog igrača optimalna njegova druga strategija za koju se ostvaruje gornja granica vrednosti igre β = min βj = min max aij = 5.▲ Da izračunata vrednost minimalnih dobitaka za igrača A nije nikada veća od vrednosti maksimalnih gubitaka za igrača B (kao što je to u ovom primeru) pokazuje i sledeće tvrđenje:

TVRĐENJE U matričnoj igri gornja granica vrednosti igre je uvek veća ili jednaka od donje granice vrednosti igre, tj. β≥α . Tačnost ovog tvrđenja sledi iz činjenice da je βj= max aij ≥ aij za svako i

j = 1,2,..., n, dok je αi = min aij ≤ aij za i = 1,2,...,m. j

Iz ove dve nejednakosti sledi da je βj = max aij ≥ aij ≥ min aij = αi i

j

odakle je βj ≥ αi . Kako navedeno važi za svako i i j može se zaključiti da je i β ≥α . Ukoliko je u matričnoj igri donja granica vrednosti igre jednaka gornjoj granici, tj. α = β , takva igra je prosta matrična igra i zove se igra sa sedlastom tačkom , ili prosto igra sa sedlom. Sedlasta tačka se nalazi na preseku optimalnih strategija igrača, i vrednost elementa koji u matrici plaćanja odgovara sedlastoj tački pokazuje vrednost igre, odnosno dobitak za igrača A i gubitak za igrača B koji iznosi v = α =β . Rešavanje proste matrične igre otuda predstavlja postupak određivanja optimalnih čistih strategija igrača A i B, sedlaste tačke i vrednosti igre.■

STROGO DETERMINISANE IGRE Za igru koja je određena matricom plaćanja A kažemo da je strogo determinisana u slučaju da matrica A sadrži element aij (i = 1, 2, ..., n, j = 1, 2, ..., m) za koji važi da je najmanji u vrsti odnosno najveći u koloni. Takav element matrice plaćanja naziva se sedlasta tačka, a igre čije matrice plaćanja sadrže takav element nazivaju se igre sa sedlastom tačkom.

Primer: U matričnoj igri igrač A ima na raspolaganju tri strategije, dok igrač B raspolaže dvema strategijama. Efekti igre, u zavisnosti od izabranih strategija dati su u tabeli:

Odrediti vrednost igre i optimalne strategije igrača. Odgovor. Igrač A od minimalnih vrednosti bira maksimalnu, tj. α = max ( -25, -10, -15 ) = -10 (gubitak); a igrač B od maksimalnih vrednosti bira minimalnu, tj. β = min ( 15, -10 ) = -10 (dobitak). Kako je α = β = v = -10 to znači da igra ima ravnotežnu (sedlastu ) tačku. Optimalna čista strategija za igrača A je strategija A 2, jer uz pomoć nje on ostvaruje minimalni gubitak od 10 novčanih jedinica. Za igrača B je optimalna čista strategija B 2, jer pomoću nje ostvaruje siguran dobitak od 10 jedinica.

MATRIČNE IGRE SA MEŠOVITIM STRATEGIJAMA Različite vrste mešovitih matričnih igara, zavisno od vrsta i dimenzija matrica plaćanja, rešavaju se na različite načine. Igre sa matricama plaćanja reda 2 x n ili m x 2 se rešavaju dosta jednostavno, grafički ili analitički. U slučaju kada je m > 2 i/ili n > 2, pokušavaju se na neki način uprostiti odgovarajuće matrice, a ako takvo uprošćavanje nije moguće koriste se druge metode (npr. linearnog programiranja). Svakako da je najjednostavniji slučaj kada oba igrača imaju na raspolaganju samo po dve strategije, a i matrica plaćanja je reda 2 x 2, zapisana u obliku:

P

a1 a12 a21a22

čiji elementi pokazuju dobitke igrača A, odnosno gubitke igrača B, u slučaju izbora bilo koje od 4 moguće kombinacije njihovih strategija Ukoliko nije u pitanju takva igra pristupa se određivanju donje i gornje vrednosti igre i njihovom izjednačavanju. U slučaju sa po dve strategije neophodna je pretpostavka da su sve strategije aktivne što če se ispuniti da ako je a11> a12 onda je a21< a22 i obrnuto. Ako je x = ( x1, x2 = 1 – x1) mešovita strategija igrača A, odnosno y= (y1, y2 = 1 – y1) mešovita strategija igrača B tada se jednačine koje moraju biri zadovoljene za optimalne mešovite strategije zapisuju u obliku: Za igrača A : a11 x1 + a21 x2 = v a12 x1 + a22 x2 = v x1 + x2 = 1

Prva i druga jednačina pokazuju moguće dobitke za igrača A koje će on ostvariti u slučaju izbora prve, odnosno druge strategije od strane igrača B, respektivno, dok je treća jednačina posledica raspodela verovatnoća po strategijama. Očigledno je da se iz navedenog sistema jednačina dobija a11 x1 + a21(1 - x1) = a12 x1 + a22(1 – x1 ) , a odavde je x1 = ( a22 – a21) / (a11 – a12 – a21 + a22), a kako je x2 = 1 – x1 , to je i x2 = ( a11 – a12) / (a11 – a12 – a21 + a22) pa je vrednost igre v = ( a11 a22 – a21 a12) / (a11 – a12 – a21 + a22) Isto tako, izračunavanjem gornje granice igre, koju će igrač B ostvariti u slučaju izbora prve i druge strategije od strane igrača A, dobija se sistem jednačina a11 y1 + a12 y2 = v a21 y1 + a22 y2 = v y1 + y2 = 1

Primer: Neka su dati matrica plaćanja i mešovite strategije u oblik x = (0,45 0,20 0,35) ;

y = (0,30 0,20 0,15 0,35) To znači da igrač A od ukupnog broja poteza u 45 % slučajeva igra svoju prvu strategiju, u 20 % slučajeva drugu, ..., ili da igrač B koristi svoje 4 strategije tako što u 30 % slučajeva bira prvu od njih,..., u 35 % slučajeva četvrtu po redu. Vrednost igre je

Dobijeni rezultat znači da će u svakom od poteza igrač A dobijati prosečno po 1,9075 novčanih jedinica, dok će toliko isto igrač B gubiti.

ZAKLJUČAK U radu je pokazano kako se ispituje matrica plaćanja kod prostih, kao i kod mešovitih matričnih igara. Ovaj rad je osnova za dalje razumevanje mešovitih matričnih igara.

LITERATURA Branović Ž. (2006), Poslovna matematika kroz primere i zadatke, Tehnički fakultet "Mihajlo Pupin" Zrenjanin