Ойын теориясының элементтері

Әрбір ойыншыға төлем матрицасының барлық элементтері белгілі деп  есептелінеді. A_ij  элементі ойын қорытындысын анықтайды, дәлірек айтқанда  A ойыншының ұтысын, егер A  және B  ойыншылары сәйкес A_i(i=1,m) және В_j(j=1,n) стратегиясын таңдайтын болса. Ойыншылардың ұтыстарының қосындысы нӛлге тең

болатындықтан, B ойыншының  төлем матрицасы A ойыншының тӛлем матрицасын (-1)-ге көбейткенге тең. Сондықтан A  ойыншының төлем матрицасын зерттеу жеткілікті. Бұл матрицаның оң элементтері A  ойыншының ұтысын және B ойыншының ұтылысын, ал теріс элементтері A  ойыншының ұтылысын  және B ойыншының ұтысын көрсетеді. Екі жақтың біржүрісті ойыны былай жүргізіледі. A ойыншы төлем  матрицасының i -  жолын таңдайды (A_i  таза стратегиясы), ал B ойыншы матрицаның j  - бағанын (B_j  таза стратегиясы) таңдайды. Таңдалған жол мен бағанның  қиылысындағы элементі A ойыншының ұтысын көрсетеді. B ойыншының ұтысы(-a_ij) -ге тең. Бұл ойында A ойыншысы өз ұтысын максималдайтын жолды таңдайды, ал B  ойыншысы өз ұтылысын минималдайтын бағананы таңдайды. Қосындысы нөл болатын екі жақтың ойынының мысалы ретінде шартты әскери «полковник Блотто ойыны» атты ойынды қарастырайық. Екі армия екі халық тұратын пункт үшін соғыс жүргізуде. Полковник Блоттоның армиясы (A ойыннан) төрт жасақтан, ал қарсыластар армиясы (A ойыншы)  -  үшеуден тұрады. Ойын ережесін келтірейік. Қай жақтың  армиясы кез-келген пунктке қарсыласынан артық жасақ жіберсе сол пунктті алады және қарсыласын жойып, пунктті алғаны үшін бір ұпай, қарсыласын жойғаны үшін бір ұпай алады. Егер әр пунктте қарсыластардың күштері тең болса, онда ұпай алмайды. Жалпы ұтыс екі пункттегі ұтыстардың қосындысы бойынша анықталады. Қарсыластар қарсы жақтың әрекетін білмей-ақ, өз күштерін дұрыс таратып, максималды ұпай жинау керек. Ойыншылар ең көп ұтысқа ұмтылғандықтан барлық жасақтарын қолданады. Полковник Блоттоның бес стратегиясы бар: (4,0);(0,4);)(3,1);(1,3);(2,2) ,  ал  қарсыласының төрт стратегиясы (3,0);(0,3);(2,1);(1,2) бар. Әрбір стратегиядағы бірінші сан бірінші пунктке жіберілген жасақтар санын, ал екіншісі  – екінші пунктке жіберілген жасақтар санын көрсетеді.  1 кестеде төлем матрицасын құрамыз.

 

1 кесте

В А	0,3	3,0	2,1	1,2
4,0	4	0	2	1
0,4	0	4	1	2
1,3	1	-1	3	0
3,1	-1	1	0	3
2,2	-2	-2	2	2

 

Төлем матрицасындағы бір  элементтің  есептелуін көрсетейік, мысалы  а₅₁=-2 (A және B ойыншылары  A₅ және B₁ өздерінің таза стратегиясын қолданады).  A ойыншысы бірінші пункте (екі) екінші B ойыншысынан (үш) кем жасақ жібереді. Ойын ережесі бойынша  A  ойыншысы екі жасағынан және бірінші пункттен айрылады және оларға сәйкес 2 және 1 ұпайға ұтылады.  A ойыншысы бірінші пунктте - 3 ұпайға ұтылады. Екінші пунктте A ойыншысы екі жасағын жібереді, ал B  жібермейді. Сондықтан A  бір ұпайға ұтады. Қорытындысында A ойыншысы 2 ұпайға ұтылады, ал B ойыншысы 2 ұпай ұтады. Ойынның шешуі. Ойын теориясының есебі ойынның шешуін табу, яғни әрбір

ойыншы үшін оның оптималды  стратегиясы мен ойын бағасын  табу.  Оптималды стратегия дегеніміз ойын бірнеше рет қайталанғанда қарсыласынан тәуелсіз, берілген ойыншы максималды орташа ұтыспен қамтамасыз ету. Ойынның бағасы дегеніміз ойыншылардың оптималды стратегиясына сәйкес ұтысы (ұтылысы). Стратегияны таңдағанда әртүрлі принциптерге сүйенуге болады. Ойын теориясын өзінен кем көрмесе, онда ойыншылардың тәртібін ең жақсы деп есептеуге болады. Осыған сәйкес ең тамаша стратегия ретінле қарсыласының әректінен тәуелсіз, ең жоғары ұтысты қаматмасыз ететін стратегияны алуға болады. Егер A  ойыншы  i  стратегиясын таңдап алса, онда оның ұтысы min а_ij →j , мұндағы минимум B  ойыншысының барлық стратегиясы бойынша (төлем матрицасының i нөмірлі жолы бойынша). A  ойыншысы өзінің әрбір стратегиясы бойынша кепілді ұтыстарды таңдағандықтан, өзінің барлық стратегиясының арасынан өзіне максималды кепілді ұтысты қамтамасыз ететін стратегияны таңдап алады:

V1=max min a_ij

Жолдардың минимумдарының  максималды мәніне сәйкес стратегия максимин стратегиясы  деп, ал V₁   шамасы  – ойынның төменгі бағасы немес максимин  деп аталады. B ойыншысы да өзінің барлық стратегиясының  ішінен өзіне  кепілді  минималды ұтысты қамтамасыз ететін стратегияны таңдайды:

V1= min max a_ij

Бағаналардың максимумдарының  мәніне сәйкес минималды стратегия, минимакс стратегиясы деп, ал V₂  шамасы  –  ойынның жоғарғы бағасы немесе минимакс деп аталады. Егер A ойыншысы максимин стратегиясын ұстаса, онда оның ұтысы максимин мәнінен кем болмайды, яғни a_ij ≥ max min a_ij. Егер B ойыншысы минимакс стратегиясын ұстаса, онда оның ұтылысы минимакс мәнінен артық болмайды, яғни a_ij ≥ min max a_ij. Жалпы жағдайда ойынның тӛменгі және жоғарғы бағасының ара қатынасы теңсіздікпен көрсетіледі:

V_1≤ V₂    V₁₌ V₂

болатын ойындар да кездеседі.A және B ойыншыларының бұл мәндерге сәйкес стратегиясы оптималды деп, ал бұл стратегияға сәйкес төлем матрицасының элементі шешу нүктесі деп аталады. Төлем матрицасының шешуші нүктесіне сәйкес элемент ойын бағасы деп есептеледі. Оны v деп белгілейік. Сонда, егер шешущі нүктесі болатын болса v=v₁₌v₂. Егер V>0 болса, А ойыншысы ұтады. Ал, V=0 болса, онда екі ойыншыға бірдей, тең деп аталады.Мынадай мысал келтірейік. Екі ойыншының әрқайсысында тӛрт стратегиядан бар және бір-бірінің қандай стратегияны қолданылатынын білмейді. Мәліметтер 2 кестеде берілген. 

 

 

 

2 кесте

В           А	В1	В2	В3	В4	Maxij
А1	6	4	3	4	3
А2	12	7	10	9	7
А3	6	6	4	9	4
А4	12	3	12	7	3
maxij	12	7	12	9	7               7

 

Бірінші төлем матрицасының әрбір жолы бойынша минимумдарын (min a_ij), соңғы бағанаға, ал бағана бойынша максимумдарын (max a_ij) кестенің соңғы жолына жазамыз. Ары қарай ойынның тӛменгі және жоғарғы бағасы табылып соңғы жол мен соңғы бағананың  қиылысқан жеріне жазылады. Берілген мысалда V₁=V₂=7. Төлем матрицасының шешуші нүктесі бар, ойыншылар үшін оптималды таза стратегиялар А₂ және В₂ болып табылады. Ойын бағасы V=7. Бұл дегеніміз, егер А ойыншысы өзінің А₂ оптималды стратегиясын ұстаса, 7-ден кем ұтпайды, бірақ егер В ойыншысы В₂  стратегиясынан ауытқыса онда ол кӛп ұтуы да мүмкін. Осы сияқты В ойыншысы да өзінің оптималды В₂ стратегиясын ұстаса, онда 7 артық ұтылмайды, бірақ, егер А, А₁, А₂, А₃ стратегияларының бірін таңдаса, онда ол 7-ден кем ұтылуы мүмкүн.

Шешуші нүктесі бар  ойындар таза стратегиямен шешіледі және шешілу процесі күрделі емес. Ал кейбір төлем матрицасында шешуші нүкте біреуден артық болуы да мүмкін. Егер төлем матрицасының шешуші нүктесі болмаса, онда ол аралас стратегиямен шешіледі. 

 

Шешуші нүктесі  жоқ ойындарды шешу

          Жалпы шешуші нүктесі бар ойындар аз кездеседі. Көп ойындардың шешуі нүктесі болмайды.  Полковник Блоттоның ойыны  да осы ойындарға жатады. Толық информациялы ойындардың әруақытта шешуші нүктесі болатындығы дәлелденген.  Егер ойынның шешуші нүктесі болмаса, онда А ойыншы өзінің максимин стратегисын қолданып отырып V₁-ден кем ұтпайды, ал В ойыншысы V₂ –тық ұтылмайды. Мұндай ойындардың кезкелген партиясында таза стратегияны қолданып ойыншылардың ұтысын арттыру немесе ұтылысын кеміту мүмкіндік бермейді. Ал ол мүмкін болуы үшін таза стратегияны жиілігін өзгертіп, кездейсоқ ауыстырып бірнеше рет қайталау керек. Мұндай стратегиялар аралас деп аталады. Олардың элементтері таза стратегиялар.  Біржүрісті ойынның бір партиясында ойыншы бір ғана таза стратегияны қолданады. А және В ойыншыларының аралас стратегиясын S_A=(p_1, p_2…p_i…p_m) және S_B=(q_1, q_2…q_j…p_n) деп белгілейік. Мұндағы p_i А ойыншының таза стратегиясын қолдану ықтималдығы (жиілік), ал q_j В ойыншының стратегиясын қолдану (жиілігі) ықтималдығы.

