8-ma’ruza. Fon Neymanning minimaks haqidagi teoremasi. 2x2, 2xn, mx2 o’lchovli o’yinlar Reja

8-ma’ruza. Fon Neymanning minimaks haqidagi teoremasi. 2x2, 2xn, mx2 o’lchovli o’yinlar


Reja:

1. 
   Aralash strategiyalar. Asosiy teorema.
   
2. 
   Optimal aralash strategiyalarning xossalari.
   
3. 
   2x2 - o’yinni yechish.
   

Tayanch so’z va iboralar: matrisaviy o’yin, aralash strategiyalar, sof strategiyalar, optimal aralash strategiyalar, to’lovlar matrisasi, muvozanat vaziyat, o’yinning quyi va yuqori bahosi, egar nuqta, o’yinchining yutug’i.


1. Aralash strategiyalar. Asosiy teorema

Faraz qilaylik, - o’lchamli matrisaviy o’yin berilgan, uning to’lovlar matrisasi

bo’lib, o’yinda egar nuqta (muvozanat vaziyati) mavjud bo’lmasin, ya’ni o’yinning quyi bahosi va yuqori bahosi uchun munosabat bajarilsin. Bu holda minimaks va maksimin strategiyalar optimal bo’la olmaydilar.
Quyidagi misolda ko’rsatamizki, muvozanat vaziyatiga ega bo’lmagan o’yinda minimaks yoki maksimin strategiyalardan foydalanish ma’qul emas.
To’lovlar matrisasi

bo’lsin. Bu matrisa uchun , ( ), ya’ni muvozanat vaziyati mavjud emas. Birinchi o’yinchining maksimin strategiyasi , ikkinchi o’yinchining minimaks strategiyasi esa . Agar ikkinchi o’yinchi strategiyadan foydalansa va birinchi o’yinchi strategiyani tanlasa, u 3ga teng yutuq oladi, bu esa maksimindan 2 birlik kattadir. Ammo, agar ikkinchi o’yinchiga birinchi o’yinchining strategiya tanlashi ma’lum bo’lib qolsa, u o’zining strategiyasini ga o’zgartiradi va unda birinchi o’yinchi faqat nolga teng yutuqqa, ya’ni maksimin holidan 1 birlik kam yutuqqa ega bo’ladi, xolos. Xuddi shunday mulohazalarni ikkinchi o’yinchi uchun ham yuritish mumkin.
Endi, muvozangat holati mavjud bo’lmagan holda o’yinchilar qanday harakat qilishlari kerak degan savol paydo bo’ladi.
Bunday savolga o’yinchilarning o’z strategiyalarini tasoddifiy tanlashi orqali javob berish mumkin. Chunki, birinchidan tasodifiy tanlash strategiyaning maxfiyligini ta’minlasa, ikkinchidan oqilona qurilgan tasodifiy tanlash mexanizmidan foydalanish strategiyaning optimalligini ta’minlaydi.
Ta’rif. matrisa satrlari nomerlarining to’plamda ehtimolli taqsimotiga I o’yinchining aralash strategiyasi deyiladi. Xuddi shuningdek, matrisa ustunlari nomerlarining to’plamdagi ehtimolli taqsimotiga II o’yinchining aralash strategiyasi deyiladi.
Shunday qilib, I o’yinchining aralash strategiyasi
,
vektordan iborat. II o’yinchining aralash strategiyasi esa
,
vektordan iborat bo’ladi. Bunda va larni o’yinchilar va aralash strategiyalardan foydalangandagi va sof strategiyalarning tanlanish ehtimollari deb tushunish mumkin.
va bilan mos ravishda I va II o’yinchilarning aralash strategiyalar to’plamini belgilaymiz. va to’plamlar chegaralangan va yopiq to’plamlardir.
aralash strategiyani qaraymiz, bu yerda . Bu strategiya matrisa -satrining, birga teng ehtimol bilan tanlanishini bildiradi. aralash strategiyaning tanlanishini I o’yinchining sof strategiyasini tanlash bilan tenglashtirish mumkin.
Xuddi shuningdek, , , , , aralash strategiyani II o’yinchining sof strategiyasi bilan tenglashtirish mumkin. Demak, aralash strategiyalar to’plamini sof strategiyalar to’plamining kengaytirilishi deb qarash mumkin.
va aralash strategiyalarning ixtiyoriy juftiga o’yindagi vaziyat deyiladi.
Endi o’yindagi vaziyatga mos keluvchi I o’yinchi yutug’ini
(1)
deb belgilaymiz. o’yinchilardan biri yoki sof strategiyani, ikkinchisi esa yoki aralash strategiyani qo’llaganda va yutuqlar quyidagi ko’rinishda bo’ladi:
, .
Shunday qilib, biz o’yindan o’yinga keldik, bu yerda – aralash strategiyalar to’plamlari, esa (1) ko’rinishdagi yutuqlar funksiyasidir. Hosil qilingan o’yinga o’yinning aralash kengaytirilishi deymiz.
Ta’rif. Agar (p^*,q^*) vaziyat uchun
(2)
munosabat barcha uchun bajarilsa, ga muvozanat vaziyati, ga esa o’yinning bahosi (qiymati) deyiladi.
o’yinda muvozanat vaziyatining mavjudligi matrisaviy o’yinlarning asosiy teoremasi deb ataluvchi quyidagi teoremada keltirilgan: