shoydullo adminstrator

Matritsaviy o`yinni aralash strategiyalarda echish.2x2, 2xn, mx2- o`yinlarni yechish.

Muallif: Ochilov S.

Qo`shilgan sana: 2015-02-13

Matritsaviy o`yinni aralash strategiyalarda yechish. 2x2, 2xn, mx2- o`yinlarni yechish

Faraz qilaylik, mxn - o‘lchamli G_N matritsaviy o‘yin berilgan, uning to‘lovlar matritsasi

bo‘lib, o‘yinda egar nuqta (muvozanat vaziyati) mavjud bo‘lmasin, ya’ni o‘yinning quyi baxosi va yuqori baxosi uchun α<β munosabat bajarilsin. Bu xolda minimaks va maksimin strategiyalar optimal bo‘la olmaydilar. Quyidagi misolda ko‘rsatamizki, muvozanat xolatga ega bo‘lmagan o‘yinda minimaks yoki maksimin strategiyadan foydalanish ma’kul emas.

To`lovlar matritsasi bo‘lsin. Bu matritsa uchun α <β ya’ni muvozanat holati mavjud emas. Birinchi o‘yinchining maksimin strategiyasi ì *=1, ikkinchi o‘yinchining minimaks strategiyasi esa j *=2, Agar ikkinchi o‘yinchi j *=2, strategiyadan foydalansa va birinchi o‘yinchi i=2, strategiyani tanlasa, u 3 ga teng yutuk oladi, bu esa maksimindan 2 birlik kattadir. Ammo, agar ikkinchi o‘yinchiga birinchi o‘yinchining strategiya tanlashi ma’lum bo‘lib qolsa, u o‘zining strategiyasini j=1 ga o‘zgartiradi va unda birinchi o‘yinchi fakat nolga teng yutukka, ya ni maksimin xolidan 1 birlik kam yutuqqa ega bo‘ladi, xolos. Xuddi shunday muloxazalarni ikkinchi o‘yinchi xam yuritishi mumkin.
Endi, muvozangat xolati mavjud bo‘lmagan xolda o‘yinchilar kanday xarakat kilishlari kerak degan savol paydo bo‘ladi.
Bunday savolga o‘yinchilarning o‘z strategiyalarini tasodifiy tanlash orkali javob berish mumkin. Chunki, birinchidan tasodifiy tanlash strategiyaning max-fiyligini ta minlasa, ikkinchidan okilona kurilgan tasodifiy tanlash mexanizmidan foydalanish strategiyaning optimalligini ta minlaydi. Ta'rif N matritsa satrlari nomerlarining Μ={1,2,....,m} to‘plamda ehtimolli taqsimotiga I o‘yinchining aralash strategiyasi deyiladi. Xuddi shuningdek, N matritsa ustunlari nomerlarining

N={1,2,....,m} to‘plamdagi extimolli taqsimotiga II o‘yinchining aralash strategiyasi deyiladi.
SHunday qilib, I o`yinchining r aralash strategiyasi

vektordan iborat. II uyinchining q aralash strategiyasi esa

vektordan iborat bo`ladi. Bunda va larni o`yinchilar r va q aralash strategiyalardan foydalangandagi

va sof strategiyalarning tanlanish extimollari deb tushunish mumkin.

P va Q bilan mos ravishda I va II uyinchilarning aralash strategiyalar to`plamini belgilaymiz. P va Q to`plamlar chegaralangan va yopik tuplamlardir.

aralash strategiyani karaymiz, bu yerda

Bu strategiya N matritsa i-satrining 1ga teng extimol bilan tanlanishini bildiradi. aralash strategiyaning tanlanishi I o`yinchining sof strategiyasini tanlash bilan tenglashtirish mumkin. Xuddi shuningdek, aralash strategiyani II uyinchining sof strategiyasi bilan tenglashtirish mumkin. Demak, aralash strategiyalar to`plamini sof strategiyalar to`plamining kengaytirilishi deb qarash mumkin.

va aralash strategiyalarning ixtiyoriy (p,q) juftiga G_nuyindagi vaziyat deyiladi.
Endi o`yindagi (p,q) vaziyatga mos keluvchi I uyinchi yutishini

deb belgilaymiz. ¡ uyinchilardan biri i yoki j sof strategiyani, ikkinchisi esa q yoki p aralash strategiyani qullaganda W(i,q) va W(p,j) yutuklar kuyidagi ko'rinishda buladi:

SHunday kilib, biz G_n=< M,N,H> o`yindan uyinga keldik, bu erda P,Q - aralash strategiyalar tuplamlari, W esa (1) kurinishdagi yutuklar funksiyasidir. Xosil qilingan o`yinga G_{n o`yinning aralash kengaytirilishi deymiz.

Ta’rif. Agar (p*,q*) vaziyat uchun}

munosabat barcha uchun bajarilsa, (p*,q*) muvozanat vaziyati,

ga esa n uyinning baxosi (kiymati) deyiladi.

uyinda muvozanat vaziyatining mavjudligi matritsaviy uyinlarning asosiy teoremasi deb ataluvchi kuyidagi teoremada keltirilgan:
1 - teorema. Xar kanday matritsaviy uyin aralash strategiyalarda muvozanat vaziyatiga egadir.
Agar (p*,q*) - muvozanat vaziyati bo`lsa, r*- I uyinchining , q* esa II uyinchining optimal aralash strategiyalari bo`ladi.
Optimal aralash strategiyalar va uyin baxosi g uchun

munosabatlar bajariladi.
Bundan tashkari amaliyot uchun kuyidagi teoremaning axamiyati kattadir.
2 – teorema. Gn matritsaviy uyin uchun

tenglik bajariladi va p*,q* optimal aralash strategiyalar

shartlardan aniklanadi.

3 - teorema. Faraz qilaylikki, berilgan G_n matritsaviy uyinda optimal aralash strategiyalar,γ esa o`yin baxosi bo`lsin. U xolda: agar

bo`lsa bo`ladi; agar bo`lsa bo`ladi. Aksincha, agar bo`lsa, bo`ladi; agar bo`lsa bo`ladi.

Isbot. Biror uchun va deb faraz qilaylik, ya’ni bo'lsin. U vaqtda Bundan tashqari bo`lgani uchun bajariladi. Demak,

ya`ni Bu esa γ ning uyin baxosi ekanligiga karama-karshidir. Demak,

bulganda bajariladi. Teoremaning kolgan tasdiklari xam shunday isbotlanadi.

Ta’rif. Agar I (mos ravishda, II) uyinchining shunday optimal (mos ravishda ) strategiyasi mavjud bulib, (mos ravishda, bulsa, (mos ravishda,

sof strategiya shu uyinchining aktiv strategiyasi deyiladi.
SHu ta’rifni xisobga olganda 3 - teoremadan kuyidagi natija kelib chikadi.

Natija. Agar I uyinchi r* optimal aralash strategiyani kullasa, rakib tomon kanday aktiv j strategiyani kullamasin, uning yutugi

uyin baxosiga teng buladi, ya’ni tenglik bajariladi. Xuddi shunga uxshash, agar II uyinchi uzining kanday aktiv i strategiyasini kullamasin,

tenglik urinli buladi.
Endi shu keltirilgan muloxazalardan foydalanib 2x2-uyinni echish usulini ka-raymiz.

Faraz kilaylik, 2x2 - uyin matritsa bilan berilgan va egar nuktaga ega bulmasin,

ya’ni ¡ uyinchilarning optimal strategiyalari p*=(p1,p2), q*=(q1,q2) va uyin baxosi γ

ni topish talab kilinadi.
Kuyidagi tasdik urinli: agar 2x2-uyinda egar nukta mavjud bulmasa, uyinchilarning ikkala strategiyasi gam aktiv buladi, ya’ni, p_j>0, q_j>0, i=1,2; j=1,2. SHuning uchun, 3-teorema natijasiga kura, agar I uyinchi p*=(p1,p2) optimal aralash strategiyani kullasa va II uyinchi j=1 yoki j=2 strategiyalaridan foydalansa, I uyinchining yutug`i uyin baxosiga teng buladi, ya’ni, j=1,2 bajariladi. r₁+r₂=1 ekanligini xisobga olsak,

