Принципи за решаване на матрични антагонистични игри. Матрични игри: примери за решаване на проблеми

Тук ли си: Почивни дни

Цел на услугата. С помощта на онлайн услугата можете:

определяне на цената на матрична игра (долна и горна граница), проверка за наличие на седлова точка, намиране на решение на смесена стратегия, намиране на минимаксна стратегия на играчите;
запишете математически модел на двойка проблеми с двойно линейно програмиране, решете матрична игра, като използвате следните методи: минимакс, симплексен метод, графичен (геометричен) метод, метод на Браун.

Инструкции. Изберете измерението на матрицата, щракнете върху Напред. В новия диалогов прозорец изберете метод за решаване на матричната игра. Пример за пълнене. Резултатите от изчислението се представят в отчет във формат Word.

Играе математически модел на реална конфликтна ситуация. Конфликтна ситуация между двама играчи се нарича игра на двойки. Удобно е да се изследва игра по двойки с нулева сума, ако е описана под формата на матрица. Тази игра се нарича матрица; матрица, съставена от числа a ij, се нарича плащане. Таблицата представя опции за решаване на играта, зададена от платежната матрица A.

Описание на алгоритъма:

Въз основа на анализа на платежната матрица е необходимо да се определи дали в нея има доминирани стратегии и да се елиминират.
Намерете горната и долната цена на играта и определете дали тази игра има седлова точка (долната цена на играта трябва да е равна на горната цена на играта).
Ако съществува седлова точка, тогава оптималните стратегии на играчите, които са решението на играта, ще бъдат техните чисти стратегии, съответстващи на седловата точка. Цената на играта е равна на горната и долната цена на играта, които са равни една на друга.
Ако играта няма седлова точка, тогава решението на играта трябва да се търси в смесени стратегии. За да се определят оптимални смесени стратегии в m × n игри, трябва да се използва симплексният метод, като първо се преформулира проблемът на играта в проблем с линейно програмиране.

Нека представим графично алгоритъма за решаване на матрична игра.

Фигура - Схема за решаване на матрична игра.

Методи за решаване на матрични игри в смесени стратегии

Така че, ако няма седлова точка, играта се решава с помощта на смесени стратегии и се решава с помощта на следните методи:

Решаване на играта чрез система от уравнения.
Ако е дадена квадратна матрица nxn (n=m), тогава векторът на вероятността може да бъде намерен чрез решаване на системата от уравнения. Този метод не винаги се използва и е приложим само в определени случаи (ако матрицата е 2x2, тогава решението на играта почти винаги се получава). Ако решението произвежда отрицателни вероятности, тогава тази система се решава с помощта на симплексния метод.
Решаване на играта графично.
В случаите, когато n=2 или m=2, матричната игра може да бъде решена графично.
Решаване на матрична игра по симплексния метод.
В този случай матричната игра се свежда до

Подходът за решаване на матрични игри може да се обобщи за случая на игри с нулева сума, в които печалбата на играчите е определена като непрекъсната функция (безкрайна игра с нулева сума).

Тази игра е представена като игра за двама играчи, в която играч 1 избира число хот много Х,играч 2 избира числото y от комплекта 7 и след това играчи 1 и 2 получават съответно печалби U(x, y) и -U(x, y).Изборът на определено число от играч означава прилагането на неговата чиста стратегия, съответстваща на това число.

По аналогия с матричните игри може да се нарече нетната по-ниска цена на една игра v (=макс мин U(x, y),и нетната най-висока цена на играта -v 2 =

мин. макс U(x, y).Тогава, по аналогия, можем да приемем, че ако за някои

при *

или безкрайна антагонистична игра на величини VИ v 2съществуват и са равни помежду си („i =v 2 =v),тогава такава игра има решение в чисти стратегии, т.е. Оптималната стратегия на играч 1 е да избере число x°д Х,и играч 2 - числа y 0 e 7, за което щч ( y 0) -v.

В такъв случай vсе нарича нетна цена на играта, а (x°, y 0) е седловата точка на безкрайна игра с нулева сума.

За матрични игри с големина v xИ v 2винаги съществуват, но в безкрайните антагонистични игри може и да не съществуват, т.е. безкрайната игра с нулева сума не винаги е разрешима.

Когато се формализира реална ситуация под формата на безкрайна антагонистична игра, обикновено се избира единичен стратегически интервал - единичен интервал, от който играчите могат да направят избор (Х -номер (стратегия), избран от играч 1; -

число (стратегия), избрано от играч 2). Технически това опростява решението, тъй като чрез проста трансформация всеки интервал може да бъде преобразуван в единичен интервал и обратно. Тази игра се нарича антагонистична игра на единичен квадрат.

Например, да кажем, че играч 1 избира числото хот много X=, играч 2 избира номер y от комплекта Y=. След това играч 2 плаща на играч 1 сумата Shchh, y) -2x 2 -y 2.Тъй като играч 2 се стреми да минимизира плащането на играч 1, той определя min ( 2x 2 - y 2) = 2x 2- 1, т.е. в този случай = 1. Играч 1 се стреми да направи mtag

Симулирайте вашето плащане, следователно определя максимален мин щчх, y)1 =

xGX y напр

- макс (2x 2 - 1) = 2- 1 = 1, което се постига, когато х = 1.

По този начин, по-ниската нетна цена на играта v x - 1. Почистете отгоре

цена на игратаv 2 =min - min (2 - y 2) = 2 - 1 = 1, т.е. в това

> напрхех ти ей

игра v l = v 2 = l.Следователно нетната цена на играта v= 1 и седловата точка (x° = 1; y° = 1).

Нека сега приемем това Чи У-отворени интервали, т.е. играч 1 избира xeA"=(0; 1), играч 2 избира ue 7= (0; 1). В този случай изборът Х,достатъчно близо до 1, играч 1 ще бъде уверен, че ще получи печалба не по-малка от число, близко до "=1; като избере y близо до 1, играч 2 няма да позволи печалбата на играч 1 да надвиши значително нетната цена на играта v= 1.

Степента на близост до цената на играта може да се характеризира с числото?>0. Следователно в описаната игра можем да говорим за оптималност на чистите стратегии x°= 1, 0 = 1 съответно играчи 1 и 2 до произволен брой?>0. Точка (Х", y E), където x д e X, y (. eY, в безкрайна игра с нулева сума се нарича z-равновесна точка (s.-седлова точка), ако за всякакви стратегии xTiger 1, ue Tiger 2 неравенството е в сила щчх, u.) - ? Ш x r , у (.) U(x t ., у) + ?. В този случай стратегиите x k.и ти. са наречени с,-оптимални стратегии. Тези стратегии оптимални ли са до? в смисъл, че ако едно отклонение от оптималната стратегия не може да донесе никаква полза на играча, тогава неговото отклонение от c-оптималната стратегия може да увеличи печалбата му с не повече от e.

Ако играта няма седлова точка (c-седлова точка), т.е. решения в чисти стратегии, тогава оптимални стратегии могат да се търсят сред смесени стратегии, които се използват като функции на вероятностно разпределение на играчи, използващи чисти стратегии.

Позволявам F(x)е функцията на разпределение на вероятността за използването на чисти стратегии от играч 1. Ако числото E е чистата стратегия на играч 1, тогава F(x) = P(q където P(q -Х)- вероятността произволно избрана чиста стратегия E да не надвишава Х.Функцията на разпределение на вероятностите за използване на чисти стратегии r| се разглежда по подобен начин. играч 2: Q(y) = P(g .

Функции F(x)И Q(y)са наречени смесени стратегиисъответно играчи 1 и 2. Ако Fx)И Q(y)са диференцируеми, тогава съществуват техните производни, означени съответно с f(x)И q(y)(функции на плътността на разпределението).

Като цяло диференциалът на функцията на разпределение dF(x) изразява вероятността стратегията с,е по средата x E, По същия начин за играч 2: dQ(y)означава вероятността неговата стратегия p да е в интервала y g| y+dy.Тогава плащането на играч 1 ще бъде Shx, y) dF(x),и плащането на играч 2 е Shx, y) dQ(y).

