Antagonistik matritsali o'yinlar. Matritsali o'yinni yechish Antagonistik matritsali o'yinlar

O'yin nazariyasida asosiy taxmin sifatida, har bir o'yinchi sherigining har qanday harakatlarida o'zi uchun mumkin bo'lgan maksimal g'alabani ta'minlashga intiladi, deb taxmin qilinadi. Faraz qilaylik, birinchi o'yinchining to'lov matritsasi va shunga mos ravishda ikkinchi o'yinchining to'lov matritsasi bilan cheklangan nol yig'indili o'yin mavjud. 1-o'yinchiga qanday strategiya tanlagan bo'lishidan qat'i nazar, 2-o'yinchi o'zining daromadini maksimal darajada oshiradigan va shu bilan 1-o'yinchining daromadini kamaytiradigan strategiyani tanlashiga ishonsin.

Shunday qilib, o'yinchi 1 tanlaydi i

2-o'yinchi, shuningdek, raqibning tanlangan strategiyasidan qat'i nazar, eng yuqori yutuqni (yoki teng ravishda, eng kichik yo'qotish miqdorini) ta'minlashga intiladi. Uning optimal strategiyasi ustun bo'ladi H 0 eng kam maksimal to'lov bilan. Shunday qilib, o'yinchi 2 tanlaydi j- muammoning yechimi bo'lgan strategiya

Natijada, agar o'yinchi 1 tanlangan strategiyaga amal qilsa (deb ataladi maksimal strategiya ), uning to'lovi har qanday holatda ham maksimal qiymatdan kam bo'ladi (deb ataladi "o'yinning pastki narxi" ), ya'ni.

Shunga ko'ra, agar o'yinchi 2 o'zining minimaks strategiyasiga rioya qilsa, uning yo'qotishi maksimal qiymatdan oshmaydi (deb ataladi). "o'yinning eng yuqori narxi" ), ya'ni.

Agar o'yinning yuqori narxi past narxga teng bo'lsa, ya'ni. = , har ikkala o'yinchi ham kafolatlangan to'lovlarini va qiymatini oladi h ij * chaqirdi o'yin narxida .

Matritsa elementi h ij strategiyalarga mos keladigan to'lov matritsasi deyiladi matritsaning egar nuqtasi N.

Agar antagonistik o'yinning narxi 0 bo'lsa, o'yin chaqiriladi adolatli .

1-o'yinchi ikkita strategiyaga ega va 2-o'yinchi uchta strategiyaga ega bo'lgan o'yinni ko'rib chiqaylik. O'yinchi 1ning to'lov matritsasi quyidagicha ko'rinadi:

Izoh . Biz nol summali o'yin misolini ko'rib chiqayotganimiz sababli, 2-o'yinchining to'lov matritsasi bo'ladi. N 2 = -H 1.

1-o'yinchi, agar u birinchi strategiyani (ya'ni, matritsaning birinchi qatorini) tanlasa, hisoblaydi. H 1), keyin raqib ikkinchi strategiyasini (ya'ni ikkinchi ustunni) tanlaydi, shunda to'lov teng bo'ladi. 1 . Agar u ikkinchi strategiyani tanlasa, raqib birinchi strategiyani tanlashi mumkin, shuning uchun foyda teng bo'ladi. -1.

Olingan qiymatlarni tahlil qilib: 1-o'yinchi o'zining birinchi strategiyasiga qaror qiladi, bu unga 1 ga teng maksimal kafolatlangan g'alabani beradi.

Xuddi shunday, 2-o'yinchi raqib birinchi yoki ikkinchi strategiyani tanlaganda yoki ikkinchi o'yinchi uchinchi ustunni tanlaganda raqib ikkinchi strategiyani tanlaganida o'zining eng yomon variantlarini ko'rib chiqadi. Ushbu variantlar 2, 1 va 6-ustunlarning maksimal qiymatlariga mos keladi.

Ushbu maksimallarning minimal qiymatlarini olib, 2-o'yinchi o'zining yo'qotishi minimal va teng bo'lgan ikkinchi strategiyasiga qaror qiladi:

Binobarin, ushbu o'yinda strategiyalarning birgalikdagi tanlovi mavjud. E

Shuning uchun, bu o'yinda raqiblar tanlagan strategiyalariga sodiq qolishlarini kutish o'rinli. Buning uchun matritsa antagonistik o'yin - butunlay aniq o'yin yoki sof strategiyalarda yechimga ega bo'lgan o'yin deb ataladi.

Biroq, barcha matritsa antagonistik o'yinlari aniq belgilanmagan.

Qat'iy tengsizlik mavjud bo'lgan o'yinlar to'liq aniqlanmagan o'yinlar (yoki sof strategiyalarda yechimga ega bo'lmagan o'yinlar) deb ataladi.

Keling, ushbu o'yinning misolini ko'rib chiqaylik:

Bu o'yin uchun.

Natijada, agar o'yinchilar yuqorida tavsiya etilgan qoidalarga rioya qilsalar, u holda 1-o'yinchi 1-strategiyani tanlaydi va 2-o'yinchi 2-strategiyani tanlashini kutadi, bu erda yo'qotish -2, 2-o'yinchi esa 3-strategiyani tanlaydi va 1-o'yinchini kutishadi. 4 ga teng foyda bilan 2-strategiyani tanlang.

Biroq, agar o'yinchi 2 o'zining uchinchi strategiyasini tanlasa, 1-o'yinchi birinchi strategiyani emas, balki ikkinchi strategiyani tanlash orqali yaxshiroq ishlaydi. Xuddi shunday, agar birinchi o'yinchi birinchi strategiyani tanlasa, ikkinchi o'yinchi uchinchi strategiyani emas, balki ikkinchi strategiyani tanlagani ma'qul. Ko'rinishidan, ayyor turdagi o'yinlarda sof strategiyalardagi yechim printsipi yaroqsiz bo'lib chiqadi.

Ta'riflangan vaziyatda o'yinchilar uchun dushman qanday strategiyadan foydalanishini taxmin qilmasligi muhim bo'ladi. Ushbu rejani amalga oshirish uchun o'yinchilar aralash strategiya deb ataladigan strategiyadan foydalanishlari kerak.

Aslida, o'yinchining aralash strategiyasi tasodifiy ravishda sof strategiyani tanlash sxemasidir. Matematik jihatdan uni ma'lum bir o'yinchining sof strategiyalari to'plamida ehtimollik taqsimoti sifatida ko'rsatish mumkin. Natijada, vektor , bu erda 1-o'yinchining strategiyadan foydalanish ehtimoliga mos keladi va bu o'yinchining aralash strategiyasini belgilaydi. 2-o'yinchining aralash strategiyasi ham xuddi shunday aniqlanadi .

Biz o'yinchilarning aralash strategiyalaridan foydalanishlari mustaqil deb faraz qilamiz, shuning uchun 1-o'yinchi ushbu strategiyani tanlashi va 2-o'yinchi tanlashi ehtimoli ga teng bo'ladi. Bunday holda to'lov. Xulosa qilib, 1-o‘yinchining yutug‘ining matematik taxminini topamiz:

yoki matritsa yozuvi

Aralashtirilgan strategiyalar to'plamida 1-o'yinchi kafolatlangan yutuqlarning eng kattasiga erishishga intilib, kutilgan yutuqning minimal qiymatlarining maksimalini olish uchun ehtimollar vektorini tanlaydi, ya'ni. bu muammoni hal qiladi:

.

Xuddi shunday, 2-o'yinchining maqsadi uning yo'qotishlarining minimal maksimal qiymatlariga erishishdir, ya'ni. u muammoni hal qiladi

.

O'yin nazariyasining asosiy natijasi Minimaks teoremasi bo'lib, unda 1-o'yinchi va 2-o'yinchining tuzilgan muammolari har doim har qanday to'lov matritsasi uchun yechimga ega ekanligini va qo'shimcha ravishda .

Aniq belgilangan o'yinlarga kelsak, 1-o'yinchining strategiyasi deyiladi Maksimal strategiya , O'yinchi 2 strategiyasi - Minimax strategiyasi, qiymati - o'yin narxida ; o'yin adolatli deb ataladigan holatda.

Minimaks teoremasining yaqqol natijasi bu munosabatdir:

.

Bu shuni anglatadiki, agar o'yinchi 2 o'zining minimaks strategiyasini qo'llasa, 1-o'yinchining hech qanday strategiyasi unga o'yin narxidan kattaroq summani yutib olishga imkon bermaydi va 2-o'yinchining hech qanday strategiyasi unga o'yin narxidan kamroq miqdorni yo'qotishga imkon bermaydi. agar o'yinchi 1 maksimal strategiyasini qo'llasa.

Bu aralash strategiyalarning alohida holati sifatida sof strategiyalar uchun ham amal qiladi. (Chunki sof strategiya 1-ehtimollik bilan qo'llaniladigan strategiyadir): Har qanday sof strategiyadan foydalanish, agar raqib o'zining optimal strategiyasidan foydalansa, o'yin narxidan ko'proq yutish (kamroq yo'qotish) imkonini bermaydi.

Bu fakt ko'pincha antagonistik matritsali o'yinlarni hal qilish uchun maxsus algoritmlarni ishlab chiqish uchun ishlatiladi.

Optimal strategiyalarni hisoblash strategiyalar soni ortib borishi bilan ancha qiyinlashadi. Optimal strategiyalarni topish uchun bir nechta yondashuvlardan foydalanish mumkin.

O'yin hajmini kamaytirish uchun satr va ustun ustunligi qo'llaniladi. Odatda aytiladiki, matritsaning i-qatori birinchi qatorda hukmronlik qiladi (ya'ni, bitta sof qator boshqasida hukmronlik qiladi), agar hamma uchun bo'lsa, kamida bittasi.

Xuddi shunday, th ustun, agar hamma uchun kamida bitta bo'lsa, ustunlik qiladi.

Ushbu ta'rifning mohiyati shundaki, dominant strategiya hech qachon ustun bo'lgan strategiyadan yomonroq va ba'zi hollarda undan ham yaxshiroq emas. Demak, muhim xulosa shundaki, o'yinchi ustunlik qiladigan strategiyadan foydalanishi shart emas. Bu amalda barcha ustun bo'lgan satr va ustunlarni yo'q qilishga imkon beradi, bu matritsa hajmini kamaytiradi (esda tutingki, bu yondashuv sof strategiyalarda yechim izlashda ham qo'llanilishi mumkin).

Misol. Quyidagi matritsaga ega o'yinni ko'rib chiqing:

Ikkinchi qatorni olib tashlash matritsaga olib keladi: Ushbu kesilgan matritsadagi uchinchi ustunda ikkinchi ustunlik qiladi va ikkinchi ustunni tashlab qo'yish quyidagilarni beradi: .

Natijada, agar natijada paydo bo'lgan o'yin uchun yechim topilsa, undan chiqarib tashlangan qatorlar va ustunlarga nol ehtimolliklarni belgilash orqali original o'yinni echish uchun osongina foydalanish mumkin.

Matritsani soddalashtirishning yana bir usuli, to'lov matritsasining affin o'zgarishi (ya'ni, matritsaning barcha elementlarini qoida bo'yicha o'zgartirish, bu erda) o'yin echimini o'zgartirmasligiga asoslanadi; bundan tashqari, konvertatsiya qilingan o'yinning narxi bir xil qoidadan foydalangan holda asl o'yin narxidan olinishi mumkin: . Bu shuni anglatadiki, o'yin vazifasi uchun, qoida tariqasida, yutuqlar qaysi birliklarda o'lchanishi muhim emas (rubl yoki dollarda); ba'zi bir belgilangan miqdorni qo'shish (ayirish) har bir o'yinchining g'alabasini (yo'qotishini) o'zgartiradi. o'yinning yechimini o'zgartirmasdan bir xil miqdorda.

Ushbu xususiyatdan to'lov matritsasini soddalashtirish va aniqroq qilish uchun foydalanish mumkin (matritsalar bo'yicha operatsiyalarga o'xshashlik bilan foydalaniladi - matritsani doimiy songa ko'paytirish, qatorlarni qo'shish va ayirish, qo'shimcha ravishda bu xususiyat har qanday matritsa nol yig'indisi o'yinini amalga oshirishga imkon beradi. adolatli, buning uchun to'lov matritsasining barcha elementlaridan narx o'yinlarini hisoblash kerak).

Bundan tashqari, o'yinni (va umuman o'yinlarni) hal qilish uchun grafik usuldan foydalanish mumkin.

Masalan, to'lov matritsasi quyidagicha ko'rinadi: .

O'yinchi 1 o'zining birinchi strategiyasini ehtimol bilan, ikkinchisini esa ehtimol bilan tanlasin. Agar 2-o'yinchi o'zining birinchi strategiyasini tanlasa, u holda (matritsaning birinchi ustunidan) 1-o'yinchi uchun kutish bo'ladi. Agar o'yinchi 2 ikkinchi strategiyasini tanlasa, u holda matritsaning ikkinchi ustuniga muvofiq: .

Ushbu tenglamalarning har biri grafikda koordinatalari va koordinatalari bo'lgan maydonda to'g'ri chiziq segmenti bilan tasvirlanishi mumkin.

Yakuniy nazorat uchun testlar

1. Antagonistik o'yinni o'rnatish mumkin:

a) ikkala o'yinchi uchun strategiyalar to'plami va egar nuqtasi.

b) ikkala o'yinchi uchun strategiyalar to'plami va birinchi o'yinchining to'lov funktsiyasi.

2. O'yin narxi har doim aralash strategiyalardagi matritsali o'yinlar uchun mavjud.

a) ha.

3.Agar to'lov matritsasidagi barcha ustunlar bir xil bo'lsa va (4 5 0 1) ko'rinishga ega bo'lsa, 1-o'yinchi uchun qanday strategiya optimal?

a) birinchi.

b) ikkinchi.

c) to'rttasining istalgani.

4. Matritsali o‘yinda 1-o‘yinchining aralash strategiyalaridan biri (0,3, 0,7), 2-o‘yinchining aralash strategiyalaridan biri esa (0,4, 0, 0,6) ko‘rinishga ega bo‘lsin. Ushbu matritsaning o'lchami qanday?

a) 2*3.

c) boshqa o'lchov.

5. Dominantlik printsipi matritsadan bir bosqichda olib tashlash imkonini beradi:

a) butun qatorlar.

b) individual raqamlar.

6. 2*m o‘yinlarni echishning grafik usulida to‘g‘ridan-to‘g‘ri grafikdan topiladi:

a) ikkala o'yinchining optimal strategiyalari.

b) o'yinning narxi va 2-o'yinchining optimal strategiyalari.

c) o'yinning narxi va 1-o'yinchining optimal strategiyalari.

7. 2*m o‘yinlarni grafik usulda yechish uchun pastki konvertning grafigi umumiy holatda:

a) buzilgan.

b) to'g'ri.

c) parabola.

8. 2*2 matritsali oʻyinda oʻyinchining aralash strategiyasining ikkita komponenti mavjud:

a) bir-birining qadriyatlarini aniqlash.

b) mustaqil.

9. Matritsali o‘yinda aij elementi:

a) 1-o‘yinchi i-strategiyadan foydalanganda, ikkinchi o‘yinchi esa j-strategiyadan foydalanganda yutuqlari.

b) raqib i-chi yoki j-chi strategiyadan foydalanganda 1-o'yinchining optimal strategiyasi.

v) j-strategiyadan foydalanganda 1-o'yinchining yo'qolishi, 2-chi - i-strategiya.

10.Aij matritsa elementi egar nuqtasiga mos keladi. Quyidagi holatlar mumkin:

a) bu element qat'iy ravishda barcha qatordagi eng kichigidir.

b) bu ​​element satrda ikkinchi o'rinda turadi.

11. Braun-Robinson usulida har bir o'yinchi keyingi bosqichda strategiya tanlashda quyidagilarga rahbarlik qiladi:

a) oldingi qadamlardagi dushmanning strategiyalari.

b) oldingi bosqichlardagi strategiyalaringiz.

c) boshqa narsa.

12. Matematik kutish mezoniga ko'ra, har bir o'yinchi quyidagilardan kelib chiqadi:

a) uning uchun eng yomon vaziyat yuzaga keladi.

c) barcha yoki ba'zi holatlar ba'zi berilgan ehtimollar bilan mumkin.

13. Matritsali o‘yin barcha elementlari manfiy bo‘lgan matritsa bilan berilgan bo‘lsin. O'yinning narxi ijobiy:

b) yo'q.

c) aniq javob yo'q.

14. O'yinning narxi:

a) raqam.

b) vektor.

c) matritsa.

15. 5*5 oʻlchamli oʻyinda egar nuqtalarining maksimal soni qancha boʻlishi mumkin (matritsada istalgan raqamlar boʻlishi mumkin):

16. 2*3 o‘lchamli matritsali o‘yinda 1-o‘yinchining aralash strategiyalaridan biri (0,3, 0,7), 2-o‘yinchining aralash strategiyalaridan biri esa (0,3, x, 0,5) ko‘rinishga ega bo‘lsin. . x soni nima?

c) boshqa raqam.

17. Vald mezoni o'yin matritsasining qaysi o'lchami uchun Laplas mezoniga aylanadi?

v) faqat boshqa hollarda.

18. O'yinning yuqori narxi har doim o'yinning past narxidan past bo'ladi.

b) yo'q.

b) savol noto'g'ri.

19. Matritsali o‘yinda qanday strategiyalar mavjud?

a) toza.

b) aralash.

c) ikkalasi.

20. Ba'zi antagonistik o'yinlarda o'zgaruvchilarning ba'zi qiymatlari uchun ikkala o'yinchining to'lov funktsiyasining qiymatlari 1 ga teng bo'lishi mumkinmi?

a) har doim.

b) ba'zan.

c) hech qachon.

21. Matritsali o‘yinda 1-o‘yinchining aralash strategiyalaridan biri (0,3, 0,7), 2-o‘yinchining aralash strategiyalaridan biri (0,4, 0,1,0,1,0,4) ko‘rinishda bo‘lsin. . Ushbu matritsaning o'lchami qanday?

c) boshqa o'lchov.

22. Dominantlik printsipi matritsadan bir bosqichda olib tashlash imkonini beradi:

a) butun ustunlar,

b) individual raqamlar.

c) kichikroq kattalikdagi submatritsalar.

23. 3*3 matritsali oʻyinda oʻyinchining aralash strategiyasining ikkita komponenti mavjud:

a) uchinchisini aniqlang.

b) aniqlamaydi.

24. Matritsali o‘yinda aij elementi:

a) j-strategiyadan foydalanganda 2-o'yinchining yo'qolishi, 2-chi esa - i-strategiya.

b) raqib i-chi yoki j-chi strategiyadan foydalanganda 2-o'yinchining optimal strategiyasi;

c) 1-o'yinchi j-strategiyadan foydalanganda, ikkinchi o'yinchi esa i-strategiyadan foydalanganda yutuq;

25. aij matritsa elementi egar nuqtasiga mos keladi. Quyidagi holatlar mumkin:

a) bu element ustundagi eng katta element.

b) bu ​​element qat'iy ravishda qatordagi eng kattasidir.

c) satrda bu elementdan katta va kichik elementlar mavjud.

26. Vald mezoniga ko'ra, har bir o'yinchi:

a) uning uchun eng yomon vaziyat yuzaga keladi.

b) barcha holatlar teng darajada mumkin.

c) ma'lum bir ehtimollik bilan barcha holatlar mumkin.

27. Pastki narx o'yinning yuqori narxidan past:

b) har doim ham emas.

c) hech qachon.

28. Matritsali o‘yin uchun aralash strategiya komponentlarining yig‘indisi har doim:

a) 1 ga teng.

b) salbiy emas.

c) ijobiy.

d) har doim ham emas.

29. 2*3 o‘lchamli matritsali o‘yinda 1-o‘yinchining aralash strategiyalaridan biri (0,3, 0,7), 2-o‘yinchining aralash strategiyalaridan biri esa (0,2, x, x) ko‘rinishga ega bo‘lsin. . x soni nima?

Yaxshi ishingizni bilimlar bazasiga yuborish oddiy. Quyidagi shakldan foydalaning

Talabalar, aspirantlar, bilimlar bazasidan o‘z o‘qishlarida va ishlarida foydalanayotgan yosh olimlar sizdan juda minnatdor bo‘lishadi.

Kirish

1. Nazariy qism

1.3 O'yin tartibi 2x2

1.4 Algebraik usul

1.5 Grafik usul

1.6 O'yinlar 2xn yoki mx2

1.7 Matritsa usuli yordamida o'yinlarni yechish

2. Amaliy qism

2.2 O'yinlar 2xn va mx2

2.3 Matritsa usuli

2.4 Jigarrang usul

Natijalarni tahlil qilish

Kirish

Nol summali o'yin nol yig'indili o'yindir. Nol summali o'yin - bu to'lovlari qarama-qarshi bo'lgan ikki o'yinchi ishtirokidagi hamkorliksiz o'yin.

Rasmiy ravishda, antagonistik o'yin troyka bilan ifodalanishi mumkin , bu erda X va Y mos ravishda birinchi va ikkinchi o'yinchilarning strategiyalar to'plamidir, F birinchi o'yinchining to'lov funktsiyasi bo'lib, har bir juft strategiyani (x,y) tayinlaydi, bu erda haqiqiy raqamning foydasiga mos keladi. ma'lum bir vaziyatni amalga oshirishda birinchi o'yinchi.

O'yinchilarning manfaatlari qarama-qarshi bo'lganligi sababli, F funktsiyasi bir vaqtning o'zida ikkinchi o'yinchining yo'qolishini anglatadi.

Tarixiy jihatdan, nol yig'indisi o'yinlar qimor o'yinlari tasvirlangan matematik o'yin nazariyasi modellarining birinchi sinfidir. Ushbu tadqiqot mavzusi o'yin nazariyasi o'z nomini olgan deb ishoniladi. Hozirgi vaqtda antagonistik o'yinlar kooperativ bo'lmagan o'yinlarning kengroq sinfining bir qismi hisoblanadi.

1. Nazariy qism

1.1 O'yinning asosiy ta'riflari va qoidalari

O'yin o'yindagi ishtirokchilar sonini, ularning mumkin bo'lgan harakatlari va yutuqlarni ularning xatti-harakatlari va natijalariga qarab taqsimlashni belgilaydigan qoidalar tizimi bilan tavsiflanadi. O'yinchi boshqa guruhlarning manfaatlariga to'g'ri kelmaydigan umumiy manfaatlarga ega bo'lgan bitta ishtirokchi yoki o'yin ishtirokchilari guruhi hisoblanadi. Shuning uchun har bir ishtirokchi o'yinchi hisoblanmaydi.

O'yin qoidalari yoki shartlari o'yin rivojlanishining istalgan bosqichida o'yinchilarning mumkin bo'lgan xatti-harakatlari, tanlovlari va harakatlarini belgilaydi. O'yinchi uchun tanlov qilish uning xatti-harakatlaridan birini tanlashni anglatadi. Keyin o'yinchi harakatlar yordamida ushbu tanlovlarni amalga oshiradi. Harakat qilish o'yinning ma'lum bir bosqichida o'yin qoidalarida ko'zda tutilgan imkoniyatlarga qarab bir vaqtning o'zida to'liq yoki bir qismini tanlashni anglatadi. Har bir o'yinchi o'yinning ma'lum bir bosqichida qilgan tanloviga ko'ra harakat qiladi. Boshqa o'yinchi birinchi o'yinchining tanlovini bilib yoki bilmagan holda ham harakat qiladi. Har bir o'yinchi, agar o'yin qoidalarida bunday imkoniyatga ruxsat berilsa, o'yinning o'tmishdagi rivojlanishi haqidagi ma'lumotlarni hisobga olishga harakat qiladi.

O'yin natijasida yuzaga keladigan vaziyatga qarab, o'yinchiga har bir harakatda qanday tanlov qilish kerakligini aniq ko'rsatadigan qoidalar to'plami o'yinchi strategiyasi deb ataladi. O'yin nazariyasidagi strategiya o'yinchi uchun o'yin rivojlanishining barcha mumkin bo'lgan holatlarida qanday harakat qilish kerakligini ko'rsatadigan ma'lum bir to'liq harakat rejasini anglatadi. Strategiya - bu o'yin rivojlanishining istalgan bosqichida o'yinchi uchun mavjud bo'lgan har qanday ma'lumot holati bo'yicha barcha ko'rsatmalar yig'indisini anglatadi. Bundan allaqachon ma'lum bo'ladiki, strategiyalar yaxshi va yomon, muvaffaqiyatli va muvaffaqiyatsiz va hokazo bo'lishi mumkin.

Nol summali o'yin, agar uning har bir o'yinidagi barcha o'yinchilarning yutuqlari yig'indisi nolga teng bo'lsa, ya'ni nol summali o'yinda barcha o'yinchilarning umumiy kapitali o'zgarmaydi, lekin o'yinchilar o'rtasida qayta taqsimlanadi. olingan natijalarga qarab. Shunday qilib, ko'plab iqtisodiy va harbiy vaziyatlarni nol summali o'yinlar sifatida ko'rish mumkin.

Xususan, ikki o'yinchi o'rtasidagi nol summali o'yin antagonistik deb ataladi, chunki undagi o'yinchilarning maqsadlari to'g'ridan-to'g'ri qarama-qarshidir: bir o'yinchining daromadi faqat ikkinchisining yo'qotishi hisobiga sodir bo'ladi.

1.1.1 Sof strategiyalarda matritsali o'yinlarning ta'rifi, misollari va echimlari

Ikki o'yinchi nol yig'indili matritsali o'yinni quyidagi mavhum ikki o'yinchili o'yin sifatida tasavvur qilish mumkin.

Birinchi o'yinchi t strategiyaga ega: i =1, 2,…, t, ikkinchisida n ta strategiya mavjud j = 1, 2,…, p. Har bir juft strategiya (i, j) a ij raqami bilan bog'langan bo'lib, uni ifodalaydi. agar birinchi o'yinchi o'zining i-strategiyasidan, ikkinchi o'yinchi esa j-chi strategiyasidan foydalansa, ikkinchi o'yinchi hisobiga birinchi o'yinchining yutug'i.

Har bir o'yinchi bitta harakat qiladi: birinchi o'yinchi o'zining i-strategiyasini tanlaydi (i = 1, 2,..., m), ikkinchisi o'zining j-strategiyasini tanlaydi (j = 1, 2,..., n) , shundan so'ng birinchi o'yinchi ikkinchi o'yinchi hisobidan ij yutuq oladi (agar a ij bo'lsa< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

O'yinchining har bir strategiyasi i = 1, 2,…, t; j = 1, 2,…, n odatda sof strategiya deb ataladi.