sistemaga ega bulamiz. Bu sistema yagona echimga ega deb faraz kilamiz, ya’ni

(4)

Kursatish mumkinki, agar egar nukta mavjud bulmasa, (4) shart bajariladi. U vaktda optimal r*=(r₁,r₂) strategiyaning komponentalari

(5)

formula buyicha topiladi.
Xuddi shunga uxshash, 3 - teorema natijasi asosida II uyinchi uchun

sistemani xosil kilamiz va (4) shart bajarilganda uni echib q*=(q₁,q₂) optimal strategiya komponentalarini topamiz: (6)

keyin baxosi esa (7)

formula buyicha topiladi.
Endi 2x2 uyin echimining geometrik interpritatsiyasini karaymiz. Buning uchun XOU koordinatalar sistemasining abssissalar ukida uzunligi birga teng bulgan [A₁;A₂] kesma olamiz. Kesma uchlari orkali unga perpendikulyar ikkita tugri chizik utkazamiz va ularda I uyinchi yutugini belgilaymiz (1 - rasm).

Ordinata uki bilan ustma ust tushuvchi chap perpendikulyar r₁=1, r₂=0 bulgan A₁ strategiyaga, ung perpendikulyar esa r₁=0, r₂=1 bulgan A₂ strategiyaga mosdir. II uyinchi V₁ strategiyani kullagan bulsin. U xolda agar I uyinchi A₁ strategiyani kullasa, uning yutugi a₁₁ ga, A₂ strategiyani kullasa, a₂₁ ga teng buladi. Tegishli perpendikulyarlarda a₁₁ va a₂₁ uzunlikdagi

kesmalarni ulchab B₁″ va B₁′ nuktalarni belgilaymiz.

Endi, II uyinchi V₂ strategiyani kullagan bulsin. U xolda, agar I o`yinchi A₁ strategiyani kullasa, uning yutugi a₁₂ ga A₂

strategiyani kullasa, a₂₂ ga teng bo`ladi. Bu xolga mos ravishda tegishli perpendikulyarda a₁₂ va a₂₂ uzunlikdagi kesmalarni

o`lchab. B₂″ va B₂′

nuktalarni belgilaymiz. B₁″B₁′chizik ustidagi ixtiyoriy nuktaning ordinatasi I uyinchining u r=(r₁,r₂ ) aralash strategiyani, II uyinchi esa j=1 sof strategiyani kullagandagi yutugi kiymatiga teng. B₂″ B₂′ chizik ustidagi ixtiyoriy nuktaning ordinatasi I uyinchining u r=(r₁,r₂) aralash strategiyani, II uyinchi esa j=2 sof strategiyani kullagandagi yutugi kiymatiga tengdir.

r* optimal strategiyani topish uchun I uyinchi yutug`ining kuyi chegarasini, ya’ni 1-rasmda yug`onlashtirib

ko`rsatilgan B₂″DB₁′

sinik chizikni yasaymiz. Ravshanki, bu sinik chiziq ustida I uyinchining u ixtiyoriy aralash strategiyani kullagandagi minimal yutuklari yotadi. I uyinchining maksimal yutugini D nukta belgilaydi. D nuktaning ordinatasi esa uyinning baxosi γ

ga teng. Bu nuktaning abssissalar ukidagi proeksiyasiga optimal strategiya mos keladi. II uyinchining optimal strategiyasi xam shunday topiladi. Buning uchun I va II uyinchilarning urinlari almashtirish, ya’ni to`lov matritsasini transponirlash va yutuk kuyi chegarasining maksimal kiymatini topish œrniga yutuq yukori chegarasining minimal šiymatini topish kerak (2-rasmga š.)

2-rasm.

1- va 2-rasmlarda o`yinning echimi tugri chiziklarning kesishi nuqtasi sifatida aniklangan. Bu xamma vaqt xam o`rinli bulavermaydi. Masalan, 3-rasmda I o`yinchi yutugining uuyi chegarasi B₂″B₂′ kesma bulgan xol kursatilgan. II-uyinchining B₁ stra-tegiyasi u uchun noqulaydir, chunki u bu strategiyani ko`llab xar qanday xolda xam B₂ strategiyani qo`llagandagidan kup yutkazadi. Bu xolda o`yin egar nuqtaga ega.

rasm3

1-misol. Tulov matritsasi 1- jadvalda keltirilgan o`yinning echimi topilsin va uning geometrik interpritatsiyasi berilsin.

