Mavzu: O’yinlar nazariyasi masalasini chiziqli programmalashtirish masalasiga keltirish

2 Matritsali o‘yinning yechimi
Yutuqlar matritsasi

ko‘rinishda bo‘lgan matritsali o‘yinni qaraylik. Agar A o‘ynovchi i-sof strategiyani tanlasa, u kamida

yutuqqa ega bo‘ladi va A o‘ynovchi o‘zining yutug‘ini maksimal qilishga harakat qiladi.Demak, u shunday i-sof strategiyani tanlashi kerakki, natijada uning yutug‘i maksimal bo‘lsin, yа’ni A o‘ynovchi

natijani beruvchi sof strategiyani tanlaydi. Ushbu kattaliknи 𝛼 bilan belgilaymiz:

Bu yerda, 𝛼 - A o‘ynovchining ishonchli yutug‘idan iborat bo‘lib u «o‘yinning quyi bahosi» deb ataladi: 𝛼 yutuqqa erishishga imkon beruvchi -sof strategiya «maksmin» deb ataladi. B o‘ynovchi o‘z navbatida, o‘zining eng katta mumkin bo‘lgan yutqazuvini minimallashtirishga harakat qiladi. Shuning uchun,

yutqazuvni beruvchi j-sof strategiyani tanlaydi. Bu yerda, 𝛽 - B o‘ynovchining ishonchli minimal yutqazuvidan iborat bo‘lib, u «o‘yinning yuqori bahosi» deb ataladi. 𝛽 yutqazuvga erishishga imkon beruvchi  yurish ( -sof strategiya) «minimaks» deb ataladi.
Teorema.Har qanday matritsali o‘yinda o‘yinning 𝛼 quyi bahosi uning 𝛽 yuqori bahosidan oshmaydi, yа’ni .
Isboti. Tа’rifga asosan,
,
Bu munosabatlarni birlashtirsak,

munosabatga ega bo‘lamiz. Bundan, tengsizlikni hosil qilamiz. Bu tenglik i va j indekslarning ixtiyoriy kombinatsiyalari uchun, shu jumladan,

shartlarni qanoatlantiruvchi i va j lar uchun ham o‘rinlidir. Demak, tengsizlikka ega bo‘lamiz. Teorema isbotlandi.
Agar matritsali o‘yinning quyi va yuqori baholari o‘zaro teng bo‘lsa, yа’ni shart bajarilsa, u holda ushbu o‘yin egar nuqtaga hamda quyidagi shartni qanoatlantiruvchi bahoga ega deyiladi.

Bu holda, A matritsaning shartni qanoatlantiruvchi ( juftlikka mos keluvchi elementi  egar nuqta deb ataladi. Bu element  ustunda maksimal bo‘ladi va  qatorda minimal bo‘ladi, yа’ni:

Agar B o‘ynovchi o‘zining minimaks strategiyasidan voz kechsa, uning yutqazuvi oshadi. Xuddi shuningdek, agar A o‘ynovchi o‘zining maksimin strategiyasidan voz kechsa, uning yutug‘i kamayadi. Demak, egar nuqtalarga o‘yinning  , optimal strategiyalari mos keladi, hamda to‘plam o‘yinning yechimi deyiladi.