Ikki o'yinchidan iborat nol yig'indili matritsali o'yin bundan buyon oddiygina matritsali o'yin deb ataladi. Shubhasiz, matritsa o'yini antagonistik o'yinlarga tegishli. Uning ta'rifidan kelib chiqadiki, matritsali o'yinni aniqlash uchun birinchi o'yinchining to'lovlari tartibining A = (a ij) matritsasini ko'rsatish kifoya.

Agar biz to'lov matritsasini ko'rib chiqsak

keyin A matritsasi bilan matritsali o'yinning har bir o'yinini o'ynash i-qatorning birinchi o'yinchisi va j-ustunning ikkinchi o'yinchisi va qabul qiluvchi birinchi o'yinchi (ikkinchi o'yin hisobidan) tanloviga qisqartiriladi. ) A matritsasida i-qator va j-ustun kesishmasida joylashgan yutuq.

Haqiqiy ziddiyatli vaziyatni matritsali o'yin shaklida rasmiylashtirish uchun har bir o'yinchining sof strategiyalarini aniqlash va qayta raqamlash va to'lov matritsasini yaratish kerak.

Keyingi bosqich - o'yinchilarning optimal strategiyalari va yutuqlarini aniqlash.

O'yinlarni o'rganishda asosiy narsa o'yinchilarning optimal strategiyalari kontseptsiyasidir. Ushbu kontseptsiya intuitiv ravishda quyidagi ma'noga ega: agar ushbu strategiyadan foydalanish unga boshqa o'yinchining barcha mumkin bo'lgan strategiyalari uchun eng katta kafolatlangan g'alabani ta'minlasa, o'yinchining strategiyasi optimal hisoblanadi. Ushbu pozitsiyalarga asoslanib, birinchi o'yinchi (1.1) formuladan foydalanib, o'z daromadlarining A matritsasini quyidagicha tekshiradi: i ning har bir qiymati uchun (i = 1, 2,..., t) minimal to'lov qiymatiga qarab belgilanadi. ikkinchi o'yinchi tomonidan ishlatiladigan strategiyalar

(i = 1, 2,..., m) (1.2)

ya'ni birinchi o'yinchi uchun minimal to'lov aniqlanadi, agar u o'zining i - sof strategiyasini qo'llasa, keyin bu minimal to'lovlardan i = i 0 strategiyasi topiladi, buning uchun bu minimal foyda maksimal bo'ladi, ya'ni.

Ta'rif. Formula (1.3) bo'yicha aniqlangan b raqami o'yinning pastki sof narxi deb ataladi va birinchi o'yinchi ikkinchi o'yinchining barcha mumkin bo'lgan harakatlari uchun o'zining sof strategiyalarini qo'llash orqali o'zi uchun qanday minimal yutuqlarni kafolatlashi mumkinligini ko'rsatadi.

Ikkinchi o'yinchi o'zining optimal xulq-atvori bilan, agar iloji bo'lsa, o'z strategiyalari orqali birinchi o'yinchining yutug'ini minimallashtirishga harakat qilishi kerak. Shuning uchun, biz ikkinchi o'yinchi uchun topamiz

ya'ni birinchi o'yinchining maksimal daromadi aniqlanadi, agar ikkinchi o'yinchi o'zining j-sof strategiyasini qo'llasa, ikkinchi o'yinchi o'zining j = j 1 strategiyasini topadi, bunda birinchi o'yinchi minimal foyda oladi, ya'ni topadi.

Ta'rif. Formula (1.5) bo'yicha aniqlangan b raqami o'yinning sof yuqori narxi deb ataladi va birinchi o'yinchi o'z strategiyalari orqali o'zi uchun qanday maksimal yutuqni kafolatlashi mumkinligini ko'rsatadi. Boshqacha qilib aytadigan bo'lsak, o'zining sof strategiyalarini qo'llash orqali birinchi o'yinchi b dan kam bo'lmagan daromadni ta'minlashi mumkin, ikkinchi o'yinchi esa o'zining sof strategiyalarini qo'llash orqali birinchi o'yinchining b dan ko'p yutishini oldini oladi.

Ta'rif. Agar A matritsasi bo'lgan o'yinda o'yinning pastki va yuqori sof narxlari mos kelsa, ya'ni b = c bo'lsa, bu o'yin sof strategiyalarda egar nuqtasi va o'yinning sof narxiga ega deb aytiladi:

n = b = v (1,6)

Egar nuqtasi - bu tenglikka erishiladigan mos ravishda birinchi va ikkinchi o'yinchilarning bir juft sof strategiyasi ()

Egar nuqtasi tushunchasi quyidagi ma'noga ega: agar o'yinchilardan biri egar nuqtasiga mos keladigan strategiyaga rioya qilsa, ikkinchi o'yinchi egar nuqtasiga mos keladigan strategiyaga rioya qilishdan yaxshiroq ish qila olmaydi. O'yinchining eng yaxshi xulq-atvori uning yutug'ining kamayishiga olib kelmasligi va eng yomon xatti-harakati uning yutug'ining kamayishiga olib kelishi mumkinligini hisobga olib, ushbu shartlarni matematik tarzda quyidagi munosabatlar shaklida yozish mumkin:

bu erda i, j mos ravishda birinchi va ikkinchi o'yinchilarning har qanday sof strategiyalari; (i 0, j 0) egar nuqtasini tashkil etuvchi strategiyalardir. Quyida biz egar nuqtasining ta'rifi shartlarga (1.8) ekvivalent ekanligini ko'rsatamiz.

Shunday qilib, (1.8) ga asoslanib, egar elementi A matritsaning i 0-qatorida minimal va j 0-ustunida maksimaldir. A matritsaning egar nuqtasini topish oson: A matritsada minimal element ketma-ket topiladi. Har bir qatorni tanlang va ushbu element uning ustunidagi maksimal qiymat ekanligini tekshiring. Agar shunday bo'lsa, u egar elementidir va unga mos keladigan strategiyalar juftligi egar nuqtasini tashkil qiladi. Egar nuqtasi va egar elementini tashkil etuvchi birinchi va ikkinchi o'yinchilarning bir juft sof strategiyasi (i 0, j 0) o'yinning yechimi deb ataladi.

Egar nuqtasini tashkil etuvchi i 0 va j 0 sof strategiyalar mos ravishda birinchi va ikkinchi o'yinchilarning optimal sof strategiyalari deb ataladi.

Teorema 1. f (x, y) ikkita x A va y B o‘zgaruvchilarning real funksiyasi bo‘lsin va mavjud bo‘lsin.

keyin b = c.

Isbot. Minimal va maksimal ta'rifdan kelib chiqadiki

Chunki (1.11) ning chap tomonida x ixtiyoriydir, demak

Tengsizlikning o'ng tomonida (1.12) y ixtiyoriy, shuning uchun

Q.E.D.

Xususan, () matritsa f (x, y) funksiyaning maxsus holatidir, ya'ni x = i, y = j, = f (x, y) ni qo'ysak, u holda 1-teoremadan biz pastki to'rni olamiz. narx matritsali o'yinda o'yinning yuqori aniq narxidan oshmaydi.

Ta'rif. f (x, y) ikkita x A va y B o‘zgaruvchilarning haqiqiy funksiyasi bo‘lsin. Agar quyidagi tengsizliklar bajarilsa, (x 0, y 0) nuqta f (x, y) funksiya uchun egar nuqtasi deyiladi.

f (x, y 0) f (x 0, y 0)f (x 0, y) (1.14)

har qanday x A va y B uchun.

1.2 Optimal aralash strategiyalar va ularning xususiyatlari

Matritsali o'yinni o'rganish sof strategiyalarda uning egar nuqtasini topishdan boshlanadi. Agar matritsali o'yin sof strategiyalarda egar nuqtasiga ega bo'lsa, o'yinni o'rganish ushbu nuqtani topish bilan tugaydi. Agar matritsali o'yinda sof strategiyalarda egar nuqtasi bo'lmasa, unda ushbu o'yinning pastki va yuqori sof narxlarini topish mumkin, bu birinchi o'yinchi o'yinning yuqori narxidan ko'proq g'alaba qozonishga umid qilmasligi kerakligini ko'rsatadi va mumkin. o'yin narxidan kam bo'lmagan yutuqni olishingizga ishonch hosil qiling. Sof strategiyalarda egar nuqtasi bo'lmagan matritsali o'yinda o'yinchilarning xatti-harakatlariga oid bunday tavsiyalar tadqiqotchilar va amaliyotchilarni qoniqtirmaydi. Matritsali o'yinlarning echimlarini takomillashtirishni sof strategiyalardan foydalanishning maxfiyligi va o'yinlar shaklida o'yinlarni ko'p marta takrorlash imkoniyatidan foydalanishda izlash kerak. Shunday qilib, masalan, shaxmat, shashka, futbol o'yinlari o'ynaladi va har safar o'yinchilar o'z strategiyalarini shunday qo'llaydilarki, raqiblari ularning mazmuni haqida hech qanday tasavvurga ega bo'lmaydilar va bu yo'lda o'rtacha o'yinlarning butun seriyasini o'ynash orqali ma'lum yutuqlarga erishing. Ushbu yutuqlar o'rtacha o'yinning past narxidan kattaroq va o'yinning yuqori narxidan kamroq. Bu o'rtacha qiymat qanchalik yuqori bo'lsa, o'yinchi foydalanadigan strategiya shunchalik yaxshi bo'ladi. Shu sababli, sof strategiyalarni tasodifiy, ma'lum bir ehtimollik bilan qo'llash g'oyasi paydo bo'ldi. Bu ulardan foydalanish sirini to'liq ta'minlaydi. Har bir o'yinchi o'zining o'rtacha daromadini maksimal darajada oshirish va yo'lda optimal strategiyalarni olish uchun o'zining sof strategiyalaridan foydalanish ehtimolini o'zgartirishi mumkin. Bu g'oya aralash strategiya kontseptsiyasiga olib keldi.

Ta'rif. O'yinchining aralash strategiyasi uning sof strategiyalaridan foydalanish ehtimolining to'liq to'plamidir.

Shunday qilib, agar birinchi o'yinchi 1, 2, … i, … m sof strategiyaga ega bo'lsa, uning x aralash strategiyasi x = (x 1, x 2, ..., x i,…, x m ) qanoatlantiruvchi raqamlar to'plamidir. munosabatlar

x i 0 (i = 1, 2, ... , t), = 1. (1.15)

Xuddi shunday, n ta sof strategiyaga ega bo‘lgan ikkinchi o‘yinchi uchun aralash strategiya y munosabatlarni qanoatlantiruvchi y = (y 1, ..., y j, ... y n) raqamlar to‘plamidir.

y j 0 (j = 1, 2, ... , n), = 1. (1.16)

O'yinchi har safar bitta sof strategiyadan foydalansa, boshqasidan foydalanishni istisno qilganligi sababli, sof strategiyalar mos kelmaydigan hodisalardir. Bundan tashqari, ular yagona mumkin bo'lgan hodisalardir.

Shubhasiz, sof strategiya aralash strategiyaning alohida holatidir. Darhaqiqat, agar aralash strategiyada biron bir i-sof strategiya bir ehtimol bilan qo'llanilsa, boshqa barcha sof strategiyalar qo'llanilmaydi. Va bu i-sof strategiya aralash strategiyaning alohida holatidir. Maxfiylikni saqlash uchun har bir o'yinchi boshqa o'yinchining tanlovidan qat'i nazar, o'z strategiyasini qo'llaydi.

Ta'rif. A matritsali o'yindagi birinchi o'yinchining o'rtacha daromadi uning to'lovlarining matematik kutilishi sifatida ifodalanadi.

E (A, x, y) = (1,20)

Shubhasiz, birinchi o'yinchining o'rtacha daromadi x va y o'zgaruvchilarning ikkita to'plamining funktsiyasidir. Birinchi o'yinchi o'zining aralash strategiyasini x o'zgartirib, o'zining o'rtacha daromadini E (A, x, y) ko'paytirishni maqsad qiladi, ikkinchi o'yinchi esa aralash strategiyalari orqali E (A, x, y) ni minimal qilishga intiladi, ya'ni. O'yinni hal qilish uchun o'yinning yuqori narxiga erishiladigan x, y ni topish kerak.

1.3 Tartibdagi o'yin 22

22-tartibdagi matritsali o'yin birinchi o'yinchi uchun quyidagi to'lov matritsasi bilan beriladi:

Ushbu o'yinning yechimi sof strategiyalarda egar nuqtasini topishdan boshlanishi kerak. Buning uchun birinchi qatordagi minimal elementni toping va uning ustunida maksimal ekanligini tekshiring. Agar bunday element topilmasa, ikkinchi qator xuddi shu tarzda tekshiriladi. Agar bunday element ikkinchi qatorda topilsa, u holda egardir.

Egar elementini topish, agar mavjud bo'lsa, uning echimini topish jarayoni tugaydi, chunki bu holda o'yinning narxi topilgan - egar elementi va egar nuqtasi, ya'ni birinchi va bir juft sof strategiyalar. optimal sof strategiyalarni tashkil etuvchi ikkinchi o'yinchi. Agar sof strategiyalarda egar nuqtasi bo'lmasa, biz aralash strategiyalarda egar nuqtasini topishimiz kerak, bu matritsa o'yinlarining asosiy teoremasi bo'yicha majburiy ravishda mavjud.

Birinchi va ikkinchi o'yinchilarning aralash strategiyalarini mos ravishda x = (x 1 , x 2), y = (y 1 , y 2) bilan belgilaymiz. Eslatib o'tamiz, x 1 birinchi o'yinchining birinchi strategiyasini qo'llash ehtimolini anglatadi va x 2 = 1 - x 1 - uning ikkinchi strategiyasidan foydalanish ehtimoli. Xuddi shunday ikkinchi o'yinchi uchun: 1 - uning birinchi strategiyadan foydalanish ehtimoli, 2 = 1 - 1 - ikkinchi strategiyadan foydalanish ehtimoli.

Teoremaning xulosasiga ko‘ra, x va y aralash strategiyalar optimal bo‘lishi uchun manfiy bo‘lmagan x 1, x 2, y 1, y 2 uchun quyidagi munosabatlar amal qilishi zarur va yetarli:

Keling, shuni ko'rsatamizki, agar matritsali o'yinda sof strategiyalarda egar nuqtasi bo'lmasa, bu tengsizliklar tenglikka aylanishi kerak:

Haqiqatdan ham. O'yinda sof strategiyalarda egar nuqtasi bo'lmasin, keyin aralash strategiyalarning optimal qiymatlari tengsizliklarni qondiradi.

0<<1, 0<< 1,

0< <1, 01. (1.25)

Faraz qilaylik (1.22) dan ikkala tengsizlik ham qat'iy

u holda teoremaga ko'ra y 1 = y 2 = 0 bo'lib, bu (1.25) shartlarga ziddir.

Xuddi shunday isbotlanganki, (1.23) dan ikkala tengsizlik ham qat'iy tengsizlik bo'la olmaydi.

Keling, tengsizliklardan biri (1.22) qat'iy bo'lishi mumkin, deb faraz qilaylik, masalan, birinchi

Bu teoremaga ko'ra y 1 = 0, y 2 = 1 ekanligini anglatadi. Natijada (1.23) dan olamiz

Agar ikkala tengsizlik (1.24) qatʼiy boʻlsa, teoremaga koʻra, (1.25) ga zid boʻlgan x 1 = x 2 = 0 boʻladi. Agar a 12 a 22 bo'lsa, u holda (1.27) tengsizliklardan biri qat'iy, ikkinchisi esa tenglikdir. Bundan tashqari, 12 va 22 ning kattaroq elementi uchun tenglik amal qiladi, ya'ni (1.27) dan bitta tengsizlik qat'iy bo'lishi kerak. Masalan, 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

Shunday qilib, agar matritsali o'yinda sof strategiyalarda egar nuqtasi bo'lmasa, birinchi o'yinchining optimal strategiyalari uchun tengsizliklar (1.22) tenglikka aylanadi. Tengsizliklar (1.23) bo'yicha shunga o'xshash fikrlash, bu holda tengsizliklar (1.23) tenglik bo'lishi kerakligiga olib keladi.

Shunday qilib, agar 22-tartibdagi matritsali o'yinda egar nuqtasi bo'lmasa, o'yinchilarning optimal aralash strategiyalari va o'yin narxini tenglamalar tizimini (1.24) echish orqali aniqlash mumkin. Shuningdek, 2x2 tartibli matritsali o'yinda o'yinchilardan biri optimal sof strategiyaga ega bo'lsa, boshqa o'yinchi ham optimal sof strategiyaga ega ekanligi aniqlangan.

Binobarin, agar matritsali o'yinda sof strategiyalarda egar nuqtasi bo'lmasa, u aralash strategiyalarda yechimga ega bo'lishi kerak, ular (1.24) tenglamalardan aniqlanadi. Tizim yechimi (1.25)

1.4 Algebraik usul

Muammolarni algebraik usul yordamida yechishning ikkita mumkin bo'lgan holatlari mavjud:

1. matritsaning egar nuqtasi bor;

2. matritsaning egar nuqtasi yo‘q.

Birinchi holda, yechim o'yinning egar nuqtasini tashkil etuvchi strategiyalar juftligidir. Keling, ikkinchi ishni ko'rib chiqaylik. Bu erda yechimlarni aralash strategiyalarda izlash kerak:

Keling, strategiyalarni topamiz va ... Birinchi o'yinchi o'zining optimal strategiyasidan foydalanganda, ikkinchi o'yinchi, masalan, ikkita sof strategiyani qo'llashi mumkin.

Bundan tashqari, mulk tufayli, agar o'yinchilardan biri optimal aralash strategiyadan foydalansa, ikkinchisi esa nolga teng bo'lmagan ehtimollik bilan o'zining optimal aralash strategiyasiga kiritilgan har qanday sof strategiyadan foydalansa, u holda g'alaba qozonishning matematik kutish har doim o'zgarishsiz va teng bo'lib qoladi. o'yin narxiga, ya'ni.

Ushbu holatlarning har birida yutuq V o'yin narxiga teng bo'lishi kerak. Bu holda quyidagi munosabatlar amal qiladi:

Ikkinchi o'yinchining optimal strategiyasi uchun (2.5), (2.6) ga o'xshash tenglamalar tizimini qurish mumkin:

Normalizatsiya shartini hisobga olgan holda:

Keling, (1.37) - (1.41) tenglamani noma'lumlarga nisbatan birgalikda yechamiz, siz bir vaqtning o'zida hammasini emas, balki uchtasini ham hal qilishingiz mumkin: alohida (1.36), (1.38), (1.40) va (1.37), ( 1.39), (1.41). Yechim natijasida biz quyidagilarni olamiz:

1.5 Grafik usul

22-o'yinning taxminiy yechimini juda oddiy grafik usul yordamida olish mumkin. Uning mohiyati quyidagicha:

1.1-rasm - uzunlik birligi kesimini topish

X o'qi bo'yicha birlik uzunlikdagi qismni tanlang. Uning chap uchi birinchi o'yinchining birinchi strategiyasini, o'ng tomoni esa ikkinchisini ifodalaydi. Barcha oraliq nuqtalar birinchi o'yinchining aralash strategiyalariga to'g'ri keladi va nuqtaning o'ng tomonidagi segmentning uzunligi birinchi strategiyadan foydalanish ehtimoliga teng va chapdagi segmentning uzunligi foydalanish ehtimoliga teng. birinchi o'yinchi tomonidan ikkinchi strategiya.

I-I va II-II ikkita eksa chizilgan. Birinchi o'yinchi birinchi strategiyadan foydalanganda I-I-ga, ikkinchi strategiyani qo'llaganida esa II-II-ga yutuqni qo'yamiz. Masalan, ikkinchi o'yinchi o'zining birinchi strategiyasini qo'llasin, so'ngra qiymat I-I o'qda, qiymat esa II-II o'qda chizilishi kerak.

Birinchi o'yinchining har qanday aralash strategiyasi uchun uning to'lovi segmentning qiymati bilan belgilanadi. I-I qator ikkinchi o'yinchining birinchi strategiyasini qo'llashiga mos keladi, biz uni ikkinchi o'yinchining birinchi strategiyasi deb ataymiz. Xuddi shunday, siz ikkinchi o'yinchining ikkinchi strategiyasini qurishingiz mumkin. Keyin, umuman olganda, o'yin matritsasining grafik ko'rinishi quyidagi shaklni oladi:

1.2-rasm - o'yin narxini topish

Ammo shuni ta'kidlash kerakki, bu qurilish birinchi o'yinchi uchun amalga oshirilgan. Bu erda segmentning uzunligi V o'yin narxiga teng.

1N2 liniyasi pastki yutuq chegarasi deb ataladi. Bu erda siz N nuqtasi birinchi o'yinchining kafolatlangan yutuqlarining maksimal miqdoriga mos kelishini aniq ko'rishingiz mumkin.

Umuman olganda, ikkinchi o'yinchining strategiyasini ham ushbu raqamdan aniqlash mumkin, masalan, quyidagi yo'llar bilan. I-I o'qi bo'yicha:

yoki II-II o'qda

Biroq, ikkinchi o'yinchining strategiyasi birinchi o'yinchi uchun qanday amalga oshirilganiga o'xshash tarzda aniqlanishi mumkin, ya'ni. shunday grafik tuzing.

1.3-rasm - ikkinchi o'yinchining strategiyasini aniqlash

Bu erda 1N2 chizig'i yo'qotishning yuqori chegarasi. N nuqtasi ikkinchi o'yinchining minimal yo'qotishiga to'g'ri keladi va u strategiyani belgilaydi.

Matritsa koeffitsientlarining o'ziga xos qiymatlariga qarab, grafikalar boshqa shaklga ega bo'lishi mumkin, masalan, bu:

1.4-rasm - birinchi o'yinchining optimal strategiyasini belgilaydi

Bunday vaziyatda birinchi o'yinchining optimal strategiyasi sof:

1.6 O'yinlar 2n yoki m2

2n tartibli o'yinlarda birinchi o'yinchi 2 ta sof strategiyaga ega, ikkinchi o'yinchi esa n ta sof strategiyaga ega, ya'ni. Birinchi o'yinchining to'lov matritsasi quyidagi shaklga ega:

Agar bunday o'yinda egar nuqtasi bo'lsa, uni topish va yechim topish oson.

O'yinda egar nuqtalari bor deb faraz qilaylik. Keyin munosabatlarni qondiradigan bunday aralash strategiyalarni va shunga mos ravishda birinchi va ikkinchi o'yinchilarni va o'yin narxi v ni topish kerak:

O'yinda egar nuqtasi bo'lmagani uchun tengsizlik (1,54) tengsizliklar bilan almashtiriladi.

(1.56), (1.55), (1.53) tizimlarini yechish uchun grafik usuldan foydalanish maqsadga muvofiqdir. Shu maqsadda biz tengsizlikning chap tomoni uchun yozuvni kiritamiz (1.53)

Matritsali o'yin matematik modeli

yoki (1.55) dan qo'yib, oddiy o'zgarishlarni amalga oshirsak, olamiz

Birinchi o'yinchining o'rtacha daromadi, agar u aralash strategiyasidan foydalansa, va ikkinchi o'yinchi o'zining j-chi sof strategiyasidan foydalanadi.

Ifodaga ko'ra, j=1, 2, …, n har bir qiymat to'rtburchaklar koordinatalar sistemasidagi to'g'ri chiziqqa mos keladi.

Ikkinchi o'yinchining maqsadi strategiyasini tanlash orqali birinchi o'yinchining yutug'ini minimallashtirishdir. Shuning uchun biz hisoblaymiz

cheklovlar to'plamining pastki chegarasi qayerda. 1.6-rasmda funksiya grafigi qalin chiziq bilan ko'rsatilgan.

http://www.allbest.ru/ saytida joylashtirilgan

1.6-rasm - funksiya grafigi

Birinchi o'yinchining maqsadi tanlov orqali o'z yutuqlarini maksimal darajada oshirishdir, ya'ni. hisoblash

1.6-rasmda nuqta eng yuqori qiymatni bildiradi. O'yinning narxi quyidagilardan iborat:

Shu tarzda birinchi o’yinchining optimal aralash strategiyasi va ikkinchi o’yinchining bir juft sof strategiyasi grafik tarzda aniqlanadi, ular kesishgan joyda nuqta hosil qiladi.1.6-rasmda ikkinchi o’yinchining 2 va 3-strategiyalari ko’rsatilgan. Bunday strategiyalar uchun tengsizliklar (1.53) tenglikka aylanadi. 1.6-rasmda bular j=2, j=3 strategiyalar.

Endi biz tenglamalar tizimini echishimiz mumkin

va qiymatlarini aniq aniqlang (grafik ravishda ular taxminan aniqlanadi). Keyin nuqta hosil qilmaydigan j uchun barcha qiymatlarni qo'yib, tenglamalar tizimini echish (1.56) 1.6-rasmda ko'rsatilgan misol uchun bu quyidagi tizimdir:

qolganlari esa bu tizimni qiyalik yo‘li bilan hal qilish mumkin. Agar ba’zi j=j 0 uchun ikkinchi o‘yinchining strategiyalari M 0 nuqtani tashkil etsa va u holda cheklovlar to‘plamining pastki chegarasining maksimal qiymati chiziqqa parallel bo‘lgan segment bilan tasvirlanadi. eksa Bu holda, birinchi o'yinchi cheksiz ko'p optimal qiymatlarga ega va o'yinning narxi Bu holat 1.7-rasmda tasvirlangan, bu erda MN segmenti yuqori chegaralarni tasvirlaydi, optimal qiymatlar chegaralar ichida Ikkinchi o'yinchi j=j 0 sof optimal strategiyaga ega.

m2 tartibli matritsali o'yinlarni grafik usul yordamida ham yechish mumkin. Bu holda birinchi o'yinchining to'lov matritsasi shaklga ega

Birinchi va ikkinchi o'yinchilarning aralash strategiyalari mos ravishda 2n tartibli o'yinlardagi kabi aniqlanadi. Birinchi o'yinchi o'zining sof i-strategiyasini (i=1, 2, ..., m), ikkinchisi - uning aralash strategiyasi (y 1, 1- y 1) =y. Masalan, m=4 grafik bo’lganda) 1.7-rasmda ko’rsatilgandek ifodalanishi mumkin.