1-jadval

Bu erda α=2 β=4

ya’ni uyin egar nuktaga ega emas. Uyinning echimini aralash strategiyalarda topamiz.a₁₁=5, a₁₂=-1, a₂₁=2, a₂₂=4. (5), (6), (7) formulalarga ko`ra

I o`yinchiga nisbatan uyinning grafik tasviri 4-rasmda kursatilgan. YUtukning quyi chegarasi B₂″DB₁′sinik chiziqni tashkil

etadi. I o`yinchining optimal strategiyasi D nuqta bilan aniqlanadi.

4-rasm

4 - rasm 5 - rasm

Uyinning II uyinchiga nisbatan grafik tasvirini yasash uchun avvalo to`lov matritsasini transponerlash kerak.

Transponirlashdan so`ng tulov matritsasi 2 – jadval qurinishda buladi

II uyinchining optimal strategiyasini topish grafik ravishda 5 - rasmda kursa-tilgan. II yinchi yutkazigining yuqori chegarasi

A₁″EA₂

strategiyasi E nukta bilan aniklanadi.
Endi 2xn-uyini echishni karaymiz. Bu o`yinda I uyinchi ikkita sof strategiyaga, II o`yinchi esa n ta sof strategiyaga ega. Uyinning to`lovlar matritsasi kurinishda bo`ladi. Faraz kilaylik, I uyinchi aralash strategiyasini, II o`yinchi esa sof strategiyasini tanlagan bo`lsin. U xolda I uyinchining (p, j) vaziyatga mos yutugi bo`ladi. (8) tenglik geometrik ravishda ξ 0W

koordinatalar tekisligida tugri chizikni ifodalaydi (6 - rasm). Demak, xar bir sof strategiyaga

strategiyaga W=W(p,j) to`g`ri chiziq mos keladi.
I uyinchining optimal r* strategiyasini topish uchun funksiyani aniklaymiz. Xar bir r=(ξ ,1-ξ) uchun F(ξ ) funksiyaning kiymati I uyinchi yutuklarining kuyi chegarasiga tengdir. Endi

optimal strategiyani shartdan aniqlaymiz. Bunda uyin baxosiga teng. Endi II o`yinchi

optimal strategiyasi qanday aniqlanishini ko`ramiz.

Dastlab faraz qilaylikki, sinik chizik grafigi ξ0w koordinatalar tekisligida gorizontal kismga ega bo`lsin va bu gorizontal qism sof strategiyaga mos keluvchi to`g`ri chiziq bilan xosil kilingan bo`lsin (6 - rasm). Bu faqat

bo`lganda bajariladi. Bunday xolda j0 sof strategiya II uyinchining yagona optimal strategiyasi bo`ladi, chunki

bo`lgani uchun (3 - teoremaga š.)

Faraz kilaylikki, I uyinchi optimal strategiyasi r*=(0,1) bo`lsin, ya’ni (9) shartda ξ *=0 bulsin. U vaqtda uyin baxosi

buladi . to`plamni karaymiz bo`lsin. munosabat r*=(1,0) , va ixtiyoriy uchun bajariladi. YA’ni (r*, j*) – muvozanat vaziyatidir. Demak, bu xolda sof strategiya II qyinchining optimal strategiyasi bo`ladi.

Faraz qilaylikki, I uyinchi optimal strategyasi r*=(1,0) bulsin. U vaktda uyin baxosi bo`ladi, bu erda

to`plamlarni karaymiz.

munosabat r*=(1,0), va ixtiyoriy uchun bajariladi, ya’ni (r*, j*)–muvozanat vaziyatdir. Demak, bu xolda sof strategiya II uyinchining optimal strategiyasi buladi.
r*=(0,1) va r*=(1,0) bo`lgan xollarning grafik tasviri mos ravishda 7 - 8 – rasmlarda keltirilgan.

Nixoyat endi I uyinchi optimal strategiyasi bulgan xolni qaraymiz. Bu xolda ξ* kamida ikkita W=W(p, j), tugri chiziqlar kesishish nuktasi abssissasi sifatida aniqlanadi. SHunday ikkita tugri chiziklar

bulsin. Agar II uyinchi j₁ va j₂ strategiyalardan boshqalarini ishlatmasa, xosil bo`lgan 2x2-uyinda I uyinchining optimal strategiyasi va uyin yutugi xuddi dastlabki 2xn-uyindagi kabi buladi. Bu esa II uyinchi fakat j₁ va j₂ strategiyalardan foydalanib I o`yinchining g dan kup yutukka erishishga yul kuymasligini bildiradi. Demak, dastlabki 2xn-uyindagi II uyinchining optimal strategiyasini j₁ va j₂ sof strategiyalar yordamida kurish mumkin. SHunday kilib, xosil kilingan 2x2-uyindagi II uyinchi optimal strategiyasi uning dastlabki 2xn-uyindagi optimal strategiyasi xam bo`ladi. II o`yinchining optimal strategiyasini xisoblash uchun (6) formuladan foydalanamiz:

(10)

2 - misol. To`lovlar matritsasi

bo`lgan 2x4-o`yinni qaraymiz. Xar bir j=1,2,3,4 uchun (8) to`g`ri chiziklar

tengliklar bilan aniqlanadi. Ularni 9-rasmda tasvirlaymiz. grafigi siniq chiziqdan iborat. shartni kanoatlantiruvchi ξ* nusxa W(p,1) va W(r,4) to`g`ri chizishlar kesishish nuqtasi abssissasidan iborat. Demak, ξ* nuqta tenglamadan aniqlanadi. Bu yerdan

9 - rasm.

bo`lgani uchun I uyinchining ikkala sof strategiyasi xam aktiv-dir. Demak, 3-teoremaga ko`ra II o`yinchi

optimal strategiyasi uchun tengliklar urinlidir.

bulgani uchun 3 – teoremaga ko`ra SHuni e’tiborga olib (11) tengliklarni yozamiz:

Bu yerdan kelib chiqadi. Demak, II uyinchi optimal strategiyasi kurinishda bo`ladi.
Ma’ruzamiz sungida mx2-uyinni echishga xam to`xtalib o`tamiz. Bu uyinni echishda xam 2xn - uyinni echishdagi kabi muloxazalar yuritish mumkin.
mx2 - o`yin to`lovlar matritsasi

ko`rinishda bo`ladi. Bu o`yinni echishni ikkinchi o`yinchi optimal strategiyasini aniqlashdan boshlaymiz. Faraz qilaylik,II uyinchining ixtiyoriy aralash strategiyasi bo`lsin. U xolda I uyinchi ixtiyoriy i€M strategiyasiga mos yutugi bo`ladi. W(i,q) funksiya grafigi η0W koordinatalar tekisligida to`gri chiziqdan iboratdir . funksiyani qaraymiz. SHu funksiyaning [0,1] dagi minimum nuqtasi η*, ya’ni

shartni qanoatlantiruvchi η* nuqta II uyinchi optimal strategiyasini aniqlaydi.

I uyinchi

optimal strategiyasini 2xn-uyinda II o`yinchi optimal strategiyasini aniqlashdagi kabi muloxazalar yuritib topamiz.

3 - misol. To`lov matritsasi

bo`lgan 3x2-uyinni karaymiz. Xar bir i=1,2,3 uchun (12) formula buyicha W(i,q) to`gri chiziklarni yasaymiz(10 - rasm):

funksiya minimum nuqtasi η* nukta W(1,q) va W(2,q) to`gri chiziqlarning kesishish nuqtasidan aniqlanadi, ya’ni Bu yerdan Demak, II o`yinchining optimal strategiyasidir. bo`lgani uchun I o`yinchi strategiyasi