Примеры решения задач. Теория игр: матричные игры (Game Theory: Matrix Games)

Содержание 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. Игры Теория игр - это математическая теория конфликтных ситуаций, т.е. таких ситуаций, в которых сталкиваются интересы двух или более сторон, преследующих различные цели. Игра - это конфликтная ситуация, регламентированная определенными правилами, в которых должны быть указаны: возможные варианты действий участников количественный результат игры или платеж (выигрыш, проигрыш), к которому при- водит данная совокупность ходов объем информации каждой стороны о поведении другой. Парная игра - игра в которой участвуют только две стороны (два игрока). Парная игра c нулевой суммой - парная игра, в которой сумма платежей равна нулю, т.е. проигрыш одного игрока равен выигрышу второго. В зависимости от отношения каждого из игроков к значению функции выигрыша парные игры подразделяются: Парная игра c нулевой суммой (антагонистическая) - парная игра, в которой сум- ма платежей равна нулю, т.е. проигрыш одного игрока равен выигрышу второго. Неантагонистическая игра - парная игра,в которой игроки преследуют разные, но не прямо противоположные цели. 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. В этой матрице строки всегда для стратегий выигрывающего (максимизирующего) иг- рока A, то есть игрока, который стремится к максимизации своего выигрыша. Столбцы отводятся для стратегий проигрывающего игрока B, то есть игрока, который стремится к минимизации критерия эффективности. Нормализация игры - процесс сведения позиционной игры к матричной игре Игрой в нормальной форме - позиционная игра, сведенная к матрич- ной игре Напомним, что, позиционная многоходовая игра является теоретико- игровой моделью конфликтной ситуации, в которой противники для дости- жения своих целей последовательно делают по одному выбору (ходу) из ко- нечного числа возможных способов действий на каждом этапе развития этой ситуации. Решение игры - нахождение оптимальных стратегий обоих игроков и определение це- ны игры Цена игры - ожидаемый выигрыш (проигрыш) игроков. Решение игры может быть найдено либо в чистых стратегиях - когда игрок должен следовать одной единственной стратегии, либо в смешанных, когда игрок должен c определенными вероятностями применять две чистые стратегии или более. Последние в этом случае называются активными. 5 Смешанная стратегия одного игрока - вектор, каждая из компонент которого показы- вает частоту использования игроком соответствующей чистой стратегии. Максимин или нижняя цена игры - число α = max min aij i j Максиминная стратегия (строка) - стратегия, которую выбрал игрок, чтобы максими- зировать свой минимальный выигрыш. Очевидно, что при выборе наиболее осторожной максиминной стратегии игрок A обеспе- чивает себе (независимо от поведения противника) гарантированный выигрыш не менее α. Максимин или верхняя цена игры - число β = min max aij j i Минимаксная стратегия (столбец) - стратегия, которую выбрал игрок, чтобы миними- зировать свой максимальный проигрыш. Очевидно, что при выборе наиболее осторожной минимаксной стратегии игрок B не дает возможности ни при каких обстоятельствах игроку A выиграть больше, чем β. Нижняя цена игры всегда не превосходит верхней цены игры α = max min aij 6 min max aij = β i j j i Теоремма 1 (основная теорема теории матричных игр). Каждая конечная игра имеет по крайней мере одно решение, возможно, в области смешанных стратегий. 6 2. Игры с седловой точкой. Решение в чистых стратегиях Игра с седловой точкой - игра, для которой α = max min aij = min max aij = β i j j i Для игр с седловой точкой нахождение решения состоит в выборе максиминной и мини- макcной стратегий, которые являются оптимальными., Чистая цена игры - общее значение нижней и верхней цены игры α=β=ν 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 бу- дет придерживаться стратегии ν, то независимо от образа действий стороны B выигрыш будет оставаться равным цене игры ν. Следовательно, если сторона 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 Найти решение игры c матрицей () −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 Найти решение игры c матрицей () 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 На концах участка восстанавливаются два перпендикуляра к оси абсцисс: ось I − I - откладывается выигрыш при стратегии A1 ось II − II - откладывается выигрыш при стратегии A2 Пусть игрок B применяет стратегию B1 ; она дает на осях I − I и II − II соответственно точки с ординатами a11 и a21 . Проводим через эти точки прямую B1 − B1′ . При любой смешанной стратегии SA = (p1 , p2) выигрыш игрока определяется точкой N на прямой B1 −B1′ , соответствующей точке SA на оси абсцисс, делящей отрезок в отношении 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 (при наихудшем для него поведении игрока B) обращался бы в мак- симум. Для этого строиться нижняя граница выигрыша игрока A при стратегиях B1 , B2 , т.е. ломаная B1 N B2′ ;. На этой границе будет лежать минимальный выигрыш игрока A при любой его смешанной стратегии, точка 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 . .x . 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 На том же графике можно дать и геометрическую интерпретацию оптимальных страте- гий игрока B . Нетрудно убедиться, что доля 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 . .x . 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 c нулевой суммой, 2 антагонистическая, 2 неантагонистическая, 2 решение, 5 в смешанных стратегиях, 5, 9 в чистых стратегиях, 5 с седловой точкой, 7 цена, 5 верхняя, 6 нижняя, 6 чистая, 7 максимин, 6 матрица игры, 5 платежная, 5 минимакс, 6 нормализация игры, 5 стратегия, 4 максиминная, 6 минимаксная, 6 оптимальная, 4 смешанная, 5 теория игр, 2 18

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

Задача теории игр состоит в выборе такой линии поведения данного игрока, отклонение от которой может лишь уменьшить его выигрыш.

Некоторые определения игры

Количественная оценка результатов игры называется платежом.

Парная игра (два лица) называется игрой с нулевой суммой, если сумма платежей равна нулю, т.е. если проигрыш одного игрока равен выигрышу другого.

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

Стратегия игрока называется оптимальной, если при многократном повторении игры она обеспечивает игроку максимально возможный средний выигрыш (или, что - то же самое, минимально возможный средний выигрыш).

Игра, определяемая матрицей А , имеющейm строк иn столбцов, называется конечной парной игрой размерностиm * n ;

где i =
- стратегия первого игрока, имеющегоmстратегий; j =- стратегия второго игрока, имеющегоnстратегий; ij – выигрыш первого игрока поi -й стратегии при использовании вторымj -й стратегии (или, что то же самое, проигрыш второго по своейj -й стратегии, при использовании первымi -й);

А =  ij – платежная матрица игры.

1.1 Игра с чистыми стратегиями

Нижняя цена игры (для игрока первого)

 = max (min  ij ). (1.2)

i j

Верхняя цена игры (для второго игрока):

= min (max  ij ) . (1.3)

J i

Если  =  , игра называется с седловой точкой (1.4), или игра с чистыми стратегиями. При этомV =  =  называют ценной игры (V - цена игры).

Пример. Дана платежная матрица игры 2 лиц А. Определить оптимальные стратегии для каждого из игроков и цену игры:

(1.4)

max 10 9 12 6

min 6

- стратегия первого игрока (строки).

Стратегия второго игрока (столбцы).

- цена игры.

Таким образом, игра имеет седловую точку. Стратегия j = 4 – оптимальная для второго игрока, стратегияi =2 - для первого. Имеем игру с чистыми стратегиями.

1.2 Игры со смешанными стратегиями

Если платежная матрица не имеет седловой точки, т.е.
, и ни один из участников игры не может выбрать один план в качестве своей оптимальной стратегии, игроки переходят на «смешанные стратегии». При этом каждый из игроков использует в процессе игры несколько раз каждую из своих стратегий.

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

Х = (х 1 …х i …х m ) – смешанная стратегия первого игрока.

У = (у 1 …у j …у n ) – смешанная стратегия второго игрока.

x i , у j – относительные частоты (вероятности) использования игроками своих стратегий.

Условия использования смешанных стратегий

. (1.5)

Если Х * = (х 1 * ….х i * …х m *) – оптимальная стратегия, выбранная первым игроком;Y * = (у 1 * …у j * …у n *) – оптимальная стратегия, выбранная вторым игроком, то число является ценой игры.

(1.6)

Для того чтобы число V было ценой игры, ах * иу * - оптимальными стратегиями, необходимо и достаточно выполнение неравенств

(1.7)

Если один из игроков применяет оптимальную смешанную стратегию, то его выигрыш равен цене игры V вне зависимости от того, с какими частотами будет применять второй игрок стратегии, вошедшие в оптимальную, в том числе и чистые стратегии.

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

Пример . Найти решение игры, определяемой платежной матрицейА .

А = (1.8)

y 1 y 2 y 3

Решение:

Составим двойственную пару задач линейного программирования.

Для первого игрока

(1.9)

у 1 +у 2 +у 3 = 1 (1.10)

Освобождаясь от переменной V (цена игры), разделим левую и правую часть выражений (1.9), (1.10) наV . Приняву j /V за новую переменнуюz i , получим новую систему ограничений (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 ….х i …х m ), мы будем использовать модель второго игрока, т.к. эти переменные находятся в его модели выигрыша (1.13), (1.14).

Приведем (1.15), (1.16) к канонической форме

(1.17)

Теория игр как раздел исследования операций – это теория математических моделей принятия оптимальных решений в условиях неопределенности или конфликта нескольких сторон, имеющих различные интересы. Теория игр исследует оптимальные стратегии в ситуациях игрового характера. К ним относятся ситуации, связанные с выбором наивыгоднейших производственных решений системы научных и хозяйственных экспериментов, организацией статистического контроля, хозяйственных взаимоотношений между предприятиями промышленности и других отраслей. Формализуя конфликтные ситуации математически, их можно представить как игру двух, трех и т.д. игроков, каждый из которых преследует цель максимизации своей выгоды, своего выигрыша за счет другого.

Раздел "Теория игр" представлен тремя онлайн-калькуляторами :

Оптимальные стратегии игроков . В таких задачах задана платежная матрица. Требуется найти чистые или смешанные стратегии игроков и, цену игры . Для решения необходимо указать размерность матрицы и метод решения. В сервисе реализованы следующие методы решения игры двух игроков:
1. Минимакс . Если необходимо найти чистую стратегию игроков или ответить на вопрос о седловой точке игры, выберите этот метод решения.
2. Симплекс-метод . Используется для решения игры в смешанных стратегиях методами линейного программирования.
3. Графический метод . Используется для решения игры в смешанных стратегиях. Если есть седловая точка, решение прекращается. Пример: По заданной платежной матрице найти оптимальные смешанные стратегии игроков и цену игры, используя графический метод решения игры.
4. Итерационный метод Брауна-Робинсона . Итеративный метод применяется тогда, когда не применим графический метод и когда практически не приминимы алгебраический и матричный методы. Этот метод дает приближенное значение цены игры, причем истинное значение можно получить с любой нужной степенью точности. Этот метод недостаточен для нахождения оптимальных стратегий, но он позволяет отслеживать динамику пошаговой игры и определить цену игры для каждого из игроков на каждом шаге.
Например, задание может звучать как "указать оптимальные стратегии игроков для игры, заданной платежной матрицей" .
Во всех методах применяется проверка на доминирующие строки и столбцы.
Биматричная игра . Обычно в такой игре задают две матрицы одинакового размера выигрышей первого и второго игроков. Строки этих матриц соответствуют стратегиям первого игрока, а столбцы матриц – стратегиям второго игрока. При этом в первой матрице представлены выигрыши первого игрока, а во второй матрице – выигрыши второго.
Игры с природой . Используется, когда необходимо выбрать управленческое решение по критериям Максимакса, Байеса, Лапласа, Вальда , Сэвиджа , Гурвица .
Для критерия Байеса необходимо также будет ввести вероятности наступления событий. Если они не заданы, оставьте значения по умолчанию (будут равнозначные события).
Для критерия Гурвица укажите уровень оптимизма λ . Если в условиях данный параметр не задан можно использовать значения 0, 0.5 и 1 .

Во многих задачах требуется находить решение средствами ЭВМ. Одним из инструментов служат вышеприведенные сервисы и функции

Заметьте! Решение вашей конкретной задачи будет выглядеть аналогично данному примеру, включая все таблицы, поясняющие тексты и рисунки, представленные ниже, но с учетом ваших исходных данных…

Задача:
Матричная игра задана следующей платежной матрицей:

Стратегии "B"

Стратегии "A"

B 1

B 2

A 1

A 2

3

2

Найти решение матричной игры, а именно:
- найти верхнюю цену игры;
- нижнюю цену игры;
- чистую цену игры;
- указать оптимальные стратегии игроков;
- привести графическое решение (геометрическую интерпретацию), при необходимости.

Шаг:1

Определим нижнюю цену игры - α

Нижняя цена игры α - это максимальный выигрыш, который мы можем гарантировать себе, в игре против разумного противника, если на протяжении всей игры будем использовать одну и только одну стратегию (такая стратегия называется "чистой").

Найдем в каждой строке платежной матрицы минимальный элемент и запишем его в дополнительный столбец (Выделен желтым цветом см. Табл.1).

Затем найдем максимальный элемент дополнительного столбца (отмечен звездочкой), это и будет нижняя цена игры.

Таблица 1

Стратегии "B"

Стратегии "A"

B 1

B 2

Минимумы строк

A 1

3 *

A 2

3

2

3

2

В нашем случае нижняя цена игры равна: α = 3 , и для того чтобы гарантировать себе выигрыш не хуже чем 3 мы должны придерживаться стратегии A 1

Шаг:2

Определим верхнюю цену игры - β

Верхняя цена игры β - это минимальный проигрыш, который может гарантировать себе игрок "В", в игре против разумного противника, если на протяжении всей игры он будет использовать одну и только одну стратегию.

Найдем в каждом столбце платежной матрицы максимальный элемент и запишем его в дополнительную строку снизу (Выделена желтым цветом см. Табл.2).

Затем найдем минимальный элемент дополнительной строки (отмечен плюсом), это и будет верхняя цена игры.

Таблица 2

Стратегии "B"

Стратегии "A"

B 1

B 2

Минимумы строк

A 1

3 *

A 2

3

2

В нашем случае верхняя цена игры равна: β = 5 , и для того чтобы гарантировать себе проигрыш не хуже чем 5 противник (игрок "B") должен придерживаться стратегии B 2

Шаг:3
Сравним нижнюю и верхнюю цены игры, в данной задаче они различаются, т.е. α ≠ β , платежная матрица не содержит седловой точки. Это значит, что игра не имеет решения в чистых минимаксных стратегиях, но она всегда имеет решение в смешанных стратегиях.

Смешанная стратегия , это чередуемые случайным образом чистые стратегии, с определенными вероятностями (частотами).

Смешанную стратегию игрока "А" будем обозначать

S A =

где B 1 , B 2 - стратегии игрока "B", а q 1 , q 2 - соответственно вероятности, с которыми эти стратегии применяются, причем q 1 + q 2 = 1.

Оптимальная смешанная стратегия для игрока "А" та, которая обеспечивает ему максимальный выигрыш. Соответственно для "B" - минимальный проигрыш. Обозначаются эти стратегии S A * и S B * соответственно. Пара оптимальных стратегий образует решение игры.

В общем случае в оптимальную стратегию игрока могут входить не все исходные стратегии, а только некоторые из них. Такие стратегии называются активными стратегиями .

Шаг:4

где: p 1 , p 2 - вероятности (частоты) с которыми применяются соответственно стратегии A 1 и A 2

Из теории игр известно, что если игрок "А" использует свою оптимальную стратегию, а игрок "B" остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок "В" использует свои активные стратегии. А в нашем случае обе стратегии активные, иначе игра бы имела решение в чистых стратегиях. Поэтому если предположить, что игрок "В" будет пользоваться чистой стратегией B 1 , то средний выигрыш v составит:

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

