Матричные игры: примеры решения задач. «Теория систем и системный анализ

Содержание 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

Возникшая в сороковых годах XX века математическая теория игр чаще всего применяется именно в экономике. Но как с помощью концепции игр смоделировать поведение людей в обществе? Зачем экономисты изучают, в какой угол чаще бьют пенальти футболисты, и как выиграть в «Камень, ножницы, бумагу» в своей лекции рассказал старший преподаватель кафедры микроэкономического анализа ВШЭ Данил Федоровых.

Джон Нэш и блондинка в баре

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

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

Игра - любая ситуация, в которой выигрыши агентов зависят друг от друга.

Стратегия - описание действий игрока во всех возможных ситуациях.

Исход - комбинация выбранных стратегий.

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

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

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

«Камень, ножницы, бумага»

Рассмотрим другие игры на предмет равновесия. Например, в «Камне, ножницах, бумаге» нет равновесия по Нэшу: во всех ее вероятных исходах нет варианта, в котором оба участника были бы довольны своим выбором. Тем не менее, существует Чемпионат мира и World Rock Paper Scissors Society, собирающее игровую статистику. Очевидно, что вы можете повысить свои шансы на победу, если будете что-то знать об обычном поведении людей в этой игре.

Чистая стратегия в игре - это такая стратегия, при которой человек всегда играет одинаково, выбирая одни и те же ходы.

По данным World RPS Society, камень является самым часто выбираемым ходом (37,8%). Бумагу ставят 32,6%, ножницы - 29,6%. Теперь вы знаете, что нужно выбирать бумагу. Однако, если вы играете с тем, кто тоже это знает, вам уже не надо выбирать бумагу, потому что от вас ожидается то же самое. Есть знаменитый случай: в 2005 году два аукционных дома Sotheby“s и Christie”s решали, кому достанется очень крупный лот - коллекция Пикассо и Ван Гога со стартовой ценой в 20 миллионов долларов. Собственник предложил им сыграть в «Камень, ножницы, бумагу», и представители домов отправили ему свои варианты по электронной почте. Sotheby“s, как они позже рассказали, особо не задумываясь, выбрали бумагу. Выиграл Christie”s. Принимая решение, они обратились к эксперту - 11-летней дочери одного из топ-менеджеров. Она сказала: «Камень кажется самым сильным, поэтому большинство людей его выбирают. Но если мы играем не с совсем глупым новичком, он камень не выбросит, будет ожидать, что это сделаем мы, и сам выбросит бумагу. Но мы будем думать на ход вперед, и выбросим ножницы».

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

Смешанные стратегии и спорт

Более серьезных примеров смешанных стратегий очень много. Например, куда подавать в теннисе или бить/принимать пенальти в футболе. Если вы ничего не знаете о вашем сопернике или просто постоянно играете против разных, лучшей стратегией будет поступать более-менее случайно. Профессор Лондонской школы экономики Игнасио Паласиос-Уэрта в 2003 году опубликовал в American Economic Review работу, суть которой заключалась в поиске равновесия по Нэшу в смешанных стратегиях. Предметом исследования Паласиос-Уэрта выбрал футбол и в связи с этим просмотрел более 1400 ударов пенальти. Разумеется, в спорте все устроено хитрее, чем в «Камне, ножницах, бумаге»: там учитывается сильная нога спортсмена, попадания в разные углы при ударе со всей силы и тому подобное. Равновесие по Нэшу здесь заключается в расчете вариантов, то есть, к примеру, определении углов ворот, в которые надо бить, чтобы выиграть с большей вероятностью, зная свои слабые и сильные стороны. Статистика по каждому футболисту и найденное в ней равновесие в смешанных стратегиях, показало, что футболисты поступают примерно так, как предсказывают экономисты. Вряд ли стоит утверждать, что люди, которые бьют пенальти, читали учебники по теории игр и занимались довольно непростой математикой. Скорее всего, есть разные способы научиться оптимально себя вести: можно быть гениальным футболистом, и чувствовать, что делать, а можно - экономистом, и искать равновесие в смешанных стратегиях.

В 2008 году профессор Игнасио Паласиос-Уэрта познакомился с Авраамом Грантом, тренером «Челси», который играл тогда в финале Лиги чемпионов в Москве. Ученый написал записку тренеру с рекомендациями по серии пенальти, которые касались поведения вратаря соперника - Эдвина ван дер Сара из «Манчестер Юнайтед». Например, по статистике, он почти всегда отбивал удары на среднем уровне и чаще бросался в естественную для пробивающего пенальти сторону. Как мы определили выше, правильнее все-таки рандомизировать свое поведение с учетом знаний о сопернике. Когда счет по пенальти был уже 6:5, Николя Анелька, нападающий «Челси», должен был забивать. Показывая перед ударом в правый угол, ван дер Сар будто спросил у Анелька, не собирается ли он бить туда.

Суть в том, что все предыдущие удары «Челси» были нанесены именно в правый от пробивающего угол. Мы не знаем точно почему, может быть, из-за консультации экономиста бить в неестественную для них сторону, ведь по статистике к этому менее готов ван дер Сар. Большинство футболистов «Челси» были правшами: ударяя в неестественный для себя правый угол, все они, кроме Терри, забивали. Видимо, стратегия была в том, чтобы Анелька пробил туда же. Но ван дер Сар, похоже, это понял. Он поступил гениально: показал в левый угол дескать «туда собрался бить?», от чего Анелька, наверное, пришел в ужас, ведь его разгадали. В последний момент он принял решение действовать по-другому, ударил в естественную для себя сторону, что и было нужно ван дер Сару, который взял этот удар и обеспечил «Манчестеру» победу. Эта ситуация учит случайному выбору, ведь в ином случае ваше решение может быть просчитано, и вы проиграете.

«Дилемма заключенного»

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

Равновесие по Нэшу здесь заключается в первой комбинации, когда оба подозреваемых не молчат и оба садятся на три года. Рассуждения каждого таковы: «если я буду говорить, я сяду на три года, если молчать - на пять лет. Если второй будет молчать, мне тоже лучше говорить: не сесть лучше, чем сесть на год». Это доминирующая стратегия: говорить выгодно, независимо от того, что делает другой. Однако в ней есть проблема - наличие варианта получше, ведь сесть на три года хуже, чем сесть на год (если рассматривать историю только с точки зрения участников и не учитывать вопросы морали). Но сесть на год невозможно, ведь, как мы поняли выше, молчать обоим преступникам невыгодно.

Улучшение по Парето

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

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

Трагедия общины

«Дилемма заключенного» - это игрушечная стилизованная история. Вряд ли вы ожидаете оказаться в подобной ситуации, но похожие эффекты есть везде вокруг нас. Рассмотрим «Дилемму» с большим количеством игроков, ее иногда называют трагедией общины. Например, на дорогах - пробки, и я решаю, как ехать на работу: на машине или на автобусе. Это же делают остальные. Если я поеду на машине, и все решат сделать то же самое, будет пробка, но мы доедем с комфортом. Если я поеду на автобусе, пробка-то все равно будет, но ехать я буду некомфортно и не особо быстрее, поэтому такой исход еще хуже. Если же в среднем все ездят на автобусе, то я, сделав то же самое, довольно быстро доеду без пробки. Но если при таких условиях поехать на машине, я тоже доеду быстро, но еще и с комфортом. Итак, наличие пробки не зависит от моих действий. Равновесие по Нэшу здесь - в ситуации, когда все выбирают ехать на машине. Что бы не делали остальные, мне лучше выбрать машину, потому что будет там пробка или нет, неизвестно, но я в любом случае доеду с комфортом. Это доминирующая стратегия, поэтому в итоге все едут на машине, и мы имеем то, что имеем. Задача государства - сделать поездку на автобусе лучшим вариантом хотя бы для некоторых, поэтому появляются платные въезды в центр, парковки и так далее.

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

Когда вас призывают прийти на субботник, ни от кого в отдельности не будет зависеть, станет двор чистым или нет: если я выйду один, я не смогу убрать все, или, если выйдут все, то не выйду я, потому что все и без меня уберут. Другой пример - перевозка грузов в Китае, о котором я узнал в замечательной книге Стивена Ландсбурга «Экономист на диване». 100-150 лет назад в Китае был распространен способ перевозки грузов: все складывалось в большой кузов, который тащили семь человек. Заказчики платили, если груз доставлялся вовремя. Представьте, что вы - один из этих шести. Вы можете прилагать усилия, и тянуть изо всех сил, и если все будут так делать, груз доедет вовремя. Если кто-нибудь один так делать не будет, все тоже доедут вовремя. Каждый думает: «Если все остальные тянут как следует, зачем это делать мне, а если все остальные тянут не со всей силы, то я ничего не смогу изменить». В итоге, со временем доставки все было очень плохо, и сами грузчики нашли выход: они стали нанимать седьмого и платить ему деньги за то, чтобы он стегал лентяев плетью. Само наличие такого человека заставляло всех работать изо всех сил, потому что иначе все попадали в плохое равновесие, из которого никому в отдельности с выгодой не выйти.

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