Средната печалба на играч 1, като се има предвид, че играч 2 използва своята чиста стратегия y,може да се получи чрез интегриране на плащания върху всички възможни стойности Х,тези. на единичен интервал:

Средна печалба на играч 1, ако приемем, че и двамата играчи използват своите смесени стратегии F(x)И Q(y),ще бъдат равни

По аналогия с матричните игри се определят оптималните смесени стратегии на играчите и цената на играта: ако двойка смесени стратегии F*(x) И Q*(y)съответно за играчи 1 и 2 са оптимални, след това за всякакви смесени стратегии F(x)И Q(y)важат следните отношения:

Ако играч 1 се отклони от своята стратегия F*(x),тогава неговата средна печалба не може да се увеличи, но може да намалее поради рационалните действия на играч 2. Ако играч 2 се оттегли от своята смесена стратегия Q*(y),тогава средната печалба на играч 1 може да се увеличи, но не и да намалее, поради по-разумни действия на играч 1. Средна печалба E(F*, Q*),получена от играч 1, когато играчите прилагат оптимални смесени стратегии, съответства на цената на играта.

Тогава минималната цена на безкрайна игра с нулева сума, решена в смесени стратегии, може да се определи като v x= проверка

мин д(FQ),и най-високата цена на играта е като v 2 =мин. макс E(F, Q).

Q Q f

Ако такива смесени стратегии съществуват F* (x)И Q*(y) съответно за играчи 1 и 2, за които долната и горната цена на играта съвпадат, тогава F*(x)И Q*(y)Естествено е да наречем оптималните смесени стратегии на съответните играчи, а v=v x = v 2- на цената на играта.

За разлика от матричните игри, решение на безкрайна игра с нулева сума не съществува за всяка функция Шшт, ъъъ).Но теоремата е доказана, че всяка безкрайна игра с нулева сума с непрекъсната функция на изплащане Шшт, ъъъ)на единичния квадрат има решение (играчите имат оптимални смесени стратегии), въпреки че няма общи методи за решаване на безкрайни игри с нулева сума, включително непрекъснати игри. Въпреки това, антагонистични безкрайни игри с изпъкнали и вдлъбнати непрекъснати функции на изплащане (те се наричат съответно изпъкналИ вдлъбнати игри).

Нека разгледаме решението на игри с изпъкнала функция на изплащане. Решението на игри с вдлъбната функция на изплащане е симетрично.

Изпъкналфункция/променлива хна интервала ( А; б)е функция, за която неравенството е в сила

Където XxИ х 2 -всякакви две точки от интервала (a; b);

X.1, A.2 > 0 и +X.2= 1.

Ако за / h * 0 D 2 * 0, строгото неравенство винаги е в сила

тогава се извиква функцията/ строго изпъкнална; б).

Геометрично изпъкнала функция изобразява дъга, чиято графика е разположена под стягащата я хорда. Аналитично, изпъкналостта на два пъти диференцируема функция съответства на неотрицателността (и в случай на строга изпъкналост, положителността) на нейната втора производна.

За вдлъбнати функции свойствата са противоположни, за тях неравенството /(/4X1 +A.2X2) > Kf(xi) +)-ако(x 2) (> със стриктна вдлъбнатост) и втората производна / "(x)

Доказано е, че непрекъсната и строго изпъкнала функция на затворен интервал приема минимална стойност само в една точка от интервала. Ако щчх, y) е непрекъсната функция на печалбите на играч 1 върху единичния квадрат и строгоизпъкнал по протежение приза всяко x, тогава има уникална оптимална чиста стратегия y=y° e за играч 2, цената на играта се определя по формулата

и значението y 0се определя като решение на следното уравнение:

Ако функцията щчх, y) не е строго изпъкнал по y, тогава играч 2 няма да има единствената оптимална чиста стратегия.

Свойството за симетрия е валидно и за строго вдлъбнати функции. Ако функцията щчх, y) е непрекъснато в двата аргумента и е строго вдлъбнато в x за всяко y, тогава играч 1 има уникална оптимална стратегия.

Цената на играта се определя по формулата

и нетната оптимална стратегия x 0 на играч 1 се определя от уравнението

Въз основа на тези свойства на безкрайни игри с нулева сума с изпъкнали или вдлъбнати функции на изплащане е изградена обща схема за решаване на такива игри на единичен квадрат (хе, уе). Представяме тази схема само за изпъкнали игри, тъй като за вдлъбнати игри тя е симетрична.

1. Проверете функцията щчх, y) за изпъкналост в y (втората частна производна трябва да е по-голяма или равна на 0).

2. Определете y 0 от връзката v-мин. макс Шшт, ъъъ)като смисъл

y,при което се постига минимакс.

3. Намерете решението на уравнението v = U(x, y 0) и направете двойки от неговите решения хИ х 2,за което

4. Намерете параметър Аот ур.

Параметър Аопределя оптималната стратегия на играч 1 и има значението на вероятността той да избере своята чиста стратегия x x.Стойността 1 - a има значението на вероятността играч 1 да избере своята чиста стратегия х 2.

Нека използваме пример, за да демонстрираме използването на тази схема за решаване на игра от този тип. Нека функцията за печалба в безкрайна игра с нулева сума е дадена на единичен квадрат и е равна на Shchh, y) = =(x - y) 2 = x 2 - 2 xy ch-y 2.

1. Тази функция е непрекъсната в хИ y,и следователно тази игра има решение. функция Шшт, ъъъ)строго изпъкнали по дължината y,защото

Следователно играч 2 има единствената чиста оптимална стратегия 0.

2. Имаме v= min max (x - y) 2. За определяне на max (x 2 - 2xy Ch-y 2)

Нека последователно намерим първата и втората частни производни на платежната функция по отношение на x:

Така че функцията Uима минимум за всяко y при x=y. Това означава, че тъй като xy - нараства, а неговият максимум трябва да се постигне в една от крайните точки x = 0 или x = 1. Нека определим стойностите на функцията Uв тези точки:

След това проверете (x - y) 2 = max (y 2; 1 - 2y + y 2). Сравняване на "вътрешен"

максимуми във къдрави скоби, лесно се вижда това на 2 > 1 - - 2y+y 2,Ако y >*/ 2 и y 2 1 - 2 y+y 2,Ако y "/ 2. Това е представено по-ясно от графиката (фиг. 2.5).

Ориз. 2.5. Вътрешни максимуми на платежната функция U(x, y) = (x- при) 2

Следователно изразът (x - y) 2достига своя максимум при x=0, ако y > 7 2 и при x= 1 ако в U 2:

следователно v= min ( min y 2 ; min (1 - y) 2 ). Всеки от

сутрешните минимуми се достигат при y=*/ 2 и приема стойност Y 4. Така цената на играта r = Y 4 и оптималната стратегия на играч 2:

3. Определете оптималната стратегия на играч 1 от уравнението U(x, y 0)= v,тези. за тази игра (x - Y 2) 2 = Y 4. Решението на това уравнение СА X| =0, x 2 = 1.

За тях има условия

4. Нека определим параметъра a, т.е. вероятността играч 1 да използва своята чиста стратегия X] = 0. Нека създадем уравнението a-1 + (1 - a) (-1) = 0, от което a = Y 2. По този начин оптималната стратегия на играч 1 е да избере своите чисти стратегии 0 и 1 с вероятност 1 / 2 всеки. Проблемът е решен.

Най-простият случай, разработен подробно в теорията на игрите, е игра на двойки с крайна нулева сума (антагонистична игра на две лица или две коалиции). Да разгледаме игра G, в която участват двама играчи А и Б, които имат противоположни интереси: печалбата на единия е равна на загубата на другия. Тъй като печалбата на играч A е равна на печалбата на играч B с противоположен знак, можем да се интересуваме само от печалбата на играч a. Естествено, A иска да максимизира, а B иска да минимизира a.

За простота, нека мислено се идентифицираме с един от играчите (нека бъде А) и да го наречем „ние“, а играч Б „противник“ (разбира се, от това не следват реални предимства за А). Нека имаме възможни стратегии, а противникът - възможни стратегии (такава игра се нарича игра). Нека отбележим нашите печалби, ако използваме стратегията и противникът използва стратегията

Таблица 26.1

Нека приемем, че за всяка двойка стратегии печалбата (или средната печалба) a ни е известна. Тогава по принцип е възможно да се изгради правоъгълна таблица (матрица), която изброява стратегиите на играчите и съответните печалби (виж Таблица 26.1).

Ако се състави такава таблица, тогава те казват, че играта G е намалена до матрична форма (довеждането на играта до такава форма само по себе си вече може да бъде трудна задача, а понякога и почти невъзможно, поради огромното разнообразие от стратегии ). Обърнете внимание, че ако играта е намалена до матрична форма, тогава играта с много ходове всъщност се свежда до игра с един ход - от играча се изисква да направи само един ход: изберете стратегия. Ще обозначим накратко игровата матрица

Нека да разгледаме пример за играта G (4X5) в матрична форма. Имаме четири стратегии на наше разположение (от които да избираме), докато врагът има пет стратегии. Матрицата на играта е дадена в таблица 26.2

Нека помислим каква стратегия трябва да използваме ние (играч А)? В Matrix 26.2 има примамлива печалба от "10"; изкушаваме се да изберем стратегия, при която ще получим тази „лаканина“.

Но почакайте: врагът също не е глупак! Ако изберем стратегия, той, за да ни напука, ще избере стратегията и ние ще получим някаква жалка печалба „1“. Не, не можете да изберете стратегия! Как да бъдем? Очевидно, въз основа на принципа на предпазливостта (и той е основният принцип на теорията на игрите), трябва да изберем стратегията, при която нашата минимална печалба е максимална.

Таблица 26.2

Това е така нареченият „принцип на мини-максимум“: действайте по такъв начин, че при най-лошото поведение на опонента ви да получите максимална печалба.

Нека пренапишем таблица 26.2 и в дясната допълнителна колона запишем минималната печеливша стойност във всеки ред (минимален ред); нека го обозначим за линия a (виж таблица 26.3).

Таблица 26.3

От всички стойности (дясна колона) най-голямата (3) е маркирана. Стратегията съответства на това. Избирайки тази стратегия, във всеки случай можем да сме сигурни, че (при каквото и да е поведение на врага) ще спечелим не по-малко от 3. Тази стойност е нашата гарантирана победа; Държейки се внимателно, не можем да получим по-малко от това, може би ще получим повече).

Тази печалба се нарича най-ниската цена на играта (или „maximin“ – максималната от минималните печалби). Ще го обозначим като a. В нашия случай

Сега нека вземем гледната точка на врага и причината за него. Той не е някаква пешка, но е и умен! Когато избира стратегия, той би искал да даде по-малко, но трябва да разчита на нашето най-лошо поведение за него. Ако избере стратегия, ние ще му отговорим и той ще даде 10; ако той избере, ние ще му отговорим и той ще даде и т.н. Ще добавим допълнителен долен ред към таблица 26.3 и ще запишем максималните стойности на колоните в него. Очевидно един внимателен опонент трябва да избере стратегията, при която тази стойност е минимален (съответстващата стойност 5 е маркирана в Таблица 26.3) . Тази стойност P е стойността на печалбата, повече от която разумен противник със сигурност няма да ни даде. Нарича се горната цена на играта (или “mi-nimax” - минималната от максималните печалби). В нашия пример и се постига със стратегията на врага

Така че, въз основа на принципа на предпазливостта (правилото за презастраховане „винаги разчитайте на най-лошото!”), трябва да изберем стратегия А и враг - стратегия. Такива стратегии се наричат „минимакс” (следвайки принципа на минимакса). Докато и двете страни в нашия пример се придържат към своите минимаксни стратегии, печалбата ще бъде

Сега нека си представим за момент, че сме научили, че врагът следва стратегия. Хайде, да го накажем за това и да изберем стратегия, ще получим 5 и това не е толкова лошо. Но врагът също не е провал; уведомете го, че нашата стратегия е , той също ще побърза да избере, намалявайки печалбите ни до 2 и т.н. (партньорите „бързаха със стратегии“). Накратко, минимаксните стратегии в нашия пример са нестабилни по отношение на информацията за поведението на другата страна; тези стратегии нямат свойството на равновесие.

Винаги ли е така? Не винаги. Разгледайте примера с матрицата, дадена в таблица 26.4.

В този пример долната цена на играта е равна на горната цена: . Какво следва от това? Минимаксните стратегии на играчи А и Б ще бъдат стабилни. Докато и двамата играчи се придържат към тях, печалбата е 6. Нека да видим какво ще се случи, ако (A) разберем, че опонентът (B) се придържа към стратегия B?

Таблица 26.4

Но абсолютно нищо няма да се промени, защото всяко отклонение от стратегията може само да влоши положението ни. По същия начин информацията, получена от опонента, няма да го принуди да се отклони от стратегията си Двойка стратегии има свойството на равновесие (балансирана двойка стратегии) и печалбата (в нашия случай 6), постигната с тази двойка стратегии се нарича „седлова точка на матрицата“. Знак за наличието на седлова точка и балансирана двойка стратегии е равенството на долната и горната цена на играта; общата стойност се нарича цена на играта. Ще го обозначим

Стратегиите (в случая), при които се постига тази печалба, се наричат оптимални чисти стратегии, а тяхната съвкупност се нарича решение на играта. В този случай за самата игра казват, че е решена в чисти стратегии. И двете страни А и Б могат да получат своите оптимални стратегии, в които тяхната позиция е най-добрата възможна. И ако играч А спечели 6, а играч Б загуби, добре, това са условията на играта: те са полезни за А и неизгодни за Б.