1.7-rasm - funksiya grafigi)

Birinchi o'yinchi o'zining o'rtacha daromadini maksimal darajada oshirishga harakat qiladi, shuning uchun u topishga intiladi

Funktsiya qalin chiziq bilan ifodalanadi va cheklovlar to'plamining yuqori chegarasini ifodalaydi. Ikkinchi o'yinchi o'z strategiyasini tanlab, minimallashtirishga harakat qiladi, ya'ni. qiymati mos keladi

Rasmda qiymat nuqta bilan ko'rsatilgan. Boshqacha qilib aytadigan bo'lsak, birinchi o'yinchining ikkita strategiyasi va ikkinchi o'yinchining ehtimoli qaysi tenglikka erishilganligi aniqlanadi.

Rasmdan ko'ramizki, o'yinning narxi nuqtaning ordinatasi, ehtimollik nuqtaning abscissasidir. Optimal aralash strategiyada birinchi o'yinchining qolgan sof strategiyalari uchun ().

Shunday qilib, tizimni (1.69) hal qilish orqali biz ikkinchi o'yinchining optimal strategiyasini va o'yin narxini olamiz. Birinchi o'yinchi uchun optimal aralash strategiyani quyidagi tenglamalar tizimini yechish orqali topamiz:

1.7 O'yinlarni echish uchun matritsa usuli

