Ma`lumotlar : 1091
Xabarlar soni: 197
Bugun: 6.3.2021
Soat: 15:17
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 GN 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 ì
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 Gn uyindagi 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 Gn=< M,N,H> o`yindan uyinga keldik, bu erda P,Q - aralash strategiyalar tuplamlari, W esa (1) kurinishdagi yutuklar funksiyasidir. Xosil qilingan
o`yinga Gn 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 Gn
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, pj>0, qj>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. r1+r2=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*=(r1,r2) 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*=(q1,q2) 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 [A1;A2] 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 r1=1, r2=0 bulgan A1 strategiyaga, ung perpendikulyar esa r1=0, r2=1 bulgan A2 strategiyaga mosdir. II uyinchi V1 strategiyani kullagan bulsin. U xolda agar I uyinchi A1 strategiyani kullasa, uning yutugi a11 ga, A2 strategiyani kullasa, a21 ga teng buladi. Tegishli perpendikulyarlarda a11 va a21 uzunlikdagi
kesmalarni ulchab B1″ va B1′ nuktalarni belgilaymiz.
Endi, II uyinchi V2 strategiyani kullagan bulsin. U xolda, agar I o`yinchi A1 strategiyani kullasa, uning yutugi a12 ga A2
strategiyani kullasa, a22 ga teng bo`ladi. Bu xolga mos ravishda tegishli perpendikulyarda a12 va a22 uzunlikdagi kesmalarni
o`lchab. B2″ va B2′
nuktalarni belgilaymiz. B1″B1′chizik ustidagi ixtiyoriy nuktaning ordinatasi I uyinchining u r=(r1,r2 ) aralash strategiyani, II uyinchi esa j=1 sof strategiyani kullagandagi yutugi kiymatiga teng. B2″ B2′ chizik ustidagi ixtiyoriy nuktaning ordinatasi I uyinchining u r=(r1,r2) 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 B2″DB1′
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 B2″B2′ kesma bulgan xol kursatilgan. II-uyinchining B1 stra-tegiyasi u uchun noqulaydir, chunki u bu strategiyani ko`llab xar qanday xolda xam B2 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.a11=5, a12=-1, a21=2, a22=4. (5), (6), (7) formulalarga ko`ra
I o`yinchiga nisbatan uyinning grafik tasviri 4-rasmda kursatilgan. YUtukning quyi chegarasi B2″DB1′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
A1″EA2
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 j1 va j2 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 j1 va j2 strategiyalardan foydalanib I o`yinchining g dan kup yutukka erishishga yul kuymasligini bildiradi. Demak, dastlabki 2xn-uyindagi II uyinchining optimal strategiyasini j1 va j2 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 matritsasibo`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
tengliklarni qanoatlantiradi. Bundan tashqari, bo`lgani uchun
U vaqtda (13) tengliklar
ko`rinishga keladi. Bu tengliklardan ni topamiz. SHunday qilib,
I o`yinchining optimal strategiyasidir.
4358 marta o`qildi.
![]() |
![]() |