где: k ij - элементы платежной матрицы.

C другой стороны, если предположить, что игрок "В" будет пользоваться чистой стратегией 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

А с учетом того, что p 1 + p 2 = 1 имеем:

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

Откуда несложно найти оптимальную частоту стратегии A 1 :

p 1 =

k 22 - k 21

k 11 + k 22 - k 12 - k 21

(3)

В данной задаче:

p 1 =

Вероятность р 2 найдем вычитанием р 1 из единицы:

p 2 = 1 - p 1 =

где: q 1 , q 2 - вероятности (частоты) с которыми применяются соответственно стратегии B 1 и B 2

Из теории игр известно, что если игрок "B" использует свою оптимальную стратегию, а игрок "A" остается в рамках своих активных стратегий, то средний выигрыш остается неизменным и равным цене игры v независимо от того как игрок "А" использует свои активные стратегии. Поэтому если предположить, что игрок "A" будет пользоваться чистой стратегией A 1 , то средний выигрыш v составит:

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

Поскольку цена игры v нам уже известна и учитывая, что q 1 + q 2 = 1 , то оптимальная частота стратегии B 1 может быть найдена как:

q 1 =

v - k 12

k 11 - k 12

(5)

В данной задаче:

q 1 =

Вероятность q 2 найдем вычитанием q 1 из единицы:

q 2 = 1 - q 1 =

Ответ:

Нижняя цена игры:

α =

Верхняя цена игры:

β =

Цена игры:

v =

Оптимальная стратегия игрока "А" :

S A * =

A 1

A 2

Оптимальная стратегия игрока "B" :

S B * =

B 1

B 2

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

Дадим геометрическую интерпретацию рассмотренной игре. Возьмем участок оси абсцисс единичной длины и проведем через его концы вертикальные прямые a 1 и a 2 соответствующие нашим стратегиям A 1 и A 2 . Предположим теперь, что игрок "B" будет пользоваться стратегией B 1 в чистом виде. Тогда, если мы (игрок "A") будем использовать чистую стратегию A 1 , то наш выигрыш составит 3.Отметим соответствующую ему точку на оси a 1 .
Если же мы будем использовать чистую стратегию A 2 , то наш выигрыш составит 6. Отметим соответствующую ему точку на оси a 2
(см. Рис. 1). Очевидно, если мы будем применять, смешивая в различных пропорциях стратегии A 1 и A 2 , наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 3) и (1 , 6), назовем ее линией стратегии B 1 (на Рис.1 показана красным цветом). Абсцисса любой точки на данной прямой равна вероятности p 2 (частоте), с которой мы применяем стратегию A 2 , а ордината - получаемому при этом выигрышу k (см. Рис.1).

Рисунок 1.
График зависимости выигрыша k от частоты р 2 , при использовании противником стратегии B 1 .

Предположим теперь, что игрок "B" будет пользоваться стратегией B 2 в чистом виде. Тогда, если мы (игрок "A") будем использовать чистую стратегию A 1 , то наш выигрыш составит 5.Если же мы будем использовать чистую стратегию A 2 , то наш выигрыш составит 3/2 (см. Рис. 2). Аналогично, если мы будем смешивать в различных пропорциях стратегии A 1 и A 2 , наш выигрыш будет меняться по прямой проходящей через точки с координатами (0 , 5) и (1 , 3/2), назовем ее линией стратегии B 2 . Как и в предыдущем случае, абсцисса любой точки на этой прямой равна вероятности, с которой мы применяем стратегию A 2 , а ордината - получаемому при этом выигрышу, но только для стратегии B 2 (см. Рис. 2).

Рисунок 2.
v и оптимальной частоты р 2 для игрока "А" .

В реальной игре, когда разумный игрок "В" пользуется всеми своими стратегиями, наш выигрыш будет изменяться по ломаной линии, показанной на Рис.2 красным цветом. Эта линия определяет так называемую нижнюю границу выигрыша . Очевидно, что самая высокая точка этой ломанной соответствует нашей оптимальной стратегии. В данном случае, это точка пересечения линий стратегий B 1 и B 2 . Обратите внимание, что если выбрать частоту p 2 равной ее абсциссе, то наш выигрыш будет оставаться неизменным и равным v при любой стратегии игрока "B", кроме того он будет максимальным который мы можем себе гарантировать. Частота (вероятность) p 2 , в этом случае, есть соответствующая частота нашей оптимальной смешанной стратегии. Кстати из рисунка 2 видна и частота p 1 , нашей оптимальной смешанной стратегии, это длина отрезка [p 2 ; 1] на оси абсцисс. (Это потому, что p 1 + p 2 = 1 )

Совершенно аналогично рассуждая, можно найти и частоты оптимальной стратегии для игрока "В", что иллюстрируется на рисунке 3.

Рисунок 3.
Графическое определение цены игры v и оптимальной частоты q 2 для игрока "В" .

Только для него следует построить так называемую верхнюю границу проигрыша (красная ломаная линия) и искать на ней самую низкую точку, т.к. для игрока "В" цель, это минимизация проигрыша. Аналогично значение частоты q 1 , это длина отрезка [q 2 ; 1] на оси абсцисс.

Называется игра двух лиц с нулевой суммой, в которой в распоряжении каждого из них имеется конечное множество стратегий. Правила матричной игры определяет платёжная матрица, элементы которой - выигрыши первого игрока, которые являются также проигрышами второго игрока.

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

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

Теперь обо всём по порядку и подробно.

Платёжная матрица, чистые стратегии, цена игры

В матричной игре её правила определяет платёжная матрица .

Рассмотрим игру, в которой имеются два участника: первый игрок и второй игрок. Пусть в распоряжении первого игрока имеется m чистых стратегий, а в распоряжении второго игрока - n чистых стратегий. Поскольку рассматривается игра, естественно, что в этой игре есть выигрыши и есть проигрыши.

В платёжной матрице элементами являются числа, выражающие выигрыши и проигрыши игроков. Выигрыши и проигрыши могут выражаться в пунктах, количестве денег или в других единицах.

Составим платёжную матрицу:

Если первый игрок выбирает i -ю чистую стратегию, а второй игрок - j -ю чистую стратегию, то выигрыш первого игрока составит a ij единиц, а проигрыш второго игрока - также a ij единиц.

Так как a ij + (- a ij ) = 0 , то описанная игра является матричной игрой с нулевой суммой.

Простейшим примером матричной игры может служить бросание монеты. Правила игры следующие. Первый и второй игроки бросают монету и в результате выпадает "орёл" или "решка". Если одновременно выпали "орёл" и "орёл" или "решка" или "решка", то первый игрок выиграет одну единицу, а в других случаях он же проиграет одну единицу (второй игрок выиграет одну единицу). Такие же две стратегии и в распоряжении второго игрока. Соответствующая платёжная матрица будет следующей:

Задача теории игр - определить выбор стратегии первого игрока, которая гарантировала бы ему максимальный средний выигрыш, а также выбор стратегии второго игрока, которая гарантировала бы ему максимальный средний проигрыш.

Как происходит выбор стратегии в матричной игре?

Вновь посмотрим на платёжную матрицу:

Сначала определим величину выигрыша первого игрока, если он использует i -ю чистую стратегию. Если первый игрок использует i -ю чистую стратегию, то логично предположить, что второй игрок будет использовать такую чистую стратегию, благодаря которой выигрыш первого игрока был бы минимальным. В свою очередь первый игрок будет использовать такую чистую стратегию, которая бы обеспечила ему максимальный выигрыш. Исходя из этих условий выигрыш первого игрока, который обозначим как v 1 , называется максиминным выигрышем или нижней ценой игры .

При для этих величин у первого игрока следует поступать следующим образом. Из каждой строки выписать значение минимального элемента и уже из них выбрать максимальный. Таким образом, выигрыш первого игрока будет максимальным из минимальных. Отсюда и название - максиминный выигрыш. Номер строки этого элемента и будет номером чистой стратегии, которую выбирает первый игрок.

Теперь определим величину проигрыша второго игрока, если он использует j -ю стратегию. В этом случае первый игрок использует такую свою чистую стратегию, при которой проигрыш второго игрока был бы максимальным. Второй игрок должен выбрать такую чистую стратегию, при которой его проигрыш был бы минимальным. Проигрыш второго игрока, который обозначим как v 2 , называется минимаксным проигрышем или верхней ценой игры .

При решении задач на цену игры и определение стратегии для определения этих величин у второго игрока следует поступать следующим образом. Из каждого столбца выписать значение максимального элемента и уже из них выбрать минимальный. Таким образом, проигрыш второго игрока будет минимальным из максимальных. Отсюда и название - минимаксный выигрыш. Номер столбца этого элемента и будет номером чистой стратегии, которую выбирает второй игрок. Если второй игрок использует "минимакс", то независимо от выбора стратегии первым игроком, он проиграет не более v 2 единиц.

Пример 1.

Наибольший из наименьших элементов строк - 2, это нижняя цена игры, ей соответствует первая строка, следовательно, максиминная стратегия первого игрока первая. Наименьший из наибольших элементов столбцов - 5, это верхняя цена игры, ей соответствует второй столбец, следовательно, минимаксная стратегия второго игрока - вторая.

Теперь, когда мы научились находить нижнюю и верхнюю цену игры, максиминную и минимаксную стратегии, пришло время научиться обозначать эти понятия формально.

Итак, гарантированный выигрыш первого игрока:

Первый игрок должен выбрать чистую стратегию, которая обеспечивала бы ему максимальный из минимальных выигрышей. Этот выигрыш (максимин) обозначается так:

Первый игрок использует такую свою чистую стратегию, чтобы проигрыш второго игрока был максимальным. Этот проигрыш обозначается так:

Второй игрок должен выбрать свою чистую стратегию так, чтобы его проигрыш был минимальным. Этот проигрыш (минимакс) обозначается так:

Ещё пример из этой же серии.

Пример 2. Дана матричная игра с платёжной матрицей

Определить максиминную стратегию первого игрока, минимаксную стратегию второго игрока, нижнюю и верхнюю цену игры.

Решение. Справа от платёжной матрицы выпишем наименьшие элементы в её строках и отметим максимальный из них, а снизу от матрицы - наибольшие элементы в столбцах и выберем минимальный из них:

Наибольший из наименьших элементов строк - 3, это нижняя цена игры, ей соответствует вторая строка, следовательно, максиминная стратегия первого игрока вторая. Наименьший из наибольших элементов столбцов - 5, это верхняя цена игры, ей соответствует первый столбец, следовательно, минимаксная стратегия второго игрока - первая.

Седловая точка в матричных играх

Если верхняя и нижняя цена игры одинаковая, то считается, что матричная игра имеет седловую точку. Верно и обратное утверждение: если матричная игра имеет седловую точку, то верхняя и нижняя цены матричной игры одинаковы. Соответствующий элемент одновременно является наименьшим в строке и наибольшим в столбце и равен цене игры.

Таким образом, если , то - оптимальная чистая стратегия первого игрока, а - оптимальная чистая стратегия второго игрока. То есть равные между собой нижняя и верхняя цены игры достигаются на одной и той же паре стратегий.

В этом случае матричная игра имеет решение в чистых стратегиях .

Пример 3. Дана матричная игра с платёжной матрицей

Нижняя цена игры совпадает с верхней ценой игры. Таким образом, цена игры равна 5. То есть . Цена игры равна значению седловой точки . Максиминная стратегия первого игрока - вторая чистая стратегия, а минимаксная стратегия второго игрока - третья чистая стратегия. Данная матричная игра имеет решение в чистых стратегиях.

Решить задачу на матричную игру самостоятельно, а затем посмотреть решение