Belgilar:

Tartib matritsasining istalgan kvadrat submatritsasi

Matritsa(1);

Matritsa ko'chiriladi;

B ga ulashgan matritsa;

- (1) X dan olingandan keyin o'chirilgan qatorlarga mos keladigan elementlarni o'chirish orqali olingan matritsa;

- (1) olingandan keyin o'chirilgan qatorlarga mos keladigan elementlarni o'chirish orqali olingan matritsa.

Algoritm:

1. Tartib () matritsasining kvadrat submatritsasini tanlang va hisoblang

2. Agar ba'zi yoki bo'lsa, topilgan matritsani tashlang va boshqa matritsani sinab ko'ring.

3. Agar (), (), X va dan va tegishli joylarga nollarni qo'shib hisoblaymiz va quramiz.

Tengsizliklar qondirilganligini tekshirish

hamma uchun (1,75)

va tengsizliklar

hamma uchun (1,76)

Agar munosabatlardan biri qoniqmasa, boshqasini sinab ko'ramiz. Agar barcha munosabatlar to'g'ri bo'lsa, u holda X va kerakli echimlar.

1.8 O'yin narxini ketma-ket yaqinlashish usuli

O'yin holatlarini o'rganayotganda, ko'pincha o'yinning aniq echimini olishning hojati yo'qligi yoki ba'zi sabablarga ko'ra o'yin narxining aniq qiymatini va optimal aralash strategiyalarni topish imkonsiz yoki juda qiyin bo'lishi mumkin. Keyin matritsali o'yinni echishning taxminiy usullaridan foydalanishingiz mumkin.

Keling, ushbu usullardan birini tasvirlab beraylik - o'yin narxini ketma-ket yaqinlashish usuli. Usuldan foydalanganda hisoblangan raqam to'lov matritsasining satrlari va ustunlari soniga mutanosib ravishda ortadi.

Usulning mohiyati quyidagicha: o'yin ko'p marta aqliy ravishda o'ynaydi, ya'ni. ketma-ket, o'yinning har bir o'yinida o'yinchi unga eng katta umumiy (jami) yutuqni beradigan strategiyani tanlaydi.

Ba'zi o'yinlarni bunday amalga oshirgandan so'ng, birinchi o'yinchining yutug'ining o'rtacha qiymati, ikkinchi o'yinchining yo'qotishlari hisoblab chiqiladi va ularning arifmetik o'rtacha qiymati o'yin narxining taxminiy qiymati sifatida olinadi. Usul ikkala o'yinchining optimal aralash strategiyalarining taxminiy qiymatini topishga imkon beradi: har bir sof strategiyani qo'llash chastotasini hisoblash va uni mos keladigan o'yinchining optimal aralash strategiyasida taxminiy qiymat sifatida qabul qilish kerak.

Dastur o'yinlari sonining cheksiz ko'payishi bilan birinchi o'yinchining o'rtacha daromadi va ikkinchi o'yinchining o'rtacha yo'qotishi o'yin narxiga cheksiz yaqinlashadi va aralash strategiyalarning taxminiy qiymatlariga yaqinlashishi isbotlanishi mumkin. o'yin o'ziga xos yechimga ega bo'lsa, har bir o'yinchining optimal aralash strategiyalariga moyil bo'ladi. Umuman olganda, ushbu qiymatlardan yuqori bo'lgan taxminiy qiymatlarning haqiqiy qiymatlarga yaqinlashish tendentsiyasi sekin. Biroq, bu jarayonni mexanizatsiyalash oson va shu bilan, hatto nisbatan katta tartibdagi to'lov matritsalarida ham kerakli darajadagi aniqlik bilan o'yinni hal qilishga yordam beradi.

2. Amaliy qism

Er-xotin qayerda sayr qilish va vaqtni ikkalasi uchun foydali o'tkazishni hal qiladi.

Qiz toza havo olish uchun parkda sayr qilishga, kechqurun esa eng yaqin kinoteatrda film tomosha qilishga qaror qiladi.

Yigit texnoparkga borishni va keyin markaziy stadionda mahalliy klub futbolchilarining o'yinini tomosha qilishni taklif qiladi.

Shunga ko'ra, siz o'yinchilardan birining maqsadiga erishish uchun qancha vaqt ketishini topishingiz kerak. G'olib matritsa quyidagicha ko'rinadi:

Jadval 1. To'lov matritsasi

beri 1 2 , Shubhasiz, bu o'yin sof strategiyalar egar nuqtasi yo'q. Shuning uchun biz quyidagi formulalardan foydalanamiz va olamiz:

http://www.allbest.ru/ saytida joylashtirilgan

2.2 O'yin 2xn va mx2

1-muammo(2xn)

Quruq va nam iqlim uchun ikkita don ekinlari yetishtiriladi.

Va tabiatning holatini: quruq, nam, o'rtacha deb hisoblash mumkin.

http://www.allbest.ru/ saytida joylashtirilgan

M() ning maksimal qiymati j=1, j"=2 ga to'g'ri keladigan chiziqlar kesishmasidan hosil bo'lgan M nuqtada erishiladi. Bunga ko'ra, quyidagilarni qabul qilamiz:

Muammo 2(mx2)

Bir yigit va qiz dam olish kunlari uchun qaerga borishni tanlashni ko'rib chiqmoqda.

Dam olish joyini tanlashni quyidagicha tasavvur qilish mumkin: park, kinoteatr, restoran.

http://www.allbest.ru/ saytida joylashtirilgan

M() ning maksimal qiymati j=1, j"=2 ga to'g'ri keladigan chiziqlar kesishmasidan hosil bo'lgan E nuqtada erishiladi. Bunga ko'ra, quyidagilarni qabul qilamiz:

v ning qiymatini aniqlash uchun quyidagi tenglamalarni echish kerak:

2.5 Matritsa usuli

Bir-biri bilan raqobatlashadigan ikkita restoran (ovqatlanish korxonalari) quyidagi xizmatlar to'plamini taqdim etadi. Birinchi restoran markazda, ikkinchisi esa shahar chekkasida joylashgan.

Markaziy restoran quyidagi xizmatlarni o'z ichiga oladi:

1) qimmatroq va sifatli mijozlarga xizmat ko'rsatish;

2) taomlar frantsuz oshxonasiga qaratilgan;

Ikkinchi restoran quyidagilarni ta'minlaydi:

1) arzon va sifatli xizmat;

2) menyu dunyoning turli mashhur oshxonalarini birlashtiradi;

3) shuningdek doimiy aksiyalar va chegirmalar;

4) uyga yetkazib berish uchun buyurtmalarni yetkazib beradi va qabul qiladi.

Vazifaga muvofiq, ikki restoran o'rtasida bir kunlik foyda quyidagicha taqsimlanadi:

Jadval 2. To'lov matritsasi

Matritsa usuli yordamida shakl o'yinini yechish:

Oltita submatritsa mavjud va:

Matritsani ko'rib chiqing:

x 1 =? 0, x 2 =? 0

Chunki x 2 =< 0, то мы отбрасываем.

Endi matritsani ko'rib chiqamiz:

x 1 =? 0, x 2 =? 0

O'yin narxi.

Bu nisbat talabga zid va shuning uchun mos emas.

Endi matritsani ko'rib chiqamiz:

x 1 =, x 2 =? 0,

y 1 =< 0, y 2 = ? 0.

y 1 = bo'lgani uchun< 0, то мы отбрасываем и.

Endi matritsani ko'rib chiqamiz:

x 1 =, x 2 = 0, chunki x 2 = 0, keyin biz tashlaymiz va.

Endi matritsani ko'rib chiqamiz:

x 1 =, x 2 =? 0. x 1 = 0 bo'lgani uchun biz va ni tashlaymiz.

Endi matritsani ko'rib chiqamiz:

x 1 =, x 2 =, y 1 =, y 2 =, keyin davom etamiz:

x 1 =, x 2 =, y 1 =, y 2 = yoki

O'yin narxi.

Endi asosiy aloqalar tekshiriladi:

http://www.allbest.ru/ saytida joylashtirilgan

Javob: x 1 = , x 2 =, y 1 = , y 2 = , y 3 =0, y 4 =0,.

Jigarrang usul

Muayyan kompaniya ishchilarining iltimosiga binoan kasaba uyushmasi rahbariyati bilan kompaniya hisobidan issiq tushlik tashkil etish bo'yicha muzokaralar olib boradi. Ishchilarni ifodalovchi kasaba uyushmasi tushlik imkon qadar yuqori sifatli va shuning uchun qimmatroq bo'lishini ta'minlashni xohlaydi. Kompaniya rahbariyati qarama-qarshi manfaatlarga ega. Yakunda tomonlar quyidagilarga kelishib oldilar. Kasaba uyushmasi (1-o'yinchi) issiq ovqat bilan ta'minlaydigan uchta kompaniyadan (A 1, A 2, A 3) birini tanlaydi va kompaniya rahbariyati (2-o'yinchi) uchta mumkin bo'lgan variantdan (B 1, B 2) idishlar to'plamini tanlaydi. , B 3). Shartnoma imzolangandan so'ng, kasaba uyushmasi quyidagi to'lov matritsasini yaratadi, uning elementlari idishlar to'plamining narxini ifodalaydi:

O'yin quyidagi to'lov matritsasi bilan aniqlansin:

Aytaylik, ikkinchi o'yinchi o'zining 2-strategiyasini tanladi, keyin birinchisi quyidagilarni oladi:

2, agar u birinchi strategiyasidan foydalansa,

3, agar u uchinchi strategiyasidan foydalansa.

Olingan qiymatlar 1-jadvalda jamlangan.

Jadval 3. Ikkinchi o'yinchining strategiyasi

3-jadvaldan ko'rinib turibdiki, ikkinchi o'yinchining 2-strategiyasi bilan birinchi o'zining 2 yoki 3-strategiyasidan foydalangan holda eng katta foyda 3 ni oladi. Birinchi o'yinchi maksimal g'alabaga erishmoqchi bo'lgani uchun u ikkinchi o'yinchining 2-strategiyasiga o'zining 2-strategiyasi bilan javob beradi. Birinchi o'yinchining 2-strategiyasi bilan ikkinchisi yo'qotadi:

1 agar u birinchi strategiyasidan foydalansa,

3, agar u ikkinchi strategiyasidan foydalansa,

4, agar u uchinchi strategiyasidan foydalansa.

Jadval 4. Birinchi o'yinchi strategiyasi

2-jadvaldan ko'rinib turibdiki, birinchi o'yinchining 2-strategiyasi bilan ikkinchi o'yinchi o'zining 1-strategiyasini qo'llasa, eng kichik 1 yo'qotishga ega bo'ladi. Ikkinchi o'yinchi kamroq yo'qotishni xohlayotgani uchun birinchi o'yinchining 2-strategiyasiga javoban u o'zining 1-strategiyasidan foydalanadi. Olingan natijalar 5-jadvalda jamlangan.

Jadval 5. Mos ravishda birinchi va ikkinchi o'yinchilarning strategiyalari

Jadvalda 5 ikkinchi qatordagi ikkinchi o'yinchining strategiya ustunida 1 raqami bor, bu ikkinchi o'yinda ikkinchi o'yinchi uchun o'zining 1-strategiyasidan foydalanish foydali ekanligini ko'rsatadi; ustunda birinchi o'yinchining birinchi o'yinda olgan eng katta o'rtacha 3 tasi; w ustunida birinchi o'yinda ikkinchi o'yinchi olgan eng kichik o'rtacha yo'qotish 1; v ustunida o'rtacha arifmetik v = (u + w) - ya'ni o'yinning bir o'yinini yo'qotish natijasida olingan o'yin narxining taxminiy qiymati mavjud. Agar ikkinchi o'yinchi o'zining 1-strategiyasini qo'llasa, birinchi o'yinchi o'zining 1, 2, 3-strategiyalari bilan mos ravishda 3, 1, 2 oladi va birinchi o'yinchining ikkala o'yin uchun umumiy yutug'i quyidagicha bo'ladi:

2 + 3 = 5 birinchi strategiyasi bilan,

3 + 1 = 4 ikkinchi strategiyasi bilan,

Uning 3-strategiyasi bilan 3 + 2 = 5.

Ushbu jami yutuqlar jadvalning ikkinchi qatorida qayd etilgan. 3 va birinchi o'yinchining strategiyalariga mos keladigan ustunlarda: 1, 2, 3.

Barcha umumiy yutuqlardan eng kattasi 5. U birinchi o'yinchining 1 va 3 strategiyalari bilan olinadi, keyin u ulardan istalganini tanlashi mumkin; Aytaylik, bunday hollarda, ikkita (yoki bir nechta) bir xil umumiy yutuq mavjud bo'lganda, eng kam raqamga ega strategiyani tanlang (bizning holatimizda biz 1-strategiyani olishimiz kerak).

