Матрични игри: примери за решаване на проблеми. Антагонистични игри с непрекъснати стратегии b) не винаги

Въведение

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

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

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

· Според вида на функциите печалбите от играта се делят на матрица (е ограничена игра с нулева сума за двама играчи, в която се дава печалбата на играча Апод формата на матрица (един ред от матрицата съответства на номера на използваната стратегия на играча IN, колона – номерът на използваната стратегия на играча IN; в пресечната точка на реда и колоната на матрицата е печалбата на играча А, съответстващи на прилаганите стратегии.

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

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

Възможни са и други подходи за разделяне на игрите. Сега да се върнем директно към темата на изследването, а именно теорията на игрите. Първо, нека дефинираме това понятие.

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

Целта на теорията е, че:

1) оптимално поведение в играта.

2) изследване на свойствата на оптималното поведение

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

4) изграждане на числени методи за намиране на оптимално поведение.

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

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

Математическата концепция на играта е необичайно широка. Той включва така наречените салонни игри (включително шах, дама, GO, игри с карти, домино), но може да се използва и за описание на модели на икономическа система с множество купувачи и продавачи, конкуриращи се помежду си. Без да навлизаме в подробности, една игра може да се дефинира широко като ситуация, в която един или повече индивиди („играчи“) съвместно контролират редица променливи и всеки играч трябва да вземе предвид действията на цялата група, когато взема решение. „Заплащането“, което се пада на всеки играч, се определя не само от неговите собствени действия, но и от действията на останалите членове на групата. Някои от „ходовете“ (индивидуални действия) по време на играта може да са произволни. Ясна илюстрация е известната игра на покер: първоначалното раздаване на карти е произволен ход. Последователността от залози и контразалози, предшестващи финалното сравнение на взятките, се формира от останалите ходове в играта.

Математическата ТЕОРИЯ НА ИГРИТЕ започва с анализ на спортове, игри с карти и други игри. Казват, че откривателят на теорията на игрите, изключителен американски математик от 20 век. Джон фон Нойман дойде с идеите за своята теория, докато гледаше игра на покер. Оттук идва и името „теория на игрите“.

Нека започнем да изследваме тази тема с ретроспективен анализ на развитието на теорията на игрите.Нека разгледаме историята и развитието на въпроса за теорията на игрите. Обикновено „родословното дърво“ се представя като дърво в смисъла на теорията на графите, в което разклонението възниква от някакъв единичен „корен“. Родословието на теорията на игрите е книга от Й. фон Нойман и О. Моргенщерн. Следователно историческият ход на развитието на теорията на игрите като математическа дисциплина естествено се разделя на три етапа:

Първи етап- преди публикуването на монографията на Й. фон Нойман и О. Моргенщерн. Може да се нарече „предмонографски“. На този етап играта все още действа като специфично състезание, описано от нейните правила със смислени термини. Едва в края й J. von Neumann развива идеята за играта като общ модел на абстрактен конфликт. Резултатът от този етап беше натрупването на редица специфични математически резултати и дори отделни принципи на бъдещата теория на игрите.

Втора фазае самата монография на Й. фон Нойман и

О. Моргенщерн „Теория на игрите и икономическо поведение“ (1944 г.), който комбинира повечето от получените по-рано (но по съвременните математически стандарти, доста малко) резултати. Тя е първата, която представя математически подход към игрите (както в конкретния, така и в абстрактния смисъл на думата) под формата на систематична теория.

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

Въпреки това дори математическата теория на игрите не е в състояние напълно да предвиди изхода от някои конфликти. Изглежда възможно да се идентифицират три основни причини за несигурността на резултата от играта (конфликт).

Първо, това са игри, в които има реална възможност да се изследват всички или поне повечето варианти на игрово поведение, от които един е най-верният, водещ до печалба. Несигурността се причинява от значителен брой опции, така че не винаги е възможно да се проучат абсолютно всички опции (например японската игра GO, руски и международни пулове, британски reversi).

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

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

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

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

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

Въведение

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-та чиста стратегия е частен случай на смесена стратегия. За да запази тайната, всеки играч прилага свои собствени стратегии, независимо от избора на другия играч.

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

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, то мы отбрасываем.