Ўйинлар назарияси

O’yinlar nazariyasi
Reja:

1. 
   O’yinlar nazariyasi haqida tushunchalar
   
2. 
   Matritsali o‘yinning yechimi
   
3. 
   Matritsali uyin bilan chizikli programmalash masalasining ekvivalentligi
   

Tayanch so‘z va iboralar: o‘yin, partiya, strategiya, sof strategiya, aralash strategiya

1. 
   O‘yinlar nazariyasi haqida tushunchalar
   

O‘yinlar nazariyasini birinchi bo‘lib yaratgan olim Fon Neymandir. O‘yinlar nazariyasi Fon Neyman tomonidan qo‘yilgan quyidagi masalani yechish bilan shug‘ullanadi:

Agar ta o‘ynovchilar biror G o‘yinni o‘ynayotgan bo‘lsa, - o‘ynovchi bu o‘yinda yutib chiqishi uchun qanday strategiyani tanlashi kerak? Bu yerda biz «o‘yin» deyilganda ma’lum kelishib olingan shart va qoidalar to‘plamini, «partiya» deganda shu shart va qoidalarning amalga oshirilishini tushunamiz. Har bir partiyadan keyin o‘ynovchi o‘yinning yutug‘i deb atalmish - yutuqqa ega bo‘ladi (pul, ochko va hokazo).

Ba’zi o‘yinlarda yutqazilgan pullar yig‘indisi yutilgan pullar yig‘indisiga teng bo‘ladi. Masalan, o‘ynovchi so‘m yutqazsa o‘ynovchi so‘m yutishi mumkin. Bu holda o‘yindagi yutuqlar yig‘indisi 0 ga teng bo‘ladi:



Bu yerda biz har bir o‘ynovchi faqat yutadi deb faraz qilamiz, chunki biror o‘ynovchi so‘m yutqazsa uning yutug‘i so‘mga teng deb olinishi mumkin. O‘yinlar, shart va qoidalarga ko‘ra va o‘ynovchilar soniga qarab turlicha bo‘ladi. Bundan so‘ng biz ikki o‘ynovchining yutuqlar yig‘indisi 0 ga teng bo‘lgan o‘yini bilan, boshqacha aytganda, ikki o‘ynovchining 0 so‘mli o‘yini bilan tanishamiz.

Bunday o‘yinga misol sifatida quyidagi o‘yinni ko‘ramiz. Birinchi o‘ynovchi tanganing biror tomonini tanlaydi. Ikkinchi o‘ynovchi ham o‘ynovchi tanganing qanday tomonini tanlanganligini bilmagan holda tanganing biror tomonini tanlaydi. Agarda ikki o‘ynovchi tanganing bir xil tomonini tanlagan bo‘lsalar, o‘ynovchi 1 ochko yutadi, aks holda o‘ynovchi 1 ochko yutadi. Bu o‘yinni quyidagi jadval ko‘rinishida ifodalash mumkin:



Bu o‘yinda har vaqt yutadi deb fikr yuritiladi. Agar yutqazsa uning yutug‘i (-1) ga teng deb olinadi. Shunday qilib, berilgan o‘yinning shartlarini quyidagi



matritsa orqali ifodalash mumkin. Matritsaning qatori ning tanlash imkoniyatiga, ustuni ning tanlash imkoniyatiga mos keladi. Faraz qilaylik, tanganing «Gerb» yoki «Raqam» tomonini tasodifiy ravishda tanlagan bo‘lsin. Bu holda o‘ynovchininig «Gerb» ni tanlash ehtimoli ga teng bo‘ladi. Xuddi shuningdek, «Raqam» ni tanlash ehtimoli ham ga teng. Agar bu holda «Gerb» ni tanlasa, o‘ynovchi yutug‘ining matematik kutilishi



bo‘ladi. Agar «Raqam» ni tanlasa o‘ynovchi yutug‘ining matematik kutilishi



bo‘ladi. Shunday qilib o‘ynovchining o‘rtacha yutug‘i 0 ga teng bo‘ladi.

Endi faraz qilaylik, «Gerb» ni ehtimol bilan tanlasin. U holda «Raqam» ni ehtimol bilan tanlaydi, bu yerda Agar «Gerb» ni tanlasa o‘ynovchining o‘rtacha yutug‘ining matematik kutilishi:



Agar «Raqam» ni tanlasa, yutug‘ini matematik kutilishi



Shunday qilib, ning o‘rtacha yutug‘i 0 bo‘lishi uchun bo‘lishi kerak.

Endi o‘yinlar nazariyasiga oid ba’zi tushunchalar bilan tanishamiz.

1 – t a ’ r i f . Har qanday G o‘yin, o‘yin matritsasi deb ataluvchi



matritsa orqali aniqlanishi mumkin. Bu matritsa birinchi o‘ynovchi uchun yutuqlar matritsasi deb ataladi.

element - o‘ynovchi matritsaning - qatoriga mos keluvchi yurishini, o‘ynovchi - ustunga mos keluvchi yurishni tanlagandagi o‘ynovchining yutuq summasini bildiradi.

2 – ta’rif . Komponentlari va shartlarni qanoatlantiruvchi vektor qator o‘ynovchining aralash strategiyasi deyiladi.

Xuddi shuningdek, komponentlari va shartlarni qanoatlantiruvchi vektor ustun o‘ynovchining aralash strategiyasi deyiladi.

va lar mos ravishda ni o‘zining - yurishini (qatorini) va o‘zining - yurishini (ustunini) tanlash chastotalarini bildiradi.

Yuqorida ko‘rilgan misol uchun o‘ynovchining aralash strategiyasi lardan biri bo‘lishi mumkin.

3 – ta’rif. - komponentasi 1 ga teng bo‘lib, qolgan komponentlari 0 ga teng bo‘lgan aralash strategiyani o‘ynovchining - sof strategiyasi deb ataymiz.

Masalan, (1, 0, 0), (0, 1, 0), (0, 0, 1).

Xuddi shuningdek, - komponentasi 1 ga teng bo‘lib, qolgan komponentlari 0 ga teng bo‘lgan aralash strategiyani o‘ynovchining sof strategiyasi deb ataymiz.

Endi yutuq matritsasi

bo‘lgan matritsali o‘yinini ko‘raylik.

Agar o‘ynovchi - sof strategiyani tanlansa, u kamida yutuqqa ega bo‘ladi. o‘ynovchi o‘zining yutug‘ini maksimal qilishga harakat qiladi. Demak, u shunday - sof strategiyani tanlashi kerakki, uning yutug‘i bo‘lsin, ya’ni o‘ynovchi beruvchi sof strategiyani tanlaydi.

1 – misol.

o‘yin matritsasi berilgan bo‘lsa, o‘ynovchi 1-sof strategiyani tanlasa, u eng kamida 0 yutuqqa ega bo‘ladi;

2-sof strategiyada uning yutug‘i kamida 1 ga teng bo‘ladi; 3-sof strategiya esa kamida -1 yutuqqa ega bo‘ladi. demak, u 2-sof strategiyani tanlaydi va bu holda uning yutug‘i

bo‘ladi.

Agarda o‘ynovchi 1-sof strategiyani tanlasa, u eng ko‘pi 4 ochko yutqazadi, 2-sof strategiyada 5, 3-sof strategiyada 3 va 4-sof strategiyada 4 ochko yutqazadi. o‘ynovchi o‘zining yutqazishini minimal qilishga harakat qiladi. Demak, 3-sof strategiyani tanlaydi. uchun yutqazish summasi .

2 – m i s o l .

matritsali o‘yinda o‘ynovchi 1-sof strategiyani tanlasa, eng kamida 3 ochko yutadi, 2-sof strategiyada 1 ochko, 3-sof strategiyada esa 0 ochko yutadi.

o‘ynovchi o‘zining yutug‘ini maksimal qilishga harakat qiladi. Shuning uchun u sof 1-sof strategiyani tanlaydi. Bu holda uning yutug‘i

bo‘ladi.

Xuddi shuningdek, o‘ynovchi 1-sof strategiyani tanlasa, u eng ko‘pi bilan 3 ochko yutqazadi. 2-sof strategiyada 7, 3-sof strategiyada 6 ochko yutqazadi.

o‘ynovchi o‘zining yutug‘ini minimallashtirishga harakat qiladi. Shuning uchun u



shartni qanoatlantiruvchi 1-sof strategiya ni tanlaydi.

Shunday qilib, berilgan o‘yinda o‘ynovchining sof strategiyasi va o‘ynovchining sof strategisi uchun



shart o‘rinli bo‘lganligi sababli, ular optimal sof strategiya deyiladi. Bu misolda matritsaning elementi o‘z ustunida maksimal va qatorida minimal element bo‘layapti. Bunday nuqtani (elementni) egar nuqta deb ataymiz.

Agar va o‘ynovchilarning tanlagan sof strategiyalari uchun

(9.1.1)

shart o‘rinli bo‘lsa, bunday sof strategiyalar optimal sof strategiya va element egar nuqta bo‘ladi.

4 – t a ’ r i f . o‘ynovchining yutuqlar funksiyasi yoki boshqacha aytganda uning yutug‘ining matematik kutilishi

(9.1.2)

formula Bilan aniqlanadi, bu yerda o‘ynovchining va o‘ynovchining ixtiyoriy aralash strategiyalari.

M i s o l . o‘yin matritsasi uchun , mos ravishda va o‘ynovchilarning aralash strategiyalari.