12.2 Матрицалық ойындар

ойыншының – стратегиясы бар, ойыншының – стратегиясы бар ақырлы ойынды қарастырайық. Мұндай ойын - ойын деп аталады. Жалпы жағдайда және сандары бір-бірінен тәуелсіз. Егер және ойыншылар тек қана жеке жүрістерін пайдаланса, онда және стратегияларын таңдау ойынның қорытындысын бірмәнді анықтайды, яғни ойыншының ұтысын және ойыншының ұтылысын сипаттайтын санды анықтайды. мәні оң да теріс те болуы мүмкін. болғанда ойыншы ұтады, ал ойыншы шамасына ұтылады және керісінше, болғанда ойыншы ұтады, ал ойыншы ұтылады. Бұл жағдайда көбінесе, ұтылыстың орнына ойыншының теріс ұтысы айтылады.

Егер ойында кездейсоқ жүрістер қарастырылса, онда және стратегиялардағы ұтыс кездейсоқ болып табылады. Бұл жағдайда күтілетін ұтыс бағасының орнына оның математикалық күтімі алынады.

Айталық, бізге ойынының барлық мәні белгілі болсын. Матрицаның жатық жолдарына ойыншының стратегияларын, тік жолдарына ойыншының стратегияларын сәйкес қоюға болады. Егер жатық жолмен тік жолдың қиылысуына ойыншының жағдайына сәйкес ұтыс функциясының мәнін қойсақ, онда ойыншының ұтыс матрицасы деп аталатын матрицасын аламыз:

. (10.1)

Осылайша, ойыншының ұтыс функциясының мәндерінен ойыншының ұтыс матрицасын аламыз.

(10.1) теңдіктен (яғни матрицасы матрицасына қарама-қарсы транспонирленген матрица) аламыз. Демек, матрицасы матрицасымен анықталады. Сондықтан, ақырлы антагонистикалық ойын тек қана бір ұтыс матрицасымен сипатталады, осыған байланысты матрицалық ойын деп аталады.

Ойын матрицасы және ойыншылардың және реттелген жиынынан маңызды түрде тәуелді. Жалпы, кез келген ақырлы антагонистикалық ойынды матрицалық ойын түрінде жазуға болады.

Ойынның матрицасы ұтыс функциясының мәндеріне тәуелді құрылады. Ол кестелік, аналитикалық (формула түрінде) немесе сөздік-сипаттау тәсілімен берілуі мүмкін.

Сонымен, матрицалық ойын толығымен ойыншының стратегиялар жиынынан, ойыншының стратегиялар жиынынан және ойыншының ұтыс матрицасынан тұратын жиынтығымен анықталады.

10.1-мысал.

«Теңгені ойлап табу» ойыны.

Бірінші ( ) ойыншы өзінің қалауы бойынша және екінші ( ) ойыншыға көрсетпей бағасы 50 немесе 100 теңгенің біреуін жұдырығына жасырады, ал екінші ойыншы қандай теңгенің жасырылғанын табуға тырысады. Егер тапса, жасырылған теңгені алады, кері жағдайда бірінші ойыншыға 75 теңге береді.

Ұтыс матрицасын жазу керек.

Шығарылуы. ойыншының екі стратегиясы бар: – 50 теңгені жасыру, – 100 теңгені жасыру; ойыншының да екі стратегиясы бар: – 50 теңге деп болжау, – 100 теңге деп болжау. Сонда осы ойынның ұтыс матрицасы мына түрде жазылады (жатық жолдар – ойыншының, тік жолдар – ойыншының стратегиялары):

.

Жауабы. .

12.3 Максимин принципі

Ойынның шешімін анықтаудың жалпы ережесін табу мақсатында ойынның таза стратегияда шешімі бар болатын (10.1) түріндегі ұтыс матрицасын қарастырайық.

Дау-жанжал жағдайын бірінші ойыншының тұрғысынан қарастырайық. Айталық, ойыншы өзінің ең жақсы стратегиясын таңдасын, яғни стратегияларының ішінен кез келген -ші стратегияға ойыншының ұтысы минималды болатындай ойыншы стратегиясымен жауап береді. Осы стратегиясын табу үшін ұтыс матрицасындағы стратегиясына сәйкес ( -ші нөмірлі жол) жолдағы сандарының ішіндегі ең кішісін табу керек. Оны арқылы белгілейміз, яғни

, (10.2)

мәні -ші стратегиясының тиімді көрсеткіші деп аталады.

ойыншының стратегиясы өзгерген кезде осы стратегияларға сәйкес әрбір саны да өзгеріп отырады. Әрине, ойыншыға максимал мәнді қабылдайтындай стратегиясына тоқтаған дұрыс. Егер ойыншы айтылғандарды ескеріп қауіп-қатерге тәуекел етпесе, келесі түрде әрекет ету керек: барлық жатық жолдардың ең кіші элементін таңдап, осы таңдалған элементтердің ең үлкенін таңдау керек, ал қауіп-қатерге тәуекел ету – тиімсіз ойнау болып табылады. Сол кезде ол өзінің ұтысына кепілдік береді, ұтыс – ең болмаса, барлық жолдардың ең кіші элементтерінің ішіндегі ең үлкеніне тең болады.

Бұл максимал мәнді арқылы белгілейік, яғни

(10.3)

немесе, үшін (10.2) өрнегін ескерсек,

, , . (10.3’)

шамасы ойынның төменгі құны (мәні) немесе максималды ұтысы (максимин) деп аталады. Бұл ойыншының кез келген стратегиясындағы ойыншының кепілденген ұтысы.

Максиминге сәйкес келетін стратегия, яғни санына сәйкес келетін матрицаның жатық жолы ойыншының максиминді стратегиясы деп аталады.

ойыншының (10.3) тиімді стратегиясын таңдау принципі максимин принципі деп аталады.

Осылайша, ойыншы үшін жүргізілген талдауды ойыншы үшін жүргізіп мына ұғымдарды аламыз:

, . (10.4)

мәні -ші стратегиясының тиімді емес көрсеткіші деп аталады.

ойыншы тек қана,

, (10.5)

немесе (10.3) формула бойынша

, , (10.5’)

өрнегімен анықталатын шамасынан кем емес ұтысқа жететініне сенімді бола алады.

– ойынның жоғарғы құны (мәні) немесе минималды ұтысы (минимакс) деп аталады. Бұл ойыншының кез келген стратегиясындағы ойыншының кепілденген ұтысы болады.

Минимакске сәйкес келетін стратегия, яғни санына сәйкес келетін матрицаның тік жолы ойыншының минимаксті стратегиясы деп аталады.

ойыншының тиімді стратегиясын таңдаудың (10.5) принципі минимакс принципі деп аталады.

Минимаксті немесе максиминді стратегиялар ойында бір немесе одан да көп болуы мүмкін.

Теорема 10.1 (максимин принципі). Кез келген матрицалық ойын үшін

.

Егер болса, яғни ойынның жоғарғы құны мен төменгі құны өзара беттессе, онда минимаксті және максиминді стратегиялар ойыншылардың тиімді стратегиялары деп, олардың жиынтығы тиімді шешім деп немесе ойынның шешімі деп аталады, шамасы ойынның мәні немесе таза құны деп аталады. Бұл жағдайда ойыншы барынша көп кепілденген ұтысын ( ойыншының жүрісінен тәуелсіз) алады, ал ойыншы барынша аз кепілденген ұтылысқа ( ойыншының жүрісінен тәуелсіз) жетеді. Егер ойыншылардың біріншісі өзінің стратегиясын ұстаған кезде, екінші ойыншы үшін өзінің тиімді стратегиясынан бас тарту қолайсыз болса, онда мұндай шешім орнықты болып табылады. Тиімді стратегиялар орнықтылық шартын қанағаттандыру керек.

Тиімді стратегияларды , арқылы белгілейік.

Егер

, (10.6)

