Maskavas pilsētas Maskavas universitāte valdības vadība

Vadības nodaļa

Lietišķās matemātikas katedra

Eseja

pēc akadēmiskās disciplīnas

"Vadības sistēmu izpētes matemātiskās metodes"

Par tēmu: "Bimatrix spēles. Līdzsvara situāciju meklēšana"

1. Bimatrix spēles

Pilnīgi jebkura vadības darbība nevar pastāvēt bez konfliktsituācijām. Tās ir situācijas, kad saduras divas vai vairākas puses ar atšķirīgām interesēm. Ir gluži dabiski, ka katra puse vēlas atrisināt konfliktu savā labā un gūt maksimālu labumu. Šādas problēmas risināšanu var sarežģīt tas, ka konfliktējošajai pusei nav pilnīga informācija par konfliktu kopumā. Citiem vārdiem sakot, mēs varam teikt, ka konfliktsituācijā ir nepieciešams pieņemt optimālo lēmumu nenoteiktības apstākļos.

Lai atrisinātu šāda veida problēmas, tiek izmantota matemātiskā modelēšana. Ieviesīsim dažus pamatjēdzienus. Konfliktu spēles matemātisko modeli sauc par spēli. Konfliktā iesaistītās puses ir spēlētāji, spēlētāja darbība ir gājiens, gājienu kopums ir stratēģija, spēles rezultāts ir uzvarošs.

Obligāts solis pirms problēmas risināšanas ir noteiktu noteikumu noteikšana. Parasti šie noteikumi ir prasību un ierobežojumu kopums spēlētāju darbībām, informācijas apmaiņa starp spēlētājiem par pretinieku darbībām, pretinieku laimestu funkcijas utt. Noteikumiem jābūt skaidriem, pretējā gadījumā spēle nenotiks.

Līdz šim ir vairāki veidi, kā klasificēt spēles. Galvenais iedalījums ir nesadarbīgās ierobežoto pāru spēlēs ar izmaksām (matricas, pozicionālās, divmatricas) un koalīcijas spēlēs. Šajā esejā mēs apskatīsim bimatrix spēles.

Spēles ar fiksēta summa– spēles, kurās spēlētāju intereses, lai arī nesakrīt, tomēr nav gluži pretējas. Īpašs gadījums ir bimatrix spēles.

Bimatrix spēle ir beigu spēle divi spēlētāji ar summu, kas nav nulle, kurā katra spēlētāja izmaksas noteiktas ar matricām atsevišķi attiecīgajam spēlētājam (katrā matricā rinda atbilst 1. spēlētāja stratēģijai, kolonna 2. spēlētāja stratēģijai, plkst. rindas un kolonnas krustpunktā pirmajā matricā ir 1. spēlētāja izmaksa, otrajā matricā - spēlētāja laimests 2.)

Apskatīsim pāru spēli, kurā katram dalībniekam ir šādas iespējas izvēlēties savu uzvedības līniju:

spēlētājs A – var izvēlēties jebkuru no stratēģijām A 1, ..., A m;

spēlētājs B – jebkura no stratēģijām B 1, ..., B n;

Ja spēlētājs A izvēlējās stratēģiju A i, spēlētājs B – B j, tad beigās spēlētāja A laime būs a ij, spēlētāja B – b ij. Spēlētāju A un B izmaksas var uzrakstīt divu tabulu veidā.

Tādējādi, ja spēlētāju intereses ir atšķirīgas, bet ne vienmēr pretējas, spēles raksturošanai tiek izmantotas divas izmaksu matricas. Šis fakts deva nosaukumu šādām spēlēm – bimatrix.

2. Līdzsvara stāvoklis bimatricas matricās

Bimatrix spēles risinājums ir risinājums, kas vienā vai otrā nozīmē ir piemērots abiem spēlētājiem. Šis formulējums ir ļoti neskaidrs, jo bi matricas spēles ah, ir diezgan grūti skaidri formulēt mērķus spēlētājiem. Viena no iespējamām iespējām ir spēlētāja vēlme kaitēt pretiniekam, kaitējot viņa paša laimestam, pretējā gadījumā mērķis būs pretējs.