Читателят може да има въпрос: защо оптималните стратегии се наричат „чисти“? Гледайки малко напред, ще отговорим на този въпрос: има „смесени“ стратегии, които се състоят в това, че играчът използва не само една стратегия, а няколко, разпръсквайки ги произволно. Така че, ако допуснем смесени стратегии в допълнение към чистите, всяка крайна игра има решение - точка на равновесие. Но това тепърва ще се обсъжда.

Наличието на седлова точка в играта далеч не е правило, а по-скоро изключение. Повечето игри нямат седлова точка. Има обаче тип игра, която винаги има седлова точка и следователно се решава в чисти стратегии. Това са така наречените „игри с пълна информация“. Игра с пълна информация е игра, в която всеки играч, с всеки личен ход, знае целия фон на своето развитие, т.е. резултатите от всички предишни ходове, както лични, така и произволни. Примери за игри с пълна информация включват: дама, шах, тик-так и др.

В теорията на игрите е доказано, че всяка игра с пълна информация има седлова точка и следователно се решава в чисти стратегии. Във всяка игра с пълна информация има двойка оптимални стратегии, които дават стабилна печалба, равна на цената на играта и. Ако такава игра се състои само от лични ходове, тогава когато всеки играч използва своята оптимална стратегия, тя трябва да завърши по много определен начин - с печалба, равна на цената на играта. Това означава, че ако решението на играта е известно, самата игра губи смисъл!

Нека вземем елементарен пример за игра с пълна информация: двама играчи последователно поставят никели на кръгла маса, произволно избирайки позицията на центъра на монетата (не се допуска взаимно припокриване на монети). Този, който постави последния никел, печели (когато няма място за други). Лесно е да се види, че изходът от тази игра по същество е предопределен. Има определена стратегия, която гарантира, че играчът, който пръв постави монетата, печели.

А именно, той трябва първо да постави никел в центъра на масата и след това да отговори на всеки ход на противника със симетричен ход. Очевидно, без значение как се държи врагът, той не може да избегне загубата. Ситуацията е абсолютно същата при шаха и игрите като цяло с пълна информация: всяка от тях, написана в матрична форма, има седлова точка, което означава, че решението е в чисти стратегии и следователно има смисъл само докато това решение не намира. Да кажем, че една шахматна партия или винаги завършва с победа на белите, или винаги с победа на черните, или винаги с равенство, но все още не знаем какво точно (за щастие на любителите на шаха). Нека добавим също: едва ли ще разберем в обозримо бъдеще, защото броят на стратегиите е толкова огромен, че е изключително трудно (ако не и невъзможно) играта да се приведе в матрична форма и да се намери седлова точка в нея.

Сега нека се запитаме какво да правим, ако играта няма седлова точка: Е, ако всеки играч е принуден да избере една единствена чиста стратегия, тогава няма какво да правим: трябва да се ръководим от принципа на минимакса. Друг е въпросът дали можете да „смесвате“ стратегиите си, да ги редувате произволно с някои вероятности. Използването на смесени стратегии се мисли по следния начин: играта се повтаря много пъти; преди всяка игра от играта, когато играчът получи личен ход, той „поверява“ избора си на случайността, „хвърля жребий“ и взема предложената стратегия (вече знаем как да организираме жребия от предишната глава ).

Смесените стратегии в теорията на игрите са модел на променлива, гъвкава тактика, когато никой от играчите не знае как ще се държи противникът в дадена игра. Тази тактика (макар и обикновено без никаква математическа обосновка) често се използва в игрите с карти. Нека отбележим в същото време, че най-добрият начин да скриете поведението си от врага е да му придадете произволен характер и следователно да не знаете предварително какво ще направите.

Така че нека поговорим за смесени стратегии. Ще обозначим смесените стратегии на играчи A и B, съответно, където (образувайки общо едно) - вероятността играч A да използва стратегии - вероятността играч B да използва стратегии

В специалния случай, когато всички вероятности с изключение на една са равни на нула, а тази е равна на единица, смесената стратегия се превръща в чиста.

Има фундаментална теорема на теорията на игрите: всяка ограничена игра с нулева сума за двама души има поне едно решение - двойка оптимални стратегии, като цяло смесени, и съответстваща цена

Двойка оптимални стратегии, които формират решение на дадена игра, има следното свойство: ако един от играчите се придържа към своята оптимална стратегия, тогава не може да бъде изгодно за другия да се отклони от неговата. Тази двойка стратегии формира определена равновесна позиция в играта: единият играч иска да превърне печалбата в максимум, другият - в минимум, всеки дърпа в своята посока и при разумно поведение и на двамата, равновесие и стабилна печалба v са установени. Ако тогава играта е от полза за нас, ако - за врага; когато играта е „честна“, еднакво изгодна и за двамата участници.

Нека разгледаме пример за игра без седлова точка и да дадем (без доказателство) нейното решение. Играта е следната: двама играчи А и Б едновременно и без да казват дума показват един, два или три пръста. Общият брой пръсти определя печалбите: ако е четен, A печели и получава от B сума, равна на това число; ако е нечетно, тогава, напротив, А плаща на Б сума, равна на това число. Какво трябва да правят играчите?

Нека създадем игрова матрица. В една игра всеки играч има три стратегии: покажете един, два или три пръста. Матрицата 3x3 е дадена в таблица 26.5; допълнителната дясна колона показва минимумите на редовете, а допълнителният долен ред показва максимумите на колоните.

По-ниската цена на играта съответства на стратегията.Това означава, че с разумно, внимателно поведение гарантираме, че няма да загубим повече от 3. Малка утеха, но все пак по-добра от, да речем, печалба от 5, открита в някои клетки на матрицата. Лошо е за нас, играч L... Но нека се утешим: позицията на врага изглежда още по-лоша: по-ниската цена на играта е. разумно поведение той ще ни даде поне 4.

Проблемът за вземане на решение, разглеждан в рамките на системния подход, съдържа три основни компонента: разграничава системата, управляващата подсистема и средата. Сега преминаваме към изследване на проблемите на вземане на решения, при които системата се влияе не от една, а от няколко управляващи подсистеми, всяка от които има свои собствени цели и възможности за действие. Този подход за вземане на решения се нарича теоретичен на игрите, а математическите модели на съответните взаимодействия се наричат игри. Поради разликите в целите на управляващите подсистеми, както и някои ограничения на възможността за обмен на информация между тях, тези взаимодействия имат конфликтен характер. Следователно всяка игра е математически модел на конфликт. Нека се ограничим до случая, когато има две управляващи подсистеми. Ако целите на системите са противоположни, конфликтът се нарича антагонистичен, а математическият модел на такъв конфликт се нарича антагонистична игра..

В терминологията на теорията на игрите се нарича 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),i=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 има формата

Изпратете добрата си работа в базата знания е лесно. Използвайте формата по-долу

Студенти, докторанти, млади учени, които използват базата от знания в обучението и работата си, ще ви бъдат много благодарни.

Въведение

1. Теоретична част

1.3 Ред на играта 2x2

1.4 Алгебричен метод

1.5 Графичен метод

1.6 Игри 2xn или mx2

1.7 Решаване на игри с помощта на матричния метод

2. Практическа част

2.2 Игри 2xn и mx2

2.3 Матричен метод

2.4 Браун метод

Анализ на резултатите

Въведение

Играта с нулева сума е игра с нулева сума. Играта с нулева сума е игра без сътрудничество, включваща двама играчи, чиито печалби са противоположни.

Формално една антагонистична игра може да бъде представена от тройка , където X и Y са наборите от стратегии на първия и втория играч, съответно, F е функцията за изплащане на първия играч, присвояваща всяка двойка стратегии (x,y), където реално число, съответстващо на полезността на първи играч в реализирането на дадена ситуация.

Тъй като интересите на играчите са противоположни, функцията F едновременно представлява загубата на втория играч.

Исторически игрите с нулева сума са първият клас математически модели на теория на игрите, с които е описан хазартът. Смята се, че тази тема на изследване е мястото, където теорията на игрите е получила името си. В наши дни антагонистичните игри се считат за част от по-широкия клас некооперативни игри.

1. Теоретична част

1.1 Основни определения и разпоредби на играта

Играта се характеризира със система от правила, които определят броя на участниците в играта, техните възможни действия и разпределението на печалбите в зависимост от тяхното поведение и резултати. За играч се счита един участник или група участници в играта, които имат общи интереси, които не съвпадат с интересите на други групи. Следователно не всеки участник се счита за играч.

Правилата или условията на играта определят възможните поведения, избори и ходове за играчите на всеки етап от развитието на играта. Да направиш избор за играч означава да избереш една от опциите му за поведение. След това играчът прави тези избори с помощта на движения. Да направите ход означава на определен етап от играта да направите целия или част от избора наведнъж, в зависимост от възможностите, предоставени от правилата на играта. Всеки играч на определен етап от играта прави ход според направения избор. Другият играч, знаейки или не за избора на първия играч, също прави ход. Всеки играч се опитва да вземе предвид информация за миналото развитие на играта, ако такава възможност е разрешена от правилата на играта.

Набор от правила, които ясно показват на играча какъв избор трябва да направи при всеки ход, в зависимост от ситуацията, която възниква в резултат на играта, се нарича стратегия на играча. Стратегията в теорията на игрите означава определен пълен план за действие на играча, показващ как той трябва да действа във всички възможни случаи на развитие на играта. Стратегия означава съвкупността от всички инструкции за всяко състояние на информацията, достъпна за играча на всеки етап от развитието на играта. От тук вече става ясно, че стратегиите могат да бъдат добри и лоши, успешни и неуспешни и т.н.

Игра с нулева сума ще бъде, когато сумата от печалбите на всички играчи във всяка от нейните игри е равна на нула, т.е. в игра с нулева сума общият капитал на всички играчи не се променя, а се преразпределя между играчите в зависимост от получените резултати. По този начин много икономически и военни ситуации могат да се разглеждат като игри с нулева сума.

По-специално, игра с нулева сума между двама играчи се нарича антагонистична, тъй като целите на играчите в нея са директно противоположни: печалбата на един играч се случва само за сметка на загубата на другия.

1.1.1 Определение, примери и решения на матрични игри в чисти стратегии

Матрична игра за двама играчи с нулева сума може да се разглежда като следната абстрактна игра за двама играчи.

Първият играч има t стратегии i =1, 2,…, t, вторият има n стратегии j = 1, 2,…, p. Всяка двойка стратегии (i, j) е свързана с число a ij, изразяващо печалбите на първия играч, дължащи се на втория играч, ако първият играч използва своята i-та стратегия, а вторият играч използва своята j-та стратегия.

Всеки играч прави един ход: първият играч избира своята i-та стратегия (i = 1, 2,..., m), вторият избира своята j-та стратегия (j = 1, 2,..., n) , след което първият играч получава печалби a ij за сметка на втория играч (ако a ij< 0, то это значит, что первый игрок платит второму сумму a ij). На этом игра заканчивается.

Всяка стратегия на играч i = 1, 2,…, t; j = 1, 2,…, n често се нарича чиста стратегия.

Матрична игра за двама играчи с нулева сума отсега нататък ще се нарича просто матрична игра. Очевидно матричната игра принадлежи към антагонистичните игри. От нейната дефиниция следва, че за да се дефинира матрична игра е достатъчно да се посочи матрица A = (a ij) от реда на печалбите на първия играч.

Ако вземем предвид матрицата на изплащането

след това играенето на всяка игра на матрична игра с матрица А се свежда до избора от първия играч на i-тия ред и втория играч на j-тата колона, като първият играч получава (за сметка на втория ) печалбите, разположени в матрица A в пресечната точка на i-тия ред и j-тата колона.

За да се формализира реална конфликтна ситуация под формата на матрична игра, е необходимо да се идентифицират и преномерират чистите стратегии на всеки играч и да се създаде матрица за изплащане.

Следващият етап е да се определят оптималните стратегии и печалби на играчите.

Основното в изучаването на игрите е концепцията за оптимални стратегии на играчите. Тази концепция интуитивно има следното значение: стратегията на играча е оптимална, ако използването на тази стратегия му осигурява най-голямата гарантирана печалба за всички възможни стратегии на другия играч. Въз основа на тези позиции, първият играч разглежда матрицата A на своите печалби, като използва формула (1.1), както следва: за всяка стойност на i (i = 1, 2,..., t) минималната стойност на печалба се определя в зависимост от стратегии, използвани от втория играч

(i = 1, 2,..., m) (1.2)

т.е. определя се минималната печалба за първия играч, при условие че той прилага своята i -та чиста стратегия, тогава от тези минимални печалби се намира стратегия i = i 0, за която тази минимална печалба ще бъде максимална, т.е.

Определение. Числото b, определено по формула (1.3), се нарича долната нетна цена на играта и показва какви минимални печалби може да гарантира за себе си първият играч, като приложи своите чисти стратегии за всички възможни действия на втория играч.

Вторият играч, с неговото оптимално поведение, трябва да се стреми, ако е възможно, чрез своите стратегии, да минимизира печалбите на първия играч. Следователно за втория играч, който намираме

т.е. максималната печалба на първия играч се определя, при условие че вторият играч прилага своята j-та чиста стратегия, тогава вторият играч намира своята j = j 1 стратегия, при която първият играч ще получи минималната печалба, т.е. намира

Определение. Числото b, определено по формула (1.5), се нарича нетна горна цена на играта и показва какви максимални печалби може да гарантира първият играч за себе си чрез своите стратегии. С други думи, прилагайки чистите си стратегии, първият играч може да осигури печалба не по-малка от b, а вторият играч, прилагайки своите чисти стратегии, може да попречи на първия играч да спечели повече от b.

Определение. Ако в игра с матрица A долната и горната нетна цена на играта съвпадат, т.е. b = c, тогава се казва, че тази игра има седлова точка в чистите стратегии и нетна цена на играта:

n = b = v (1.6)

Седловата точка е двойка чисти стратегии () съответно на първия и втория играч, при които се постига равенство

Концепцията за седлова точка има следното значение: ако един от играчите се придържа към стратегия, съответстваща на седлова точка, тогава другият играч не може да се справи по-добре от това да се придържа към стратегия, съответстваща на седлова точка. Имайки предвид, че най-доброто поведение на даден играч не трябва да води до намаляване на печалбите му, а най-лошото поведение може да доведе до намаляване на печалбите му, тези условия могат да бъдат записани математически под формата на следните отношения:

където i, j са всякакви чисти стратегии съответно на първия и втория играч; (i 0 , j 0) са стратегии, които образуват седлова точка. По-долу ще покажем, че определението за седлова точка е еквивалентно на условия (1.8).

Така, въз основа на (1.8), седловият елемент е минимален в i 0-ия ред и максимален в j 0-та колона в матрица A. Намирането на седловата точка на матрица A е лесно: в матрица A минималният елемент се намира последователно в всеки ред и проверете дали този елемент е максималният в неговата колона. Ако е такъв, то той е седловиден елемент, а двойката стратегии, съответстваща на него, образува седлова точка. Двойка чисти стратегии (i 0 , j 0) на първия и втория играч, образуващи седлова точка и седлов елемент, се нарича решение на играта.

Чистите стратегии i 0 и j 0, образуващи седлова точка, се наричат оптимални чисти стратегии съответно на първия и втория играч.

Теорема 1. Нека f (x, y) е реална функция на две променливи x A и y B и съществува

тогава b = c.

Доказателство. От определението за минимум и максимум следва, че

Тъй като от лявата страна на (1.11) x е произволно, тогава

Следователно от дясната страна на неравенството (1.12) y е произволно

Q.E.D.

По-специално, матрицата () е специален случай на функцията f (x, y), т.е. ако поставим x = i, y = j, = f (x, y), тогава от теорема 1 получаваме, че долната мрежа цената не надвишава горната нетна цена на играта в матричната игра.

Определение. Нека f (x, y) е реална функция на две променливи x A и y B. Точката (x 0, y 0) се нарича седлова точка за функцията f (x, y), ако са изпълнени следните неравенства

f (x, y 0) f (x 0, y 0)f (x 0, y) (1.14)

за всякакви x A и y B.

1.2 Оптимални смесени стратегии и техните свойства

Изучаването на матрична игра започва с намирането на нейната седлова точка в чистите стратегии. Ако една матрична игра има седлова точка в чистите стратегии, тогава изучаването на играта завършва с намирането на тази точка. Ако в една матрична игра няма седлова точка в чистите стратегии, тогава можете да намерите долната и горната нетни цени на тази игра, които показват, че първият играч не трябва да се надява да спечели повече от горната цена на играта и може бъдете сигурни, че ще спечелите не по-ниска цена от играта. Подобни препоръки относно поведението на играчите в матрична игра без седлова точка в чистите стратегии не могат да задоволят изследователите и практиците. Подобряването на решенията на матричните игри трябва да се търси в използването на тайната на използването на чисти стратегии и възможността за многократно повтаряне на игри под формата на игри. Така например се играят поредица от игри на шах, дама и футбол и всеки път играчите прилагат стратегиите си по такъв начин, че опонентите им нямат представа за тяхното съдържание, и по този начин средно те постигнете определени печалби, като изиграете цялата поредица от игри. Тези печалби са средно по-големи от долната цена на играта и по-малки от горната цена на играта. Колкото по-висока е тази средна стойност, толкова по-добра стратегия използва играчът. Ето защо възникна идеята да се прилагат чисти стратегии на случаен принцип, с известна вероятност. Това напълно гарантира тайната на тяхното използване. Всеки играч може да промени вероятностите за използване на своите чисти стратегии по такъв начин, че да увеличи максимално средната си печалба и да получи оптимални стратегии по пътя. Тази идея доведе до концепцията за смесена стратегия.

Определение. Смесената стратегия на играча е пълният набор от вероятности за използване на неговите чисти стратегии.

Така, ако първият играч има m чисти стратегии 1, 2, … i, … m, тогава неговата смесена стратегия x е набор от числа x = (x 1, x 2, ..., x i,…, x m ), удовлетворяващи отношенията

x i 0 (i = 1, 2, ... , t), = 1. (1.15)

По същия начин, за втория играч, който има n чисти стратегии, смесена стратегия y е набор от числа y = (y 1, ..., y j, ... y n), удовлетворяващи отношенията

y j 0 (j = 1, 2, ... , n), = 1. (1.16)

Тъй като всеки път, когато играч използва една чиста стратегия, това изключва използването на друга, чистите стратегии са несъвместими събития. Освен това те са единствените възможни събития.

Очевидно чистата стратегия е частен случай на смесена стратегия. Наистина, ако в смесена стратегия която и да е i-та чиста стратегия се приложи с вероятност единица, тогава всички други чисти стратегии не се прилагат. И тази i-та чиста стратегия е частен случай на смесена стратегия. За да запази тайната, всеки играч прилага свои собствени стратегии, независимо от избора на другия играч.

Определение. Средната печалба на първия играч в матрична игра с матрица А се изразява като математическото очакване на неговите печалби

E (A, x, y) = (1.20)

Очевидно средната печалба на първия играч е функция на два набора от променливи x и y. Първият играч се стреми, като променя своите смесени стратегии x, да максимизира средната си печалба E (A, x, y), а вторият играч, чрез своите смесени стратегии, се стреми да направи E (A, x, y) минимално, т.е. За решаване на играта е необходимо да се намерят такива x, y, при които се постига горната цена на играта.

1.3 Игра от ред 22

Матрична игра от порядък 22 се дава от следната матрица на изплащане за първия играч:

Решението на тази игра трябва да започне с намиране на седловина в чистите стратегии. За да направите това, намерете минималния елемент в първия ред и проверете дали е максималният в неговата колона. Ако такъв елемент не бъде намерен, тогава вторият ред се проверява по същия начин. Ако такъв елемент се намери във втория ред, тогава това е седло.

Намирането на седловия елемент, ако има такъв, завършва процеса на намиране на решението му, тъй като в този случай е намерена цената на играта - седловия елемент и седловата точка, т.е. двойка чисти стратегии за първата и втори играч, съставляващи оптимални чисти стратегии. Ако в чистите стратегии няма седлова точка, тогава трябва да намерим седлова точка в смесените стратегии, която задължително съществува според основната теорема на матричните игри.

Нека означим с x = (x 1 , x 2), y = (y 1 , y 2) смесените стратегии съответно на първия и втория играч. Спомнете си, че x 1 означава вероятността първият играч да използва първата си стратегия, а x 2 = 1 - x 1 е вероятността той да използва втората си стратегия. По същия начин за втория играч: 1 е вероятността той да използва първата стратегия, 2 = 1 - 1 е вероятността той да използва втората стратегия.

Съгласно следствието от теоремата, за да бъдат оптимални смесените стратегии x и y, е необходимо и достатъчно за неотрицателни x 1, x 2, y 1, y 2 да са изпълнени следните отношения:

Нека сега покажем, че ако една матрична игра няма седлова точка в чистите стратегии, тогава тези неравенства трябва да се превърнат в равенства:

Наистина. Нека играта няма седлова точка в чистите стратегии, тогава оптималните стойности на смесените стратегии удовлетворяват неравенствата

0<<1, 0<< 1,

0< <1, 01. (1.25)

Да приемем, че и двете неравенства от (1.22) са строги

тогава, съгласно теоремата, y 1 = y 2 = 0, което противоречи на условия (1.25).

По подобен начин се доказва, че и двете неравенства от (1.23) не могат да бъдат строги неравенства.

Нека сега приемем, че едно от неравенствата (1.22) може да бъде строго, например първото

Това означава, че според теоремата y 1 = 0, y 2 = 1. Следователно от (1.23) получаваме

Ако и двете неравенства (1.24) са строги, тогава, съгласно теоремата, x 1 = x 2 = 0, което противоречи на (1.25). Ако a 12 е 22, тогава едно от неравенствата (1.27) е строго, а другото е равенство. Освен това, равенството ще се запази за по-големия елемент от 12 и 22, т.е. едно неравенство от (1.27) трябва да е строго. Например 12< а 22 . Тогда справедливо а 12 < v, а это равносильно тому, что первое неравенство из (1.24) строгое. Тогда согласно теореме должно х 1 = 0, что противоречит условию (1.25). Если а 12 = а 22 , то оба неравенства (1.27) превращаются в равенства и тогда можно положить х 1 = 0, что противоречит (1.25). Итак, предположение о том, что первое неравенство из (1.22) может быть строгим, не справедливо. Аналогично можно показать, что второе неравенство из (1.22) также не может быть строгим.

По този начин се показва, че ако една матрична игра няма седлова точка в чистите стратегии, тогава за оптималните стратегии на първия играч неравенствата (1.22) се превръщат в равенства. Подобни разсъждения по отношение на неравенствата (1.23) ще доведат до факта, че в този случай неравенствата (1.23) трябва да бъдат равенства.

Така че, ако матрична игра от порядък 22 няма седлова точка, тогава оптималните смесени стратегии на играчите и цената на играта могат да бъдат определени чрез решаване на системата от уравнения (1.24). Установено е също, че ако в матрична игра от порядък 2x2 един от играчите има оптимална чиста стратегия, то другият играч също има оптимална чиста стратегия.

Следователно, ако една матрична игра няма седлова точка в чистите стратегии, тогава тя трябва да има решение в смесените стратегии, които се определят от уравнения (1.24). Решение на система (1.25)

1.4 Алгебричен метод

Има два възможни случая за решаване на проблеми с помощта на алгебричния метод:

1. матрицата има седлова точка;

2. матрицата няма седлова точка.

В първия случай решението е двойка стратегии, които формират седловината на играта. Да разгледаме втория случай. Решенията тук трябва да се търсят в смесени стратегии:

Да намерим стратегии и... Когато първият играч използва своята оптимална стратегия, вторият играч може например да приложи две такива чисти стратегии

Освен това, поради свойството, ако единият от играчите използва оптимална смесена стратегия, а другият използва всяка чиста стратегия, включена в неговата оптимална смесена стратегия с вероятност, неравна на нула, тогава математическото очакване за печалба винаги остава непроменено и равно към цената на играта, т.е.

Печалбите във всеки от тези случаи трябва да са равни на цената на играта V. В този случай са валидни следните отношения:

Система от уравнения, подобна на (2.5), (2.6), може да бъде конструирана за оптималната стратегия на втория играч:

Като се вземе предвид условието за нормализиране:

Нека решим уравнението (1.37) - (1.41) заедно по отношение на неизвестните, можем да решим не всички наведнъж, а три наведнъж: отделно (1.36), (1.38), (1.40) и (1.37), ( 1.39), (1.41). В резултат на решението получаваме:

1.5 Графичен метод

Приблизителното решение на игра 22 може да се получи доста просто с помощта на графичния метод. Същността му е следната:

Фигура 1.1 - намиране на участък с единична дължина

Изберете част от единична дължина на оста x. Левият му край ще изобразява първата стратегия на първия играч, а десният ще представлява втората. Всички междинни точки съответстват на смесени стратегии на първия играч, а дължината на сегмента вдясно от точката е равна на вероятността да се използва първата стратегия, а дължината на сегмента вляво от е вероятността да се използва втората стратегия от първия играч.

Начертани са две оси I-I и II-II. Ще поставим печалбите на I-I, когато първият играч използва първата стратегия, на II-II, когато използва втората стратегия. Нека, например, вторият играч приложи първата си стратегия, тогава стойността трябва да бъде нанесена по оста I-I, а стойността трябва да бъде нанесена по оста II-II

За всяка смесена стратегия на първия играч, неговата печалба ще се определя от стойността на сегмента. Линия I-I съответства на прилагането на първата стратегия от втория играч; ще я наречем първа стратегия на втория играч. По същия начин можете да конструирате втората стратегия на втория играч. Тогава, като цяло, графичният дисплей на матрицата на играта ще приеме следната форма:

Фигура 1.2 - намиране на цената на играта

Трябва да се отбележи обаче, че тази конструкция е извършена за първия играч. Тук дължината на сегмента е равна на цената на играта V.

Линията 1N2 се нарича долна граница на печалба. Тук можете ясно да видите, че точка N съответства на максималната сума на гарантираната печалба на първия играч.

Най-общо казано, стратегията на втория играч също може да се определи от тази фигура, например по следните начини. По оста I-I:

или по ос II-II

Стратегията на втория играч обаче може да се определи подобно на начина, по който се прави за първия играч, т.е. изградете такава графика.

Фигура 1.3 - определяне на стратегията на втория играч

Тук линия 1N2 е горната граница на загубата. Точка N съответства на минималната възможна загуба на втория играч и определя стратегията.

В зависимост от конкретните стойности на коефициентите на матрицата, графиките могат да имат различна форма, например това:

Фигура 1.4 - определя оптималната стратегия на първия играч

В такава ситуация оптималната стратегия на първия играч е чиста:

1.6 Игри 2n или m2

В игри от порядък 2n първият играч има 2 чисти стратегии, а вторият играч има n чисти стратегии, т.е. Матрицата на печалбите на първия играч има формата:

Ако такава игра има седлова точка, тогава е лесно да я намерите и да получите решение.

Да приемем, че играта има седлови точки. Тогава е необходимо да се намерят такива смесени стратегии и съответно първи и втори играч и цена на играта v, които да удовлетворяват отношенията:

Тъй като играта няма седлова точка, неравенството (1.54) се заменя с неравенствата

За решаване на системи (1.56), (1.55), (1.53) е препоръчително да се използва графичният метод. За тази цел въвеждаме обозначение за лявата страна на неравенството (1.53)

матрична игра математически модел

или, извеждайки от (1.55) и извършвайки прости трансформации, получаваме

където е средната печалба на първия играч, при условие че той използва смесената си стратегия, а вторият играч - своята j-та чиста стратегия.

Съгласно израза всяка стойност j=1, 2, …, n съответства на права линия в правоъгълна координатна система.

Целта на втория играч е да минимизира печалбите на първия играч, като избира неговите стратегии. Затова изчисляваме

където е долната граница на набора от ограничения. На фигура 1.6 графиката на функцията е показана с дебела линия.

Публикувано на http://www.allbest.ru/

Фигура 1.6 - графика на функцията

Целта на първия играч е да максимизира своите печалби чрез избор, т.е. изчисли

На фигура 1.6 точката означава максималната стойност, която се получава при. Цената на играта е защото:

По този начин графично се определят оптималната смесена стратегия на първия играч и двойка чисти стратегии на втория играч, които в пресечната точка образуват точка.Фигура 1.6 показва 2-ра и 3-та стратегии на втория играч. За такива стратегии неравенствата (1.53) се превръщат в равенства. На фигура 1.6 това са стратегии j=2, j=3.