теңсіздігі орындалса, онда және ойыншылар, сәйкес және , , стратегияларын таңдау нәтижесінде құрылған жағдайы ойыншы үшін қанағаттанарлық жағдайы деп аталады, және егер

, (10.7)

теңсіздігі орындалса онда жағдайы ойыншы үшін қанағаттанарлық деп аталады.

Теорема 10.2. Егер ойыншының ұтысы ойыншының стратегиясының тиімді емес көрсеткішімен бірдей болған кезде ғана

, (10.8)

яғни ойын матрицасының тік жолында ең көп болса, жағдайы ойыншы үшін қанағаттанарлық болып табылады.

Осындай критерий ойыншының қанағаттанарлық жағдайы үшін де орындалады.

Теорема 10.3. Егер ойыншының ұтылысы ойыншының стратегиясының тиімді көрсеткішімен бірдей болған кезде ғана

, (10.9)

яғни ойын матрицасының жатық жолында ең кіші болса, онда жағдайы ойыншы үшін қанағаттанарлық болып табылады.

ойыншы үшін қанағаттанарлық жағдайдың саны мәнінен кем емес және мәнінен артық емес.

Тепе-теңдік жағдай

Егер және ойыншыларының әрқайсысы үшін жағдайы қанағаттанарлық жағдай болса, яғни егер (10.6) және (10.7) теңсіздіктер орындалса:

, , , (10.10)

немесе (10.2 және 10.3-теоремалар негізінде) (10.8) және (10.9) теңдіктер орындалса

, (10.11)

онда жағдайы ойынның тепе-теңдік жағдайы, немесе орнықты, немесе ер нүктесі деп аталады.

Сонымен, (10.10) қос теңсіздік пен (10.11) қос теңдік пара-пар. жағдайына сәйкес келетін ұтысы ойын матрицасының ер нүктесі деп аталады.

Тиімді стратегиялар жұбының және ойын құнының жиынтығы ер нүктесі бар ойынның шешімі деп аталады.

және ойыншыларының сәйкес таза тиімді стратегиялар жиынын және арқылы белгілейік ( әрібі ағылшынның optimal – «тиімді» сөзінің бірінші әрібі).

және ойыншыларының таза тиімді стратегиялар жиыны мен ойынның құнынан тұратын жиынтығы таза стратегиядағы ойынның толық шешімі деп аталады. Ал қандай да бір және таза стратегиялар жұбы мен ойынның құнының жиынтығы таза стратегиядағы ойынның дербес шешімі деп аталады.

Теорема 10.4 (таза стратегиялардағы ойын құнының бар болу критерийі). Таза стратегиялардағы ойын құны бар болу үшін, яғни ойынның төменгі құны мен жоғарғы құны тең болу үшін осы ойынның ұтыс матрицасының ер нүктесінің бар болуы қажетті және жеткілікті.

Теорема 10.5. Келесі тұжырымдар ақиқат.

1. ойыншының әрбір тиімді стратегиясы оның максиминді стратегиясы болып табылады, ал ойыншының әрбір тиімді стратегиясы оның минимаксті стратегиясы болып табылады.

2. Ер нүктесі жоқ ойында жалпы тиімді стратегия болмайтындықтан бұл ойында бірде бір максиминді және минимаксті стратегиялар тиімді болмайды.

3. Ер нүктесі бар ойында және ойыншыларының сәйкес әрбір максиминді және минимаксті стратегиялары тиімді болып табылады.

Басқаша айтқанда, ер нүктесі бар ойында ойыншының тиімді стратегиялар жиыны оның максиминді стратегиялар жиынымен беттеседі: , ал ойыншының тиімді стратегиялар жиыны оның минимаксті стратегиялар жиынымен беттеседі: . Ер нүктесі жоқ ойында ойыншының максиминді стратегиясы Ø және ойыншының минимаксті стратегиясы Ø барлық уақытта бар болса да, бірде бір ойыншының тиімді стратегиясы жоқ: Ø.

10.2-мысал.