Parasti tiek apsvērtas divas pieejas bimatrix spēles risināšanai. Pirmā ir līdzsvara situāciju meklēšana: tiek meklēti apstākļi, kad spēle ir kādā līdzsvarā, kuru pārkāpt individuāli ir neizdevīgi nevienam no spēlētājiem. Otrais ir Pareto optimālo situāciju meklēšana: tādu apstākļu atrašana, kādos spēlētāji kopīgi nevar palielināt viena spēlētāja peļņu, nesamazinot otra atdevi.

Koncentrēsimies uz pirmo pieeju.

Šī pieeja izmanto jauktas stratēģijas, t.i. gadījumā, kad spēlētāji aizstāj savu tīras stratēģijas ar zināmām varbūtībām.

Ļaujiet spēlētājam A izvēlēties stratēģiju A 1 ar varbūtību p 1, A 2 – p 2, ..., A m – p m un

Spēlētājs B izmanto stratēģiju B 1 ar varbūtību q 1, B 2 – q 2, ..., B n – q n un

Kā spēles “veiksmes” kritēriju ņemam matemātiskās cerības uz spēlētāju laimestiem, kas tiek aprēķināti pēc formulas:

Tādējādi mēs varam formulēt pamata definīciju:

Varbūtības sadalījums P * (

Ja pastāv līdzsvara situācija, tad novirze no tās ir neizdevīga pašam spēlētājam.

Patiesa ir arī Dž.Neša teorēma. Katrai bimatrix spēlei ir vismaz viena līdzsvara situācija jauktās stratēģijās.

3. Bimatrix spēļu risināšanas vispārīgais princips

Visas spēlētāja A tīrās stratēģijas tiek secīgi aizstātas ar sistēmas pirmo nevienlīdzību, pieņemot, ka B ievēro savu optimālo stratēģiju. Visas spēlētāja B tīrās stratēģijas tiek aizstātas ar otro nevienlīdzību, pieņemot, ka A ievēro savu optimālo stratēģiju.

Iegūtā m+n nevienādību sistēma, kuras risinājums dod optimālo elementu vērtību jauktas stratēģijas(P*,Q*) un spēlētāju saņemtie maksājumi līdzsvara punktā.

Piemērs: cīņa par tirgu.

Problēmas risinājums

v A =-10 × 1q 1 + 2 × 1 * (1-q 1) + (1-p 1) q 1 -(1-p 1) (1-q 1) = -14 × 1 q 1 + 3 × 1+2q 1-1

v B =5×1q 1 -2×1*(1-q 1)-(1-p 1)q 1 +(1-p 1) (1-q 1)=9 × 1q 1 -3 × 1- 2q 1 +1

p 1 = 1, tad v A = 2-12q 1

p 1 =0, tad v A = -1+2q 1

q 1 =1, tad v B =-1+6×1

q 1 =0, tad v B =1–3 × 1

Mēs sastādām 4 sistēmas, pārveidojam, iegūstam.

65. Grafiskajā metodē 3*3 spēļu risināšanai, lai atrastu optimālas spēlētāju stratēģijas:
a) ir izveidoti divi trīsstūri (*atbilde*)
b) izveidots viens trīsstūris.
c) trijstūri vispār nav konstruēti.
66. Apakšējās aploksnes grafiks spēļu risināšanas grafiskajai metodei 2*m vispārīgā gadījumā attēlo funkciju:
a) monotoni samazinās.
b) monotoni pieaug.
c) nemotonisks.
67. Ja antagonistiskā spēlē segmentā 1. spēlētāja F(x,y) izmaksas funkcija ir vienāda ar 2*x+C, tad atkarībā no C:
a) nekad nav seglu punktu.
b) vienmēr ir seglu punkti (*atbilde*)
c) cita iespēja
68. Kā uz galīgām kopām noteikt lēmumu pieņemšanas problēmu nenoteiktības apstākļos:
a) divas matricas.
b) laimesti.
c) kaut kas cits (*atbilde*)
69. Patvaļīgas dimensijas antagonistiskā spēlē pirmā spēlētāja izmaksa ir:
skaitlis.
b) daudzi.
c) vektors vai sakārtota kopa.
d) funkcija (*atbilde*)
70. 3*3 matricas spēlē ir divas spēlētāja jauktās stratēģijas sastāvdaļas:
a) noteikt trešo (*atbilde*)
b) nedefinē.
71. Bimatrix spēli var definēt:
a) divas vienādas dimensijas matricas ar patvaļīgiem elementiem,
b) divas matricas, kurām nav obligāti jābūt vienādas dimensijas,
c) viena matrica.
72. Matricas spēlē elements aij ir:
a) otrā spēlētāja zaudējums, kad viņš izmanto j-to stratēģiju, un 2. - i-tā stratēģija(*atbilde*)
b) optimāla stratēģija 2. spēlētājs, kad tiek lietots ienaidnieks i vai j-tā stratēģija,
c) 1. spēlētāja laimestu, kad viņš izmanto j-to stratēģiju, un 2. spēlētāja laimestu - i-to stratēģiju,
73. Seglu punktam atbilst matricas elements aij. Iespējamas šādas situācijas:
a) optimāls.
b) tīrs.
c) nav skaidras atbildes (*atbilde*)
84. Ja visas matricas kolonnas ir vienādas un tām ir forma (4 3 0 2), tad kāda stratēģija ir optimāla 2. spēlētājam?
a) vispirms. b) trešais. c) jebkura (*atbilde*)
85. Kāds ir maksimālais seglu punktu skaits 3*3 spēlē (matricā var būt jebkādi skaitļi):
a)3.
b)9.
c)27 (*atbilde*)
86. Pieņemsim, ka X=(1;5) ir 1. stratēģiju kopa
spēlētājs, Y=(2;8) - 2. spēlētāja stratēģiju kopa. Vai pāris (1,2)
būt par seglu punktu šajā spēlē:
a) vienmēr.
b) dažreiz (*atbilde*)
c) nekad.
87. Vai bimatricas spēlē ar dimensiju 3*3 ir tieši 2 līdzsvara situācijas?
a) Vienmēr.
b) dažreiz (*atbilde*)
c) nekad.
88. Ļaujiet matricas spēlē ar dimensiju 2*3 vienai no 1. spēlētāja jauktajām stratēģijām ir forma (0,3, 0,7), un vienai no otrā spēlētāja jauktajām stratēģijām ir forma (0,3, x, x). . Kas ir cipars x?
a)0,7 b)0,4 c)kaut kas cits (*atbilde*)
89. Matricas spēle ir īpašs gadījums bimatrix, kurā vienmēr ir taisnība:
a) matrica A ir vienāda ar matricu B, kas ņemta ar pretēju zīmi.
b) matrica A ir vienāda ar matricu B.
c) Matricu A un B reizinājums ir identitātes matrica.
90. Bimatrix spēlē elements by apzīmē:
a) otrā spēlētāja laimestu, kad viņš izmanto i-to stratēģiju, un 1. spēlētāja laimestu - j-to stratēģiju,
b) otrā spēlētāja optimālā stratēģija, kad pretinieks izmanto i-to vai j-to stratēģiju/
c) kaut kas cits (*atbilde*)
91. Bimatricas spēlē elements ac atbilst līdzsvara situācijai. Iespējamas šādas situācijas:
a) kolonnā ir elementi, kas vienādi ar šo elementu (*atbilde*)
b) šis elements ir mazāks par dažiem kolonnā.
c) šis elements ir mazākais kolonnā.
92. Matricas spēlē, zinot katra spēlētāja stratēģijas un izmaksas funkciju,
spēles cenu tīrās stratēģijās var atrast:
a) vienmēr.
b) dažreiz (*atbilde*)
c) jautājums ir nepareizs.