Пример 4. Дана матричная игра с платёжной матрицей

Найти нижнюю и верхнюю цену игры. Имеет ли данная матричная игра седловую точку?

Матричные игры с оптимальной смешанной стратегией

В большинстве случаев матричная игра не имеет седловой точки, поэтому соответствующая матричная игра не имеет решений в чистых стратегиях.

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

Итак, чтобы чтобы первый игрок получил максимальный средний выигрыш и чтобы средний проигрыш второго игрока был минимальным, чистые стратегии следует использовать с определённой вероятностью.

Если первый игрок использует чистые стратегии с вероятностями , то вектор называется смешанной стратегией первого игрока. Иначе говоря, это "смесь" чистых стратегий. При этом сумма этих вероятностей равна единице:

Если второй игрок использует чистые стратегии с вероятностями , то вектор называется смешанной стратегией второго игрока. При этом сумма этих вероятностей равна единице:

Если первый игрок использует смешанную стратегию p , а второй игрок - смешанную стратегию q , то имеет смысл математическое ожидание выигрыша первого игрока (проигрыша второго игрока). Чтобы его найти, нужно перемножить вектор смешанной стратении первого игрока (который будет матрицей из одной строки), платёжную матрицу и вектор смешанной стратегии второго игрока (который будет матрицей из одного столбца):

Пример 5. Дана матричная игра с платёжной матрицей

Определить математическое ожидание выигрыша первого игрока (проигрыша второго игрока), если смешанная стратегия первого игрока , а смешанная стратегия второго игрока .

Решение. Согласно формуле математического ожидания выигрыша первого игрока (проигрыша второго игрока) оно равно произведению вектора смешанной стратегии первого игрока, платёжной матрицы и вектора смешанной стратегии второго игрока:

первого игрока называется такая смешанная стратегия , которая обеспечивала бы ему максимальный средний выигрыш , если игра повторяется достаточное число раз.

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

По аналогии с обозначениями максимина и минимакса в случах чистых стратегий оптимальные смешанные стратегии обозначаются так (и увязываются с математическим ожиданием, то есть средним, выигрыша первого игрока и проигрыша второго игрока):

В таком случае для функции E существует седловая точка , что означает равенство .

Для того, чтобы найти оптимальные смешанные стратегии и седловую точку, то есть решить матричную игру в смешанных стратегиях , нужно свести матричную игру к задаче линейного программирования, то есть к оптимизационной задаче, и решить соответствующую задачу линейного программирования.

Сведение матричной игры к задаче линейного программирования

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

Функция цели в прямой задаче линейного программирования:

Система ограничений в прямой задаче линейного программирования:

Функция цели в двойственной задаче:

Система ограничений в двойственной задаче:

Оптимальный план прямой задачи линейного программирования обозначим

а оптимальный план двойственной задачи обозначим

Линейные формы для соответствующих оптимальных планов обозначим и ,

а находить их нужно как суммы соответствующих координат оптимальных планов.

В соответствии определениям предыдущего параграфа и координатами оптимальных планов, в силе следующие смешанные стратегии первого и второго игроков:

Математики-теоретики доказали, что цена игры следующим образом выражается через линейные формы оптимальных планов:

то есть является величиной, обратной суммам координат оптимальных планов.

Нам, практикам, остаётся лишь использовать эту формулу для решения матричных игр в смешанных стратегиях. Как и формулы для нахождения оптимальных смешанных стратегий соответственно первого и второго игроков:

в которых вторые сомножители - векторы. Оптимальные смешанные стратегии также, как мы уже определили в предыдущем параграфе, являются векторами. Поэтому, умножив число (цену игры) на вектор (с координатами оптимальных планов) получим также вектор.

Пример 6. Дана матричная игра с платёжной матрицей

Найти цену игры V и оптимальные смешанные стратегии и .

Решение. Составляем соответствующую данной матричной игре задачу линейного программирования:

Получаем решение прямой задачи:

Находим линейную форму оптимальных планов как сумму найденных координат.