Төмендегі ұтыс матрицасымен берілген ойынның төменгі және жоғарғы құнын, ер нүктесін, тиімді стратегиясын анықтау керек.

.

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

Осындай мүмкіндіктерді көре отырып, бірінші ойыншы өзінің ең аз ұтысын максимизациялау мақсатында келесі стратегияны таңдайды:

.

Алынған мәні ойыншының кепілденген ұтысы (ойынның төменгі құны). ұтысын қамтитын стратегиясы – минимаксті стратегия. Бірінші ойыншы үшін қолайлы жағдайлар: , , .

Осылайша екінші ойыншының ең жақсы стратегиясын анықтаймыз. Екінші ойыншы стратегиясын таңдаса, ең кем дегенде ұтылысын, стратегиясын таңдаса ұтылысын, стратегиясын таңдаса ұтылысын алады. Ойыншы ұтылысы ең аз болатын стратегияны таңдайды:

мәні ойыншының кепілденген ұтылысы (ойынның жоғарғы құны). ұтылысын қамтитын және стратегиялары – максимнді стратегия. Екінші ойыншы үшін қолайлы жағдайлар: , , , , , , , .

Алынған мәндерді матрицаның төменгі жағына сәйкес әр бағанның астына жазамыз:

, , .

Бұл мысалда ойынның төменгі құны мен жоғарғы құны өзара тең: . Яғни ойынның таза стратегиялар жиынында шешімі бар, ол мәніне тең. Қарастырылып отырған мысалда екі тиімді стратегия (ер нүктені анықтайды) бар: , .

Жауабы. Ойынның төменгі құны , жоғарғы құны , . Ойынның құны – . Тиімді стратегиялар: , . Екі ер нүкте бар: .

Қарастырылып отырған ойында екі ер нүкте бар. Жалпы практикада бір ер нүкте болатын немесе екі, үш, төрт және одан да көп ер нүкте болатын есептер кездеседі.

13-лекция.Аралас стратегиялар

Таза стратегиялардың бірін кездейсоқ таңдаудан тұратын ойыншының стратегиясы аралас стратегия деп аталады. Сонымен, ойыншының аралас стратегиясы – нөмірлері оның таза стратегиясының мәні болатын дискреттік кездейсоқ шама болып табылады.

ойыншының аралас стратегиясын матрица түрінде жазуға болады:

немесе , .

Осылайша ойыншының аралас стратегиясы:

немесе , .

Таза стратегияларды аралас стратегиялардың дербес жағдайы деп қарастыруға болады. Себебі, ойыншының әрбір _{, таза стратегиясын}

түріндегі аралас стратегия ретінде қарастыруға болады. Бұл жерде таза стратегия ықтималдықпен, ал қалған таза стратегиялар нөлге тең ықтималдықтармен таңдалынады.

Минимакс принципінің негізінде ойынның тиімді шешімі анықталады: егер ойыншылардың біреуі өзінің тиімді стратегиясын ұстаса, онда екіншісіне өзінің стратегиясынан бас тарту тиімді болмайтындай , тиімді стратегиялар жұбы болады. Тиімді шешімге сәйкес ұтыс ойынның құны деп аталады. Ойынның құны

теңсіздігін қанағаттандырады, мұндағы және сәйкес ойынның төменгі және жоғарғы құндары.

Теорема 10.6 (ойындар теориясының негізгі теоремасы – Нейман теоремасы). Кез келген ақырлы ойынның кем дегенде бір тиімді шешімі бар болады және ол аралас стратегияларда болуы мүмкін.

және – тиімді стратегиялар жұбы болсын. Егер таза стратегия нөлдік ықтималдықтан өзге тиімді аралас стратегияға енетін болса, онда ол белсенді стратегия деп аталады.

Теорема 10.7 (белсенді стратегиялар туралы). Егер ойыншылардың біреуі өзінің тиімді стратегиясын ұстаса, онда екіншісі өзінің белсенді стратегияларынан тыс кетпесе, онда ұтыс өзгеріссіз қалады және ойынның құнына тең болады.

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