Spēlēs ar summa, kas nav nulle Visi spēles dalībnieki var uzvarēt vai zaudēt. Bimatrix spēle ir ierobežotas nulles summas spēle starp diviem spēlētājiem. Šajā gadījumā katrai spēles situācijai A i B j katram spēlētājam ir sava izmaksa a ij pirmajam spēlētājam un b ij otrajam spēlētājam. Piemēram, ražotāju uzvedība nepilnīgās konkurences tirgos ir saistīta ar bimatrix spēli. Izmantojot tiešsaistes kalkulatoru, varat atrast risinājumu bimatrix spēle, kā arī situācijas Pareto optimālās un Neša stabilās situācijas.

Apsvērsim konfliktsituācija, kurā katram no diviem dalībniekiem ir šādas iespējas izvēlēties savu uzvedības līniju:

• spēlētājs A – var izvēlēties jebkuru no stratēģijām A 1,…, A m,
• spēlētājs B – jebkura no stratēģijām B 1,…, B n.

Tajā pašā laikā viņu kopīgā izvēle tiek vērtēta diezgan noteikti: ja spēlētājs A izvēlējās i-to stratēģiju A i , bet spēlētājs B izvēlējās k-to stratēģiju B k , tad beigās spēlētāja A izmaksa būs vienāda ar noteikts skaitlis a ik , un spēlētāja B izmaksa būs vienāda ar noteiktu skaitli, vispārīgi runājot, ar citu skaitli b ik .
Secīgi izejot cauri visām spēlētāja A stratēģijām un spēlētāja B stratēģijām, mēs varam aizpildīt divus galdus ar viņu laimestiem.