Birinchi o'yinchining birinchi strategiyasi bilan ikkinchi o'zining 1, 2, 3 strategiyalariga mos ravishda 3, 2, 3 ni yo'qotadi va ikkinchi o'yinchining ikkala o'yin uchun umumiy yo'qotishi:

1 + 3 = 4 birinchi strategiyasi bilan,

3 + 2 = 5 ikkinchi strategiyasi bilan,

Uning 3-strategiyasi bilan 4 + 3 = 7.

Ushbu jami yo'qotishlar jadvalning ikkinchi qatorida qayd etilgan. 5 va ikkinchi o'yinchining 1, 2, 3-strategiyalariga mos keladigan ustunlarda.

Ikkinchi o'yinchining jami yo'qotishlaridan eng kichigi 4 tani tashkil etadi. Bu uning 1-strategiyasi bilan olinadi, shuning uchun uchinchi o'yinda ikkinchi o'yinchi o'zining birinchi strategiyasini qo'llashi kerak. Birinchi o'yinchining ikkita o'yin bo'yicha eng katta umumiy yutuqlari, o'yinlar soniga bo'lingan holda, ustunga joylashtiriladi, ya'ni; W ustunida ikki o'yin davomida ikkinchi o'yinchining eng kichik umumiy yo'qotishlari o'yinlar soniga bo'linadi, ya'ni; v ustunida ushbu qiymatlarning o'rtacha arifmetik qiymati qo'yiladi, ya'ni = Bu raqam ikkita "o'ynagan" o'yin bilan o'yin narxining taxminiy qiymati sifatida olinadi.

Shunday qilib, ikkita o'yin uchun quyidagi jadval 4 olinadi.

Jadval 6. Ikki o'yindan keyin o'yinchilarning umumiy yutuqlari va yo'qotishlari

6-jadvalning uchinchi qatorida ikkinchi o'yinchining strategiya ustunida 1 raqami mavjud bo'lib, bu uchinchi o'yinda ikkinchi o'yinchi o'zining 1-strategiyasini qo'llashi kerakligini ko'rsatadi. Bunday holda, birinchi o'yinchi mos ravishda 1, 2, 3 strategiyalaridan foydalangan holda 3, 1, 2 yutadi va uning uchta o'yindagi umumiy yutug'i quyidagicha bo'ladi:

3 + 5 = 8 birinchi strategiyasi bilan,

1 +4 = 5 ikkinchi strategiyasi bilan,

2 + 5 = 7 3-strategiya bilan.

Birinchi o'yinchining ushbu umumiy yutug'i 6-jadvalning uchinchi qatorida va uning 1, 2, 3 strategiyalariga mos keladigan ustunlarda qayd etilgan. Birinchi o'yinchining eng katta umumiy yutug'i 8 1-strategiya bilan olinganligi sababli, 1-chi tanlanadi. mos ravishda.

Birinchi o'yinchining birinchi strategiyasi bilan ikkinchi o'zining 1, 2, 3 strategiyalariga mos ravishda 3, 1, 2 yo'qotadi va ikkinchi o'yinchining ikkala o'yin uchun umumiy yo'qotishi:

3 + 4 = 7 birinchi strategiyasi bilan,

2 + 5 = 7 ikkinchi strategiyasi bilan,

3 + 7 = 10 3-strategiya bilan.

Ushbu jami yo'qotishlar jadvalning uchinchi qatorida qayd etilgan. 6 va ikkinchi o'yinchining 1, 2, 3-strategiyalariga mos keladigan ustunlarda. Uning jami yo'qotishlaridan 7 tasi eng kichiki bo'lib, uning 1 va 2 strategiyalari bilan olinadi, keyin ikkinchi o'yinchi birinchi strategiyasini qo'llashi kerak.

Jadvalda Ustunning uchinchi qatorida 6 va uchta o'yin davomida birinchi o'yinchining eng katta umumiy yutug'ini qayd etadi, o'yin soniga bo'linadi, ya'ni; w ustunida uchta o'yin davomida ikkinchi o'yinchining eng kichik umumiy yo'qotishlari o'yinlar soniga bo'lingan holda joylashtiriladi, ya'ni; v ustunida ularning o'rtacha arifmetik qiymati mavjud

Shunday qilib, biz stolga ega bo'lamiz. Uch o'yin uchun 7.

Jadval 7. O'ynagan uchta o'yindan so'ng o'yinchilarning umumiy yutuqlari va yo'qotishlari

8-jadval. Yigirmata o'yindan so'ng yakuniy jadval

Stoldan 7 va 8 dan ko'rinib turibdiki, 20 ta mag'lubiyatga uchragan o'yinlarda birinchi o'yinchi uchun 1, 2, 3 strategiyalari mos ravishda 12, 3, 5 marta sodir bo'ladi, shuning uchun ularning nisbiy chastotalari mos ravishda teng; ikkinchi o'yinchi uchun 1, 2, 3 strategiyalari mos ravishda 7, 11,2 marta sodir bo'ladi, shuning uchun ularning nisbiy chastotalari mos ravishda teng; o'yinning taxminiy narxi. Bu yaqinlik juda yaxshi.

Va nihoyat, shuni yodda tutingki, agar o'yin bir nechta echimga ega bo'lsa, o'yin narxining taxminiy qiymati hali ham o'yinning haqiqiy narxiga cheksiz yaqinlashadi va o'yinchilar strategiyalarining nisbiy chastotalari endi o'yinchilarning haqiqiy optimalligiga yaqinlashmaydi. aralash strategiyalar.

Natijalarni tahlil qilish

Ushbu kurs ishida biz grafik, matritsa usuli va o'yin narxini ketma-ket yaqinlashish usuli yordamida nol yig'indili o'yinlarning echimlarini topish materialini o'rgandik. Birinchi va ikkinchi o'yinchilarning optimal strategiyalari, shuningdek, 2x2, 2xn va mx2 o'yinlarida, shuningdek, matritsa usuli va Braun usulidan foydalangan holda o'yinlarda o'ynash narxi topildi.

Juftlik misolidan foydalanib, 2x2 o'yin simulyatsiya qilindi, u algebraik va grafik usullar yordamida hal qilindi. O'yinni algebraik tarzda yechish, yechim ularning optimal aralash strategiyalaridan foydalangan holda, birinchi va ikkinchi o'yinchilar birgalikda 4,6 soat vaqt sarflashlarini ko'rsatadi. Muammoning grafik yechimi kichik xatolik bilan olingan va 4,5 soatni tashkil etgan.

Shuningdek, ikkita muammo 2xn va mx2 simulyatsiya qilindi. 2xn muammosida qishloq xo'jaligi ekinlari ko'rib chiqildi va strategiya 50 dan 50 gacha maydonni ekish yaxshiroq ekanligini ko'rsatadi va o'yinning narxi 3,75 million rublni tashkil etdi. Va mx2 muammosida strategiyasi park va kinoga borish arzonroq ekanligini va narxi 4,3 rublni tashkil etadigan er-xotin ko'rib chiqildi.

Matritsa usuli uchun muammo modellashtirildi, unda ikkita restoran ko'rib chiqildi; muammoni hal qilish shuni ko'rsatdiki, uning optimal aralash strategiyasidan foydalanganda birinchi restoranning foydasi 15,6 million rublni tashkil qiladi, ikkinchisiga esa optimal aralash strategiyasidan foydalanganda. restoran, birinchi bo'lib 15,6 million rubldan ko'proq pul ishlashga ruxsat bermaydi. Grafik yechim xatolikka olib keldi va o'yinning narxi 14,9 million rublni tashkil etdi.

Braun usuli uchun kasaba uyushmasi va kompaniya rahbariyati ko'rib chiqiladigan vazifa tuzildi, ularning vazifasi ishchilarni oziq-ovqat bilan ta'minlashdir. Agar ikkala o'yinchi ham o'zlarining optimal strategiyalaridan foydalansa, bir kishi uchun oziq-ovqat 2,45 ming rublni tashkil qiladi.

Foydalanilgan manbalar ro'yxati

1) Vilisov V.Ya. Ma'ruza matnlari "O'yin nazariyasi va statistik qarorlar", - Filial - "Vosxod" MAI. 1979. 146 b.

2) Krushevskiy A.V. O'yin nazariyasi, - Kiev: Vishcha maktabi, 1977. - 216 p.

3) Cherkovchilar U., Akof R., Arnof L., Operatsion tadqiqotlarga kirish. - M.: Fan. 1967. - 488 b.

4) http://www.math-pr.com/exampl_gt2.htm

5) http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D1% 82%D0%B0%D0%B3%D0%BE%D0%BD%D0%B8%D1%81 %D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B0%D1%8F_%D0%B8%D0%B3%D1%80%D0%B0

Allbest.ru saytida e'lon qilingan

Shunga o'xshash hujjatlar

Qaror qabul qilish inson faoliyatining alohida turi sifatida. O'yin matritsasining ratsional tasviri. Sof va aralash strategiyalardagi matritsali o'yinlarga misollar. Operatsion tadqiqotlar: chiziqli dasturlash muammolarining o'yin nazariyasi modeli bilan aloqasi.

kurs ishi, 05.05.2010 qo'shilgan


Ko'p marta takrorlangan o'yinlar, ularning o'ziga xos xususiyatlari va bosqichlari. Aralash strategiyalar, ulardan amaliyotda foydalanish shartlari va imkoniyatlari. 2 x 2 turdagi o'yinni echishning analitik usuli. To'rtburchaklar o'yinlari uchun asosiy teoremalar. Algebraik yechimlar.

taqdimot, 23/10/2013 qo'shilgan


Bimatritsali o'yinlar nazariyasining asosiy ta'riflari. "Talaba-o'qituvchi" bimatritsali o'yiniga misol. Bimatrix o'yinlarida aralash strategiyalar. "Muvozanat holati" ni qidiring. 2x2 bimatritsali o'yinlar va har bir o'yinchi ikkita strategiyaga ega bo'lgan holatlar uchun formulalar.

referat, 2011-yil 13-02-da qo‘shilgan


Matritsa va nol yig'indili o'yinlar haqida umumiy ma'lumotlarni bilib oling. Pozitsion o'yin, daraxt, axborot to'plami tushunchasi. Maksimin printsipi va muvozanat tamoyilini ko'rib chiqish. Pareto optimalligi. Pozitsion antagonistik bo'lmagan o'yin, uning xususiyatlari.

kurs ishi, 10/17/2014 qo'shilgan


O'yin nazariyasi - bu matematikaning bir tarmog'i bo'lib, uning predmeti ziddiyatli vaziyatlarda optimal qarorlar qabul qilish uchun matematik modellarni o'rganishdir. Iterativ Braun-Robinson usuli. Matritsali o'yinlarni yechish uchun monotonik iterativ algoritm.

dissertatsiya, 08/08/2007 qo'shilgan


To'lov matritsasini tuzish, o'yinning pastki va yuqori sof narxlarini, o'yinchilarning maksimal va minimaks strategiyalarini qidirish. To'lov matritsasini soddalashtirish. Chiziqli dasturlash muammosini qisqartirish va "Yechim izlash" qo'shimchasidan foydalangan holda matritsali o'yinni hal qilish.

test, 11/10/2014 qo'shilgan


O'yin nazariyasi - ziddiyatli vaziyatlarning matematik nazariyasi. Ikki kishilik nol yig‘indili o‘yinning matematik modelini ishlab chiqish, uni dastur kodlari ko‘rinishida amalga oshirish. Muammoni hal qilish usuli. Ma'lumotlarni kiritish va chiqarish. Dastur, foydalanuvchi qo'llanma.

kurs ishi, 17.08.2013 yil qo'shilgan


Simpleks usuli haqida asosiy ma'lumotlar, uning chiziqli dasturlashdagi o'rni va ahamiyatini baholash. Geometrik talqin va algebraik ma'no. Chiziqli funksiyaning maksimal va minimumini topish, maxsus holatlar. Masalani matritsali simpleks usuli yordamida yechish.

dissertatsiya, 06/01/2015 qo'shilgan


Kompyuter tizimlarining tuzilishi va ishlash jarayonlarini aks ettiruvchi matematik modellarini qurish texnikasi. O'rtacha muammoni hal qilish jarayonida fayllarga kirishlar soni. Fayllarni tashqi xotira disklariga joylashtirish imkoniyatini aniqlash.

laboratoriya ishi, 21/06/2013 qo'shilgan


Matematik modelni loyihalash. Tik-tak-toe o'yinining tavsifi. Boolean algebrasiga asoslangan mantiqiy o'yin modeli. Raqamli elektron qurilmalar va ularning matematik modelini ishlab chiqish. O'yin konsoli, o'yin boshqaruvchisi, o'yin maydoni chizig'i.

Moskva energetika instituti

(Texnik universitet)

Laboratoriya hisoboti

o'yin nazariyasida

"Matritsa shaklida berilgan juftlangan nol summali o'yin uchun optimal strategiyalarni topish dasturi"

Talabalar tomonidan to'ldirilgan

A5-01 guruhi

Ashrapov Daler

Ashrapova Olga

O'yin nazariyasining asosiy tushunchalari

O'yin nazariyasi hal qilish uchun mo'ljallangan ziddiyatli vaziyatlar , ya'ni. turli maqsadlarni ko'zlagan ikki yoki undan ortiq tomonlarning manfaatlari to'qnashadigan vaziyatlar.

Agar tomonlarning maqsadlari to'g'ridan-to'g'ri qarama-qarshi bo'lsa, ular haqida gapirishadi antagonistik to'qnashuv .

O'yin konfliktli vaziyatning soddalashtirilgan rasmiylashtirilgan modeli deb ataladi.

