От теорията на игрите е известно, че ако играч "А" използва оптималната си стратегия, а играч "Б" остане в рамките на своите активни стратегии, тогава средната печалба остава непроменена и е равна на цената на играта. vнезависимо от това как играч "B" използва активните си стратегии. И в нашия случай и двете стратегии са активни, иначе играта би имала решение в чисти стратегии. Следователно, ако приемем, че играч „B“ ще използва чиста стратегия B 1, тогава средната печалба vще бъде:

k 11 p 1 + k 21 p 2 = v (1)

Където: к ij - елементи на платежната матрица.

От друга страна, ако приемем, че играч „B“ ще използва чиста стратегия B 2, тогава средната печалба ще бъде:

k 12 p 1 + k 22 p 2 = v (2)

Приравнявайки левите части на уравнения (1) и (2), получаваме:

k 11 p 1 + k 21 p 2 = k 12 p 1 + k 22 p 2

И като се има предвид факта, че стр 1 + стр 2 = 1 ние имаме:

k 11 p 1 + k 21 (1 - p 1 ) = k 12 p 1 + k 22 (1 - p 1 )

В тази задача:

От теорията на игрите е известно, че ако играч "Б" използва оптималната си стратегия, а играч "А" остане в рамките на своите активни стратегии, тогава средната печалба остава непроменена и е равна на цената на играта. vнезависимо как играч А използва своите активни стратегии. Следователно, ако приемем, че играч „A“ ще използва чиста стратегия A 1, тогава средната печалба vще бъде:

k 11 q 1 + k 12 q 2 = v (4)

В тази задача:

Отговор:

Геометрична интерпретация (графично решение):

Снимка 1.
Графика на изплащане к от честотата стр. 2 , когато врагът използва стратегията Б 1.

Нека сега приемем, че играч „B“ ще използва стратегия B 2 в нейната чиста форма. След това, ако ние (играч „А“) използваме чиста стратегия A 1, тогава нашата печалба ще бъде 5. Ако използваме чиста стратегия A 2, тогава нашата печалба ще бъде 3/2 (виж Фиг. 2). По същия начин, ако смесим стратегии A 1 и A 2 в различни пропорции, печалбите ни ще се променят по права линия, минаваща през точките с координати (0, 5) и (1, 3/2), нека я наречем линия на стратегия Б 2. Както и в предишния случай, абсцисата на която и да е точка от тази линия е равна на вероятността, с която прилагаме стратегия A 2, а ординатата е получената печалба, но само за стратегия B 2 (виж фиг. 2).

Фигура 2.
v и оптимална честота стр. 2 за играча "А".

В реална игра, когато разумен играч „B“ използва всичките си стратегии, печалбите ни ще се променят по линията, показана на фиг. 2 в червено. Тази линия определя т.нар долна граница на печалбата. Очевидно най-високата точка на тази прекъсната линия съответства на нашата оптимална стратегия. В този случай това е точката на пресичане на линиите на стратегии B 1 и B 2. Моля, имайте предвид, че ако изберете честота стр 2 равно на неговата абциса, тогава нашата печалба ще остане непроменена и равна v за всяка стратегия на играч „Б“, в допълнение, това ще бъде максимумът, който можем да си гарантираме. Честота (вероятност) стр 2 , в този случай, е съответната честота на нашата оптимална смесена стратегия. Между другото, от фигура 2 можете да видите честотата стр 1 , нашата оптимална смесена стратегия, е дължината на сегмента [ стр 2 ; 1] по оста x. (Това е защото стр 1 + стр 2 = 1 )

Използвайки напълно подобни разсъждения, можем да намерим честотите на оптималната стратегия за играч „B“, която е илюстрирана на фигура 3.

Фигура 3.
Графично определяне на цената на играта v и оптимална честота р 2 за играча "IN".

Само за него трябва т.нар горна граница на загуба(червена прекъсната линия) и потърсете най-ниската точка на нея, т.к за играч "Б" целта е да минимизира загубите. Същата честотна стойност р 1 , това е дължината на сегмента [ р 2 ; 1] по оста x.

Секцията "Теория на игрите" е представена от три онлайн калкулатори:

1. Оптимални стратегии на играчите. При такива проблеми се посочва матрица за плащане. Изисква се да се намерят чисти или смесени стратегии на играчи и, цена на играта. За да решите, трябва да посочите размерността на матрицата и метода на решение. Услугата прилага следните методи за решаване на игра за двама играчи:
   1. Минимакс. Ако трябва да намерите чистата стратегия на играчите или да отговорите на въпрос относно седловата точка на дадена игра, изберете този метод на решение.
   2. Симплексен метод. Използва се за решаване на смесени стратегически игри с помощта на методи за линейно програмиране.
   3. Графичен метод. Използва се за решаване на смесени стратегически игри. Ако има седлова точка, решението спира. Пример: Дадена е матрица на изплащане, намерете оптималните смесени стратегии на играчите и цената на играта, като използвате графичния метод за решаване на играта.
   4. Итеративен метод на Браун-Робинсън. Итеративният метод се използва, когато графичният метод е неприложим и когато алгебричните и матричните методи са практически неприложими. Този метод дава приблизителна стойност на цената на играта, като истинската стойност може да бъде получена с всяка желана степен на точност. Този метод не е достатъчен за намиране на оптимални стратегии, но ви позволява да проследявате динамиката на походова игра и да определяте цената на играта за всеки играч на всяка стъпка.
   Например, задачата може да звучи като „посочете оптималните стратегии на играчите за играта, дадени от матрицата на изплащане“.
   Всички методи използват проверка за доминиращи редове и колони.
2. Биматрична игра. Обикновено в такава игра се задават две матрици с еднакъв размер на печалбите на първия и втория играч. Редовете на тези матрици съответстват на стратегиите на първия играч, а колоните на матриците съответстват на стратегиите на втория играч. В този случай първата матрица представлява печалбите на първия играч, а втората матрица представлява печалбите на втория.
3. Игри с природата. Използва се, когато е необходимо да се избере управленско решение по критериите на Maximax, Bayes, Laplace, Wald, Savage, Hurwitz.
   За критерия на Bayes също ще е необходимо да се въведат вероятностите за настъпване на събития. Ако не са посочени, оставете стойностите по подразбиране (ще има еквивалентни събития).
   За критерия на Хурвиц посочете нивото на оптимизъм λ. Ако този параметър не е посочен в условията, можете да използвате стойностите 0, 0,5 и 1.

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

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

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

Из историята на теорията на игрите

История на теорията на игрите като самостоятелна дисциплина започва през 1944 г., когато Джон фон Нойман и Оскар Моргенщерн публикуват книгата „Теорията на игрите и икономическото поведение“. Въпреки че примери за теория на игрите са били срещани и преди: трактатът на Вавилонския Талмуд за разделянето на имуществото на починал съпруг между неговите съпруги, игрите на карти през 18 век, развитието на теорията на шаха в началото на 20 век век, доказателството на минимаксната теорема на същия Джон фон Нойман през 1928 г., без която не би имало теория на игрите.

През 50-те години на 20 век Мелвин Дрешър и Мерил Флъд от Корпорация РандДжон Наш, първият, който експериментално приложи дилемата на затворника, разви концепцията за равновесието на Наш в своите трудове върху състоянието на равновесие в игрите на двама.

Райнхард Салтен публикува книгата „Третирането на олигопола в теорията на игрите при поискване“ („Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit“) през 1965 г., с която приложението на теорията на игрите в икономиката получава нова движеща сила. Стъпка напред в еволюцията на теорията на игрите се свързва с работата на Джон Мейнард Смит „Еволюционна стабилна стратегия“ (1974). Дилемата на затворника е популяризирана в книгата на Робърт Акселрод от 1984 г. „Еволюцията на сътрудничеството“. През 1994 г. Джон Неш, Джон Харсани и Райнхард Зелтен бяха удостоени с Нобелова награда за техния принос в теорията на игрите.

Теорията на игрите в живота и бизнеса

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

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

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

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

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

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

Математически модел в теорията на игрите и формализация на проблемите

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

1. заинтересовани лица;
2. възможни действия от всяка страна;
3. интересите на страните.

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

Реална конфликтна ситуация не винаги е, но играта (в концепцията на теорията на игрите) винаги протича според определени правила , които точно определят:

1. опции за действия на играчите;
2. количеството информация, която всеки играч има за поведението на своя партньор;
3. печалбата, до която води всеки набор от действия.

Примери за формализирани игри включват футбол, игри с карти и шах.

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

Играта се характеризира с несигурност на изхода . Причините за несигурност могат да бъдат разделени на следните групи:

1. комбинаторни (както в шаха);
2. влиянието на случайни фактори (както в играта "глави или опашки", зарове, игри с карти);
3. стратегически (играчът не знае какво действие ще предприеме врагът).

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

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

Класификация на игрите

1. Класиране по брой играчи (игра на двама или повече лица). Игрите за двама заемат централно място в цялата теория на игрите. Основната концепция на теорията на игрите за игри с двама е обобщение на много важната идея за равновесие, която естествено се появява в игрите с двама. Що се отнася до игрите ниндивиди, тогава една част от теорията на игрите е посветена на игри, в които сътрудничеството между играчите е забранено. В друга част от теорията на игрите ниндивидите приемат, че играчите могат да си сътрудничат за взаимна изгода (вижте по-нататък в този параграф за некооперативните и кооперативните игри).
2. Класификация по брой играчи и техните стратегии (броят на стратегиите е най-малко две, може да бъде безкрайност).
3. Класификация по количество информация спрямо минали ходове: игри с пълна информация и непълна информация. Нека има играч 1 - купувач и играч 2 - продавач. Ако играч 1 няма пълна информация за действията на играч 2, тогава играч 1 може да не прави разлика между двете алтернативи, между които трябва да направи избор. Например, избор между два вида на някакъв продукт и не знаейки, че според някои характеристики, продуктът Апо-лош продукт б, играч 1 може да не види разликата между алтернативите.
4. Класиране според принципите на разделяне на печалбите : кооперативни, коалиционни от една страна и некооперативни, некоалиционни от друга страна. IN некооперативна игра , или иначе - некооперативна игра , играчите избират стратегии едновременно, без да знаят коя стратегия ще избере вторият играч. Комуникацията между играчите е невъзможна. IN кооперативна игра , или иначе - коалиционна игра , играчите могат да формират коалиции и да предприемат колективни действия, за да увеличат своите печалби.
5. Крайна игра с нулева сума за двама или антагонистична игра е стратегическа игра с пълна информация, която включва страни с противоположни интереси. Антагонистичните игри са матрични игри.

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

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

Ако тази стратегическа задача се формулира като заключение, тя се свежда до следното:

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

Примери за използване на математически инструменти на теорията на игрите

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

Пример за формализиране на некооперативна (некооперативна) игра на двама души

В предишния параграф вече разгледахме пример за некооперативна (некооперативна) игра (дилема на затворника). Нека засилим уменията си. За това е подходящ и класически сюжет, вдъхновен от „Приключенията на Шерлок Холмс” на Артър Конан Дойл. Може, разбира се, да се възрази: примерът не е от живота, а от литературата, но Конан Дойл не се е утвърдил като писател на научна фантастика! Класически и защото задачата е изпълнена от Оскар Моргенщерн, както вече установихме, един от основоположниците на теорията на игрите.

Пример 1.Ще бъде дадено съкратено резюме на фрагмент от едно от „Приключенията на Шерлок Холмс“. Съгласно добре познатите концепции на теорията на игрите, създайте модел на конфликтна ситуация и формално запишете играта.

Шерлок Холмс възнамерява да пътува от Лондон до Дувър с по-нататъшната цел да стигне до континента (европейския), за да избяга от професор Мориарти, който го преследва. След като се качи на влака, той видя професор Мориарти на перона на гарата. Шерлок Холмс признава, че Мориарти може да избере специален влак и да го изпревари. Шерлок Холмс има две алтернативи: да продължи пътуването до Дувър или да слезе на гара Кентърбъри, която е единствената междинна гара по маршрута му. Приемаме, че опонентът му е достатъчно интелигентен, за да определи способностите на Холмс, така че той има същите две алтернативи. И двамата опоненти трябва да изберат гара, на която да слязат от влака, без да знаят какво решение ще вземе всеки от тях. Ако в резултат на вземането на решение и двамата се окажат на една и съща станция, тогава определено можем да предположим, че Шерлок Холмс ще бъде убит от професор Мориарти. Ако Шерлок Холмс стигне благополучно до Дувър, той ще бъде спасен.

Решение. Можем да разглеждаме героите на Конан Дойл като участници в играта, тоест играчи. Достъпно за всеки играч аз (аз=1,2) две чисти стратегии:

• слезте на Доувър (стратегия сi1 ( аз=1,2) );
• слезте на междинна гара (стратегия сi2 ( аз=1,2) )

В зависимост от това коя от двете стратегии избира всеки от двамата играчи, ще бъде създадена специална комбинация от стратегии като двойка с = (с1 , с 2 ) .

Всяка комбинация може да бъде свързана със събитие - резултатът от опита за убийство на Шерлок Холмс от професор Мориарти. Ние създаваме матрица на тази игра с възможни събития.

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

Пример за формализиране и решение на кооперативна (коалиционна) игра нлица

На този етап практическата част, тоест процесът на решаване на примерна задача, ще бъде предшествана от теоретична част, в която ще се запознаем с концепциите на теорията на игрите за решаване на кооперативни (некооперативни) игри. За тази задача теорията на игрите предлага:

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

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

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

За игра ннека обозначим множеството от всички негови играчи като н= (1,2,...,n) Всяко непразно подмножество на множеството ннека го обозначим като T(включително себе си ни всички подмножества, състоящи се от един елемент). Има урок на сайта " Множества и операции върху множества“, който се отваря в нов прозорец, когато щракнете върху връзката.

Характеристичната функция се означава като vи неговата област на дефиниране се състои от възможни подмножества на множеството н. v(T) - стойността на характеристичната функция за определено подмножество, например доходът, получен от коалиция, евентуално включваща такава, състояща се от един играч. Това е важно, тъй като теорията на игрите изисква проверка на наличието на суперадитивност за стойностите на характеристичната функция на всички несвързани коалиции.

За две непразни подмножества коалиции T1 И T2 Адитивността на характеристичната функция на кооперативна (коалиционна) игра се записва по следния начин:

А суперадитивността е така:

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

Средно приходите им на вечер бяха:

• цигуларят има 600 единици;
• китаристът има 700 единици;
• певецът има 900 единици.

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

• цигулар + китарист спечелиха 1500 единици;
• цигулар + певец спечели 1800 единици;
• китарист + певец спечели 1900 единици;
• цигулар + китарист + певец спечелиха 3000 единици.

Решение. В този пример, броят на играчите в играта н= 3, следователно областта на дефиниране на характеристичната функция на играта се състои от 2³ = 8 възможни подмножества от множеството на всички играчи. Нека изброим всички възможни коалиции T:

• коалиции от един елемент, всяка от които се състои от един играч - музикант: T{1} , T{2} , T{3} ;
• коалиция от два елемента: T{1,2} , T{1,3} , T{2,3} ;
• коалиция от три елемента: T{1,2,3} .

Ще присвоим сериен номер на всеки играч:

• цигулар - 1-ви играч;
• китарист - 2-ри играч;
• певец - 3-ти играч.

Въз основа на данните за проблема определяме характерната функция на играта v:

v(T(1)) = 600; v(T(2)) = 700; v(T(3)) = 900; тези стойности на характеристичната функция се определят въз основа на печалбите съответно на първия, втория и третия играч, когато те не се обединяват в коалиция;

v(T(1,2)) = 1500; v(T(1,3)) = 1800; v(T(2,3)) = 1900; тези стойности на характеристичната функция се определят от приходите на всяка двойка играчи, обединени в коалиция;

v(T(1,2,3)) = 3000; тази стойност на характеристичната функция се определя от средния приход в случай, че играчите са обединени по тройки.

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

Как са изпълнени условията за суперадитивност в този пример? Нека определим как играчите формират несвързани коалиции T1 И T2 . Ако някои играчи са част от коалиция T1 , тогава всички останали играчи са част от коалицията T2 и по дефиниция тази коалиция се формира като разлика между целия набор от играчи и набора T1 . Тогава ако T1 - коалиция от един играч, след това в коалиция T2 ще има втори и трети играч, ако са в коалиция T1 ще има първи и трети играч, след това коалицията T2 ще се състои само от втория играч и т.н.

Съдържание 1 Обща информация 2 1.1 Игри. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Ходове. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Стратегии. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 Матрична игра. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Точка пътека. Чисти стратегии 7 2.1 Примери. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Пример 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 Пример 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Смесени стратегии 9 3.1 Игра 2×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.1.1 Примери. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Пример 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Пример 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1.2 Геометрична интерпретация. . . . . . . . . . . . . . . . . . . . 12 3.2 Игри 2×n и m×2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Пример 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1 1. Общи сведения от теорията на игрите 1.1. Игрите Теорията на игрите е математическа теория на конфликтните ситуации, т.е. ситуации, в които се сблъскват интересите на две или повече страни, преследващи различни цели. Играта е конфликтна ситуация, регулирана от определени правила, които трябва да посочват: възможни варианти за действия на участниците; количествения резултат от играта или плащането (печалба, загуба), до което води даден набор от ходове; количеството информация на всяка страна относно поведението на другата. Играта на двойки е игра, в която участват само две страни (двама играчи). Игра с двойки с нулева сума е игра с двойки, в която сумата на плащанията е нула, т.е. Загубата на един играч е равна на печалбата на втория. В зависимост от отношението на всеки играч към стойността на функцията за изплащане, игрите с двойки се подразделят: Игра с двойки с нулева сума (антагонистична) - игра с двойки, в която сумата на плащанията е равна на нула, т.е. Загубата на един играч е равна на печалбата на втория. Неантагонистична игра е игра по двойки, в която играчите преследват различни, но не директно противоположни цели. 2 1.2. Ходове Ход - избор на едно от действията, предвидени в правилата на играта; изпълнение на този избор. Ходовете са два вида: Личен ход - + съзнателен избор на едно от действията, предвидени в правилата на играта + изпълнение на този избор. Случаен ход - Случайният ход е избор от няколко възможности, който не се извършва по решение на играча, а чрез някакъв механизъм за случаен избор. По-долу разглеждаме игри с двойки с нулева сума, съдържащи само лични ходове. Всяка страна няма информация за поведението на другата. 3 1.3. Стратегии Стратегията на играча е набор от правила, които определят избора на действия за всеки личен ход на този играч, в зависимост от ситуацията, която възниква по време на играта. В зависимост от броя на възможните стратегии игрите се делят на крайни и безкрайни. Безкрайна игра е игра, в която поне един от играчите има безкраен брой стратегии. Крайна игра е игра, в която всеки играч има само краен брой стратегии. Броят на последователните ходове за всеки играч определя разделението на игрите на едноходови и многоходови, или позиционни. + В игра с един ход всеки играч прави само един избор от възможните опции и след това определя резултата от играта. + Игра с много ходове или позиционна игра се развива с течение на времето, представлявайки поредица от последователни етапи, всеки от които се случва след хода на един от играчите и съответната промяна в ситуацията. В игра с един ход всеки играч прави само един избор от възможните опции и след това определя резултата от играта. Оптималната стратегия на играча е стратегия, която, когато играта се повтаря много пъти, осигурява на този играч максималната възможна средна печалба (или, което е същото, минималната възможна средна загуба). В теорията на игрите всички препоръки се правят въз основа на предположението за разумно поведение на играчите. Грешките и грешките на играчите, неизбежни във всяка конфликтна ситуация, както и елементите на вълнение и риск не се вземат предвид в теорията на игрите. 4 1.4. Матрична игра Матричната игра е игра с краен нулев резултат с един ход Матричната игра е теоретико-игров модел на конфликтна ситуация, в която опонентите, за да постигнат диаметрално противоположни цели, правят един избор (ход) от краен брой възможни варианти на действие В съответствие с избраните методи на действие (стратегии) ​​се определя постигнатият резултат. Нека разгледаме един пример. Нека има двама играчи A и B, единият от които може да избере i-тата стратегия от m от възможните си стратегии A1, A2, ...Am, а вторият избира j-та стратегия от възможните си стратегии B1, B2. , .. .Bm. В резултат на това първият играч печели стойността aij, а вторият играч губи тази стойност. От числата aij създаваме матрица   a11 a11 · · · a1n  a21 a22 · · · a2n    A = (aij) =  .. .. ..   . . . .  am1 am2 · · · amn Матрицата A = (aij), i = 1, m, j = 1, n се нарича матрица на изплащане или m × n матрица на играта. В тази матрица редовете винаги са за стратегиите на печелившия (максимизиращ) играч А, тоест играчът, който се стреми да максимизира своите печалби. Колоните са разпределени за стратегиите на губещия играч B, т.е. играчът, който се стреми да минимизира критерия за ефективност. Нормализирането на игра е процесът на редуциране на позиционна игра до матрична игра. Игра в нормална форма е позиционна игра, намалена до матрична игра. Нека припомним, че позиционната игра с няколко хода е теоретико-игров модел на конфликтна ситуация, в която опонентите последователно правят един избор (ход) от краен брой възможни варианти на действие на всеки етап от развитието на тази ситуация. Решението на играта е намиране на оптималните стратегии на двамата играчи и определяне на цената на играта.Цената на играта е очакваната печалба (загуба) на играчите. Решението на играта може да се намери или в чистите стратегии - когато играчът трябва да следва една единствена стратегия, или в смесените, когато играчът трябва да използва две или повече чисти стратегии с определени вероятности. Последните в този случай се наричат ​​активни. 5 Смесена стратегия на един играч е вектор, всеки компонент на който показва честотата на използване от играча на съответната чиста стратегия. Maximin или по-ниска цена на играта - номер α = max min aij i j Maximin стратегия (линия) - стратегията, която играчът е избрал, за да максимизира своите минимални печалби. Очевидно, когато избира най-предпазливата максимин стратегия, играч А си осигурява (независимо от поведението на опонента) гарантирана печалба от поне α. Maximin или горна цена на играта - число β = min max aij j i Минимакс стратегия (колона) - стратегията, която играчът е избрал, за да минимизира максималната си загуба. Очевидно, когато избира най-предпазливата минимакс стратегия, играч Б не позволява при никакви обстоятелства на играч А да спечели повече от β. Долната цена на играта винаги не надвишава горната цена на играта α = max min aij 6 min max aij = β i j j i Теорема 1 (основната теорема на теорията на матричните игри). Всяка ограничена игра има поне едно решение, вероятно в сферата на смесените стратегии. 6 2. Игри със седло. Решение в чисти стратегии Игра със седлова точка е игра, за която α = max min aij = min max aij = β i j j i За игри със седлова точка намирането на решение се състои от избор на максимин и минимакс стратегии, които са оптимални. , Нетна цена на играта - общата стойност на долната и горната цена на играта α=β=ν 2.1. Примери Пример 1 Намерете решение в чисти стратегии на играта, дадени от матрицата   8 4 7 A= 6 5 9  7 7 8 Решение: определете горната и долната цена на играта. За да направим това, ще намерим минимума от числата aij в i-тия ред αi = min aij j и максимума от числата aij в j-тата колона βj = max aij i Ще запишем числата αi (ред минимуми) до платежната матрица вдясно под формата на допълнителна колона. Записваме числата βi (максимуми на колони) под матрицата под формата на допълнителен ред: αi 8 4 7 4 6 5 9 5 7 7 8 7 βj 8 7 9 7 Намерете максимума от числата αi α = max αi = 7 i и минимумът от числата βj β = min βj = 7 j α = β - играта има седлова точка. Оптималната стратегия за играч е стратегия A3, а за играч B е стратегия B2, нетна цена на играта ν = 7 Пример 2 Дадена е матрицата на плащане:   2 2 1 1 2  0 1 1 1 1  A=  1 1 1 1 2   1 2 1 1 2 Намерете решение на играта в чисти стратегии. Решение: 2 2 1 1 2 1 0 1 1 1 1 0 1 1 1 1 2 1 1 2 1 1 2 1 βj 2 2 1 1 2 α = β = 1. Играта има шест седлови точки. Оптималните стратегии ще бъдат: A1 и B3 или B4 A3 и B3 или B4 A4 и B3 или B4 8 3. Решение на играта при смесени стратегии Когато α = β. В случай, че при избора на своите стратегии и двамата играчи нямат информация за избора на другия, играта има решение в смесени стратегии. SA = (p1, p2, ..., pm) - смесена стратегия на играч A, при която се прилагат стратегии A1, A2, ..., Am с вероятности ∑ m p1, p2, ..., pm, pi = 1, pi > 0, i = 1, m i=1 SB = (q1, q2, ..., qn) - смесена стратегия на играч B, при която стратегиите B1, B2, ..., Bm се прилагат с вероятности ∑ n q1, q2 , ..., qm , qi = 1, qi > 0, i = 1, n i=1 Ако: SA∗ е оптималната стратегия на играч A, SB∗ е оптималната стратегия на играч B, тогава цената на играта е ∑ n ∑ m ν = aij · p∗i · qi∗ j=1 i=1 Следващата теорема отговаря на въпроса как да се намери решение за игрите 2 × 2, 2 × n, m × 2 Теорема 2 (как да намерим решение за игрите 2 × 2, 2 × n, m × 2). Ако един от играчите използва оптимална смесена стратегия, тогава неговата печалба е равна на цената на играта ν, независимо от вероятностите, с които вторият играч ще използва стратегиите, включени в оптималната (включително чисти стратегии). 9 3.1. Игра 2 × 2 Да разгледаме игра 2 × 2 с матрицата: () a11 a21 a21 a22 Нека играта няма решение в чисти стратегии. Нека намерим оптималните стратегии SA∗ и SB∗. Първо, дефинираме стратегията SA∗ = (p∗1, p∗2). Според теоремата, ако страна А се придържа към стратегия ν, тогава независимо от курса на действие на страна Б, печалбата ще остане равна на цената на игра ν. Следователно, ако страна A се придържа към оптималната стратегия SA∗ = (p∗1, p∗2), тогава страна B може да приложи всяка своя стратегия, без да променя своята печалба. Тогава, когато играч B използва чиста стратегия B1 или B2, играчът ще получи средна печалба, равна на цената на играта: a11 p∗1 + a21 p∗2 = ν ← за стратегия B1 a12 p∗1 + a22 p∗ 2 = ν ← за стратегия B2 Като се има предвид, че p∗1 + p∗2 = 1: p∗1 = a2 2−a2 1 a11 +a22 −a12 −a21 p∗2 = a1 1−a1 2 a11 +a22 −a12 −a21 Цена на играта: a22 a11 − a12 a21 ν= a11 + a22 − a12 − a21 Оптималната стратегия на играч B се намира по подобен начин: SB∗ = (q1∗ , q2∗). Като се има предвид, че q1∗ + q2∗ = 1: q1∗ = a2 2−a1 2 a11 +a22 −a12 −a21 q2∗ = a1 1−a2 1 a11 +a22 −a12 −a21 3.1.1. Примери Пример 3 Намерете решение на играта с матрица () −1 1 A= 1 −1 10 Решение: играта няма седлова точка, тъй като α= -1, β = 1, α ̸= β. Търсим решение в смесените стратегии. Използвайки формулите за p∗ и q∗, получаваме p∗1 = p∗2 = 0,5 и q1∗ = q2∗ = 0,5, ν = 0 Така SA∗ = (0,5, 0,5) SB∗ = (0,5, 0,5 ) Пример 4 Намерете решение на играта с матрица () 2 5 A= 6 4 Решение: играта няма седлова точка, тъй като α= 4, β = 5, α ̸= β. Търсим решение в смесените стратегии. Използвайки формулите за p∗ и q∗, получаваме p∗1 = 0,4, p∗2 = 0,6 и q1∗ = 0,2 q2∗ = 0,8, ν = 4,4 Така SA∗ = (0,4, 0,6) SB∗ = ( 0,2, 0,8) 11 3.1.2. Геометрична интерпретация Играта 2 × 2 може да получи проста геометрична интерпретация. Нека вземем единичен участък от абсцисната ос, всяка точка от която свързваме с някаква смесена стратегия S = (p1, p2) = (p1, 1 − p1) и вероятността p1 на стратегия A1 да бъде равна на разстоянието от точка SA до десния край на сечението, а вероятността p2 , стратегия A2 - разстоянието до левия край. .y .I .I I .B1′ .N .B1 .a21 .a11 .I I .I .∗ .x .P2 .SA∗ .P1∗ По-специално, левият край на сечението (точка с абциса = 0) съответства към стратегия A1, десен край на сегмента (x = 1) - стратегия A2 В краищата на сегмента се възстановяват два перпендикуляра на оста x: ос I − I - изплащането за стратегия A1 се отлага; ос II − II - изплащането за стратегия A2 е отложено Нека играч B приложи стратегия B1; тя дава съответно на осите I − I и II − II точки с ординати a11 и a21. Прекарваме права B1 − B1′ през тези точки. За всяка смесена стратегия SA = (p1, p2), печалбата на играча се определя от точка N на правата B1 − B1′, съответстваща на точка SA на оста x, разделяща сегмента в съотношение p2: p1. Очевидно правата B2 − B2′, която определя печалбата за стратегия B2, може да бъде конструирана по абсолютно същия начин. 12 .y .I .I I .B2 .N .a21 .B2′ a . 22 .I I .I .∗ .x .P2 .SA∗ .P1∗ Необходимо е да се намери оптималната стратегия SA∗ , т.е. така че минималната печалба на играч А (предвид най-лошото поведение за него от играч Б) ще се превърне в максимална. За да направите това, конструирайте долна граница за печалбата на играч A за стратегии B1, B2, т.е. прекъсната линия B1 N B2′ ;. На тази граница ще лежи минималната печалба на играч А за всяка от неговите смесени стратегии, точка N, в която тази печалба достига максимум и определя решението и цената на играта. .y .I .I I .B2 .B1′ .N .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P Ординатата на точка N не е нищо повече от цената на играта ν, нейната абциса е равна на ∗2, а разстоянието до десния край на отсечката е равно на ∗1, т.е. разстоянието от точката SA∗ до краищата на сегмента са равни на вероятностите ∗2 и ∗1 на стратегии A2 и A1 на оптималната смесена стратегия на играч A. в този случай решението на играта се определя от пресечна точка на стратегии B1 и B2. По-долу е даден случай, при който оптималната стратегия на играча е чиста стратегия A2. Тук стратегия A2 (за всяка вражеска стратегия) е по-печеливша от стратегия A1, 13 .y .y .I .I I .I I. I .B2′ . 1′ B .B1′ B . 2 .B2′ B . 2 .B1 .ν = a21 .B1 .ν = a21 I. I I. I .I . .x .I . .х. 2∗ P . A∗S = A2. 2∗ P . A∗ S = A2 Вдясно е показан случаят, когато играч B има очевидно непечеливша стратегия.Геометричната интерпретация също така позволява да се визуализират долната цена на играта α и горната цена β .y .I .I I .B2 .B1′ .N .B1 .B2′ .β = a21 .α = a22 .I I .I .∗ .x .P2 . A∗ S . 1∗ P На същата графика можем да дадем и геометрична интерпретация на оптималните стратегии на играч Б. Лесно се проверява, че делът q1∗ на стратегия B1 от оптималната смесена стратегия SB∗ = (q1∗, q2∗) е равен на отношението на дължината на сегмента KB2 към сумата от дължините на сегментите KB1 и KB2 по оста I − I: .y .I .I I .B2 .B1′ .N .K .L .B1 .B2′ .I I .I .∗ .x .P2 . A∗ S . 1∗ P 14 KB2 q1∗ = KB2 + KB1 или LB2′ q1∗ = LB2′ + LB1′ Оптималната стратегия SB∗ = (q1∗, q2∗) може да бъде намерена по друг начин, ако разменим играчите B и B, и вместо максимума на долната граница на печалбите, помислете за минимума на горната граница. .y .I .I I .A2 .A′1 .N .A1 .A′2 .I I .I . .x .q2∗ . B∗ S .q1∗ 15 3.2. Игри 2 × n и m × 2. Решението на игрите 2 × n и m × 2 се основава на следната теорема. Теорема 3. Всяка ограничена игра m × n има решение, в което броят на активните стратегии на всяка страна не надвишава най-малкото от числата m и n. Съгласно тази теорема, игра 2 × n винаги има решение, в което всеки играч има най-много две активни стратегии. След като намерите тези стратегии, играта 2 × n се превръща в игра 2 × 2, която може да бъде решена по елементарен начин. Намирането на активни стратегии може да стане графично: 1) изгражда се графична интерпретация; 2) определя се долната граница на печалбите; 3) две стратегии на втория играч са идентифицирани на долната граница на печалбата, които съответстват на две линии, пресичащи се в точката с максималната ордината (ако повече от две линии се пресичат в тази точка, всяка двойка се взема) - тези стратегии представляват активните стратегии на играч B. Така играта 2 × n се свежда до играта 2 × 2. Играта m × 2 също може да бъде решена, с тази разлика, че не долната, а горната граница на печалбата е конструиран, като върху него се търси не максимумът, а минимумът. Пример 5 Намерете решение на играта () 7 9 8 A= 10 6 9 Решение: използвайки геометричния метод, избираме активни стратегии. Директните линии B1 − B1′, B2 − B2′ и B3 − B3′ съответстват на стратегиите B1, B2, B3. Прекъснатата линия B1 N B2 е долната граница на печалбите на играча. Играта има решение S∗A = (23, 31); S*B = (0,5; 0,5; 0); v = 8. 16 .y .I .I I . 1′ B B . 2 .B3′ .N .B3 .B1 .B2′ .I I .I . .х. 2∗ P . A∗ S . 1∗ P 17 Индексна игра, 2 хода, 3 2 × 2, 10 лични, 3 2 × 2, 9 случайни, 3 геометрия, 12 нетна цена на играта, 7 примера, 10 2 × n, 9, 16 m × 2, 9 , 16 безкрайни, 4 в нормална форма, 5 крайни, 4 многоходови, 4 едноходови, 4 матрични, 5 сдвоени, 2 нулева сума, 2 антагонистични, 2 неантагонистични, 2 решение, 5 в смесени стратегии, 5 , 9 в чисти стратегии, 5 със седлова точка, 7 цена, 5 горна, 6 долна, 6 чиста, 7 максимин, 6 матрица на играта, 5 изплащане, 5 минимакс, 6 нормализиране на играта, 5 стратегия, 4 максимин, 6 минимакс, 6 оптимален, 4 смесени, 5 теория на игрите, 2 18