Сommitment device

Во многих ситуациях одному из участников игры может понадобиться инструмент, который убедит остальных, что тот не блефует. Он называется commitment device. Например, закон некоторых стран запрещает платить выкуп похитителям людей, чтобы снизить мотивацию преступников. Однако это законодательство часто не работает. Если вашего родственника захватили, и у вас есть возможность спасти его, обойдя закон, вы это сделаете. Представим ситуацию, что закон можно обойти, но родственники оказались бедными и выкуп им платить нечем. У преступника в этой ситуации два пути: отпустить или убить жертву. Убивать он не любит, но тюрьму он не любит больше. Отпущенный пострадавший, в свою очередь, может либо дать показания, чтобы похититель был наказан, либо молчать. Самый лучший исход для преступника: отпустить жертву, которая его не сдаст. Жертва же хочет быть отпущенной и дать показания.

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

Другие примеры игр:

Модель Бертрана

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

Разъезд на узкой дороге

Рассмотрим примеры выбора между двумя возможными равновесиями. Представьте, что Петя и Маша едут навстречу друг другу по узкой дороге. Дорога настолько узкая, что им обоим нужно съехать на обочину. Если они решат повернуть налево или направо от себя, они просто разъедутся. Если же один повернет направо, а другой налево от себя, или наоборот, случится авария. Как выбрать, куда съехать? Чтобы помогать искать равновесие в подобных играх, существуют, например, правила дорожного движения. В России каждому нужно повернуть направо.

В забаве Chiken, когда два человека едут на большой скорости навстречу друг другу, тоже есть два равновесия. Если оба сворачивают на обочину, возникает ситуация, которая называется Chiken out, если оба не сворачивают, то погибают в страшной аварии. Если я знаю, что мой соперник едет прямо, мне выгодно съехать, чтобы выжить. Если я знаю, что мой соперник съедет, то мне выгодно ехать прямо, чтобы после получить 100 долларов. Сложно предсказать, что случится на самом деле, однако, у каждого из игроков есть свой метод выиграть. Представьте, что я закрепил руль так, что его нельзя повернуть, и показал это своему сопернику. Зная, что у меня нет выбора, соперник отскочит.

QWERTY-эффект

Иногда бывает очень сложно перейти из одного равновесия в другое, даже если оно означает пользу для всех. Раскладка QWERTY была создана, чтобы замедлить скорость печати. Поскольку если бы все печатали слишком быстро, головки печатной машинки, которые бьют по бумаге, цеплялись бы друг за друга. Поэтому Кристофер Шоулз разместил часто стоящие рядом буквы на максимально далеком расстоянии. Если вы зайдете в настройки клавиатуры на своем компьютере, вы сможете выбрать там раскладку Dvorak и печатать гораздо быстрее, так как сейчас нет проблемы аналоговых печатных машин. Дворак рассчитывал, что мир перейдет на его клавиатуру, но мы по-прежнему живем с QWERTY. Конечно, если бы мы перешли на раскладку Дворака, будущее поколение было бы нам благодарно. Все мы приложили бы усилия и переучились, в результате вышло бы равновесие, в котором все печатают быстро. Сейчас мы тоже в равновесии - в плохом. Но никому не выгодно быть единственным, кто переучится, потому что за любым компьютером, кроме личного, работать будет неудобно.

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

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

Из истории теории игр

История теории игр как самостоятельной дисциплины начинается в 1944 году, когда Джон фон Нейман и Оскар Моргенштерн опубликовали книгу "Теория игр и экономическое поведение" ("Theory of Games and Economic Behavior"). Хотя примеры теории игр встречались и раньше: трактат Вавилонского Талмуда о разделе имущества умершего мужа между его жёнами, карточные игры в 18-м веке, развитие теории шахматной игры в начале 20-го века, доказательство теоремы о минимаксе того же Джона фон Неймана в 1928 году, без которой не было бы никакой теории игр.

В 50-х годах 20-го века Мелвин Дрешер и Мерил Флод из Rand Corporation первыми экспериментально применили дилемму заключённого, Джон Нэш в работах о состоянии равновесия в играх двух лиц развил понятие равновесия Нэша.

Рейнхард Сэлтен в 1965 году опубликовал книгу "Обработка олигополии в теории игр по требованию" ("Spieltheoretische Behandlung eines Oligomodells mit Nachfrageträgheit"), с которой применение теории игр в экономике получило новую движущую силу. Шагом вперёд в эволюции теории игр связан с работой Джона Мейнарда Смита "Эволюционно стабильная стратегия" ("Evolutionary Stable Strategy", 1974). Дилемма заключённого была популяризована в книге Роберта Аксельрода "Эволюция кооперации" ("The Evolution of Cooperation"), опубликованной в 1984 году. В 1994 году именно за вклад в теорию игр Нобелевской премии были удостоены Джон Нэш, Джон Харсаньи и Рейнхард Сэлтен.

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

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

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

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

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

Одна из самых простых конфликтных ситуаций, которая может быть записана и решена в теории игр - дуэль, представляющая собой конфликт двух игроков 1 и 2, имеющих соответственно p и q выстрелов. Для каждого игрока существует функция, указывающая вероятность того, что выстрел игрока i в момент времени t даст попадание, которое окажется смертельным.

В итоге теория игр приходит к такой формулировке некоторого класса столкновений интересов: имеются n игроков, и каждому нужно выбрать одну возможность из стого определённого набора, причём при совершении выбора у игрока нет никаких сведений о выборах других игроков. Область возможных выборов игрока может содержать такие элементы, как "ход тузом пик", "производство танков вместо автомобилей", или в общем смысле, стратегию, определяющую все действия, которые нужно совершить во всех возможных обстоятельствах. Перед каждым игроком стоит задача: какой выбор он должен сделать, чтобы его частное влияние на исход принесло ему как можно больший выигрыш?

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

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

заинтересованных сторон;
возможных действий с каждой стороны;
интересов сторон.

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

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

варианты действий игроков;
объём информации каждого игрока о поведении партнёра;
выигрыш, к которому приводит каждая совокупность действий.

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

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

Для игры характерна неопределённость результата . Причины неопределённости можно распределить по следующим группам:

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

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

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

Классификация игр

Классификация по числу игроков (игра двух и более лиц). Игры двух лиц занимают центральное место во всей теории игр. Основным понятием теории игр для игры двух лиц является обобщение весьма существенной идеи равновесия, которая естественно появляется в играх двух лиц. Что же касается игр n лиц, то одна часть теории игр посвящена играм, в которых сотрудничество между игроками запрещено. В другой части теории игр n лиц предполагается, что игроки могут сотрудничать для взаимной пользы (см. далее в этом параграфе о некооперативных и кооперативных играх).
Классификация по числу игроков и их стратегиям (число стратегий не менее двух, может быть бесконечностью).
Классификация по количеству информации относительно прошлых ходов: игры с полной информацией и неполной информацией. Пусть есть игрок 1 - покупатель и игрок 2 - продавец. Если у игрока 1 нет полной информации о действиях игрока 2, то игрок 1 может и не различить две альтернативы, между которыми ему предстоит сделать выбор. Например, выбирая между двумя видами некоторого товара и не зная о том, что по некоторым признакам товар A хуже товара B , игрок 1 может не видеть различия между альтернативами.
Классификация по принципам деления выигрыша : кооперативные, коалиционные с одной стороны и некооперативные, бескоалиционные с другой стороны. В некооперативной игре , или иначе - бескоалиционной игре , игроки выбирают стратегии одновременно, не зная, какую стратегию выберет второй игрок. Коммуникация между игроками невозможна. В кооперативной игре , или иначе - коалиционной игре , игроки могут объединяться в коалиции и предпринимать коллективные действия, чтобы увеличить свои выигрыши.
Конечная игра двух лиц с нулевой суммой или антогонистическая игра – это стратегическая игра с полной информацией, в которой участвуют стороны с противоположными интересами. Анатагонистическими играми являются матричные игры .

Классический пример из теории игр - дилемма заключённого

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

Если эту стратегическую задачу сформулировать в сроках заключения, то она сводится к следующему:

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

Примеры использования математических средств теории игр

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

Пример формализации некооперативной (бескоалиционной) игры двух лиц

В предыдущем параграфе мы уже рассмотрели пример некооперативной (бескоалиционной) игры (дилемма заключённого). Давайте закрепим наши навыки. Для этого подойдёт также классический сюжет, навеянный "Приключениями Шерлока Холмса" Артура Конан Дойля. Можно, конечно, возразить: пример не из жизни, а из литературы, но ведь Конан Дойль не зарекомендовал себя как писатель-фантаст! Классический ещё и потому, что задание выполнено Оскаром Моргенштерном, как мы уже установили - одним из основателей теории игр.