Pirmā no tabulām apraksta spēlētāja A izmaksu, bet otrā - spēlētāja B. Parasti šīs tabulas ir rakstītas matricas veidā.
Šeit A ir spēlētāja A izmaksas matrica, B ir spēlētāja B izmaksu matrica.

Tādējādi gadījumā, ja spēlētāju intereses ir atšķirīgas (bet ne vienmēr pretējas), tiek iegūtas divas maksājumu matricas: viena ir maksājumu matrica spēlētājam A, otra ir maksājumu matrica spēlētājam B. Tādējādi vārds, kas parasti tiek piešķirts šādai spēlei, izklausās pilnīgi dabiski - bimatrica.

Neša līdzsvars– līdzsvars, kad katrs spēles dalībnieks izvēlas sev optimālu stratēģiju, ar nosacījumu, ka pārējie spēles dalībnieki ievēro noteiktu stratēģiju.
Neša līdzsvars ne vienmēr ir optimālākais dalībniekiem. Šajā gadījumā viņi saka, ka līdzsvars nav Pareto-optimāls.
Tīra stratēģija– spēlētāja noteikta reakcija uz iespējamie varianti citu spēlētāju uzvedība.
Jaukta stratēģija– iespējamība (nav precīzi definēta) spēlētāja reakcija uz citu spēlētāju uzvedību.

Piemērs Nr.1. Cīņa par tirgiem.
Uzņēmums a plāno pārdot preču sūtījumu vienā no diviem tirgiem, ko kontrolē lielāka firma b. Šim nolūkam viņa veic sagatavošanās darbi saistīta ar noteiktām izmaksām. Ja firma b uzmin, kurā tirgū firma a pārdos savu produktu, tā veiks pretpasākumus un neļaus tai “ieņemt” tirgu (šī iespēja nozīmē uzņēmuma a sakāvi); ja nē, tad uzvar firma a. Pieņemsim, ka firmai a iekļūšana pirmajā tirgū ir izdevīgāka nekā iekļūšana otrajā, bet cīņa pirmajā tirgū arī prasa no tā vairāk līdzekļu. Piemēram, uzņēmuma uzvara pirmajā tirgū nes divreiz lielāku peļņu nekā uzvara otrajā, bet sakāve pirmajā tirgū to pilnībā sagrauj.
Izveidosim šī konflikta matemātisko modeli, uzskatot uzņēmumu a par spēlētāju 1 un uzņēmumu b par spēlētāju 2. 1. spēlētāja stratēģijas: A 1 — iekļūšana tirgū 1, A 2 – iekļūšana tirgū 2; 2. spēlētāja stratēģijas: IN 1 – pretpasākumi tirgū 1, IN 2 – pretpasākumi tirgū 2. Ļaujiet firmai a tās uzvara 1. tirgū novērtēta ar 2 vienībām, bet uzvara 2. tirgū – par 1 vienību; Firmas a sakāve 1. tirgū tiek lēsta -10, bet 2. tirgū - -1. Firmai b tās uzvara ir attiecīgi 5 un 1 vienība, un sakāve ir -2 un -1. Rezultātā iegūstam bimatricas spēli Г ar izmaksu matricām
.
Saskaņā ar teorēmu šai spēlei var būt gan tīras, gan pilnīgi jauktas līdzsvara situācijas. Tīrās stratēģijās šeit nav līdzsvara situāciju. Tagad pārliecināsimies, ka šai spēlei ir pilnīgi jaukta līdzsvara situācija. Mēs atradām , .
Tātad aplūkotajai spēlei ir unikāla līdzsvara situācija (x 0 ;y 0), kur , . To var īstenot, atkārtojot spēli daudzas reizes (tas ir, atkārtojot aprakstīto situāciju daudzas reizes) šādi: firmai a jāizmanto tīras stratēģijas 1 un 2 ar frekvencēm 2/9 un 7/9, un firmai b jāizmanto tīras stratēģijas 1 un 2 ar frekvencēm 3/14 un 11/14. Jebkurš uzņēmums, kas novirzās no šīs jauktās stratēģijas, samazina paredzamo peļņu.

