Matricne Igre čolić.doc

Fakultet Tehnicki fakultet “Mihajlo Pupin” Grad Zrenjanin

SEMINARSKI RAD IZ PREDMETA FINANSIJSKA MATEMATIKA TEMA : Proste matricne igre

Profesor: Prof. dr Momčilo Bjelica

Ime studenta : Irena Colic Broj indeksa : 128/09-08

BEOGRAD,APRIL 2014

PROSTE MATRIČNE IGRE

UVOD 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. Analizirajmo igru dva igraca sa nultom sumom u normalnoj formi,za slucaj kada svakom od igraca stoji na raspolaganju odredjeni,konacan broj strategija.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 placanja 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 optimalna strategija, matrica plaćanja, matricne igre

Pretpostavimo da imamo igru u kojoj učestvuju dva igraca,igrac 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:

Za potrebe analize i resavanja igre matrica plaćanja se često prikazuje u vidu odgovarajuće tabele:

Strategije igrača A su predstavljene vrstama matrice plaćanja,dok su strategije igrača B predstavljene kolonama.Kao što vidimo elementi matrice plaćanja pokazuju koliko će iznositi dobitak za igrača A,odnosno igrača B,u slučaju izbora bilo koje od mogućih kombinacija(para)strategija koje im stoje na raspolaganju.Igra dva lica sa nultom sumom,predstavljena predhodnom matricom plaćanja realizuje se u uslovima kada igrači prilikom izbora bilo koje od strategija ne znaju koju ce strategiju izabrati protivnik. Svaki od igrača,ne znajući izbor protivnika,vrši prdhodnu analizu mogućih dobitaka,odnosno gubitaka.Igrač A,zbog toga,za svaku čistu strategiju Ai(i=1,2,...,m) odredjuje minimalan dobitak koji će ostvariti bez obzira na izbor strategije igrača B,tj. opredeljuje minimalan element 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 mi 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 Ovim je predstavljeno ispitivanje matrice plaćanja kod prostih, kao i kod mešovitih matričnih igara.

LITERATURA Prof.dr Zelimir Branovic (2006), Poslovna matematika kroz primere i zadatke, Tehnički fakultet Mihajlo Pupin" Zrenjanin