Ако има няколко конфликтни страни (лица), всяка от които взема определено решение, определено от даден набор от правила, и всяко от лицата знае окончателното състояние на конфликтната ситуация с плащания, предварително определени за всяка от страните, тогава игра се казва, че се провежда.
Задачата на теорията на игрите е да избере линия на поведение за даден играч, отклонението от която може само да намали печалбите му.
Някои определения на играта
Количествената оценка на резултатите от играта се нарича плащане.
Двойки (две лица) се нарича игра с нулева сума, ако сумата на плащанията е нула, т.е. ако загубата на един играч е равна на печалбата на другия.
Недвусмисленото описание на избора на играча във всяка от възможните ситуации, в които той трябва да направи личен ход, се нарича стратегия на играча .
Стратегията на играча се нарича оптимална, ако, когато играта се повтаря многократно, тя предоставя на играча максималното възможно средни печалби(или, което е същото, минималната възможна средна печалба).
Игра, дефинирана от матрица Аимайки млинии и нколони се нарича игра на измерение с ограничени двойки м* н;
Където аз=
- стратегия на първия играч с mstrategy;
й=
- стратегия на втория играч с n стратегии;
ij– печалбата на първия играч аз-стратегия, когато се използва от втория йта стратегия (или, което е същото, загубата на втората в нейната й-та стратегия, когато се използва първа аз th);
A = ij– платежна матрица на играта.
1.1 Игра с чисти стратегии
Ниска цена на играта (за първи играч)
= макс (мин ij). (1.2)
аз й
Топ цена на играта (за втори играч):
= мин
(макс
ij)
. (1.3)
Дж аз
Ако = , играта се нарича игра със седлова точка (1.4) или игра с чисти стратегии. При което V = = наречена ценна игра ( V- цена на играта).
Пример.Дадена е матрицата за плащане на играта за 2 лица A. Определете оптимални стратегииза всеки играч и цената на играта:
(1.4)
макс 10 9 12 6
аз
мин 6
й
- стратегия на първия играч (ред).
Стратегия за втори играч (колони).
- цена на играта.
Така играта има седлова точка. Стратегия й = 4 – оптимална стратегия за втория играч аз=2 - за първия. Имаме игра с чисти стратегии.
1.2 Игри със смесени стратегии
Ако платежната матрица няма седлова точка, т.е. 
и никой в играта не може да избере един план като своя оптимална стратегия, играчите преминават към „смесени стратегии“. Освен това всеки играч използва всяка своя стратегия няколко пъти по време на играта.
Вектор, всеки от компонентите на който показва относителната честота на използване от играча на съответната чиста стратегия, се нарича смесена стратегия на този играч.
х= (х 1 …Х аз …Х м) – смесена стратегия на първия играч.
U= (при 1 ...г й ...г н) – смесена стратегия на втория играч.
хаз , г й– относителни честоти (вероятности) на играчите, използващи своите стратегии.
Условия за използване на смесени стратегии
.
(1.5)
Ако х* = (х 1 * ….хаз*... х м*) – оптимална стратегия, избрана от първия играч; Y* = (при 1 * …при j*... при н*) е оптималната стратегия, избрана от втория играч, тогава числото е цената на играта.
(1.6)
По ред за броя Vбеше цената на играта и х* И при* - оптимални стратегии, необходимо и достатъчно е да се удовлетворят неравенствата
(1.7)
Ако един от играчите използва оптималната смесена стратегия, тогава неговата печалба е равна на цената на играта Vнезависимо от честотата, с която вторият играч ще използва стратегиите, включени в оптималната, включително чистите стратегии.
Намаляване на проблемите на теорията на игрите до проблеми на линейното програмиране.
Пример. Намерете решение на играта, дефинирана от матрицата на изплащане А.
А = 
(1.8)
г 1 г 2 г 3
Решение:
Нека създадем двойна двойка задачи за линейно програмиране.
За първи играч
(1.9)
при 1 +при 2 +при 3 = 1 (1.10)
Освобождавайки се от променливата V(цена на играта), разделете лявата и дясната страна на изразите (1.9), (1.10) на V. След като прие при й /Vза нова променлива z аз, получаваме нова системаограничения (1.11) и целева функция (1.12)
(1.11)
.
(1.12)
По същия начин получаваме модела на играта за втория играч:
(1.13)
х 1 +х 2 +х 3 = 1 . (1.14)
Редуциране на модел (1.13), (1.14) до форма без променлива V, получаваме
(1.15)
,
(1.16)
Където 
.
Ако трябва да определим стратегията на поведение на първия играч, т.е. относителна честота на използване на неговите стратегии ( х 1 ….х аз …Х м), ще използваме модела на втория играч, защото тези променливи са в неговия модел на изплащане (1.13), (1.14).
Нека редуцираме (1.15), (1.16) до каноничния вид
(1.17)
Задача:
Матричната игра е дадена от следната матрица на изплащане:
| Стратегии "Б" | ||||||||
| Стратегии "А" | Б 1 | Б 2 | ||||||
| A 1 | 3 | 5 | ||||||
| А 2 | 6 |
|
||||||
Намерете решението на матричната игра, а именно:
- намерете най-високата цена на играта;
- по-ниска ценаигри;
- нетна цена на играта;
- посочват оптималните стратегии на играчите;
- донеси графично решение(геометрична интерпретация), ако е необходимо.
Етап 1
Нека определим по-ниската цена на играта - α
Най-ниска цена на игратаα е максималната печалба, която можем да си гарантираме в игра срещу разумен противник, ако използваме една и само една стратегия през цялата игра (тази стратегия се нарича „чиста“).Нека намерим във всеки ред от платежната матрица минимумелемент и го запишете в допълнителна колона (Избрано жълтовиж таблица 1).
Тогава ще намерим максимумелемент от допълнителната колона (маркиран със звездичка), това ще бъде по-ниската цена на играта.
маса 1
| Стратегии "Б" | |||||||||||||||
| Стратегии "А" | Б 1 | Б 2 | Минимум на реда | ||||||||||||
| A 1 | 3 | 5 | 3 * | ||||||||||||
| А 2 | 6 |
|
|
||||||||||||
В нашия случай по-ниската цена на играта е: α = 3, и за да гарантираме победа не по-лоша от 3, трябва да се придържаме към стратегия A 1
Стъпка 2
Нека определим горната цена на играта - β
Топ цена на игратаβ е минималната загуба, която играч B може да си гарантира в игра срещу разумен противник, ако използва една и само една стратегия през цялата игра.Нека намерим във всяка колона от платежната матрица максимумелемент и го напишете в допълнителен ред по-долу (маркиран в жълто, вижте таблица 2).
Тогава ще намерим минимумелемент от допълнителната линия (отбелязан с плюс), това ще бъде горната цена на играта.
таблица 2
| Стратегии "Б" | ||||||||||||
| Стратегии "А" | Б 1 | Б 2 | Минимум на реда | |||||||||
| A 1 | 3 | 5 | 3 * | |||||||||
| А 2 | 6 |
| В нашия случай горната цена на играта е: β = 5, и за да се гарантира загуба не по-лоша от 5, противникът (играч „B“) трябва да се придържа към стратегия B 2 Стъпка:3 Смесена стратегия, това са чисти стратегии, редуващи се на случаен принцип, с определени вероятности (честоти). Ще обозначим смесената стратегия на играч „А“
|
|||||||||
където B 1, B 2 са стратегиите на играч „B“, а q 1, q 2 са съответно вероятностите, с които се прилагат тези стратегии, и q 1 + q 2 = 1.
Оптималната смесена стратегия за играч „А“ е тази, която му осигурява максимална печалба. Съответно за „Б” има минимална загуба. Тези стратегии са обозначени С A* и С B* съответно. Двойка оптимални стратегии формира решение на играта.
IN общ случайОптималната стратегия на играча може да не включва всички първоначални стратегии, а само някои от тях. Такива стратегии се наричат активни стратегии.
Стъпка: 4
Където: стр 1 , стр 2 - вероятности (честоти), с които се прилагат съответно стратегии A 1 и A 2
От теорията на игрите е известно, че ако играч „А” използва своята оптимална стратегия, а играч „Б” остане в рамките на своите активни стратегии, тогава средната печалба остава непроменена и е равна на цената на играта. 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 )
Къде е лесно да се намери оптималната честота на стратегия A 1:
| стр 1 = |
| (3) |
В тази задача:
| стр 1 = |
| = |
|
Вероятност Р 2 намерете чрез изваждане Р 1 от единица:
| стр 2 = 1 - стр 1 = | 1 | - |
| = | + | 6 | · |
Където: р 1 , р 2 - вероятности (честоти), с които се прилагат съответно стратегии B 1 и B 2
От теорията на игрите е известно, че ако играч "Б" използва оптималната си стратегия, а играч "А" остане в рамките на своите активни стратегии, тогава средната печалба остава непроменена и е равна на цената на играта. vнезависимо как играч А използва своите активни стратегии. Следователно, ако приемем, че играч „A“ ще използва чиста стратегия A 1, тогава средната печалба vще бъде:
k 11 q 1 + k 12 q 2 = v (4)
Тъй като цената на играта v вече знаем и имайки предвид това р 1 + р 2 = 1 , тогава оптималната честота на стратегия B 1 може да се намери като:
| р 1 = |
| (5) |
В тази задача:
| р 1 = |
| = |
|
Вероятност р 2 намерете чрез изваждане р 1 от единица:
| р 2 = 1 - р 1 = | 1 | - |
| = |
|
Отговор:
| Най-ниска цена на играта: | α = | 3 | |||
| Топ цена на играта: | β = | 5 | |||
| Цена на играта: | v = |
|
| Оптималната стратегия на играч А: |
|
|||||||||||||||
| Оптимална стратегия за играч "B": |
|
Геометрична интерпретация (графично решение):
Нека дадем геометрична интерпретация на разглежданата игра. Вземете част от абсцисната ос с единична дължина и начертайте вертикални прави линии през нейните краища а 1 И а 2 съответстващи на нашите стратегии A 1 и A 2 . Нека сега приемем, че играч "B" ще използва стратегия B 1 in чиста форма. Тогава, ако ние (играч „А“) използваме чиста стратегия A 1, тогава нашата печалба ще бъде 3. Нека маркираме съответната точка на оста а 1 .Ако използваме чиста стратегия A 2, тогава нашата печалба ще бъде 6. Нека маркираме съответната точка на оста а 2
(виж Фиг. 1). Очевидно, ако приложим, смесвайки стратегии A 1 и A 2 в различни пропорции, нашите печалби ще се променят по права линия, минаваща през точки с координати (0, 3) и (1, 6), нека я наречем линия на стратегия B 1 (на фиг. .1 е показано в червено). Абсцисата на всяка точка от дадена линия е равна на вероятността стр 2 (честота), с която прилагаме стратегия A 2, а по ординатата - получената печалба к (виж Фиг. 1).
Снимка 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 в червено. Тази линия определя т.нар долна граница на печалби. Очевидно най-много висока точкатази прекъсната линия съответства на нашата оптимална стратегия. IN в такъв случай, това е пресечната точка на линиите на стратегии 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 Главна информация 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. Матрична игра Матричната игра е игра с краен нулев резултат с един ход. Матричната игра е теоретична модел за игриконфликтна ситуация, в която противниците, за да постигнат диаметрално противоположни цели, правят един избор (ход) от краен брой възможни начинидействия.В съответствие с избраните методи на действие (стратегии) се определя постигнатият резултат. Нека разгледаме един пример. Нека има двама играчи А и Б, единият от които може да избира 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
От популярния американски блог Cracked.
Теорията на игрите е за изучаване на начини да направите най-добрия ход и в резултат на това да получите възможно най-голяма част от печелившата торта, като откъснете част от нея от други играчи. Учи ви да анализирате много фактори и да правите логически балансирани заключения. Мисля, че трябва да се учи след числата и преди азбуката. Просто защото твърде много хора вземат важни решения въз основа на интуиция, тайни пророчества, местоположението на звездите и други подобни. Задълбочено съм изучавал теорията на игрите и сега искам да ви разкажа за нейните основи. Може би това ще добави малко здрав разум към живота ви.
1. Дилемата на затворника
Берто и Робърт бяха арестувани за банков обир, след като не използваха правилно открадната кола, за да избягат. Полицията не може да докаже, че точно те са обрали банката, но са ги хванали на местопрестъплението в крадена кола. Разведени са в различни стаи и на всеки е предложена сделка: да предаде съучастник и да го прати в затвора за 10 години, а самият той да бъде освободен. Но ако и двамата се предадат, всеки ще получи по 7 години. Ако никой не каже нищо, и двамата ще влязат в затвора за 2 години само за кражба на кола.
Оказва се, че ако Берто мълчи, но Робърт го предаде, Берто отива в затвора за 10 години, а Робърт излиза на свобода. Всеки затворник е играч и ползата за всеки може да се изрази като „формула“ (какво получават и двамата, какво получава другият). Например, ако ви ударя, моят печеливш модел ще изглежда така (получавам груба победа, вие страдате от силна болка). Тъй като всеки затворник има две възможности, можем да представим резултатите в таблица.
Практическо приложение: Идентифициране на социопати
Тук виждаме основното приложение на теорията на игрите: идентифициране на социопати, които мислят само за себе си.Истинската теория на игрите е мощен аналитичен инструмент и аматьорството често служи като червен флаг, който разкрива някой, който няма чувство за чест. Хората, които правят интуитивни изчисления, вярват, че е по-добре да направите нещо грозно, защото ще доведе до по-кратка присъда затвор, независимо какво прави другият играч. Технически това е правилно, но само ако сте късоглед човек и поставяте числата по-високи човешки животи. Ето защо теорията на игрите е толкова популярна във финансите.
Истинският проблем с дилемата на затворника е, че той игнорира данните.Например, не взема предвид възможността да се срещнете с приятели, роднини или дори кредитори на лицето, което сте изпратили в затвора за 10 години.
Най-лошото е, че всички замесени в дилемата на затворника се държат така, сякаш никога не са чували за нея.
А най-добрият ход е да мълчиш и след две години заедно с добър приятел да използваш същите пари.
2. Доминираща стратегия
Това е ситуация, в която вашите действия дават най-голямата победа, независимо от действията на противника.Каквото и да се случи, направихте всичко както трябва. Ето защо много хора с дилемата на затворника вярват, че предателството води до „най-добрия“ резултат, независимо от това какво прави другият човек, а непознаването на реалността, присъщо на този метод, го прави да изглежда супер лесен.
Повечето от игрите, които играем, нямат строго доминиращи стратегии, защото в противен случай биха били ужасни. Представете си, че винаги правите едно и също нещо. Няма доминираща стратегия в играта камък-ножица-хартия. Но ако играете с човек, който има ръкавици за готвене и може да показва само камък или хартия, ще имате доминираща стратегия: хартия. Вашата хартия ще увие неговия камък или ще доведе до равенство и вие не можете да загубите, защото опонентът ви не може да покаже ножици. Сега, когато имате доминираща стратегия, ще бъдете глупак да опитате нещо различно.
3. Битката на половете
Игрите са по-интересни, когато нямат строго доминираща стратегия. Например битката на половете. Анджали и Борислав излизат на среща, но не могат да избират между балет и бокс. Анджали обича бокса, защото й харесва да гледа как тече кръв за насладата на крещяща тълпа от зрители, които се смятат за цивилизовани, само защото са платили нечия глава да бъде разбита.
Борислав иска да гледа балета, защото разбира през какво преминават балерините голяма сумаконтузии и най-трудните тренировки, знаейки, че една контузия може да сложи край на всичко. балетисти - най-великите спортистиНа земята. Една балерина може да те ритне в главата, но никога няма да го направи, защото кракът й струва много повече от лицето ти.
Всеки от тях иска да отиде на любимото си събитие, но не иска да му се наслаждава сам, затова ето как печели: най-висока стойност- правят каквото им харесва, най-малка стойност- просто да си с друг човек, и нула - да си сам.
Някои хора предлагат упорито упорство: ако правите каквото искате, независимо от всичко, другият трябва да се съобрази с вашия избор или да загуби всичко. както вече казах, опростената теория на игрите е страхотна в идентифицирането на глупаците.
Практическо приложение: Избягвайте острите ъгли
Разбира се, тази стратегия има и своите съществени недостатъци. Първо, ако се отнасяте към срещите си като към „битка между половете“, няма да се получи. Разделете се, за да може всеки от вас да намери някого, когото харесва. И вторият проблем е, че в тази ситуация участниците са толкова неуверени в себе си, че не могат да направят това.
Истински печелившата стратегия за всеки е да прави това, което иска.и след това или на следващия ден, когато са свободни, отидете заедно на кафе. Или редувайте бокс и балет, докато не настъпи революция в света на развлеченията и бъде изобретен боксовият балет.
4. Равновесие на Наш
Равновесието на Наш е набор от ходове, при които никой не иска да направи нещо различно след факта.И ако успеем да я накараме да работи, теорията на игрите ще замени цялата философска, религиозна и финансова система на планетата, защото „волята да не фалираме“ е станала по-мощна за човечеството движеща силаотколкото огън.
Нека бързо разделим $100. Вие и аз решаваме колко от стотиците ни трябват и в същото време обявяваме сумите. Ако нашите обща сумапо-малко от сто, всеки получава това, което иска. Ако обща сумаповече от сто, този, който е поискал най-малко, получава желаната сума, а по-алчният получава това, което е останало. Ако поискаме същата сума, всеки получава $50. Колко ще поискате? Как ще разделите парите? Има само един печеливш ход.
Ако поискате $51, ще получите максимална сумабез значение какво ще избере опонентът ви. Ако той поиска повече, ще получите $51. Ако той поиска $50 или $51, ще получите $50. И ако той поиска по-малко от $50, ще получите $51. Така или иначе, няма друга опция, която да ви донесе повече пари от тази. Равновесие на Наш – ситуация, в която и двамата избираме 51$.
Практическо приложение: Първо помислете
Това е целият смисъл на теорията на игрите. Не е нужно да печелите, още по-малко да вредите на други играчи, но трябва да направите най-добрия ход за себе си, независимо от това, което хората около вас са подготвили за вас. И още по-добре е, ако този ход е от полза за други играчи. Това е видът математика, който може да промени обществото.
Интересен вариант на тази идея е пиенето, което може да се нарече зависимо от времето равновесие на Наш. Когато пиете достатъчно, не се интересувате от действията на другите хора, независимо какво правят, но на следващия ден наистина съжалявате, че не сте направили нещо различно.
5. Игра на хвърляне
Хвърлянето се играе между Играч 1 и Играч 2. Всеки играч едновременно избира глави или опашки. Ако познаят правилно, Играч 1 получава пенито на Играч 2. Ако не, Играч 2 получава монетата на Играч 1.
Печелившата матрица е проста...
...оптимална стратегия: играйте напълно произволно.По-трудно е, отколкото си мислите, защото изборът трябва да е напълно случаен. Ако имате предпочитание глави или опашки, вашият опонент може да го използва, за да вземе парите ви.
Разбира се, истинският проблем тук е, че би било много по-добре, ако просто си хвърлят по едно пени един на друг. В резултат печалбите им биха били същите и получената травма може да помогне на тези нещастни хора да почувстват нещо различно от ужасна скука. В крайна сметка това най-лошата игранякога съществуващ. А това е идеалният модел за изпълнение на дузпи.
Практическо приложение: Дузпа
Във футбола, хокея и много други игри продълженията са изпълнение на дузпи. И биха били по-интересни, ако се основаваха на това колко пъти играчите пълна формабиха могли да правят колело, защото това най-малкото би било индикация за техните физически способности и би било забавно за гледане. Вратарите не могат ясно да определят движението на топка или шайба в самото начало на движението й, тъй като, за съжаление, роботите все още не участват в нашите спортни състезания. Вратарят трябва да избере лява или дясна посока и да се надява, че неговият избор съвпада с избора на противника, който стреля към вратата. Това има нещо общо с играта на монети.
Имайте предвид обаче, че това не е перфектен пример за приликата с играта на глави и опашки, защото дори правейки правилния изборпосока, вратарят може да не хване топката, а нападателят може да не удари вратата.
И така, какво е нашето заключение според теорията на игрите? Игрите с топка трябва да завършват по начин на „много топки“, при който всяка минута на играчите един срещу един се дава допълнителна топка/шайба, докато едната страна постигне определен резултат, което е индикация за истинските умения на играчите, и не е грандиозно случайно съвпадение.
В крайна сметка теорията на игрите трябва да се използва, за да направи играта по-умна. Което означава, че е по-добре.
Теория на игратакато клон на изследването на операциите, това е теорията на математическите модели за вземане на оптимални решения в условия на несигурност или конфликт на няколко страни с различни интереси. Теорията на игрите изучава оптималните стратегии в игрови ситуации. Те включват ситуации, свързани с избора на най-печелившите производствени решения за система от научни и икономически експерименти, организацията статистически контрол, икономическите взаимоотношения между индустриалните предприятия и други сектори. Формализиране конфликтни ситуацииматематически те могат да бъдат представени като игра на двама, трима и т.н. играчи, всеки от които преследва целта да максимизира своята полза, своите печалби за сметка на другия.Секцията "Теория на игрите" е представена от три онлайн калкулатори:
- Оптимални стратегии на играчите. При такива проблеми се посочва матрица за плащане. Изисква се да се намерят чисти или смесени стратегии на играчи и, цена на играта. За да решите, трябва да посочите размерността на матрицата и метода на решение. Услугата изпълнява следните методирешения за игра за двама играчи:
- Минимакс. Ако трябва да намерите чистата стратегия на играчите или да отговорите на въпрос относно седловата точка на дадена игра, изберете този метод на решение.
- Симплексен метод. Използва се за решаване на смесени стратегически игри с помощта на методи за линейно програмиране.
- Графичен метод. Използва се за решаване на смесени стратегически игри. Ако има седлова точка, решението спира. Пример: За дадена платежна матрица намерете оптималните смесени стратегии на играчите и цената на играта, като използвате графичен методигрови решения.
- Итеративен метод на Браун-Робинсън. Итеративният метод се използва, когато графичният метод е неприложим и когато алгебричният и матрични методи. Този метод дава приблизителна стойност на цената на играта, като истинската стойност може да бъде получена с всяка желана степен на точност. Този метод не е достатъчен за намиране на оптимални стратегии, но ви позволява да проследявате динамиката на походова игра и да определяте цената на играта за всеки играч на всяка стъпка.
Всички методи използват проверка за доминиращи редове и колони. - Биматрична игра. Обикновено в такава игра се задават две матрици с еднакъв размер на печалбите на първия и втория играч. Редовете на тези матрици съответстват на стратегиите на първия играч, а колоните на матриците съответстват на стратегиите на втория играч. В този случай първата матрица представлява печалбите на първия играч, а втората матрица представлява печалбите на втория.
- Игри с природата. Използва се, когато трябва да изберете управленско решениепо критериите на Maximax, Bayes, Laplace, Wald, Savage, Hurwitz.
За критерия на Bayes също ще е необходимо да се въведат вероятностите за настъпване на събития. Ако не са посочени, оставете стойностите по подразбиране (ще има еквивалентни събития).
За критерия на Хурвиц посочете нивото на оптимизъм λ. Ако този параметър не е посочен в условията, можете да използвате стойностите 0, 0,5 и 1.
Много проблеми изискват намиране на решения с помощта на компютри. Горните услуги и функции са един от инструментите.
