антагонистична игра. Решаване на матрични антагонистични игри Принципи за решаване на матрични антагонистични игри
Теорията на игрите е теория на математическите модели за вземане на решения в условия на конфликт или несигурност. Предполага се, че действията на страните в играта се характеризират с определени стратегии - набори от правила за действие. Ако печалбата на едната страна неизбежно води до загуба на другата страна, тогава се говори за антагонистични игри. Ако наборът от стратегии е ограничен, тогава играта се нарича матрична игра и решението може да се получи много просто. Решенията, получени с помощта на теорията на игрите, са полезни при изготвяне на планове в случай на възможна опозиция от страна на конкуренти или несигурност във външната среда.
Ако биматричната игра е антагонистична, тогава матрицата на изплащане на играч 2 е напълно определена от матрицата на изплащане на играч 1 (съответстващите елементи на тези две матрици се различават само по знаци). Следователно биматричната антагонистична игра е напълно описана от една единствена матрица (матрицата на изплащане на играч 1) и съответно се нарича матрична игра.
Тази игра е антагонистична. В него j = x2 - O, P и R (O, O] = H (P, P) = -I и R (O, P) = R (P, O) = 1, или в матрична форма o p
Нека някой клас игри Г е "огледално затворен", т.е. заедно с всяка своя игра съдържа огледална изоморфна игра (тъй като всички игри, които са огледално изоморфни на дадена, са изоморфни една на друга, ние, в съответствие с току-що казаното, можем да говорим за една огледална изоморфна игра). Такъв клас е например класът на всички антагонистични игри или класът на всички матрични игри.
Припомняйки дефиницията на приемливи ситуации в антагонистичната игра, получаваме, че ситуацията (X, Y) в смесеното разширение на матричната игра е приемлива за играч 1, ако и само ако за всяко x G x неравенството
Процесът на превръщане на игри в симетрични се нарича симетризация. Тук описваме един метод на симетризация. Друга, фундаментално различна версия на симетризацията ще бъде дадена в раздел 26.7. И двата варианта на симетризация са действително приложими за произволни антагонистични игри, но ще бъдат формулирани и доказани само за матрични игри.
По този начин първоначалните термини и обозначения на теорията на общите антагонистични игри съвпадат със съответните термини и обозначения на теорията на матричните игри.
За крайни антагонистични (матрични) игри съществуването на тези екстремуми беше доказано от нас в глава 10. 1, а целта беше да се установи тяхното равенство или поне да се намерят начини за преодоляване на неравенството им.
Разглеждането на матричните игри вече показва, че има антагонистични игри без равновесни ситуации (и дори без е-равновесни ситуации за достатъчно малки e > 0) в първоначално зададените стратегии на играчите.
Но всяка ограничена (матрична) игра може да бъде разширена до безкрайна игра, например, като предостави на всеки играч произволен брой доминирани стратегии (вижте 22 гл. 1). Очевидно такова разширяване на набора от стратегии на играча всъщност няма да означава разширяване на неговите възможности и действителното му поведение в разширената игра не трябва да се различава от поведението му в оригиналната игра. Така веднага получихме достатъчен брой примери за безкрайни антагонистични игри, които нямат седлови точки. Има и такива примери.
По този начин, за да се приложи принципът на максимин в безкрайна антагонистична игра, е необходимо, както в случая на крайна (матрична) игра, известно разширяване на стратегическите възможности на играчите. За 96
Както в случая с матричните игри (виж гл. 1, 17), за общите антагонистични игри важна роля играе концепцията за смесен стратегически спектър, която тук обаче трябва да получи по-общо определение.
И накрая, имайте предвид, че множеството от всички смесени стратегии на играч 1 в произволна антагонистична игра е, както в матрицата
Дори разглеждането на антагонистични игри показва, че голям брой такива игри, включително крайни, матрични игри, имат равновесни ситуации не в оригиналните, чисти стратегии, а само в обобщени, смесени стратегии. Следователно за общите, неантагонистични, некооперативни игри е естествено да се търсят равновесни ситуации именно в смесените стратегии.
Така например (вижте фиг. 3.1), вече отбелязахме, че „Изпълнителят“ почти никога не трябва да се справя с поведенческа несигурност. Но ако вземем концептуалното ниво на типа "Администратор", тогава всичко е точно обратното. По правило основният вид несигурност, с която трябва да се сблъска такъв „наш човек, който взема решения“, е „Конфликт“. Сега можем да изясним, че това обикновено е нестрого съперничество. Малко по-рядко "Администраторът" взема решения в условия на "естествена несигурност", а още по-рядко се натъква на строг, антагонистичен конфликт. В допълнение, сблъсъкът на интереси при вземане на решения от „Администратора“ се случва, така да се каже, „веднъж“, т.е. според нашата класификация той често играе само една (понякога много малък брой) игри от играта. Скалите за оценка на последствията са по-често качествени, отколкото количествени. Стратегическата независимост на "Администратора" е доста ограничена. Като се има предвид гореизложеното, може да се твърди, че проблемни ситуации от такъв мащаб най-често трябва да се анализират с помощта на некооперативни неантагонистични двуматрични игри, освен това в чисти стратегии.
Принципи за решаване на матрични антагонистични игри
В резултат на това е разумно да се очаква, че в играта, описана по-горе, опонентите ще се придържат към избраните от тях стратегии. Матрична антагонистична игра, за която max min fiv = min max Aiy>
Въпреки това, не всички матрични антагонистични игри са съвсем определени и в общия случай
По този начин, в общия случай, за да се реши матрична антагонистична игра с измерение /uxl, е необходимо да се реши двойка проблеми с двойно линейно програмиране, което води до набор от оптимални стратегии, / и цената на играта v.
Как се дефинира матричната антагонистична игра на две лица?
Какви са методите за опростяване и решаване на матрични антагонистични игри
При игра на двама е естествено техните интереси да се разглеждат като директно противоположни – играта е антагонистична. Така печалбата на един играч е равна на загубата на другия (сборът от печалбите на двамата играчи е нула, откъдето идва и името, играта с нулева сума). Ще разгледаме игри, в които всеки играч има краен брой алтернативи. Функцията за печалба за такава игра с нулева сума за двама души може да бъде дадена в матрична форма (под формата на матрица за печалба).
Както вече беше отбелязано, последната антагонистична игра се нарича матрица.
МАТРИЧНИ ИГРИ - клас антагонистични игри, в които участват двама играчи, като всеки играч има краен брой стратегии. Ако един играч има m стратегии, а другият играч има n стратегии, тогава можем да конструираме игрова матрица с размерност txn. M.i. може да има или да няма седлова точка. В последния случай
Московски енергиен инженерен институт
(Технически университет)
Лабораторен доклад
в теорията на игрите
„Програма за търсене на оптимални стратегии за сдвоена антагонистична игра, дадена в матрична форма“
Попълнено от студенти
група А5-01
Ашрапов Далер
Ашрапова Олга
Основни понятия на теорията на игрите
Теория на игрите, предназначена да разрешава конфликтни ситуации , т.е. ситуации, в които се сблъскват интересите на две или повече страни, преследващи различни цели.
Ако целите на страните са директно противоположни, тогава те говорят за антагонистичен конфликт .
игра наречен опростен формализиран модел на конфликтна ситуация.
Играенето на игра веднъж от началото до края се нарича партия . Резултатът от партито е плащане (или печеля ).
Партията се състои от се движи , т.е. избор на играчи от набор от възможни алтернативи.
Движенията могат да бъдат личнии случаен.личен ход , За разлика от случаен , предполага съзнателен избор от играча на някаква опция.
Наричат се игри, в които има поне един личен ход стратегически .
Игрите, в които всички ходове са произволни, се наричат хазарт .
Когато правят личен ход, те също говорят за стратегии играч, т.е. за правилото или набор от правила, които определят избора на играча. В същото време стратегията трябва да бъде всеобхватна, т.е. изборът трябва да бъде определен за всяка възможна ситуация по време на играта.
Предизвикателство по теория на игрите– намиране на оптималните стратегии на играчите, т.е. стратегии, които им осигуряват максимална печалба или минимална загуба.
Класификация на моделите на теория на игрите
игра нлицата обикновено се наричат къде 
е набор от стратегии на i-тия играч, 
- плащане на играта.
В съответствие с това обозначение може да се предложи следната класификация на моделите на теория на игрите:
Дискретни (набори от стратегии 
отделен)
Финал
Безкраен
Непрекъснати (набори от стратегии 
непрекъснато)
Безкраен
нлица ( 
)
Коалиция (кооперация)
Несътрудничество (несътрудничество)
2 души (сдвоени)
Антагонистични (игри с нулева сума)
(интересите на страните са противоположни, т.е. загубата на един играч е равна на печалбата на другия)
Неантагонистичен
С пълна информация (ако играчът, който прави личен ход, знае цялата история на играта, т.е. всички ходове на противника)
С непълна информация
С нулева сума (общото плащане е нула)
С ненулева сума
Еднопосочно (лотарии)
многопосочен
Матрично представяне на антагонистична игра по двойки
В този урок ще разгледаме антагонистични игри на двама души
дадени в матрична форма. Това означава, че знаем набора от стратегии на първия играч (играч А){
А аз },
аз = 1,…,
ми набора от стратегии на втория играч (играч б){
б й },
й = 1,...,
н, и матрицата А
= ||
а ij ||
печалбите на първия играч. Тъй като говорим за антагонистична игра, се приема, че печалбата на първия играч е равна на загубата на втория. Считаме, че матричният елемент а ijе печалбата на първия играч, когато той избере стратегия А ази отговорът на втория играч със стратегията б й. Такава игра ще наричаме 
, където м
- брой стратегии на играча НО,н
- брой стратегии на играча AT.Най-общо може да се представи със следната таблица:
|
б 1 |
|
б й |
|
б н |
|
|
А 1 |
|
| |||
|
|
|
|
|
|
|
|
А аз |
|
| |||
|
|
|
|
|
|
|
|
А м |
|
|
Пример 1
Като прост пример, помислете за игра, в която играта се състои от два хода.
1-ви ход: Играч НОизбира едно от числата (1 или 2), без да казва на противника за своя избор.
2-ри ход: Играч ATизбира едно от числата (3 или 4).
Резултат: Избор на играч НОи ATдобавите. Ако сборът е четен, тогава ATплаща своята стойност на играча НО, ако е нечетно - обратното, НОплаща на играча AT.
Тази игра може да бъде представена като 
по следния начин:
|
|
|
|
|
| ||
|
|
(избор 3)
(избор 4)
(избор 1)
(избор 2)Лесно е да се види това тази играе антагонистична, освен това е игра с непълна информация, тъй като играч AT,правейки личен ход, не е известно какъв избор е направил играчът НО.
Както беше отбелязано по-горе, задачата на теорията на игрите е да намери оптималните стратегии на играчите, т.е. стратегии, които им осигуряват максимална печалба или минимална загуба. Този процес се нарича решение на играта .
Когато решавате игра в матрична форма, трябва да проверите играта за присъствие решителна точка . За това се въвеждат две стойности:
е долната граница за цената на играта и
е горната оценка на цената на играта.
Първият играч най-вероятно ще избере стратегията, при която ще получи максимална печалба сред всички възможни отговори на втория играч, а вторият, напротив, ще избере тази, която минимизира собствената му загуба, т.е. възможна победа на първия.
Може да се докаже, че α ≤ V ≤ β , където V–цена на играта , т.е. вероятната печалба на първия играч.
Ако връзката α
=
β
=
V, тогава те казват, че играта има седлова точка
, и решени в чисти стратегии
. С други думи, има няколко стратегии 
, давайки на играча НОV.
Пример 2
Нека се върнем към играта, която разгледахме в Пример 1 и я проверим за наличието на седлова точка.
|
|
|
|
|
|
| |||
|
| |||
|
|
(избор 3)
(избор 4)
(избор 1)
(избор 2)
За тази игра 
=
-5,
=
4,
, следователно няма седлова точка.
Отново имайте предвид, че тази игра е игра с непълна информация. В този случай можете само да посъветвате играча НОизберете стратегия 
, защото в този случай обаче той може да получи най-голямата печалба, при условие че играчът избере ATстратегии 
.
Пример 3
Нека направим някои промени в правилата на играта от пример 1. Нека дадем играча ATинформация за избор на играч НО.Тогава ATИма две допълнителни стратегии:
- стратегия, която е от полза за НО.Ако избор А - 1,тогава ATизбира 3 при избор А - 2,тогава ATизбира 4;
- стратегия, която не е от полза за НО.Ако избор А - 1,тогава ATизбира 4 при избор А - 2,тогава ATизбира 3.
|
|
|
|
|
|
|
|
| |||||
|
| |||||
|
|
(избор 3)
(избор 4)
(избор 1)
(избор 2)
Тази игра е пълна с информация.
В такъв случай 
=
-5,
=
-5,
, следователно играта има седлова точка 
. Тази седлова точка съответства на две двойки оптимални стратегии: 
и 
. Цена на играта V= -5.
Очевидно е, че за НОтази игра е безполезна.
Примери 2 и 3 са добра илюстрация на следната теорема, доказана в теорията на игрите:
Теорема 1
Всяка сдвоена антагонистична игра с перфектна информация се решава в чисти стратегии.
Че. Теорема 1 казва, че всяка игра за двама с перфектна информация има седлова точка и има двойка чисти стратегии 
, давайки на играча НОустойчива печалба, равна на цената на играта V.
В случай на липса на седлова точка, т.нар смесени стратегии
:, където стр аз ир йса вероятностите за избор на стратегии А аз
и
б йсъответно първият и вторият играч. Решението на играта в този случай е двойка смесени стратегии 
максимизиране на математическото очакване на цената на играта.
Обобщение на теорема 1 за случай на игра с непълна информация е следната теорема:
Теорема 2
Всяка двойка антагонистична игра има поне едно оптимално решение, т.е. двойка смесени стратегии в общия случай 
, давайки на играча НОустойчива печалба, равна на цената на играта V, освен това α ≤
V ≤
β
.
В специален случай, за игра със седлова точка, решението при смесените стратегии изглежда като двойка вектори, в които един елемент е равен на единица, а останалите са равни на нула.
Най-простият случай, разработен подробно в теорията на игрите, е игра с крайна двойка с нулева сума (антагонистична игра на две лица или две коалиции). Помислете за тази игра Ж, в който двама играчи НОи AT,имащи противоположни интереси: печалбата на единия е равна на загубата на другия. Тъй като печалбата на играча НОе равно на печалбата на играча В ссрещуположен знак, можем да се интересуваме само от печалбата аиграч НО.Естествено, НОиска да увеличи максимално и В -минимизирам а.За простота, нека мислено се идентифицираме с един от играчите (нека бъде НО)и ще го наричаме "ние", и играча В -"противник" (разбира се, без реални предимства за НОне следва от това). Нека имаме Tвъзможни стратегии НО 1 , А 2 , ..., НО м, и врагът нвъзможни стратегии AT 1 , AT 2 , ..; AT н(такава игра се нарича игра T × н). Обозначете а ijнашата печалба, ако използваме стратегията А аз , а врагът е стратегия б й .
Таблица 26.1
|
А аз б й |
б 1 |
б 2 |
б н |
|
|
А 1 А 2 А м |
а 11 а 21 а m1 |
а 21 а м |
а 1 н а 2 н а мн |
Да предположим, че за всяка двойка стратегии A<, AT,победа (или средна печалба) а, йние знаем. Тогава по принцип е възможно да се състави правоъгълна таблица (матрица), в която са изброени стратегиите на играчите и съответните печалби (виж таблица 26.1).
Ако се състави такава таблица, тогава казваме, че играта Жсведен до матрична форма (само по себе си привеждането на играта в такава форма вече може да бъде трудна задача, а понякога и почти невъзможна, поради огромния брой стратегии). Обърнете внимание, че ако играта е сведена до матрична форма, тогава играта с няколко хода всъщност се свежда до игра с един ход - от играча се изисква да направи само един ход: изберете стратегия. Ще обозначим накратко игровата матрица ( а ij).
Помислете за примерна игра Ж(4×5) в матрична форма. На наше разположение (за избор) четири стратегии, врагът има пет стратегии. Матрицата на играта е дадена в таблица 26.2
Нека помислим каква стратегия ние (играчът НО)възползвам се? Матрица 26.2 има примамливата печалба "10"; ние сме привлечени да изберем стратегия НО 3 , при което ще получим тази "лаканина". Но чакайте, врагът също не е глупав! Ако изберем стратегия НО 3 , той, за да ни напука, ще избере стратегия AT 3 , и получаваме някаква мизерна печалба "1". Не, изберете стратегия НО 3 забранено е! Как да бъдем? Очевидно, въз основа на принципа на предпазливостта (и той е основният принцип на теорията на игрите), трябва да изберем
Таблица 26.2
|
б й А аз |
б 1 |
б 2 |
б 3 |
б 4 |
б 5 |
|
А 1 А 2 А 3 А 4 |
стратегията, която нашата минимална печалба е максимална.Това е така нареченият "минимаксен принцип": действайте по такъв начин, че при най-лошото поведение на врага за вас, вие получавате максимална печалба.
Пренаписваме таблица 26.2 и в дясната допълнителна колона записваме минималната стойност на изплащането във всеки ред, (минимален ред); нека го определим за аз-ти ред α аз(виж таблица 26.3).
Таблица 26.3
|
б й А аз |
б 1 |
б 2 |
б 3 |
б 4 |
б 5 | |
|
А 1 А 2 А 3 А 4 | ||||||
|
β й |
От всички ценности α аз(дясна колона) най-големият (3) е маркиран. Съвпада със стратегията Ачетири . Избирайки тази стратегия, ние във всеки случай можем да сме сигурни, че (при каквото и да е поведение на врага) ще спечелим не по-малко от 3. Тази стойност е нашата гарантирана печалба; като внимаваме, не можем да получим по-малко от това (може да получа повече). Това изплащане се нарича най-ниската цена на играта (или "maximin" - максимумът от минималните изплащания). Ще го обозначим а.В нашия случай α = 3.
Сега нека приемем гледната точка на врага и да го защитим. Той не е някаква пешка, но и разумен! Избирайки стратегия, той би искал да даде по-малко, но трябва да разчита на нашето поведение, което е най-лошото за него. Ако избере стратегия AT 1 , ние ще му отговорим НО 3 , и той ще даде 10; ако реши б 2 - ще му отговорим НО 2 , и той ще даде 8 и т.н. Добавяме допълнителен долен ред към таблица 26.3 и записваме в него максимумите на колоните β й. Очевидно един предпазлив противник трябва да избере стратегията, която минимизира тази стойност (съответстващата стойност от 5 е подчертана в таблица 26.3). Тази стойност на β е стойността на печалбата, повече от която разумен противник със сигурност няма да ни даде. Нарича се горната цена на играта (или "минимакс" - минималната от максималните печалби). В нашия пример β = 5 и се постига със стратегията на противника б 3 .
Така че, въз основа на принципа на предпазливостта (правилото на презастраховането „винаги разчитайте на най-лошото!“), Ние трябва да изберем стратегия НО 4 , а врагът – стратегия AT 3 . Такива стратегии се наричат "минимакс" (следващи от принципа на минимакса). Докато и двете страни в нашия пример се придържат към своите минимакс стратегии, печалбата ще бъде а 43 = 3.
Сега си представете за момент, че сме научили, че врагът следва стратегия AT 3 . Хайде, да го накажем за това и да изберем стратегия НО 1 - ще получим 5, което не е толкова лошо. Но в крайна сметка врагът също не е пропуск; нека знае, че нашата стратегия НО 1 ; той също избира бързо AT 4 , намаляване на нашата печалба до 2 и т.н. (партньорите „бързаха със стратегиите“). С една дума, минимаксни стратегии в нашия пример нестабилен по отношение нада се информация за поведението на другата страна;тези стратегии нямат свойството равновесие.
Винаги ли е така? Не винаги. Разгледайте пример с матрицата, дадена в таблица 26.4.
В този пример долната цена на играта е равна на горната: α = β = 6. Какво следва от това? Стратегии за играч на Minimax НОи ATще бъде устойчиво. Докато и двамата играчи се придържат към тях, печалбата е 6. Да видим какво ще се случи, ако ние (НО)знайте, че врагът (AT)
Таблица 26.4
|
бй А аз |
б 1 |
б 2 |
б 3 |
б 4 | |
|
А 1 А 2 А 3 | |||||
|
β й |
се придържа към стратегията б 2 ? И точно нищо няма да се промени. Защото всяко отклонение от стратегията НО 2 може само да влоши положението ни. По същия начин информацията, получена от врага, няма да го накара да отстъпи от стратегията си. AT 2 . Двойка стратегии НО 2 , б 2 притежава свойството на равновесие (балансирана двойка стратегии), а печалбата (в нашия случай 6), постигната с тази двойка стратегии, се нарича „седлова точка на матрицата“ 1). Знак за наличието на седлова точка и балансирана двойка стратегии е равенството на долната и горната цена на играта; общата стойност на α и β се нарича цена на играта. Ще го обозначим v:
α = β = v
Стратегии А аз , б й(в такъв случай НО 2 , AT 2 ), за които се постига тази печалба се наричат оптимални чисти стратегии, а тяхната съвкупност се нарича решение на играта. В този случай се казва, че самата игра се решава в чисти стратегии. И двете страни НОи ATмогат да се посочат техните оптимални стратегии, при които тяхната позиция е най-добрата възможна. Какво е играч НОв този случай 6 печели, а играчът В -губи 6, - добре, това са условията на играта: те са от полза за НОи неблагоприятно за AT
1) Терминът "седлова точка" е взет от геометрията - това е името на точката от повърхнината, където едновременно се достига минимум по едната координата и максимумът по другата.
Читателят може да има въпрос: защо оптималните стратегии се наричат „чисти“? Гледайки малко напред, нека да отговорим на този въпрос: има "смесени" стратегии, които се състоят в това, че играчът използва не една стратегия, а няколко, като ги редува на случаен принцип. Така че, ако допуснем, освен чистите, и смесени стратегии, всякакви край на игратаима решение – равновесна точка. Но все пак говорим за атома.
Наличието на седлова точка в играта далеч не е правило, а по-скоро изключение. Повечето игри нямат седлова точка. Има обаче различни игри, които винаги имат седлова точка и следователно се решават в чисти стратегии. Това са така наречените "игри с пълна информация". Игра с рафт информация е игра, в която всеки играч знае цялата история на своето развитие, тоест резултатите от всички предишни ходове, както лични, така и произволни, при всеки личен ход. Примери за игри с пълна информация са дама, шах, тик-так и др.
В теорията на игрите е доказано, че всяка игра с пълна информация има седлова точка,и следователно могат да бъдат решени в чисти стратегии. Във всяка игра с перфектна информация има двойка оптимални стратегии, които дават стабилна печалба, равна на веригата на играта v. Ако една такава игра се състои само от лични ходове, тогава когато всеки играч прилага собствената си оптимална стратегия, тя трябва да завърши по съвсем определен начин - с печалба, равна на цената на играта. Така че, ако решението на играта е известно, самата игра губи смисъл!
Да вземем елементарен пример за игра с пълна информация: двама играчи последователно поставят монети върху кръгла маса, като избират произволно позицията на центъра на монетата (не се допуска взаимно припокриване на монети). Победител е този, който сложи последната стотинка (когато няма място за други). Лесно е да се види, че изходът от тази игра по същество е предрешен. Има определена стратегия, която гарантира, че играчът, който първи постави монетата, печели. А именно, той трябва първо да постави никел в центъра на масата и след това да отговори на всеки ход на опонента със симетричен ход. Очевидно, както и да се държи противникът, той не може да избегне загубата. Ситуацията е абсолютно същата при шаха и игрите с пълна информация като цяло: всяка от тях, написана в матрична форма, има седлова точка и следователно решението е в чистите стратегии и следователно има смисъл само докато това решението не е намерено. Да кажем, че една игра на шах е едно от двете винагизавършва с победа на белите, или винаги -черните печелят, или винаги -реми, само че с какво точно - все още не знаем (за щастие на любителите на шаха). Нека добавим още нещо: едва ли ще разберем в обозримо бъдеще, защото броят на стратегиите е толкова огромен, че е изключително трудно (ако не и невъзможно) играта да се сведе до матрична форма и да се намери седлова точка в нея.
Сега нека се запитаме какво да правим, ако играта няма седлова точка: α ≠ β ? Е, ако всеки играч е принуден да избере една - единствената чиста стратегия, тогава няма какво да се направи: човек трябва да се ръководи от принципа на минимакса. Друго нещо е, ако е възможно да се „смеси“ набор от стратегии, редуващи се произволно с някои вероятности. Използването на смесени стратегии е замислено по следния начин: играта се повтаря многократно; преди всяка игра от играта, когато на играча се даде личен ход, той "поверява" избора си на случайността, "хвърля жребий" и взема стратегията, която е паднала (вече знаем как да организираме жребия от предишната глава ).
Смесените стратегии в теорията на игрите са модел на променлива, гъвкава тактика, когато никой от играчите не знае как ще се държи противникът в дадена игра. Тази тактика (макар и обикновено без никаква математическа обосновка) често се използва в игрите с карти. Нека отбележим в същото време, че най-добрият начин да скриете поведението си от врага е да му придадете произволен характер и следователно да не знаете предварително какво ще направите.
И така, нека поговорим за смесени стратегии. Ще обозначим смесените стратегии на играчите НОи ATсъответно С A = ( стр 1 , Р 2 , ..., стр м), С б = (р 1 , р 2 , …, р н), където стр 1 , стр 2 , …, стр м(образувайки общо едно) - вероятностите на играча да използва НОстратегии НО 1 , А 2 ,… , А м ; р 1 , р 2 , …, р н- вероятности за използване от играча ATстратегии AT 1 , AT 2 , ..., AT н . В конкретен случай, когато всички вероятности, с изключение на една, са равни на нула, а тази е равна на единица, смесената стратегия се превръща в чиста.
Има една основна теорема на теорията на игрите: всяка игра с краен резултат с нулева сума за двама има поне едно решение -двойка оптимални стратегии, обикновено смесени 
и съответната цена v.
Двойка оптимални стратегии 
формирането на решението на играта има следното свойство: ако един от играчите се придържа към своята оптимална стратегия, тогава не може да бъде изгодно за другия да се отклони от своята.Тази двойка стратегии формира един вид равновесие в играта: единият играч иска да превърне печалбата до максимум, другият до минимум, всеки дърпа в собствената си посока и, с разумно поведение и на двамата, равновесие и стабилен се установяват печалба. v.Ако v > 0, тогава играта е печеливша за нас, ако v<
0
-
за врага; при v= 0 играта е „честна“, еднакво изгодна и за двамата участници.
Разгледайте пример за игра без седлова точка и дайте (без доказателство) нейното решение. Играта е следната: двама играчи НОи ATедновременно и без да казва дума показва един, два или три пръста. Печалбата се определя от общия брой пръсти: ако е четен, печели НОи получава от ATсума, равна на това число; ако е странно, тогава обратното НОплаща ATсума, равна на това число. Какво трябва да направят играчите?
Нека създадем игрова матрица. В една игра всеки играч има три стратегии: покажете един, два или три пръста. Матрицата 3 × 3 е дадена в таблица 26.5; допълнителната дясна колона показва минимумите на редовете, а допълнителният долен ред показва максимумите на колоните.
По-ниската цена на играта α = - 3 и съответства на стратегията А 1 . Това означава, че с разумно, предпазливо поведение гарантираме, че няма да загубим повече от 3. Слаба утеха, но все пак по-добре от, да речем, печалба от 5, която се случва в някои клетки на матрицата. Лошо за нас, играча НО...Но нека се утешим:
позицията на противника изглежда още по-лоша: по-ниската цена на играта е β = 4, т.е. при разумно поведение той ще ни даде поне 4. Като цяло позицията не е много добра - нито за един, нито за друга страна. Но да видим дали може да се подобри? Оказва се, че можете. Ако всяка страна използва не една чиста стратегия, а смесена, при която
Таблица 26.5
|
бй А аз |
б 1 |
б 2 |
б 3 | |
|
А 1 А 2 А 3 | ||||
|
β й |
първото и третото влизат с вероятност 1/4, а второто - с вероятност 1/2, т.е.
тогава средната печалба ще бъде постоянно равна на нула (което означава, че играта е „честна“ и еднакво изгодна и за двете страни). Стратегии 
формират решение на играта и нейната цена v= 0. Как намерихме това решение? Това е друг въпрос. В следващия раздел ще покажем как обикновено се решават крайни игри.
Помислете за игра на двойки с ограничена нулева сума. Означаваме с апечалба на играча А, и през b- победа на играча б. защото а = –b, тогава при анализиране на такава игра няма нужда да се вземат предвид и двете числа - достатъчно е да се вземе предвид печалбата на един от играчите. Нека бъде напр. А. По-нататък, за удобство на представянето, отстрани Аусловно ще назовем " ние"и отстрани б – "враг".
Нека имаме мвъзможни стратегии А 1 , А 2 , …, A m, и врагът нвъзможни стратегии б 1 , б 2 , …, B n(такава игра се нарича игра m×n). Да приемем, че всяка страна е избрала определена стратегия: ние сме избрали Ai, противник B j. Ако играта се състои само от лични ходове, тогава изборът на стратегии Aiи B jеднозначно определя изхода от играта – нашата печалба (положителна или отрицателна). Нека обозначим тази печалба като aij(печелим, когато изберем стратегията Ai, а врагът - стратегии B j).
Ако играта съдържа, в допълнение към личните произволни ходове, тогава печалбата за двойка стратегии Ai, B jе случайна променлива, която зависи от резултатите от всички произволни ходове. В този случай естествената оценка на очакваната печалба е математическо очакване на случайна печалба. За удобство ще означаваме с aijкакто самата печалба (в игра без произволни ходове), така и математическото очакване (в игра със случайни ходове).
Да предположим, че знаем стойностите aijза всяка двойка стратегии. Тези стойности могат да бъдат записани като матрица, чиито редове съответстват на нашите стратегии ( Ai), а колоните показват стратегиите на противника ( B j):
| B j A i | б 1 | б 2 | … | B n |
| А 1 | а 11 | а 12 | … | а 1н |
| А 2 | а 21 | а 22 | … | а 2н |
| … | … | … | … | … |
| A m | a m 1 | a m 2 | … | amn |
Такава матрица се нарича матрица на изплащане на игратаили просто игрова матрица.
Имайте предвид, че изграждането на матрица за изплащане за игри с голям брой стратегии може да бъде трудна задача. Например за игра на шахброят на възможните стратегии е толкова голям, че изграждането на матрицата за изплащане е практически невъзможно. По принцип обаче всяка крайна игра може да бъде сведена до матрична форма.
Обмисли пример 1 4×5 антагонистична игра. Имаме четири стратегии на наше разположение, врагът има пет стратегии. Матрицата на играта е следната:
| B j A i | б 1 | б 2 | б 3 | б 4 | б 5 |
| А 1 | |||||
| А 2 | |||||
| А 3 | |||||
| А 4 |
Каква стратегия трябва да използваме (т.е. играчът А) да използвам? Каквато и стратегия да изберем, разумният противник ще й отговори със стратегията, за която нашата печалба ще бъде минимална. Например, ако изберем стратегията А 3 (изкушен от победа от 10), опонентът ще избере стратегия в отговор б 1 , а нашата печалба ще бъде само 1. Очевидно, въз основа на принципа на предпазливостта (и той е основният принцип на теорията на игрите), трябва да изберем стратегията, в която нашата минимална печалба е максимална.
Означаваме с a iминимална стойност на изплащане за стратегията Ai:
и добавете колона, съдържаща тези стойности към матрицата на играта:
| B j A i | б 1 | б 2 | б 3 | б 4 | б 5 | минимум в редове a i | |
| А 1 | |||||||
| А 2 | |||||||
| А 3 | |||||||
| А 4 | максимин |
Когато избираме стратегия, трябва да изберем тази, за която стойността a iмаксимум. Нека означим тази максимална стойност с α :
Стойност α Наречен по-ниска цена на игратаили максимин(максимална минимална печалба). Стратегия на играча Асъответстващ на максимина α , е наречен максимин стратегия.
В този пример максиминът α е равно на 3 (съответната клетка в таблицата е маркирана в сиво), а стратегията maximin е Ачетири . След като сме избрали тази стратегия, можем да сме сигурни, че за каквото и да е поведение на врага ще спечелим не по-малко от 3 (а може би и повече с „неразумното” поведение на врага).Тази стойност е нашият гарантиран минимум, който можем да осигурим за себе си, придържайки се към най-предпазливата („презастрахователна“) стратегия.
Сега ще проведем подобни разсъждения за врага б б А б 2 - ще му отговорим А .
Означаваме с βj А б) за стратегията Ai:
βj β :
7. КАКВО Е ИГРАТА С ГОРНА СТОЙНОСТ Сега ще проведем подобно разсъждение за противника б. Той е заинтересован да минимизира печалбата ни, тоест да ни даде по-малко, но трябва да разчита на нашето поведение, което е най-лошото за него. Например, ако той избира стратегията б 1 , тогава ще му отговорим със стратегия А 3 , а той ще ни даде 10. Ако реши б 2 - ще му отговорим А 2 , а той ще даде 8 и т. н. Очевидно предпазливият противник трябва да избере стратегията, в която нашата максимална печалба ще бъде минимална.
Означаваме с βjмаксималните стойности в колоните на матрицата за изплащане (максималното изплащане на играча А, или, което е същото, максималната загуба на играча б) за стратегията Ai:
и добавете ред, съдържащ тези стойности към матрицата на играта:
Избирайки стратегия, врагът ще предпочете тази, за която стойността βjминимум. Нека го обозначим с β :
Стойност β Наречен топ цена на игратаили минимакс(минимална максимална печалба). Стратегията на противника (играча), съответстваща на минимакса б), е наречен минимакс стратегия.
Минимакс е стойността на печалбата, повече от която разумният противник със сигурност няма да ни даде (с други думи, разумният противник няма да загуби повече от β ). В този пример минимакс β е равно на 5 (съответната клетка в таблицата е маркирана в сиво) и се постига със стратегията на противника б 3 .
Така че, въз основа на принципа на предпазливостта („винаги очаквай най-лошото!“), трябва да изберем стратегия А 4 , а врагът - стратегия б 3 . Принципът на предпазливост е основен в теорията на игрите и се нарича минимаксен принцип.
Обмисли пример 2. Нека играчите Аи ATедно от трите числа се изписва едновременно и независимо едно от друго: или "1", или "2", или "3". Ако сборът на написаните числа е четен, тогава играчът бплаща на играча Атази сума. Ако сумата е нечетна, тогава играчът плаща тази сума Аиграч AT.
Нека запишем матрицата на изплащане на играта и да намерим долната и горната цена на играта (номерът на стратегията съответства на написаното число):
Играч Атрябва да се придържа към стратегията maximin А 1, за да спечелите поне -3 (т.е. да загубите най-много 3). Стратегия за играч Minimax бкоято и да е от стратегиите б 1 и б 2 , което гарантира, че няма да даде повече от 4.
Ще получим същия резултат, ако напишем матрицата за изплащане от гледна точка на играча AT. Всъщност тази матрица се получава чрез транспониране на матрицата, конструирана от гледна точка на играча А, и промяна на знаците на елементите на противоположни (тъй като печалбата на играча Ае загубата на играча AT):
Въз основа на тази матрица следва, че играчът бтрябва да следва някоя от стратегиите б 1 и б 2 (и тогава той ще загуби не повече от 4), и играчът А– стратегии А 1 (и тогава той ще загуби не повече от 3). Както можете да видите, резултатът е абсолютно същият като този, получен по-горе, така че анализът няма значение от гледна точка на кой играч го провеждаме.
8 КАКВО Е СТОЙНА ИГРА.
9. В КАКВО СЕ СЪСТОИ ПРИНЦИПЪТ НА МИНИМАКС. 2. Долна и горна цена на играта. Минимаксен принцип
Помислете за матрична игра от типа с матрица на изплащане
Ако играчът НОще избере стратегия A i, тогава всички негови възможни печалби ще бъдат елементи аз-ти ред на матрицата ОТ. Най-лошото за играч НОслучай, когато играчът ATприлага стратегия, подходяща за минимумелемент от тази линия, печалбата на играча НОще бъде равно на числото.
Следователно, за да получите максимална печалба, играчът НОтрябва да изберете една от стратегиите, за които броят максимум.
Проблемът за вземане на решение, разглеждан в рамките на системния подход, съдържа три основни компонента: в него се идентифицират системата, управляващата подсистема и средата. Сега се обръщаме към изследването на проблемите на вземане на решения, при които системата се влияе не от една, а от няколко контролни подсистеми, всяка от които има свои собствени цели и възможности за действие. Този подход за вземане на решения се нарича теоретичен на игрите, а математическите модели на съответните взаимодействия се наричат игри. Поради разликата в целите на управляващите подсистеми, както и някои ограничения на възможността за обмен на информация между тях, тези взаимодействия имат конфликтен характер. Следователно всяка игра е математически модел на конфликт. Ограничаваме се до случая, когато има две управляващи подсистеми. Ако целите на системите са противоположни, конфликтът се нарича антагонистичен, а математическият модел на такъв конфликт се нарича антагонистична игра..
В терминологията на теорията на игрите се нарича 1-ва подсистема за управление играч 1, 2-ра подсистема за управление - играч 2, комплекти
техните алтернативни действия се наричат набори от стратегиитези играчи. Позволявам х- набор от стратегии за играч 1, Y- много стратегии
играч 2. Състоянието на системата се определя еднозначно от избора на контролни действия от подсистеми 1 и 2, т.е. избора на стратегии
х∈хи г∈Y. Позволявам Е(х,г) - оценка на полезността за играч 1 от това състояние
системата, към която преминава, когато играч 1 избере стратегия хи
стратегия за играч 2 при. Номер Е(х,г) е наречен печелившиграч 1 в ситуацията ( х,г), и функцията Е- функция за изплащане на играч 1. Победа на играча
1 е и загубата на играч 2, тоест стойността, която първият играч се стреми да увеличи, а вторият - да намали. Това е, което е
проявление на антагонистичния характер на конфликта: интересите на играчите са напълно противоположни (каквото печели единият, другият губи).
Антагонистична игра е естествено зададена от системата G=(X, Y, F).
Обърнете внимание, че формално антагонистичната игра всъщност е поставена по същия начин като проблема за вземане на решение в условия на несигурност - ако
идентифицира контролната подсистема 2 с околната среда. Съществената разлика между управляващата подсистема и средата е в това
поведението на първия е целенасочено. Ако при съставянето на математически модел на реален конфликт имаме причина (или намерение) да разглеждаме средата като противник, чиято цел е да донесе
ни максимална вреда, тогава такава ситуация може да бъде представена като антагонистична игра. С други думи, антагонистичната игра може да се тълкува като екстремен случай на ZPR при условия на несигурност,
характеризиращ се с това, че средата се разглежда като противник с цел. В същото време трябва да ограничим видовете хипотези за поведението на околната среда.
Най-обоснована тук е хипотезата за изключителна предпазливост, когато при вземане на решение разчитаме на възможно най-лошия за нас сценарий на действие в средата.
Определение.Ако хи Yса крайни, тогава антагонистичната игра се нарича матрица. В матричната игра можем да приемем това х={1,…,н},
Y={1,…,м) и поставете aij=F(i,j). Така матричната игра се определя изцяло от матрицата А=(aij), т.е=1,…,n, j=1,…,м.
Пример 3.1. Игра с два пръста.
Двама души едновременно показват един или два пръста и наричат числото 1 или 2, което според говорещия означава числото
пръсти, показани на другите. След показване на пръстите и назоваване на числата, печалбите се разпределят съгласно следните правила:
ако и двамата са познали или и двамата не са познали колко пръста е показал противникът им, печалбата на всеки е равна на нула; ако само един е познал правилно, тогава противникът плаща на познатия сумата пари, пропорционална на общия брой показани
Това е антагонистична матрична игра. Всеки играч има четири стратегии: 1- покажете 1 пръст и кажете 1, 2- покажете 1 пръст и кажете 2, 3-
покажете 2 пръста и кажете 1, 4 - покажете 2 пръста и кажете 2. След това матрицата за изплащане A=(aij), i= 1,…, 4, j= 1,…, 4 се определя, както следва:
a12= 2, a21 = – 2, a13=a42=–3, a24=a31= 3, a34 = – 4, a43= 4,aij= 0 в противен случай.
Пример 3.2. Дискретна игра тип дуел.
Задачите от тип дуел описват например борбата на двама играчи,
всеки от които иска да извърши някакво еднократно действие (пускане на партида стоки на пазара, заявка за покупка на търг) и избира момент за това. Оставете играчите да се движат един към друг нстъпки. След всяка направена стъпка играчът може или не може да стреля по противника. Всеки човек може да има само един удар. Смята се, че вероятността да ударите врага, ако напреднете с к n =5 има формата