А және В ойыншыларының  аралас  стратегияларының нөлден өзге Ықтималдықтары p_i және q_j   бар стратегиялары белсенді деп аталады.  Ойын теориясының  негізгі теоремасы  (минимакс туралы теорема). Кез-келген қосындысы нӛл болатын екі жақтың аяқталған ойынының кем дегенде бір шешімі болады, яғни жалпы жағдайда бағасы  болатын аралас жұп оптималды стратегиясы болады. Шешуші нүктесі болмайтын ойындардың шешімі әртүрлі әдістермен алынады. Ондай ойындардың кейбірінің шешімі сызықтық программалау есептеріне келтіріледі.Реті (mxn) болатын шешуші нүктесі жоқ төлем матрицасы берілсін. Ойында сызықтық программалау есептеріне келтіру үшін, артық стратегияларынан құтылып, оңайлату керек. 1 кестесіндегі ойыннның оңайлату процесін қарастырайық.

 

1 кесте

Вj Аi	В1	В2	В3	В4
А1	2	4	8	6
А2	1	4	6	4
А3	2	4	8	6
А4	8	6	2	1

 

Бірінші А ойыншысыың стратегиясын қарайық. Матрицаны талдау А₁ стратегиясы А₃ стратегиясын қайталағанын кқріп тұр. Сондықтан біреуін А₃(А₁) шығаруға болады. А₁ жолындағы барлық ұтыс А₂ жолындағылардан тең немесе үлкен, сондықтан А₁ қарағанда А₂ стратегиясы пайдасыз. Оны алып тастауға болады. Қысқартулардан кейінгі ойын түрі 2 кестеде көрсетілген. 2 кестесі бойынша В ойыншының стратегияларын таңдаймыз. В_j бағанасындағы ұтылыстар В₄ үлкен, яғни ол B үшін тиімісіз.

        Сондықтан В₃ алып тастап, 3 кестеде берілген ойынды аламыз. (4x4) тӛлем матрицасы қысқартулар  көмегімен (2x3) ретті матрицаға айналады.

Вj Ai	B1	B2	B4
A1	2	4	6
A2	8	6	1

2 кесте               3 кесте

Вj Ai	B1	B2	B3	B4
A1	2	4	8	6
A4	8	6	2	1

 

Ойынды сызықтық программалау есебіне келтіруді сипаттайық. Төлем матрицасының барлық a_ij элементтері оң болсын. Ол үшін матрицаның барлық мүшесіне үлкен оң M санын қосу керек. Одан ойынның бағасы V(M)-ге артады, ал есептің шешімі . Егер a_ij оң болса, онда ойынның бағасы V>0. Ойынның шешімін, яғни екі оптималды аралас стратегияны

 =(p_1, p_2…p_i…p_m) және =(q_1, q_2…q_j…p_n)

әрбір ойыншы үшін мүмкін болатын максималды орташа ұтысты (минималды  орташа ұтылыс) табу керек. Бірінші  табайық. А ойыншысы В ойыншысының стратегиясы қандай болған күнде де ӛзінің оптиальды стратегиясын қолдана отырып V кем ұтыс алмайды. Яғни, оны былай аламыз: 

а₁₁p₁₊a₂₁p_2+…a_m1p_{m  ≥ V}

а₁₂p₁₊a₂₂p_2+…a_m2p_{m  ≥ V}

_{… …  … …   …  …     …}

а_1np₁₊a_2np_2+…a_mnp_{m  ≥ V}

 

Теңсіздіктің екі жағын V оң санына бөлеміз.

 

                                 а_{11 +} a_{21 +…+} a_{m1 ≥1}

а_{12 +} a_{22 +…+} a_{m2 ≥1}

_{… … … …   …  …     …}

а_{1n +} a_{2n +…+} a_{mn ≥1}

Төмендегідей белгілеулер енгіземіз:

x₁= _, x₂= _,…,x_i= _,…,x_m=

Бұл жүйе мына түрге енеді:

а₁₁x₁₊a₂₁x_2+…a_m1x_{m  ≥ 1}

а₁₂x₁₊a₂₂x_2+…a_m2x_{m  ≥ 1}

_{… …  … …   …  …     …}

 а_1nx₁₊a_2nx_2+…a_mnx_{m  ≥ 1}

x_i ≥ 0 (i=1,m)

x_i (i=1,m) және p₁+p₂+…p_m=1 болғандықтан айнымалылар x_1, x_{2, … ,} x_m  мына шартты қанағаттандырады: