Господство и съкращения стратегии

Помислете за няколко метода опростят матрица плащане.

Първият метод. се използват за намаляване на размера на матрицата се основава на един от най-важните понятия в теорията на игрите - на идеята за стратегии за надмощие.

Ако аз-ти ред елемент стрелка поне (≥) к-тия ред. тогава можем да кажем, че аз-ти ред доминира й-ти ред. Затова Играчът не използва стратегията й-ти, като неговата победа в стратегията-тото е не по-малко, отколкото в стратегията й-то, без значение колко игра играч Б.

По същия начин, ако I-тата колона елемент стрелка поне (≥) j-тата колона. Тогава ние казваме, че й-тата колона доминира-тото колона. Ето защо, играч Б не използва стратегията-тото, тъй като загубата му (получат равен на играч а) вече не е в стратегията й-ти (≤), отколкото в стратегията-тото, независимо от начина, по който играчът играе А. стратегии, над която е доминирана от други стратегии трябва да бъде изхвърлена и да се приписват на тях нулева вероятност. От стойността на играта това няма да повлияе. Но размерът на матрицата на спада на игра. С това решение, а вие трябва да започнете играта.

Специален случай на господство е dublirovaniestrategy.

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

Опростяване (намаляване измерение) плащане матрица чрез премахване на възможно най-очевидно неблагоприятни чисти стратегии с оглед на следната теорема на доминиращите стратегии:

Нека I - една игра, в която аз-ти матрица стратегия първият играч доминира аз едно, а G - игра, чиято матрица, получена от матрицата аз освен аз + 1 стратегия (линия). След това:

1. Цената на игра I е равна на цената на играта G;

2. смесен оптимална стратегия Q * = (q1 *, q2 *, ..., QN *) на втория играч на играта, G е неговата смесена оптимална стратегия в играта I;

3. Ако P * = (p1 *, p2 *, ..., пи *. Р * аз + 2, ..., ч *) най-добре смес стратегия на първия играч в играта G, а след това е смесена стратегия P * = (p1 *, p2 *, ..., пи *. * р аз + 2, ..., ч *) е оптимална в игра I.

От горното следва, че както първата, така и втората няма никакъв смисъл да се използва доминиран стратегия, така че всички доминирани стратегии могат да бъдат премахнати, т.е. всъщност спадна редове и колони от оригиналната матрица A, съответстващи на тези редове. Това превръщане намалява размера на първоначалния плащане матрица А, като по този начин се опрости търсене на оптималните решения.

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

Пример 1. плащане игра матрица дава като:

Опростяване на играта (опростяване на матрицата на плащанията).

1-ви и 4-ти струни са равни. Ето защо ние се изхвърли 4-ти ред. Р4 вероятност = 0. получи матрица:

2-ра линия доминира третия низ (6> 3, 5> 4, 8 = 8, 7> 6). Затова ние изхвърли третия ред. p3 вероятността = 0. получи матрица:

Второ колона доминира третата колона (9 = 9, 5 <8). Поэтому отбросим 3-й столбец. Вероятность q3 = 0. Получим матрицу:

Линии не са сравними един с друг (8> 6, 4 <7), столбцы тоже (8 <9, 6> 5; 8> 4, 6 <7; 9> 4, 5 <7). Дальнейшее упрощение невозможно. Мы свели игру 4×4 к игре 2×3.

Пример 2: Матрицата игри

Първа стъпка: А1 доминира А2. 2- заличени ия ред, като в резултат се получи Р2 = 0 и плащане матрица:

2ри етап: A3 доминиращ А1. 1- заличени ия ред, резултатът е p1 = 0 и плащане матрица:

Трета стъпка: B2 B1 доминира заличени 1- та колона, резултатът е q1 = 0 и плащане матрица:

Четвъртия етап: B4 B3 доминира заличени 2 - та колона, резултатът е q3 = 0 и плащане матрица:

5-ти етап: A3, доминиран от А4. заличени 4 - ия ред, резултатът е p4 = 0 и плащане матрица:

2ри етап: B2 доминира В4 заличени четвърта колона, резултатът е q4 = 0 и плащане матрица:

В резултат на опростяването на плащането на матрицата разкри, че играта има уникална оптимално решение в чисти стратегии, това, което те казват, че вероятността вектори P и Q.

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

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

V * = макс мин Aij = макс = 6
V * = мин макс Aij = мин = 6
V * = V * = 6, A32 матрицата елемент е точка седло.
Забележка. Ако играта е м х н е с точка на седлото, ние винаги се получи след опростяване на плащане матрица игра 1 × 1.

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

На теоремата на афинни трансформации. Affine трансформация (сходство трансформация и срязване) финал матрица, т.е. превръщане на всички елементи на матрицата на формата: a'ij = к * Aij + б, където к ≠ 0 и б - всяка постоянна, не променя разтвор на играта. Освен това, цената на игра трансформира V ", могат да бъдат получени от цената на оригиналната игра V от същото правило: V '= кВ + б
Това означава по-специално, че задачата на играта основно Няма значение какво единици се измерва печалби, като в рубли или други валути.
Добавянето (изваждане) на фиксирана сума б до всеки елемент Aij на матрицата A плащане ще се промени с една и съща сума на печалба (загуба) на всеки един от играчите, без да се променя решенията на игра. Тази функция може да се използва за преобразуване на първоначалната матрица на играта в по-удобна форма. Например, ако елементи финал матрични представляват фракции с общ знаменател Aij на матрицата може да бъде умножена по всеки елемент от постоянна, при което елементите на матрицата ще бъде трансформирана числа; ако по-голямата част от клетките са изпълнени с еднакви матрични елементи, те могат да бъдат извадени от всеки елемент на матрицата за нули, които са равни на съответните елементи на матрицата. В допълнение, цената на игра V ", винаги е възможно да се направи положителна, т.е. V '> 0, което ние използваме в намаляването на игра проблем за линейното програмиране проблем.

В края на този раздел ще се даде формула преобразуване от преобразуваната стойност на игра V ", с оригиналния V:

Пример 3. Комплект игра на таксите за профила матрица:

Необходимо е да се опрости матрицата на играта.

1 - тата стъпка: размножават всеки от елементите на матрицата за к = 0.01, получаваме:

2 - та СТЪПКА: всеки елемент на матрицата "добавяне б = 4, ние получаваме матрицата:

По този начин, ние сме получили от матрицата на плащане с положителни елементи и малки по размер. Работа с такава матрица е по-просто, отколкото оригиналната матрица. Елементите на матрицата А '' получава чрез превръщане:

Пример 4. плащане матрични игри са дадени в форма. Опростяване на играта (за опростяване на матрицата на плащанията), за да се намери оптималното решение.