Сега можем да решим системата от уравнения

и точно определяне на стойностите на и (графично те се определят приблизително). След това, поставяйки всички стойности за тези j, за които те не образуват точка, решавайки системата от уравнения (1.56) За примера, показан на фигура 1.6, това е следната система:

и останалите. Тази система може да бъде решена чрез наклон. Ако за някои j=j 0 стратегиите на втория играч образуват точка M 0 и тогава максималната стойност на долната граница на наборите от ограничения е изобразена от сегмент, успореден на ос В този случай първият играч има безкрайно много оптимални стойности и цената на играта. Този случай е изобразен на фигура 1.7, където сегментът MN изобразява горните граници, оптималните стойности са в границите Вторият играч има чиста оптимална стратегия j=j 0 .

Матрични игри от порядък m2 също могат да бъдат решени с помощта на графичния метод. Матрицата на печалбите на първия играч в този случай има формата

Смесените стратегии на първия и втория играч, съответно, се дефинират подобно на игрите от ред 2n. Нека стойността от 0 до 1 бъде нанесена по хоризонталната ос, а стойността на средната печалба) на първия играч по вертикалната ос, при условията, че първият играч прилага своята чиста i-та стратегия (i=1, 2, ..., m), вторият - неговата смесена стратегия (y 1, 1- y 1) =y. Например, когато m=4 графично) може да се представи, както е показано на фигура 1.7.

Фигура 1.7 - функционална графика)

Първият играч се опитва да максимизира средната си печалба, така че се стреми да намери

Функцията е представена с дебела линия и представлява горната граница на набор от ограничения. Вторият играч се опитва да минимизира, като избира своята стратегия, т.е. стойност съответства

На фигурата стойността е обозначена с точка. С други думи, двете стратегии на първия играч и вероятността за втория играч се определят, при които се постига равенство

От фигурата виждаме, че цената на играта е ординатата на точката, вероятността е абсцисата на точката. За останалите чисти стратегии на първия играч в оптималната смесена стратегия трябва ().

Така, решавайки система (1.69), получаваме оптималната стратегия на втория играч и цената на играта. Ние намираме оптималната смесена стратегия за първия играч, като решаваме следната система от уравнения:

1.7 Матричен метод за решаване на игри

Обозначения:

Всякаква квадратна подматрица на подредната матрица

Матрица (1);

Матрица, транспонирана към;

Матрица, свързана с B;

- (1) матрица, получена от X чрез изтриване на елементи, които съответстват на редовете, изтрити от при получаване;

- (1) матрица, получена чрез изтриване на елементи, които съответстват на редовете, изтрити от при получаване.

Алгоритъм:

1. Изберете квадратна подматрица на матрицата от ред () и изчислете

2. Ако има или, изхвърлете намерената матрица и опитайте друга матрица.

3. Ако (), (), изчисляваме и конструираме X и от и, добавяйки нули на подходящи места.

Проверка дали неравенствата са изпълнени

за всеки (1.75)

и неравенства

за всеки (1.76)

Ако една от връзките не е удовлетворена, тогава опитваме друга. Ако всички отношения са валидни, тогава X и необходимите решения.

1.8 Метод на последователно приближаване на цената на играта

При изучаване на игрови ситуации често може да се случи, че няма нужда да се получи точно решение на играта или по някаква причина е невъзможно или много трудно да се намери точната стойност на цената на играта и оптималните смесени стратегии. След това можете да използвате приблизителни методи за решаване на матрична игра.

Нека опишем един от тези методи - методът за последователно приближаване на цената на една игра. Броят, изчислен при използване на метода, нараства приблизително пропорционално на броя на редовете и колоните на матрицата на изплащане.

Същността на метода е следната: играта се играе мислено много пъти, т.е. последователно, във всяка игра играчът избира стратегията, която му дава най-големите общи (общи) печалби.

След такова изпълнение на някои игри се изчислява средната стойност на печалбите на първия играч и загубите на втория играч, като средноаритметичното им се приема като приблизителна стойност на цената на играта. Методът позволява да се намери приблизителната стойност на оптималните смесени стратегии на двамата играчи: необходимо е да се изчисли честотата на прилагане на всяка чиста стратегия и да се вземе като приблизителна стойност в оптималната смесена стратегия на съответния играч.

Може да се докаже, че с неограничено увеличаване на броя на програмните игри, средната печалба на първия играч и средната загуба на втория играч ще се доближат за неопределено време до цената на играта, а приблизителните стойности на смесените стратегии в случаят, когато играта има уникално решение, ще има тенденция към оптималните смесени стратегии на всеки играч. Най-общо казано, тенденцията на приблизителните стойности над тези стойности да се доближат до истинските стойности е бавна. Въпреки това, този процес е лесен за механизиране и по този начин помага да се получи решение на играта с необходимата степен на точност дори с матрици на изплащане от относително голям порядък.

2. Практическа част

Двойката решава къде да отиде на разходка и да прекара времето си полезно и за двамата.

Момичето решава да се разходи в парка, за да подиша чист въздух, а вечерта да гледа филм в най-близкото кино.

Човекът предлага да отидете в технологичния парк и след това да гледате мач на футболисти от местния клуб на централния стадион.

В съответствие с това трябва да разберете колко време ще отнеме за постигане на целта на един от играчите. Печелившата матрица ще изглежда така:

Таблица 1. Матрица на изплащане

Стратегии

От 1 2 , Очевидно тази игра няма седлова точка в чистите стратегии. Затова използваме следните формули и получаваме:

Публикувано на http://www.allbest.ru/

2.2 Игра 2xn и mx2

Задача 1(2xn)

Отглеждат се две зърнени култури за сух и влажен климат.

А природното състояние може да се разглежда като: сухо, влажно, умерено.

Публикувано на http://www.allbest.ru/

Максималната стойност на M() се постига в точка M, образувана от пресечната точка на линии, съответстващи на j=1, j"=2. Според това приемаме:

Задача 2(mx2)

Момче и момиче обмислят варианти къде да отидат за уикенда.

Изборът на място за почивка може да се разглежда като: парк, кино, ресторант.

Публикувано на http://www.allbest.ru/

Максималната стойност на M() се постига в точка E, образувана от пресечната точка на линии, съответстващи на j=1, j"=2. Според това приемаме:

За да се определи стойността на v, трябва да се решат следните уравнения:

2.5 Матричен метод

Два ресторанта (заведения за обществено хранене), конкуриращи се помежду си, предоставят следните набори от услуги. Първият ресторант се намира в центъра, а другият в покрайнините на града.

Централният ресторант включва следните услуги:

1) по-скъпо и висококачествено обслужване на клиентите;

2) ястията са насочени към френската кухня;

Вторият ресторант предлага:

1) евтино и висококачествено обслужване;

2) менюто съчетава различни известни кухни на света;

3) също постоянни промоции и отстъпки;

4) доставя и приема поръчки за доставка до дома.

В съответствие със задачата печалбата за един ден между два ресторанта ще се разпредели както следва:

Таблица 2. Матрица на изплащане

Стратегии

Решаване на игра от вида с помощта на матричен метод:

Има шест подматрици и:

Помислете за матрицата:

x 1 = ? 0, x 2 = ? 0

Тъй като x 2 =< 0, то мы отбрасываем.