Matematičke metode i modeli u ekonomiji

Matrične igre

Uvod

U ekonomskoj praksi često se javljaju situacije u kojima različite strane težiti različitim ciljevima. Na primjer, odnos između prodavca i kupca, dobavljača i potrošača, banke i deponenta, itd. Takve konfliktne situacije nastaju ne samo u privredi, već iu drugim vrstama djelatnosti. Na primjer, kada igrate šah, dame, domine, loto itd.

Igra je matematički model konfliktne situacije u kojoj su uključene najmanje dvije osobe koristeći nekoliko na razne načine da postignete svoje ciljeve. Igra se zove parna soba, ako uključuje dva igrača. Igra se zove antagonistički, ako je dobitak jednog igrača jednak gubitku drugog. Stoga je za postavljanje igre dovoljno postaviti dobitne vrijednosti jednog igrača u različitim situacijama.

Poziva se bilo koja metoda djelovanja igrača ovisno o trenutnoj situaciji strategija. Svaki igrač ima određeni skup strategija. Ako je broj strategija konačan, onda se igra zove krajnji, inače - beskrajno . Strategije se zovu čisto, ako svaki igrač odabere samo jednu strategiju na specifičan, a ne nasumičan način.

Rešenje za igru je odabrati strategiju koja zadovoljava stanje optimalnosti. Ovaj uslov je da jedan igrač dobije maksimalna pobeda, ako se drugi drži svoje strategije. Suprotno tome, drugi igrač prima minimalni gubitak, ako se prvi igrač drži svoje strategije. Takve strategije se nazivaju optimalno . dakle, Cilj igre je odrediti optimalnu strategiju za svakog igrača.

Čista strateška igra

Zamislite igru ​​sa dva igrača A I IN. Pretpostavimo da je igrač A Ima m strategije A 1, A 2, …, A m, i plejer IN Ima n strategije B 1, B 2, …, B n. Pretpostavićemo da je izbor igrača A strategije A i, i plejer IN strategije Bj jednoznačno određuje ishod utakmice, tj. dobitke a ij igrač A i dobitke b ij igrač IN. Evo i=1,2,…,m, j=1,2,…,n.

Najjednostavnija igra sa dva igrača je igra sa nultom sumom. , one. igra u kojoj su interesi igrača direktno suprotstavljeni. U ovom slučaju, isplate igrača su povezane jednakošću

b ij =-a ij

Ova jednakost znači da je dobitak jednog igrača jednak gubitku drugog. U ovom slučaju, dovoljno je uzeti u obzir samo dobitke jednog od igrača, na primjer, igrača A.

Svaki par strategija A i I Bj odgovara dobitku a ij igrač A. Zgodno je sve ove dobitke zapisati u obliku tzv matrica plaćanja

Redovi ove matrice odgovaraju strategijama igrača A, a kolone – strategije igrača IN. Općenito, takva igra se zove (m×n)-igra.

Primjer 1. Dva igraca A I IN baci novčić. Ako se strane novčića poklapaju, on pobjeđuje A, tj. igrač IN plaća igrača A određeni iznos jednak 1, a ako se ne poklapaju, onda igrač B pobjeđuje, tj. naprotiv, igrač A plaća igrača IN isti iznos , jednak 1. Kreirajte matricu plaćanja.

Rješenje. Prema uslovima problema

Mješovita strategija SA igrača A je korištenje čistih strategija A1, A2, ..., Am sa vjerovatnoćama p1, p2, ..., pi, ..., pm i suma vjerovatnoća je jednaka 1: Mješovite strategije igrača A zapisuju se u obliku matrice ili u obliku niza SA = (p1, p2, ..., pi, ..., pm) Slično, mješovite strategije igrača B se označavaju: , ili, SB = (q1, q2, ..., qi, ..., qn ), gdje je zbir vjerovatnoća pojave strategija jednak 1: Čiste strategije se mogu smatrati posebnim slučajem mješovitih i može se specificirati linijom u kojoj 1 odgovara čistoj strategiji. Određuje se na osnovu principa minimaksa optimalno rešenje(ili rješenje) igre: ovo je par optimalnih strategija S*A, S*B, općenito pomiješanih, koji imaju sljedeće svojstvo: ako se jedan od igrača pridržava svoje optimalne strategije, onda to ne može biti isplativo za drugog odstupiti od njegovog. Isplata koja odgovara optimalnom rješenju naziva se cijena igre v. Cijena igre zadovoljava nejednakost: ? ? v? ? (3.5) gdje? I? - donje i gornje cijene igre. Tačna je sljedeća osnovna teorema teorije igara – Neumannova teorema. Svaka konačna igra ima barem jedno optimalno rješenje, moguće među mješovite strategije. Neka je S*A = (p*1, p*2, ..., p*i, ..., p*m) i S*B = (q*1, q*2, ..., q* i, ..., q*n) je par optimalnih strategija. Ako je čista strategija uključena u optimalnu mješovitu strategiju s vjerovatnoćom različitom od nule, tada se naziva aktivnom. Teorema o aktivnim strategijama je tačna: ako se jedan od igrača pridržava svoje optimalne mješovite strategije, tada isplata ostaje nepromijenjena i jednaka je cijeni igre v, ako drugi igrač ne prelazi granice svojih aktivnih strategija. Ova teorema je od velike praktične važnosti – pruža specifične modele za pronalaženje optimalnih strategija u odsustvu sedlo. Razmotrimo igru ​​veličine 2x2, što je najjednostavniji slučaj konačne igre. Ako takva igra ima sedlo, onda je optimalno rješenje par čistih strategija koje odgovaraju ovoj tački. Igra u kojoj nema sedla, u skladu s glavnom teoremom teorije igara, postoji optimalno rješenje i određeno je parom mješovitih strategija S*A = (p*1, p*2) i S*B = (q*1, q*2) . Da bismo ih pronašli, koristimo teoremu o aktivnim strategijama. Ako se igrač A pridržava svoje optimalne strategije S "A, tada će njegova prosječna isplata biti jednaka cijeni igre v, bez obzira koju aktivnu strategiju koristi igrač B. Za igru ​​2x2, svaka čista strategija protivnika je aktivna ako nema sedla za igrača A (gubitak igrača B) je slučajna varijabla, čije je matematičko očekivanje (prosječna vrijednost) cijena igre jednako v za 1. i 2. strategiju protivnika. Neka igra bude postavljena na isplatu. 1. kolona matrice plaćanja P), jednaka je cijeni igre v: a11 p*1+ a21 p*2= v. prosječnu isplatu prima igrač A ako drugi igrač koristi strategiju B2, tj. a12 p*1+ a22 p*2= v. Uzimajući u obzir da je p*1+ p*2= 1, dobijamo sistem jednačina za određivanje optimalne strategije S"A i cijene igre v: (3.6) Rješavanje ovog sistema, dobijamo optimalnu strategiju (3.7) i cenu igre (3.8). Primjenom teoreme o aktivnim strategijama pri pronalaženju SV* - optimalne strategije igrača B, dobijamo da je za bilo koju čistu strategiju igrača A (A1 ili A2) prosjek gubitak igrača B jednak je cijeni igre v, tj. (3.9) Tada je optimalna strategija određena formulama: (3.10)

Opis bimatrične igre. Sve igre koje su pregledane pripadale su klasi igre sa nultom sumom. Međutim, brojne konfliktne situacije koje nastaju u toku delovanja karakteriše činjenica da dobitak jedne strane nije baš jednak gubitku druge. Teorijski modeli igara Slične situacije su nekooperativne igre bez sume. Takve igre se nazivaju bimatričnim jer se zadatak svake takve igre svodi na zadatak dvije matrice istog oblika: .

Proces bimatrična igra sastoji se u nezavisnom izboru od strane igrača I broja i igrača II broja, nakon čega igrač I dobija, a igrač II dobija pobedu.

Pozivaju se brojevi redova matrica čiste igračke strategije I, a brojevi kolona ovih matrica su čiste igračke strategije II. Tada će parovi forme biti situacije u čistim strategijama bimatrična igra, te brojevi i isplate igrača I i II u situaciji. Prema tome, distribucija vjerovatnoće korištenja čistih strategija igrača I je i igrač II - zvaćemo mješovite strategije. Tada parovi oblika predstavljaju situacije bimatrična igra V mješovite strategije, i brojevi I su matematička očekivanja pobjede za igrače I i II.

Situacija ravnoteže bimatrične igre u mješovitim strategijama zvaćemo takav par za koji:

(8.2)

gdje je matematičko očekivanje pobjedničkog igrača I;

Matematičko očekivanje pobjede za igrača II;

Optimalno miješano strategija igrača I;

Optimalno miješano strategija igrača II.

Zadatak

Konstrukcija i rješenje bimatrične igre. Pretpostavimo da je protivpodmornica Podmornica Zemlja traga za državnom raketnom podmornicom koja manevrira u strogo definisanom dijelu područja borbenog patroliranja. Ostatak područja upravlja protupodmorničkom podmornicom, koja provodi operacije protupodmorničke potrage. Neka svaki protupodmornički čamac koristi vlastitu hidroakustičku stanicu za otkrivanje neprijatelja ili u aktivnom načinu rada, povremeno ga uključuje, ili samo u pasivnom načinu, obavljajući kontinuiranu pretragu.

I protivpodmornica i raketna podmornica sa sonarnom detekcijom mogu izbjeći neprijatelja. Međutim, frekvencija aktivacije sonara čini detekciju mogućim, ali nepouzdanim.

U takvoj konfliktnoj situaciji, jedan od igrača je protivpodmornica, a drugi protivpodmornica Očigledno, raketna podmornica ne može biti igrač, jer ima samo jedan način djelovanja, a to je manevar. i izvodi manevre izbjegavanja dok detektuje sonarne signale.

Karakteristično je da svaki od igrača teži različitim, ali ne i suprotnim ciljevima. Zaista, svrha protupodmorničke podmornice je da otkrije raketnu podmornicu, a svrha protupodmorničke podmornice je da otkrije protupodmorničku podmornicu. Dakle, za procjenu ostvarenja cilja od strane svakog igrača, u zavisnosti od odabranih metoda djelovanja (strategija), potrebno je imati dva kriterija efikasnosti i, shodno tome, dvije funkcije isplate. Tada će model takve konfliktne situacije biti konačna igra s nenultim zbrojem, opisana s dvije matrice istog oblika I , nazvan bimatrix.

Uzmimo to kao kriterij učinka protupodmorničku podmornicu (igrač I) vjerovatnoću otkrivanja raketne podmornice, i za kriterij učinka anti-submarine submarine (player II) – vjerovatnoća otkrivanja protupodmorničke podmornice. Tada će bimatrična igra biti data matricom (slika 9.a) i matricom (slika 9.b).

Gdje - korištenje aktivnog načina rada;

Korištenje pasivnog načina rada.

teorija igre strategija mješovita

Mješovite strategije

Ako matrična igra nema sedlo u čistim strategijama, tada se pronalaze gornja i donja cijena igre. Oni pokazuju da igrač 1 neće dobiti isplatu veću od top cijena igru, a tom igraču 1 je zagarantovana pobeda ništa manje niža cijena igrice.

Mešovita strategija igrača je kompletan skup njegovih čistih strategija kada se igra ponavlja mnogo puta pod istim uslovima sa datim verovatnoćama. Hajde da sumiramo ono što je rečeno i navedemo uslove za korišćenje mešovitih strategija:

• * igra bez sedla;
• * igrači koriste nasumičnu mješavinu čistih strategija sa datim vjerovatnoćama;
• * igra se ponavlja više puta pod sličnim uslovima;
• * tokom svakog poteza nijedan igrač nije obavešten o izboru strategije od strane drugog igrača;
• * Usrednjavanje rezultata igre je dozvoljeno.

Koriste se sljedeće oznake za mješovite strategije.

Za igrača 1, mješovita strategija se sastoji u korištenju čistih strategija A 1, A 2, ..., A t sa odgovarajućim vjerovatnoćama p 1, p 2, ..., p t.

Za igrača 2

q j je vjerovatnoća korištenja čiste strategije B j .

U slučaju kada je p i = 1, za igrača 1 imamo čistu strategiju

Čiste strategije igrača su jedini mogući nekompatibilni događaji. U matričnoj igri, znajući matricu A (odnosi se i na igrača 1 i na igrača 2), možemo odrediti, za date vektore, prosječnu isplatu (matematičko očekivanje efekta) igrača 1:

gdje i su vektori;

p i i q i su komponente vektora.

Primjenom njihovih mješovitih strategija, igrač 1 nastoji maksimizirati svoj prosječni dobitak, a igrač 2 nastoji minimizirati ovaj učinak moguće značenje. Igrač 1 nastoji da dostigne

Igrač 2 osigurava da je uvjet ispunjen

Označimo i vektore koji odgovaraju optimalnim mješovitim strategijama igrača 1 i 2, tj. takve vektore i za koje će jednakost biti zadovoljena

Cijena igre je prosječna isplata igrača 1 kada oba igrača koriste mješovite strategije. Dakle, rješenje matrične igre je:

• - optimalna mješovita strategija igrača 1;
• - optimalna mješovita strategija za igrača 2;

Cijena igre.

Mješovite strategije će biti optimalne (i) ako formiraju sedlo za funkciju, tj.

Postoji osnovna teorema za matematičke igre.

Za matričnu igru ​​sa bilo kojom matricom A veličine

postoje i jednaki su jedno drugom: = = .

Treba napomenuti da će prilikom odabira optimalnih strategija igraču 1 uvijek biti zagarantovana prosječna isplata, ne manja od cijene igre, za bilo koju fiksnu strategiju igrača 2 (i, obrnuto, za igrača 2). Aktivne strategije igrača 1 i 2 su strategije koje su dio optimalnih mješovitih strategija odgovarajućih igrača sa vjerovatnoćama različitim od nule. To znači da optimalne mješovite strategije igrača možda ne uključuju sve njihove a priori određene strategije.

Rješavanje igre znači pronalaženje cijene igre i optimalne strategije. Započnimo naše razmatranje metoda za pronalaženje optimalnih mješovitih strategija za matrične igre najjednostavnija igrica, opisan u matrici 22. Igre sa sedlom neće se posebno razmatrati. Ako se dobije sedlo, to znači da postoje neisplative strategije koje treba napustiti. U nedostatku sedla mogu se dobiti dvije optimalne mješovite strategije. Kao što je već napomenuto, ove mješovite strategije su napisane na sljedeći način:

To znači da postoji matrica plaćanja

a 11 p 1 + a 21 p 2 = ; (1.16)

a 12 p 1 + a 22 p 2 = ; (1.17)

p 1 + p 2 = 1. (1.18)

a 11 p 1 + a 21 (1 - p 1) = a 12 p 1 + a 22 (1 - p 1); (1.19)

a 11 p 1 + a 21 - a 21 p 1 = a 12 p 1 + a 22 - a 22 p 1 , (1.20)

gde dobijamo optimalne vrednosti:

Znajući i, nalazimo:

Nakon izračunavanja nalazimo:

a 11 q 1 + a 12 q 2 = ; q 1 + q 2 = 1; (1.24)

a 11 q 1 + a 12 (1 - q 1) = . (1.25)

u 11 do 12 . (1.26)

Problem je riješen, jer su pronađeni vektori i cijena igre. Imajući matricu plaćanja A, problem možete riješiti grafički. Sa ovom metodom, algoritam rješenja je vrlo jednostavan (slika 2.1).

• 1. Segment jedinične dužine iscrtan je duž ose apscise.
• 2. Y-osa prikazuje dobitke za strategiju A 1 .
• 3. Na liniji paralelnoj sa ordinatom, u tački 1, ucrtani su dobici za strategiju a 2.
• 4. Krajevi segmenata su označeni za a 11 -b 11, a 12 -b 21, a 22 -b 22, a 21 -b 12 i nacrtane su dvije prave linije b 11 b 12 i b 21 b 22.
• 5. Određuje se ordinata tačke preseka sa. Ona je jednaka. Apscisa tačke c je jednaka p 2 (p 1 = 1 - p 2).

Rice. 1.1.

Ova metoda ima prilično široko područje primjene. Ovo se zasniva na opšta imovina igre TP, koji se sastoji u tome da u bilo kojoj igri TP svaki igrač ima optimalnu mješovitu strategiju u kojoj broj čistih strategija nije veći od min(m, n). Iz ovog svojstva možemo dobiti dobro poznatu posljedicu: u bilo kojoj igri 2n i m2, svaka optimalna strategija sadrži najviše dvije aktivne strategije. To znači da se bilo koja igra 2n i m2 može svesti na igru ​​22. Posljedično, igre 2n i m2 mogu se riješiti grafički. Ako matrica konačne igre ima dimenziju mn, gdje je m > 2 i n > 2, tada se linearno programiranje koristi za određivanje optimalnih mješovitih strategija.