O'yinning boshidan oxirigacha bitta o'yin deyiladi partiya . O'yin natijasi to'lov (yoki yutuqlar ).

Partiya tarkibiga kiradi harakat qiladi , ya'ni. mumkin bo'lgan muqobillarning ma'lum bir to'plamidan o'yinchilarning tanlovi.

Harakatlar bo'lishi mumkin shaxsiy Va tasodifiy.Shaxsiy harakat , farqli o'laroq tasodifiy , o'yinchining qandaydir variantni ongli ravishda tanlashini o'z ichiga oladi.

Kamida bitta shaxsiy harakat mavjud bo'lgan o'yinlar deyiladi strategik .

Barcha harakatlar tasodifiy bo'lgan o'yinlar deyiladi qimor .

Shaxsiy harakatni amalga oshirishda ular ham bu haqda gapirishadi strategiyalar o'yinchi, ya'ni. o'yinchining tanlovini belgilaydigan qoida yoki qoidalar to'plami haqida. Shu bilan birga, strategiya keng qamrovli bo'lishi kerak, ya'ni. tanlov o'yin davomida har qanday mumkin bo'lgan vaziyat uchun aniqlanishi kerak.

O'yin nazariyasi muammosi- o'yinchilar uchun optimal strategiyalarni topish, ya'ni. ularni maksimal daromad yoki minimal yo'qotish bilan ta'minlaydigan strategiyalar.

O'yin nazariy modellarining tasnifi

O'yin n shaxslar odatda, qaerda, deb belgilanadi
- i-o'yinchining strategiyalari to'plami,
- o'yin uchun to'lov.

Ushbu belgiga muvofiq, o'yin nazariyasi modellarining quyidagi tasnifini taklif qilish mumkin:

Diskret (bir nechta strategiyalar diskret)

Final

Cheksiz

Uzluksiz (bir nechta strategiya davomiy)

Cheksiz

n shaxslar (
)

Koalitsiya (kooperativ)