Пример 1. Будет приведено сокращённое изложение фрагмента одного из "Приключений Шерлока Холмса". Согласно известным понятиям теории игр составить модель конфликтной ситуации и формально записать игру.

Шерлок Холмс намерен отправиться из Лондона в Дувр с дальнейшей целю попасть на континент (европейский), чтобы спастись от профессора Мориарти, который преследует его. Сев в поезд, он увидел на вокзальной платформе профессора Мориарти. Шерлок Холмс допускает, что Мориарти может выбрать особый поезд и обогнать его. У Шерлока Холмса две альтернативы: продолжать поездку до Дувра или сойти на станции Кентерберри, являющейся единственной промежуточной станцией на его маршруте. Мы принимаем, что его противник достаточно разумен, чтобы определить возможности Холмса, поэтому перед ним те же две альтернативы. Оба противника должны выбрать станцию, чтобы сойти на ней с поезда, не зная, какое решение примет каждый из них. Если в результате принятия решения оба окажутся на одной и той же станции, то можно однозначно считать, что Шерлок Холмс будет убит профессором Мориарти. Если же Шерлок Холмс благополучно доберётся до Дувра, то он будет спасён.

Решение. Героев Конан Дойля можем рассматривать как участников игры, то есть игроков. В распоряжении каждого игрока i (i =1,2) две чистые стратегии:

сойти в Дувре (стратегия s i1 (i =1,2) );
сойти на промежуточной станции (стратегия s i2 (i =1,2) )

В зависимости от того, какую из двух стратегий выберет каждый из двух игроков, будет создана особая комбинация стратегий как пара s = (s 1 , s 2 ) .

Каждой комбинации можно поставить в соответствие событие - исход попытки убийства Шерлока Холмса профессором Мориарти. Составляем матрицу данной игры с возможными событиями.

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

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

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

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

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

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

Для игры n обозначим множество всех её игроков как N = {1,2,...,n} Любое непустое подмножество множества N обозначим как Т (включая само N и все подмножества, состоящие из одного элемента). На сайте есть занятие "Множества и операции над множествами ", которое при переходе по ссылке открывается в новом окне.

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

Для двух непустых коалиций из подмножеств T 1 и T 2 аддитивность характеристической функции кооперативной (коалиционной) игры записывается так:

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

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

В среднем их выручка за один вечер составляла:

у скрипача 600 единиц;
у гитариста 700 единиц;
у певицы 900 единиц.

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

скрипач + гитарист зарабатывали 1500 единиц;
скрипач + певица зарабатывали 1800 единиц;
гитарист + певица зарабатывали 1900 единиц;
скрипач + гитарист + певица зарабатывали 3000 единиц.

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

коалиции из одного элемента, каждая из которых состоит из одного игрока - музыканта: T {1} , T {2} , T {3} ;
коалиции из двух элементов: T {1,2} , T {1,3} , T {2,3} ;
коалиция из трёх элементов: T {1,2,3} .

Каждому из игроков присвоим порядковый номер:

скрипач - 1-й игрок;
гитарист - 2-й игрок;
певица - 3-й игрок.

По данным задачи определим характеристическую функцию игры v :

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

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

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

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

Как выполняются условия супераддитивности в этом примере? Определим, как игроки образуют непересекающиеся коалиции T 1 и T 2 . Если часть игроков входят в коалицию T 1 , то все остальные игроки входят в коалицию T 2 и по определению эта коалиция образуется как разность всего множества игроков и множества T 1 . Тогда, если T 1 - коалиция из одного игрока, то в коалиции T 2 будут второй и третий игроки, если в коалиции T 1 будут первый и третий игроки, то коалиция T 2 будет состоять только из второго игрока, и так далее.

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

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

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

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

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

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

Рассмотрим игру, в которой имеются два участника: первый игрок и второй игрок. Пусть в распоряжении первого игрока имеется 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 и оптимальные смешанные стратегии и .

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

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

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

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

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

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

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

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

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

В каждой игре решаются три основных вопроса:

В чем состоит оптимальность поведения каждого из игроков в данной игре?

Реализуемо ли такое понимание оптимальности? Существуют ли соответствующие стратегии?

Если оптимальные стратегии существуют, то, как их найти?

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

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

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

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

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