Piemērs Nr.2. Atrodiet Pareto optimālās situācijas un Neša stabilas situācijas bimatrix spēlei.

Piemērs Nr.3. Ir 2 uzņēmumi: pirmais var ražot vienu no diviem produktiem A 1 un A 2, otrais var ražot vienu no diviem produktiem B 1, B 2. Ja pirmais uzņēmums ražo produktus A i (i = 1, 2), bet otrais - B j (j = 1, 2), tad šo uzņēmumu peļņu (atkarībā no tā, vai šie produkti ir savstarpēji papildinoši vai konkurētspējīgi) nosaka tabula Nr. 1 :

Pārbaudes gala kontrolei

1. Antagonistisku spēli var iestatīt:

a) stratēģiju kopums abiem spēlētājiem un seglu punkts.

b) abu spēlētāju stratēģiju kopums un pirmā spēlētāja izmaksas funkcija.

2. Spēles cena vienmēr pastāv matricas spēlēm jauktās stratēģijās.

a) jā.

3.Ja visas izmaksas matricas kolonnas ir vienādas un tām ir forma (4 5 0 1), tad kāda stratēģija ir optimāla 1. spēlētājam?

a) vispirms.

b) otrais.

c) kāds no četriem.

4. Ļaujiet matricas spēlē vienai no 1. spēlētāja jauktajām stratēģijām formā (0,3, 0,7), un vienai no otrā spēlētāja jauktajām stratēģijām ir forma (0,4, 0, 0,6). Kāda ir šīs matricas dimensija?

a) 2*3.

c) cita dimensija.

5. Dominēšanas princips ļauj noņemt no matricas vienā solī:

a) veselas rindas.

b) atsevišķi numuri.

6. Grafiskajā metodē 2*m spēļu risināšanai tieši no grafika atrod:

a) abu spēlētāju optimālās stratēģijas.

b) spēles cena un 2. spēlētāja optimālās stratēģijas.

c) spēles cena un 1. spēlētāja optimālās stratēģijas.

7. Apakšējās aploksnes grafiks 2*m spēļu risināšanas grafiskajai metodei ir vispārīgā gadījumā:

a) salauzts.

b) taisni.

c) parabola.

8. 2*2 matricas spēlē ir divas spēlētāja jauktās stratēģijas sastāvdaļas:

a) nosaka viens otra vērtības.

b) neatkarīgs.

9. Matricas spēlē elements aij ir:

a) 1. spēlētāja laimestu, kad viņš izmanto i-to stratēģiju, un 2. - j-to stratēģiju.

b) 1. spēlētāja optimālā stratēģija, kad pretinieks izmanto i-to vai j-to stratēģiju.

c) 1. spēlētāja zaudējums, kad viņš izmanto j-to stratēģiju, un 2. - i-to stratēģiju.

10.Matricas elements aij atbilst seglu punktam. Iespējamas šādas situācijas:

a) šis elements ir strikti mazākais no visiem rindā.

b) šis elements rindā ir otrais.

11. Brauna-Robinsona metodē katrs spēlētājs, izvēloties stratēģiju nākamajā solī, vadās pēc:

a) ienaidnieka stratēģijas iepriekšējos soļos.

b) jūsu stratēģijas iepriekšējās darbībās.

c) kaut kas cits.

12. Saskaņā ar matemātiskās cerības kritēriju katrs spēlētājs vadās no tā, ka:

a) notiks viņam vissliktākā situācija.

c) visas vai dažas situācijas ir iespējamas ar noteiktām varbūtībām.

13. Ļaujiet matricas spēlei dot matricu, kurā visi elementi ir negatīvi. Spēles cena ir pozitīva:

b) nē.

c) nav skaidras atbildes.

14. Spēles cena ir:

skaitlis.

b) vektors.

c) matrica.

15. Kāds ir maksimālais seglu punktu skaits, kas var būt spēlē ar izmēru 5*5 (matricā var būt jebkādi skaitļi):

16. Ļaujiet matricas spēlē ar dimensiju 2*3 vienai no 1. spēlētāja jauktajām stratēģijām ir forma (0,3, 0,7), un vienai no 2. spēlētāja jauktajām stratēģijām ir forma (0,3, x, 0,5). . Kas ir cipars x?

c) cits numurs.

17. Kurai spēles matricas dimensijai Valda kritērijs pārvēršas par Laplasa kritēriju?

c) tikai citos gadījumos.

18. Spēles augstākā cena vienmēr ir mazāka par spēles zemāko cenu.

b) nē.

b) jautājums ir nepareizs.

19. Kādas stratēģijas pastāv matricas spēlē:

a) tīrs.

b) jaukts.

c) abi.

20. Vai kādā antagonistiskā spēlē abu spēlētāju izmaksas funkcijas vērtības dažām mainīgo vērtībām var būt vienādas ar 1?

a) vienmēr.

b) dažreiz.

c) nekad.

21. Matricas spēlē viena no jauktajām 1. spēlētāja stratēģijām ir formā (0,3, 0,7), bet viena no otrā spēlētāja jauktajām stratēģijām ir formā (0,4, 0,1, 0,1, 0,4) . Kāda ir šīs matricas dimensija?

c) cita dimensija.

22. Dominēšanas princips ļauj vienā solī izņemt no matricas:

a) veselas kolonnas,

b) atsevišķi numuri.

c) mazāka izmēra apakšmatricas.

23. 3*3 matricas spēlē ir divas spēlētāja jauktās stratēģijas sastāvdaļas:

a) nosaka trešo.

b) nedefinē.

24. Matricas spēlē elements aij ir:

a) 2. spēlētāja zaudējums, kad viņš izmanto j-to stratēģiju, un 2. - i-to stratēģiju.

b) otrā spēlētāja optimālā stratēģija, ja pretinieks izmanto i-to vai j-to stratēģiju,

c) 1. spēlētāja laimestu, kad viņš izmanto j-to stratēģiju, un 2. spēlētāja laimestu - i-to stratēģiju,

25. Seglu punktam atbilst matricas elements aij. Iespējamas šādas situācijas:

a) šis elements ir lielākais kolonnā.

b) šis elements ir stingri lielākais rindā.

c) virknē ir elementi, kas ir gan lielāki, gan mazāki par šo elementu.

26. Saskaņā ar Valda kritēriju katrs spēlētājs pieņem, ka:

a) notiks viņam vissliktākā situācija.

b) visas situācijas ir vienādi iespējamas.

c) visas situācijas ir iespējamas ar noteiktām varbūtībām.

27. Zemākā cena ir mazāka par spēles augšējo cenu:

b) ne vienmēr.

c) nekad.

28. Matricas spēles jauktās stratēģijas sastāvdaļu summa vienmēr ir:

a) ir vienāds ar 1.

b) nenegatīvs.

c) pozitīvs.

d) ne vienmēr.

29. Ļaujiet matricas spēlē ar dimensiju 2*3 vienai no 1. spēlētāja jauktajām stratēģijām ir forma (0,3, 0,7), un vienai no 2. spēlētāja jauktajām stratēģijām ir forma (0,2, x, x). . Kas ir cipars x?