Koalitsiyaga kirmaslik (kooperativ bo'lmagan)

2 kishi (juftlik)

Antagonistik (nol summali o'yinlar)

(tomonlarning manfaatlari qarama-qarshidir, ya'ni bir o'yinchining yo'qotilishi ikkinchisining foydasiga teng)

Antagonistik bo'lmagan

To'liq ma'lumot bilan (agar shaxsiy harakatni amalga oshirayotgan o'yinchi o'yinning butun fonini, ya'ni raqibning barcha harakatlarini bilsa)

To'liq bo'lmagan ma'lumotlar bilan

Nol miqdori bilan (umumiy to'lov nolga teng)

Nolga teng bo'lmagan summa

Bir harakat (lotereyalar)

Ko'p o'tish

Juftlangan nol yig‘indili o‘yinning matritsali tasviri

Ushbu qo'llanmada biz ko'rib chiqamiz Ikki kishilik antagonistik o'yinlar , matritsa shaklida berilgan. Bu shuni anglatadiki, biz birinchi o'yinchining ko'plab strategiyalarini bilamiz (o'yinchi A){ A i }, i = 1,…, m va ikkinchi o'yinchi uchun turli xil strategiyalar (o'yinchi B){ B j }, j = 1,..., n, va shuningdek, matritsa berilgan A = || a ij || birinchi o'yinchining yutuqlari. Biz antagonistik o'yin haqida gapirganimiz sababli, birinchi o'yinchining daromadi ikkinchi o'yinchining yo'qotishiga teng deb taxmin qilinadi. Biz matritsa elementi deb faraz qilamiz a ij- strategiyani tanlagan birinchi o'yinchining yutuqlari A i va ikkinchi o'yinchining unga strategiya bilan javobi B j. Biz bunday o'yinni belgilaymiz
, Qayerda m - o'yinchi strategiyalari soni A,n - o'yinchi strategiyalari soni IN. Umuman olganda, uni quyidagi jadval bilan ifodalash mumkin:

1-misol

Oddiy misol sifatida, o'yin ikkita harakatdan iborat bo'lgan o'yinni ko'rib chiqing.

1-harakat: O'yinchi A o'z tanlovi haqida raqibiga xabar bermasdan, raqamlardan birini (1 yoki 2) tanlaydi.

2-harakat: O'yinchi IN raqamlardan birini tanlaydi (3 yoki 4).

Pastki chiziq: O'yinchilarning tanlovi A Va IN katlang. Agar summa juft bo'lsa, unda IN o'yinchiga o'z qiymatini to'laydi A, agar g'alati bo'lsa - aksincha, A summani o'yinchiga to'laydi IN.

Ushbu o'yin shaklda taqdim etilishi mumkin
quyida bayon qilinganidek:

Bu o'yin antagonistik ekanligini ko'rish oson, bundan tashqari, bu to'liq bo'lmagan ma'lumotlarga ega o'yin, chunki o'yinchiga IN, shaxsiy harakat qilish, futbolchi qanday tanlov qilgani noma'lum A.

Yuqorida ta'kidlab o'tilganidek, o'yin nazariyasining vazifasi o'yinchilarning optimal strategiyalarini topishdir, ya'ni. ularni maksimal daromad yoki minimal yo'qotish bilan ta'minlaydigan strategiyalar. Bu jarayon deyiladi o'yin yechimi .

O'yinni matritsa shaklida hal qilishda siz o'yinning mavjudligini tekshirishingiz kerak egar nuqtasi . Buning uchun ikkita qiymat kiritiladi:

- o'yin narxining past bahosi va

- o'yin narxining yuqori bahosi.

Birinchi o'yinchi ikkinchi o'yinchining barcha mumkin bo'lgan javoblari orasidan maksimal g'alaba qozonadigan strategiyani tanlaydi, ikkinchi o'yinchi esa, aksincha, o'z yo'qotishlarini minimallashtiradigan strategiyani tanlaydi, ya'ni. birinchisida g'alaba qozonish mumkin.

Buni isbotlash mumkin α ≤ V ≤ β , Qayerda V–o'yin narxi , ya'ni birinchi o'yinchining ehtimoliy g'alabasi.

Agar munosabatlar saqlanib qolsa α = β = V, keyin shunday deyishadi o'yinning asosiy nuqtasi bor
, Va sof strategiyalarda hal qilish mumkin . Boshqacha qilib aytganda, bir nechta strategiyalar mavjud
, o'yinchiga berish AV.

2-misol

Keling, 1-misolda ko'rib chiqqan o'yinga qaytaylik va uni egar nuqtasi mavjudligini tekshiramiz.

Bu o'yin uchun
= -5,
= 4,
, shuning uchun uning egar nuqtasi yo'q.

Keling, bu o'yin to'liq bo'lmagan ma'lumotlarga ega o'yin ekanligiga yana bir bor e'tibor qaratamiz. Bu holatda futbolchiga faqat maslahat berishimiz mumkin A strategiyani tanlang , chunki bu holatda, u eng katta g'alabani qo'lga kiritishi mumkin, ammo o'yinchining tanloviga ko'ra IN strategiyalar .

3-misol

Keling, 1-misoldan o'yin qoidalariga ba'zi o'zgarishlar kiritaylik. Biz futbolchini taqdim etamiz IN o'yinchi tanlash ma'lumotlari A. Keyin bor IN ikkita qo'shimcha strategiya paydo bo'ladi:

- foydali strategiya A. Agar tanlov A - 1, Bu IN agar tanlasa 3 tani tanlaydi A - 2, Bu IN 4 tanlaydi;

- foyda keltirmaydigan strategiya A. Agar tanlov A - 1, Bu IN agar tanlasa 4 tani tanlaydi A - 2, Bu IN 3 ni tanlaydi.

Ushbu o'yin to'liq ma'lumotga ega.

Ushbu holatda
= -5,
= -5,
, shuning uchun o'yinda egar nuqtasi bor
. Ushbu egar nuqtasi ikki juft optimal strategiyaga mos keladi:
Va
. O'yin narxi V= -5. uchun bu aniq A bunday o'yin foydasiz.

2 va 3-misollar o'yin nazariyasida isbotlangan quyidagi teoremaning yaxshi tasviridir:

Teorema 1

To'liq ma'lumotga ega bo'lgan har bir juftlashgan antagonistik o'yinni sof strategiyalarda hal qilish mumkin.

Bu. 1-teoremada aytilishicha, to'liq ma'lumotga ega bo'lgan har qanday ikki o'yinchi o'yinida egar nuqtasi bor va bir juft sof strategiya mavjud.
, o'yinchiga berish A o'yin narxiga teng barqaror yutuqlar V.

Egar nuqtasi yo'q bo'lsa, deb atalmish aralash strategiyalar :, Qayerda p i Vaq j– strategiyalarni tanlash ehtimoli A i Va B j mos ravishda birinchi va ikkinchi o'yinchilar. Bu holda o'yinning yechimi aralash strategiyalar juftligidir
, o'yin narxining matematik kutishini maksimal darajada oshirish.

Quyidagi teorema 1-teoremani to'liq bo'lmagan ma'lumotga ega bo'lgan o'yin holatiga umumlashtiradi:

Teorema 2

Har qanday juftlashgan antagonistik o'yin kamida bitta optimal echimga ega, ya'ni umumiy holatda bir juft aralash strategiyalar.
, o'yinchiga berish A o'yin narxiga teng barqaror yutuqlar V, va α ≤ V ≤ β .

Maxsus holatda, egar nuqtasi bo'lgan o'yin uchun aralash strategiyalardagi yechim bitta element birga, qolganlari esa nolga teng bo'lgan vektor juftligiga o'xshaydi.

O'yin nazariyasida batafsil ishlab chiqilgan eng oddiy holat - bu cheklangan nol yig'indili juftlik o'yini (ikki kishi yoki ikkita koalitsiyaning antagonistik o'yini). Qarama-qarshi manfaatlarga ega ikki o'yinchi A va B ishtirok etadigan G o'yinini ko'rib chiqaylik: birining foydasi boshqasining yo'qotilishiga teng. A o'yinchisining to'lovi qarama-qarshi belgili B o'yinchisining to'loviga teng bo'lganligi sababli, bizni faqat a o'yinchining to'lovi qiziqtirishi mumkin. Tabiiyki, A maksimallashtirishni, B esa a minimallashtirishni xohlaydi.

Oddiylik uchun, keling, o'zimizni o'yinchilardan biri bilan (bu A bo'lsin) aqlan tanishtiramiz va uni "biz", B o'yinchini esa "raqib" deb ataymiz (albatta, bundan A uchun haqiqiy ustunlik yo'q). Keling, bizda mumkin bo'lgan strategiyalar va raqib - mumkin bo'lgan strategiyalar (bunday o'yin o'yin deb ataladi). Agar biz strategiyadan foydalansak va raqib strategiyadan foydalansa, yutuqimizni belgilaymiz

26.1-jadval

Faraz qilaylik, har bir juft strategiya uchun foyda (yoki o'rtacha daromad) bizga ma'lum. Keyin, printsipial jihatdan, o'yinchilarning strategiyalari va mos keladigan daromadlari ro'yxatini ko'rsatadigan to'rtburchaklar jadvalini (matritsani) qurish mumkin (26.1-jadvalga qarang).

Agar bunday jadval tuzilgan bo'lsa, unda ular G o'yini matritsa shakliga tushirilganligini aytishadi (o'yinni bunday shaklga keltirish allaqachon qiyin vazifa bo'lishi mumkin va ba'zida juda ko'p strategiyalar tufayli deyarli imkonsizdir. ). E'tibor bering, agar o'yin matritsa shakliga tushirilsa, u holda ko'p harakatli o'yin aslida bitta harakatli o'yinga qisqartiriladi - o'yinchi faqat bitta harakatni amalga oshirishi kerak: strategiyani tanlang. Biz o'yin matritsasini qisqacha belgilaymiz

Keling, G (4X5) o'yinining matritsa ko'rinishidagi misolini ko'rib chiqaylik. Bizning ixtiyorimizda to'rtta strategiya mavjud (tanlash uchun), dushmanning esa beshta strategiyasi bor. O'yin matritsasi 26.2-jadvalda keltirilgan

Keling, o'ylab ko'raylik, biz (A o'yinchisi) qanday strategiyadan foydalanishimiz kerak? Matritsa 26.2 da "10" vasvasasi bor; biz ushbu "tidbit" ni oladigan strategiyani tanlash vasvasasiga tushdik.

Ammo kuting: dushman ham ahmoq emas! Agar biz strategiyani tanlasak, u bizga g'azablanib, strategiyani tanlaydi va biz "1" achinarli foyda olamiz. Yo'q, siz strategiyani tanlay olmaysiz! Qanday bo'lish kerak? Shubhasiz, ehtiyotkorlik printsipiga asoslanib (va bu o'yin nazariyasining asosiy printsipi), biz minimal daromadimiz maksimal bo'lgan strategiyani tanlashimiz kerak.

26.2-jadval

Bu "mini-maks printsipi" deb ataladi: shunday harakat qilingki, raqibingizning siz uchun eng yomon xatti-harakatlarini hisobga olgan holda, siz maksimal g'alaba qozonasiz.

Keling, 26.2-jadvalni qayta yozamiz va o'ngdagi qo'shimcha ustunga har bir qatorga minimal yutuq qiymatini yozamiz (minimum qator); a satr uchun belgilaymiz (26.3-jadvalga qarang).

26.3-jadval

Barcha qiymatlardan (o'ng ustun) eng kattasi (3) ta'kidlangan. Strategiya unga mos keladi. Ushbu strategiyani tanlab, biz har qanday holatda ham (dushmanning har qanday xatti-harakati uchun) 3 dan kam bo'lmagan g'alaba qozonishimizga ishonch hosil qilishimiz mumkin. Bu qiymat bizning kafolatlangan g'alabamizdir; Ehtiyotkorlik bilan harakat qilsak, bundan kam ololmaymiz, balki ko'proq olamiz).

Ushbu yutuq o'yinning eng past narxi deb ataladi (yoki "maksimin" - minimal yutuqning maksimal qiymati). Biz uni a sifatida belgilaymiz. Bizning holatda

Endi dushmanning nuqtai nazarini va uning sababini olaylik. U qandaydir piyon emas, lekin u ham aqlli! Strategiyani tanlashda u kamroq berishni xohlaydi, lekin u bizning eng yomon xatti-harakatlarimizga ishonishi kerak. Agar u strategiya tanlasa, biz unga javob beramiz va u 10 beradi; agar u tanlasa, biz unga javob beramiz va u beradi va hokazo.26.3-jadvalga qo'shimcha pastki chiziq qo'shamiz va undagi ustunlarning maksimallarini yozamiz.Shubhasiz, ehtiyotkor raqib bu qiymat bo'lgan strategiyani tanlashi kerak. minimal (tegishli qiymat 5 26.3-jadvalda ta'kidlangan) . Bu qiymat P daromadning qiymati bo'lib, undan ko'proq oqilona raqib bizga bermaydi. Bu o'yinning yuqori narxi deb ataladi (yoki "mi-nimax" - maksimal yutuqning minimal qiymati). Bizning misolimizda va dushmanning strategiyasi bilan erishiladi

Shunday qilib, ehtiyotkorlik printsipiga asoslanib (qayta sug'urta qilish qoidasi "har doim eng yomoniga ishoning!"), biz A strategiyasini va dushman strategiyasini tanlashimiz kerak - Bunday strategiyalar "minimax" deb ataladi (minimax printsipidan kelib chiqqan holda). Bizning misolimizdagi ikkala tomon ham o'zlarining minimaks strategiyalariga sodiq qolar ekan, foyda bo'ladi

Endi bir zum tasavvur qilaylik, biz dushman strategiyaga amal qilayotganini bilib oldik. Keling, uni buning uchun jazolaymiz va strategiyani tanlaymiz, biz 5 ta olamiz va bu unchalik yomon emas. Ammo dushman ham muvaffaqiyatsiz emas; unga bizning strategiyamiz ekanligini bilsin , u ham tanlashga shoshiladi, yutuqimizni 2 ga kamaytiradi va hokazo (hamkorlar “strategiyalar bilan yugurishdi”). Qisqasi, bizning misolimizdagi minimaks strategiyalari boshqa tomonning xatti-harakatlari haqidagi ma'lumotlarga nisbatan beqaror; bu strategiyalar muvozanat xususiyatiga ega emas.

Har doim shundaymi? Yo'q har doim emas. 26.4-jadvalda keltirilgan matritsa bilan misolni ko'rib chiqing.

Ushbu misolda o'yinning past narxi yuqori narxga teng: . Bundan nima kelib chiqadi? A va B o'yinchilarining minimaks strategiyalari barqaror bo'ladi. Ikkala o'yinchi ham ularga amal qilgan ekan, to'lov 6 ga teng. Keling, agar (A) raqib (B) B strategiyasiga amal qilishini bilsak nima bo'lishini ko'rib chiqaylik?

26.4-jadval

Ammo mutlaqo hech narsa o'zgarmaydi, chunki strategiyadan har qanday og'ish bizning ahvolimizni yanada yomonlashtirishi mumkin. Xuddi shunday, raqib tomonidan olingan ma'lumotlar uni o'z strategiyasidan chetga chiqishga majburlamaydi.Bir juft strategiya muvozanatlilik xususiyatiga ega (muvozanatli strategiyalar juftligi) va ushbu juft strategiya yordamida erishilgan foyda (bizning holatimizda 6) "matritsaning egar nuqtasi" deb ataladi. Egar nuqtasi va muvozanatli juft strategiya mavjudligining belgisi o'yinning pastki va yuqori narxlarining tengligidir; umumiy qiymati o'yin narxi deb ataladi. Biz uni belgilaymiz

Ushbu daromadga erishiladigan strategiyalar (bu holda) optimal sof strategiyalar deb ataladi va ularning umumiyligi o'yinning echimi deb ataladi. Bunday holda, ular o'yinning o'zi haqida sof strategiyalarda hal qilinishini aytishadi. Ikkala A va B partiyalariga ularning pozitsiyalari eng yaxshi bo'lgan optimal strategiyalari berilishi mumkin. Va agar A o'yinchisi 6 ta g'alaba qozonsa va B o'yinchisi yutqazsa, bu o'yin shartlari: A uchun foydali va B uchun zarar.

O'quvchida savol tug'ilishi mumkin: nima uchun optimal strategiyalar "sof" deb ataladi? Biroz oldinga qarab, biz bu savolga javob beramiz: "aralash" strategiyalar mavjud bo'lib, ular o'yinchi faqat bitta strategiyani emas, balki bir nechtasini tasodifiy kesishgan holda ishlatadi. Shunday qilib, agar biz sof strategiyalarga qo'shimcha ravishda aralash strategiyalarga ruxsat beradigan bo'lsak, har bir cheklangan o'yinda yechim bor - muvozanat nuqtasi. Ammo bu hali muhokama qilinishi kerak.

O'yinda egar nuqtasining mavjudligi qoida emas, aksincha, bu istisno. Aksariyat o'yinlarda egar nuqtasi yo'q. Biroq, har doim egar nuqtasi bo'lgan va shuning uchun sof strategiyalarda hal qilinadigan o'yin turi mavjud. Bular "to'liq ma'lumotga ega o'yinlar" deb ataladi. To'liq ma'lumotga ega bo'lgan o'yin - bu har bir o'yinchi, har bir shaxsiy harakati bilan, uning rivojlanishining butun fonini, ya'ni shaxsiy va tasodifiy barcha oldingi harakatlar natijalarini biladigan o'yin. To'liq ma'lumotga ega o'yinlarga misollar: shashka, shaxmat, tic-tac-toe va boshqalar.

O'yin nazariyasida to'liq ma'lumotga ega bo'lgan har bir o'yinning egar nuqtasi borligi isbotlangan va shuning uchun sof strategiyalarda hal qilinadi. To'liq ma'lumotga ega bo'lgan har bir o'yinda o'yin narxiga teng barqaror daromad keltiradigan bir juft optimal strategiya mavjud va. Agar bunday o'yin faqat shaxsiy harakatlardan iborat bo'lsa, unda har bir o'yinchi o'zining optimal strategiyasidan foydalanganda, u juda aniq tarzda - o'yin narxiga teng g'alaba bilan yakunlanishi kerak. Bu shuni anglatadiki, agar o'yinning echimi ma'lum bo'lsa, o'yinning o'zi o'z ma'nosini yo'qotadi!

To'liq ma'lumotga ega bo'lgan o'yinning oddiy misolini olaylik: ikkita o'yinchi navbatma-navbat nikellarni dumaloq stol ustiga qo'yadi, tanga markazining o'rnini tasodifiy tanlaydi (tangalarning o'zaro bir-biriga yopishishiga yo'l qo'yilmaydi). Oxirgi nikelni qo'ygan kishi g'alaba qozonadi (boshqalar uchun joy qolmaganida). Bu o'yinning natijasi, mohiyatan, oldindan belgilab qo'yilganligini ko'rish oson. Tangani birinchi bo'lib joylashtirgan o'yinchi g'alaba qozonishini ta'minlaydigan ma'lum bir strategiya mavjud.

Ya'ni, u birinchi navbatda stolning o'rtasiga nikel qo'yishi kerak, so'ngra har bir raqibning harakatiga nosimmetrik harakat bilan javob berishi kerak. Shubhasiz, dushman o'zini qanday tutmasin, mag'lubiyatdan qochib qutula olmaydi. Vaziyat shaxmat va umuman to'liq ma'lumotga ega o'yinlar bilan bir xil: matritsa shaklida yozilgan ularning har qandayida egar nuqtasi bor, bu yechim sof strategiyalarda ekanligini anglatadi va shuning uchun bu yechim faqat ma'noga ega. topilmaydi. Aytaylik, shaxmat o‘yini yo har doim oq g‘alaba bilan tugaydi, yoki har doim qora tanlilar g‘alabasi bilan yoki durang bilan tugaydi, lekin biz aniq nima ekanligini hali bilmaymiz (shaxmat ixlosmandlari uchun baxtga). Yana qo'shamiz: biz yaqin kelajakda bilishimiz dargumon, chunki strategiyalar soni shunchalik kattaki, o'yinni matritsa shakliga keltirish va unda egar nuqtasini topish juda qiyin (agar imkonsiz bo'lsa).

Endi o'zimizdan so'raymiz, agar o'yinda egar nuqtasi bo'lmasa, nima qilish kerak: Xo'sh, agar har bir o'yinchi bitta sof strategiyani tanlashga majbur bo'lsa, unda hech narsa qilish kerak emas: biz minimax printsipiga amal qilishimiz kerak. Agar siz o'z strategiyalaringizni "aralashtirsangiz", ularni tasodifiy ba'zi ehtimolliklar bilan almashtira olsangiz, bu boshqa masala. Aralash strategiyalardan foydalanish shu tarzda o'ylangan: o'yin ko'p marta takrorlanadi; o'yinning har bir o'yinidan oldin, o'yinchiga shaxsiy navbat berilganda, u o'z tanlovini tasodifga "ishonib beradi", "qur'a tashlaydi" va paydo bo'lgan strategiyani oladi (biz oldingi bobdan lotni qanday tashkil qilishni allaqachon bilamiz. ).

O'yin nazariyasidagi aralash strategiyalar o'zgaruvchan, moslashuvchan taktikalar modeli bo'lib, o'yinchilarning hech biri ma'lum bir o'yinda raqib o'zini qanday tutishini bilmasa. Ushbu taktika (odatda hech qanday matematik asossiz) ko'pincha karta o'yinlarida qo'llaniladi. Ayni paytda shuni ta'kidlaymizki, o'z xatti-harakatingizni dushmandan yashirishning eng yaxshi usuli - unga tasodifiy belgi berish va shuning uchun nima qilishingizni oldindan bilmaslikdir.

Keling, aralash strategiyalar haqida gapiraylik. Biz mos ravishda A va B o'yinchilarining aralash strategiyalarini belgilaymiz, bu erda (jami bittadan iborat) - A o'yinchisining strategiyalardan foydalanish ehtimoli - B o'yinchisining strategiyalardan foydalanish ehtimoli

Maxsus holatda bittadan tashqari barcha ehtimollar nolga teng bo'lsa va bu bittaga teng bo'lsa, aralash strategiya sofga aylanadi.

O'yin nazariyasining asosiy teoremasi mavjud: har qanday cheklangan ikki kishilik nol yig'indili o'yin kamida bitta yechimga ega - odatda aralashgan optimal strategiyalar juftligi va mos keladigan narx.

O'yinning yechimini tashkil etuvchi optimal strategiyalar juftligi quyidagi xususiyatga ega: agar o'yinchilardan biri o'zining optimal strategiyasiga rioya qilsa, ikkinchisi unikidan chetga chiqishi foydali bo'lmaydi. Ushbu juftlik strategiyasi o'yinda ma'lum bir muvozanat pozitsiyasini hosil qiladi: bir o'yinchi daromadni maksimalga, ikkinchisi - minimalga aylantirmoqchi, har biri o'z yo'nalishi bo'yicha tortadi va ikkalasining ham oqilona harakati bilan muvozanat va barqaror daromad keltiradi. v o'rnatildi. Agar u holda o'yin biz uchun foydali bo'lsa, agar - dushman uchun; o'yin "adolatli" bo'lganda, ikkala ishtirokchi uchun ham bir xil foydali.

Keling, egar nuqtasi bo'lmagan o'yin misolini ko'rib chiqamiz va uning yechimini (isbotsiz) keltiramiz. O'yin quyidagicha: ikkita o'yinchi A va B bir vaqtning o'zida va hech qanday so'z aytmasdan bir, ikki yoki uchta barmoqni ko'rsatadi. Barmoqlarning umumiy soni yutuqni aniqlaydi: agar u juft bo'lsa, A yutadi va B dan shu raqamga teng miqdorni oladi; agar u g'alati bo'lsa, unda, aksincha, A B ga bu raqamga teng miqdorda to'laydi. Futbolchilar nima qilishlari kerak?

Keling, o'yin matritsasini yarataylik. Bitta o'yinda har bir o'yinchi uchta strategiyaga ega: bitta, ikki yoki uchta barmoqni ko'rsatish. 3x3 matritsa 26.5-jadvalda keltirilgan; qo'shimcha o'ng ustun qatorning minimalini, qo'shimcha pastki qator esa ustun maksimalini ko'rsatadi.

O'yinning past narxi strategiyaga mos keladi. Bu shuni anglatadiki, oqilona va ehtiyotkor xatti-harakatlar bilan biz 3 dan ortiq yo'qotmasligimizga kafolat beramiz. Kichik tasalli, lekin baribir ba'zi hujayralarda topilgan, aytaylik, 5 g'alabadan yaxshiroq. matritsadan. Bu biz uchun yomon, o'yinchi L... Ammo keling, o'zimizni taskinlaylik: dushmanning ahvoli bundan ham battarroq ko'rinadi: o'yinning narxi pastroq. oqilona xulq u bizga kamida 4 beradi.