Примеры с решениями по теории игр. Седловая точка в матричных играх
Содержание 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
Решение матричной игры с использованием графического метода
Решение матричной игры с использованием методов линейного программирования
- Матричная игра. Использование симплексного метода . Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a i) = 2, которая указывает на максимальную чистую стратегию A 1 .
- Пример решения матричной игры методом линейного программирования . Решить матричную игру методом линейного программирования.
Дайте графическое представление, приведите к нормальной форме и найдите точное решение позиционной игры со следующей функцией выигрышей:
1-й ход делает игрок А: он выбирает число x из множества двух чисел.
2-й ход делает игрок В: не зная о выборе игрока А на 1-м ходе, он выбирает число y из множества двух чисел.
3-й ход делает игрок А: он выбирает число z из множества двух чисел, зная значения y, выбранное игроком В на 2-м ходе, но не помня собственного выбора x на 1-м ходе.
Игры с природой
- Статистические игры
Сельскохозяйственное предприятие может реализовать некоторую продукцию:
А1) сразу после уборки;
А2) в зимние месяцы;
А3) в весенние месяцы.
Прибыль зависит от цены реализации в данный период времени, затратами на хранение и возможных потерь. Размер прибыли, рассчитанный для разных состояний-соотношений дохода и издержек (S1, S2 и S3), в течение всего периода реализации, представлен в виде матрицы (млн.руб.) - Фирма производит платья и костюмы, реализация которых зависит от состояния погоды . Затраты фирмы в течение апреля-мая на единицу продукции составят...
- Решение задачи про запасы сырья . За некоторый период времени на предприятии потребление исходного сырья в зависимости от его качества составляет в 1 , в 2 , в 3 и в 4 .
- Стратегии крайнего пессимизма, крайнего оптимизма и оптимизма-пессимизма
Биматричные игры
Дерево решений в теории игр (пример решения задачи).
см. также сборник решений по теории игр (решение матричных игр), типовые задачи по ЭММ (линейное программирование, теория игр).
В городе работают три телекомпании: АВС, СВS и NВС . Эти компании могут начинать программу вечерних новостей в 6.30 или в 7.00. 60% телезрителей предпочитают смотреть вечерние новости в 6.30, а 40% — в 7.00. Наиболее популярна программа вечерних новостей у компании АВС , наименьшей популярностью пользуются новости, подготовленные компанией NВС . Доля телезрителей вечерних новостных программ представлена в таблице (NBС, СВS , АВС)
|
АВС: 6.30 |
|||
|
N ВС |
СВ S |
||
|
АВС: 7.00 |
|||
|
NB С |
СВ S |
||
Найти оптимальные стратегии компаний по времени показа новостных программ
Указание к решению: в игре существует доминируемая стратегия
Лекция 11: Теория игр и принятие решений
Предмет и задачи теории игр
Классическими задачами системного анализа являются игровые задачи принятия решений в условиях риска и неопределенности.
Неопределенными могут быть как цели операции, условия выполнения операции, так и сознательные действия противников или других лиц, от которых зависит успех операции.
Разработаны специальные математические методы, предназначенные для обоснования решений в условиях риска и неопределенности. В некоторых, наиболее простых случаях эти методы дают возможность фактически найти и выбрать оптимальное решение. В более сложных случаях эти методы доставляют вспомогательный материал, позволяющий глубже разобраться в сложной ситуации и оценить каждое из возможных решений с различных точек зрения, и принять решений с учетом его возможных последствий. Одним из важных условий принятия решений в этом случае является минимизация риска.
При решении ряда практических задач исследования операций (в области экологии, обеспечения безопасности жизнедеятельности и т. д.) приходится анализировать ситуации, в которых сталкиваются две (или более) враждующие стороны, преследующие различные цели, причем результат любого мероприятия каждой из сторон зависит от того, какой образ действий выберет противник. Такие ситуации мы можно отнести к конфликтным ситуациям .
Теория игр является математической теорией конфликтных ситуаций, при помощи которой можно выработать рекомендации по рациональному образу действий участников конфликта. Чтобы сделать возможным математический анализ ситуации без учета второстепенных факторов, строят упрощенную, схематизированную модель ситуации, которая называется игрой . игра ведется по вполне определенным правилам, под которыми понимается система условий, регламентирующая возможные варианты действий игроков; объем информации каждой стороны о поведении другой; результат игры, к которому приводит каждая данная совокупность ходов.
Результат игры (выигрыш или проигрыш) вообще не всегда имеет количественное выражение, но обычно можно, хотя бы условно, выразить его числовым значением.
Ход — выбор одного из предусмотренных правилами игры действий и его осуществление. Ходы делятся на личные и случайные. Личным ходом называется сознательный выбор игроком одного из возможных вариантов действий и его осуществление. Случайным ходом называется выбор из ряда возможностей, осуществляемый не решением игрока, а каким-либомеханизмом случайного выбора (бросание монеты, выбор карты из перетасованной колоды и т. п.). Для каждого случайного хода правила игры определяют распределение вероятностей возможных исходов. Игра может состоять только их личных или только из случайных ходов, или из их комбинации. Следующим основным понятием теории игр является понятие стратегии. Стратегия — это априори принятая игроком система решений (вида «если — то»), которых он придерживается во время ведения игры, которая может быть представлена в виде алгоритма и выполняться автоматически.
Целью теории игр является выработка рекомендаций для разумного поведения игроков в конфликтной ситуации, т. е. определение «оптимальной стратегии» для каждого из них. Стратегия, оптимальная по одному показателю, необязательно будет оптимальной по другим. Сознавая эти ограничения и поэтому не придерживаясь слепо рекомендаций, полученных игровыми методами, можно все же разумно использовать математический аппарат теории игр для выработки, если не в точности оптимальной, то, во всяком случае «приемлемой» стратегии.
Игры можно классифицировать: по количеству игроков, количеству стратегий, характеру взаимодействия игроков, характеру выигрыша, количеству ходов, состоянию информации и т.д. .
В зависимости от количества игроков различают игры двух и n игроков. Первые из них наиболее изучены. Игры трех и более игроков менее исследованы из-за возникающих принципиальных трудностей и технических возможностей получения решения.
В зависимости от числа возможных стратегий игры делятся на «конечные » и «бесконечные ».
Игра называется конечной, если у каждого игрока имеется только конечное число стратегий, и бесконечной, если хотя бы у одного из игроков имеется бесконечное число стратегий.
По характеру взаимодействия игры делятся на бескоалиционные: игроки не имеют права вступать в соглашения, образовывать коалиции; коалиционные (кооперативные) — могут вступать в коалиции.
В кооперативных играх коалиции заранее определены.
По характеру выигрышей игры делятся на: игры с нулевой суммой (общий капитал всех игроков не меняется, а перераспределяется между игроками; сумма выигрышей всех игроков равна нулю) и игры с ненулевой суммой.
По виду функций выигрыша игры делятся на: матричные, биматричные, непрерывные, выпуклые и др.
Матричная игра — это конечная игра двух игроков с нулевой суммой, в которой задается выигрыш игрока 1 в виде матрицы (строка матрицы соответствует номеру применяемой стратегии игрока 1, столбец — номеру применяемой стратегии игрока на пересечении строки и столбца матрицы находится выигрыш игрока 1, соответствующий применяемым стратегиям).
Для матричных игр доказано, что любая из них имеет решение и оно может быть легко найдено путем сведения игры к задаче линейного программирования.
Биматричная игра — это конечная игра двух игроков с ненулевой суммой, в которой выигрыши каждого игрока задаются матрицами отдельно для соответствующего игрока (в каждой матрице строка соответствует стратегии игрока 1, столбец — стратегии игрока 2, на пересечении строки и столбца в первой матрице находится выигрыш игрока 1, во второй матрице — выигрыш игрока)
Непрерывной считается игра, в которой функция выигрышей каждого игрока является непрерывной. Доказано, что игры этого класса имеют решения, однако не разработано практически приемлемых методов их нахождения.
Если функция выигрышей является выпуклой, то такая игра называется выпуклой . Для них разработаны приемлемые методы решения, состоящие в отыскании чистой оптимальной стратегии (определенного числа) для одного игрока и вероятностей применения чистых оптимальных стратегий другого игрока. Такая задача решается сравнительно легко.
Запись матричной игры в виде платежной матрицы
Рассмотрим конечную игру, в которой первый игрок А имеет m стратегий, а второй игрок B-n стратегий. Такая игра называется игрой m×n. Обозначим стратегии A 1 , А 2 , ..., А m ; и В 1 , В 2 , ..., В n . Предположим, что каждая сторона выбрала определенную стратегию: A i или B j . Если игра состоит только из личных ходов, то выбор стратегий однозначно определяет исход игры — выигрыш одной из сторон a ij . Если игра содержит кроме личных случайные ходы, то выигрыш при паре стратегий A i и B является случайной величиной, зависящей от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша, которое также обозначается за a ij .
Предположим, что нам известны значения a ij при каждой паре стратегий. Эти значения можно записать в виде прямоугольной таблицы (матрицы), строки которой соответствуют стратегиям A i , а столбцы — стратегиям B j .
Тогда, в общем виде матричная игра может быть записана следующей платежной матрицей:
| B 1 | B 2 | ... | B n | |
|---|---|---|---|---|
| A 1 | a 11 | a 12 | ... | a 1n |
| A 2 | a 21 | a 22 | ... | a 2n |
| ... | ... | ... | ... | ... |
| A m | a m1 | a m2 | ... | a mn |
Таблица — Общий вид платежной матрицы матричной игры
где A i — названия стратегий игрока 1, B j — названия стратегий игрока 2, a ij — значения выигрышей игрока 1 при выборе им i–й стратегии, а игроком 2 — j-й стратегии. Поскольку данная игра является игрой с нулевой суммой, значение выигрыша для игрока 2 является величиной, противоположенной по знаку значению выигрыша игрока 1.
Понятие о нижней и верхней цене игры. Решение игры в чистых стратегиях
Каждый из игроков стремится максимизировать свой выигрыш с учетом поведения противодействующего ему игрока. Поэтому для игрока 1 необходимо определить минимальные значения выигрышей в каждой из стратегий, а затем найти максимум из этих значений, то есть определить величину
V н = max i min j a ij
или найти минимальные значения по каждой из строк платежной матрицы, а затем определить максимальное из этих значений. Величина V н называется максимином матрицы или нижней ценой игры . Та стратегия игрока, которая соответствует максимину V н называется максиминной стратегией.
Очевидно, если мы будем придерживаться максиминной стратегии, то нам при любом поведении противника гарантирован выигрыш, не меньший V н. Поэтому величина V н — это тот гарантированный минимум, который мы можем себе обеспечить, придерживаясь своей наиболее осторожной стратегии.
Величина выигрыша игрока 1 равна, по определению матричной игры, величине проигрыша игрока Поэтому для игрока 2 необходимо определить значение
V в = min j max i a ij
Или найти максимальные значения по каждому из столбцов платежной матрицы, а затем определить минимальное из этих значений. Величина V в называется минимаксом матрицы, верхней ценой игры или минимаксным выигрышем. Соответствующая выигрышу стратегия противника называется его минимаксной стратегией. Придерживаясь своей наиболее осторожной минимаксной стратегии, противник гарантирован, что в любом случае он проиграет не больше V в.
В случае, если значения V н и V в не совпадают, при сохранении правил игры (коэффициентов a ij) в длительной перспективе, выбор стратегий каждым из игроков оказывается неустойчивым. Устойчивость он приобретает лишь при равенстве V н = V в = V. В этом случае говорят, что игра имеет решение в чистых стратегиях , а стратегии, в которых достигается V — оптимальными чистыми стратегиями . Величина V называется чистой ценой игры .
Например, в матрице:
| B 1 | B 2 | B 3 | B 4 | Min j | |
|---|---|---|---|---|---|
| A 1 | 17 | 16 | 15 | 14 | 14 |
| A 2 | 11 | 18 | 12 | 13 | 11 |
| A 3 | 18 | 11 | 13 | 12 | 11 |
| Max i | 18 | 18 | 15 | 14 |
Таблица — Платежная матрица, в которой существует решение в чистых стратегиях
существует решение в чистых стратегиях. При этом для игрока 1 оптимальной чистой стратегией будет стратегия A 1 , а для игрока 2 — стратегия B 4 .
В матрице решения в чистых стратегиях не существует, так как нижняя цена игры достигается в стратегии A 1 и ее значение равно 12, в то время как верхняя цена игры достигается в стратегии B 4 и ее значение равно 13.
| B 1 | B 2 | B 3 | B 4 | Min j | |
|---|---|---|---|---|---|
| A 1 | 17 | 16 | 15 | 12 | 12 |
| A 2 | 11 | 18 | 12 | 13 | 11 |
| A 3 | 18 | 11 | 13 | 12 | 11 |
| Max i | 18 | 18 | 15 | 13 |
Таблица — Платежная матрица, в которой не существует решения в чистых стратегиях
Уменьшение порядка платежной матрицы
Порядок платежной матрицы (количество строк и столбцов) может быть уменьшен за счет исключения доминируемых и дублирующих стратегий.
Стратегия K* называется доминируемой стратегией K**, если при любом варианте поведения противодействующего игрока выполняется соотношение
A k* < A k** ,
где A k* и A k** — значения выигрышей при выборе игроком, соответственно, стратегий K* и K**.
В случае, если выполняется соотношение
стратегия K* называется дублирующей по отношению к стратегии K**.
Например, в матрице с доминируемыми и дублирующими стратегиями стратегия A 1 является доминируемой по отношению к стратегии A 2 , стратегия B 6 является доминируемой по отношению к стратегиям B 3 , B 4 и B 5 , а стратегия B 5 является дублирующей по отношению к стратегии B 4 .
| B 1 | B 2 | B 3 | B 4 | B 5 | B 6 | |
|---|---|---|---|---|---|---|
| A 1 | 1 | 2 | 3 | 4 | 4 | 7 |
| A 2 | 7 | 6 | 5 | 4 | 4 | 8 |
| A 3 | 1 | 8 | 2 | 3 | 3 | 6 |
| A 4 | 8 | 1 | 3 | 2 | 2 | 5 |
Таблица — Платежная матрица с доминируемыми и дублирующими стратегиями
Данные стратегии не будут выбраны игроками, так как являются заведомо проигрышными и удаление этих стратегий из платежной матрицы не повлияет на определение нижней и верхней цены игры, описанной данной матрицей.
Множество недоминируемых стратегий, полученных после уменьшения размерности платежной матрицы, называется еще множеством Парето.
Примеры игр
1. Игра «Цыпленок»
Игра «Цыпленок» заключается в том, что игроки вступают во взаимодействие, которое ведет в нанесению серьезного вреда каждому из них, пока один из игроков не выйдет из игры. Пример использования этой игры — взаимодействие автотранспортный средств, например, ситуации, когда два автомобиля идут навстречу друг другу, и тот, который первым сворачивает в сторону, считается «слабаком» или «цыпленком». Смысл игры заключается в создании напряжения, которое бы привело к устранению игрока. Подобная ситуация часто встречается в среде подростков или агрессивно настроенных молодых людей, хотя иногда несет в себе меньший риск. Еще одно из применений этой игры — ситуация, в которой две политические партии вступают в контакт, при котором они не могут ничего выиграть, и только гордость заставляет их сохранять противостояние. Партии медлят с уступками до тех пор, пока не дойдут до финальной точки. Возникающее психологическое напряжение может привести одного из игроков к неправильной стратегии поведения: если никто из игроков не уступает, то столкновение и фатальная развязка неизбежны.
Платежная матрица игры выглядит следующей:
| Уступить | Не уступать | |
|---|---|---|
| Уступить | 0, 0 | -1, +1 |
| Не уступать | +1, -1 | -100, -100 |
2. Игра «коршун и голубь»
Игра «коршун и голубь» является биологическим примером игры. В этой версии двое игроков, обладающих неограниченными ресурсами, выбирают одну из двух стратегий поведения. Первая («голубь») заключается в том, что игрок демонстрирует свою силу, запугивая противника, а вторая («коршун») — в том, что игрок физически атакует противника. Если оба из игроков выбирают стратегию «коршуна», они сражаются, наносф друг другу увечья. Если один из игроков выбирает стратегию «коршуна», а второй «голубя» — то первый побеждает второго. В случае, если оба игрока — «голуби», то соперники приходит к компромиссу, получая выигрыш, который оказывается меньше, чем выигрыш «коршуна», побеждающего «голубя», как это следует из платежной матрицы этой игры.
Здесь V — цена соглашения, C — цена конфликта, причем V В игре «коршун и голубь» есть три точки равновесия по Нэшу: «Дилемма заключенного» — одна из наиболее распространенных конфликтных ситуаций, рассматриваемая в теории игр. Классическая «дилемма заключенного» звучит следующим образом: двое подозреваемых, A и B, находятся в разных камерах. Следователь, навещая их поодиночке, предлагает сделку следующего содержания: если один из них будет свидетельствовать против другого, а второй будет молчать, то первый заключенный будет освобожден, а второго осудят на 10 лет. Если оба будут молчать, то отсидят по 6 месяцев. Если оба предадут друг друга, то каждый получит по 2 года. Каждый из заключенных должен принять решение: предать подельника или молчать, не зная о том, какое решение принял другой. Дилемма: какое решение примут заключенные? Платежная матрица игры: В данном случае, результат базируется на решении каждого из заключенных. Положение игроков осложняется тем, что они не знают о том, какое решение принял другой, и тем, что они не доверяют друг другу. Наилучшей стратегией игроков будет кооперация, при которой оба молчат, и получают максимальный выигрыш (меньший срок), каждое другое решение будет менее выигрышным. Проанализируем «дилемму заключенного», перейдя для наглядности к платежной матрице канонического вида: Согласно этой матрице, цена взаимного отказа от кооперации (S) составляет по 1 баллу для каждого из игроков, цена за кооперацию (R) — по 3 балла, а цена соблазна предать другого (T) составляет 5 баллов. Можем записать следующее неравенство: T > R > S. При повторении игры несколько раз, выбор кооперации превосходит соблазн предать и получить максимальный выигрыш: 2 R > T + S. Равновесие по Нэшу — это ситуация, когда ни у одного игрока нет стимулов изменять свою стратегию при данной стратегии другого игрока (другой фирмы), позволяющая игрокам достичь компромиссного решения. Определение равновесия по Нэшу и его существование определяется следующим образом. Пусть (S, f) — это игра, в которой S — множество стратегий, f — множество выигрышей. Когда каждый из игроков i ∈ {1, ..., n} выбирает стратегию x i &isin S, где x = (x 1 , ..., x n), тогда игрок i получает выигрыш f i (x). Выигрыш зависит от стратегии, выбранной всеми игроками. Стратегия x* ∈ S является равновесием по Нэшу, если никакое отклонение от нее каким-то одним игроком не приносит ему прибыль, то есть, для всех i выполняется следующее неравенство: f i (x*) ≥ f i (x i , x* -i) Например, игра «дилемма заключенного» имеет одно равновесие по Нэшу — ситуацию, когда оба заключенных предают друг друга. Проще всего определить равновесие по Нэшу можно по платежной матрице, особенно в случаях, когда в игре участвуют два игрока, имеющие в арсенале более двух стратегий. Так как в этом случае формальный анализ будет достаточно сложным, применяется мнемоническое правило, которое заключается в следующем: ячейка платежной матрицы представляет собой равновесие по Нэшу, если первое число, стоящее в ней, является максимальным среди всех значений, представленных в столбцах, а второе число, стоящее в ячейке — максимальное число среди всех строк. Например, применим это правило для матрицы 3x3: Точки равновесия по Нэшу: (B,A), (A,B) и (C,C). Indeed, for cell (B,A), так как 40 — максимальное значение в первом столбце, 25 максимальное значение во втором ряду. Для ячейки (A,B) 25 — это максимальное значение во втором столбце, 40 — максимальное значение во втором ряду. То же самое и для ячейки (C,C). Рассмотрим пример игры в загрязнения (окружающей среды). Здесь объектом нашего внимания станет такой вид побочных эффектов производства, как загрязнение. Если бы фирмы никогда и никого не спрашивали о том, как им поступить, любая из них скорее предпочла бы создавать загрязнения, чем устанавливать дорогостоящие очистители. Если же какая-нибудь фирма решилась бы уменьшить вредные выбросы, то издержки, а, следовательно, и цены на ее продукцию, возросли бы, а спрос бы упал. Вполне возможно, эта фирма просто обанкротилась бы. Живущие в жестоком мире естественного отбора, фирмы скорее предпочтут оставаться в условиях равновесия по Нэшу (ячейка D), при котором не нужно расходовать средства на очистные сооружения и технологии. Ни одной фирме не удастся повысить прибыль, уменьшая загрязнение. Таблица — Платежная матрица игры в загрязнение окружающей среды. Вступив в экономическую игру, каждая неконтролируемая государством и максимизирующая прибыль сталелитейная фирма будет производить загрязнения воды и воздуха. Если какая-либо фирма попытается очищать свои выбросы, то тем самым она будет вынуждена повысить цены и потерпеть убытки. Некооперативное поведение установит равновесие по Нэшу в условиях высоких выбросов. Правительство может предпринять меры с тем, чтобы равновесие переместилось в ячейку А. В этом положении загрязнение будет незначительным, прибыли же останутся теми же. Игры загрязнения - один из случаев того, как механизм действия «невидимой руки» не срабатывает. Это ситуация, когда равновесие по Нэшу неэффективно. Иногда подобные неконтролируемые игры становятся угрожающими, и здесь может вмешаться правительство. Установив систему штрафов и квот на выбросы, правительство может побудить фирмы выбрать исход А, соответствующий низкому уровню загрязнения. Фирмы зарабатывают ровно столько же, сколько и прежде, при больших выбросах, мир же становится несколько чище. Рассмотрим пример решения матричной игры в чистых стратегиях, в условиях реальной экономики, в ситуации борьбы двух предприятий за рынок продукции региона. Два предприятия производят продукцию и поставляют ее на рынок региона. Они являются единственными поставщиками продукции в регион, поэтому полностью определяют рынок данной продукции в регионе. Каждое из предприятий имеет возможность производить продукцию с применением одной из трех различных технологий. В зависимости от экологичности технологического процесса и качества продукции, произведенной по каждой технологии, предприятия могут установить цену единицы продукции на уровне 10, 6 и 2 денежных единиц соответственно. При этом предприятия имеют различные затраты на производство единицы продукции. Таблица — Затраты на единицу продукции, произведенной на предприятиях региона (д.е.). В результате маркетингового исследования рынка продукции региона была определена функция спроса на продукцию: Y = 6 - 0.5⋅X, где Y — количество продукции, которое приобретет население региона (тыс. ед.), а X — средняя цена продукции предприятий, д.е. Данные о спросе на продукцию в зависимости от цен реализации приведены в таблице: Цена реализации 1 ед. продукции, д.е. Средняя цена реализации 1 ед. продукции, д.е. Спрос на продукцию, тыс. ед. Таблица — Спрос на продукцию в регионе, тыс. ед. Значения Долей продукции предприятия 1, приобретенной населением, зависят от соотношения цен на продукцию предприятия 1 и предприятия В результате маркетингового исследования эта зависимость установлена и значения вычислены: Таблица — Доля продукции предприятия 1, приобретаемой населением в зависимости от соотношения цен на продукцию По условию задачи на рынке региона действует только 2 предприятия. Поэтому долю продукции второго предприятия, приобретенной населением, в зависимости от соотношения цен на продукцию можно определить как единица минус доля первого предприятия. Стратегиями предприятий в данной задаче являются их решения относительно технологий производства продукции. Эти решения определяют себестоимость и цену реализации единицы продукции. В задаче необходимо определить: Прибыль предприятия в данной задаче зависит: Таким образом, значения разницы прибыли предприятий, соответствующие коэффициентам платежной матрицы, необходимо определить по формуле: D = p⋅(S⋅R1 - S⋅C1) - (1 - p)⋅(S⋅R2 - S⋅C2), где D — значение разницы прибыли от производства продукции предприятия 1 и предприятия p — доля продукции предприятия 1, приобретаемой населением региона; S — количество продукции, приобретаемой населением региона; R1 и R2 — цены реализации единицы продукции предприятиями 1 и C1 и C2 — полная себестоимость единицы продукции, произведенной на предприятиях 1 и Вычислим один из коэффициентов платежной матрицы. Пусть, например, предприятие 1 принимает решение о производстве продукции в соответствии с технологией III, а предприятие 2 — в соответствии с технологией II. Тогда цена реализации единицы. продукции для предприятия 1 составит 2 д.е. при себестоимости единицы. продукции 1,5 д.е. Для предприятия 2 цена реализации единицы. продукции составит 6 д.е. при себестоимости 4 д.е.. Количество продукции, которое население региона приобретет при средней цене 4 д.е., равно 4 тыс. ед. (таблица 1). Доля продукции, которую население приобретет у предприятия 1, составит 0,85, а у предприятия 2 — 0,15 (табл. 1.3). Вычислим коэффициент платежной матрицы a 32 по формуле: a 32 = 0,85⋅(4⋅2 - 4×1,5) - 0,15⋅(4⋅6 - 4⋅4) = 0,5 тыс. ед. где i=3 — номер технологии первого предприятия, а j=2 — номер технологии второго предприятия. Аналогично вычислим все коэффициенты платежной матрицы. В платежной матрице стратегии A 1 — A 3 – представляют собой решения о технологиях производства продукции предприятием 1, стратегии B 1 – B 3 — решения о технологиях производства продукции предприятием 2, коэффициенты выигрышей — разницу прибыли предприятия 1 и предприятия Таблица — Платежная матрица в игре «Борьба двух предприятий». В данной матрице нет ни доминируемых, ни дублирующих стратегий. Это значит, что для обоих предприятий нет заведомо невыгодных технологий производства продукции. Определим минимальные элементы строк матрицы. Для предприятия 1 каждый из этих элементов имеет значение минимально гарантированного выигрыша при выборе соответствующей стратегии. Минимальные элементы матрицы по строкам имеют значения: 0,17, -1,5, 0,4. Определим максимальные элементы столбцов матрицы. Для предприятия 2 каждый из этих элементов также имеет значение минимально гарантированного выигрыша при выборе соответствующей стратегии. Максимальные элементы матрицы по столбцам имеют значения: 3, 0,62, 0,4. Нижняя цена игры в матрице равна 0,4. Верхняя цена игры также равна 0,4. Таким образом, нижняя и верхняя цена игры в матрице совпадают. Это значит, что имеется технология производства продукции, которая является оптимальной для обоих предприятий в условиях данной задачи. Эта технология III, которая соответствует стратегиям A 3 предприятия 1 и B 3 предприятия Стратегии A 3 и B 3 — чистые оптимальные стратегии в данной задаче. Значение разницы прибыли предприятия 1 и предприятия 2 при выборе чистой оптимальной стратегии положительно. Это означает, что предприятие 1 выиграет в данной игре. Выигрыш предприятия 1 составит 0,4 тыс. д.е. При этом на рынке будет реализовано 5 тыс. ед. продукции (реализация равна спросу на продукцию, таблица 1).. Оба предприятия установят цену за единицу продукции в 2 д.е. При этом для первого предприятия полная себестоимость единицы продукции составит 1,5 д.е., а для второго — 1 д.е. Предприятие 1 окажется в выигрыше лишь за счет высокой доли продукции, которую приобретет у него население. ЛПР определяет наиболее выгодную стратегию в зависимости от целевой установки, которую он реализует в процессе решения задачи. Результат решения задачи ЛПР определяет по одному из критериев принятия решения
. Для того, чтобы прийти к однозначному и по возможности наиболее выгодному варианту решению, необходимо ввести оценочную (целевую) функцию. При этом каждой стратегии ЛПР (A i) приписывается некоторый результат W i , характеризующий все последствия этого решения. Из массива результатов принятия решений ЛПР выбирает элемент W, который наилучшим образом отражает мотивацию его поведения. В зависимости от условий внешней среды и степени информативности ЛПР производится следующая классификация задач принятия решений: Использование критерия ожидаемого значения обусловлено стремлением максимизировать ожидаемую прибыль (или минимизировать ожидаемые затраты). Использование ожидаемых величин предполагает возможность многократного решения одной и той же задачи, пока не будут получены достаточно точные расчетные формулы. Математически это выглядит так: пусть Х — случайная величина с математическим ожиданием MX и дисперсией DX. Если x 1 , x 2 , ..., x n — значения случайной величины (с.в.) X, то среднее арифметическое их (выборочное среднее) значений x^=(x 1 +x 2 +...+x n)/n имеет дисперсию DX/n. Таким образом, когда n→∞ DX/n→∞ и X→MX. Другими словами при достаточно большом объеме выборки разница между средним арифметическим и математическим ожиданием стремится к нулю (так называемая предельная теорема теории вероятности). Следовательно, использование критерия ожидаемое значение справедливо только в случае, когда одно и тоже решение приходится применять достаточно большое число раз. Верно и обратное: ориентация на ожидания будет приводить к неверным результатам, для решений, которые приходится принимать небольшое число раз. Пример 1
. Требуется принять решение о том, когда необходимо проводить профилактический ремонт ПЭВМ, чтобы минимизировать потери из-за неисправности. В случае если ремонт будет производится слишком часто, затраты на обслуживание будут большими при малых потерях из-за случайных поломок. Так как невозможно предсказать заранее, когда возникнет неисправность, необходимо найти вероятность того, что ПЭВМ выйдет из строя в период времени t. В этом и состоит элемент »риска». Математически это выглядит так: ПЭВМ ремонтируется индивидуально, если она остановилась из-за поломки. Через T интервалов времени выполняется профилактический ремонт всех n ПЭВМ. Необходимо определить оптимальное значение m, при котором минимизируются общие затраты на ремонт неисправных ПЭВМ и проведение профилактического ремонта в расчете на один интервал времени. Пусть р t — вероятность выхода из строя одной ПЭВМ в момент t, а n t — случайная величина, равная числу всех вышедших из строя ПЭВМ в тот же момент. Пусть далее С 1 – затраты на ремонт неисправной ПЭВМ и С 2 — затраты на профилактический ремонт одной машины. Применение критерия ожидаемого значения в данном случае оправдано, если ПЭВМ работают в течение большого периода времени. При этом ожидаемые затраты на один интервал составят ОЗ = (C 1 ∑M(n t)+C 1 n)/T, где M(n t) — математическое ожидание числа вышедших из строя ПЭВМ в момент t. Так как n t имеет биномиальное распределение с параметрами (n, p t), то M(n t) = np t . Таким образом ОЗ = n(C 1 ∑p t +C 2)/T. Необходимые условия оптимальности T * имеют вид: ОЗ (T * -1) ≥ ОЗ (T *), ОЗ (T * +1) ≥ ОЗ (T *). Следовательно, начиная с малого значения T, вычисляют ОЗ( T), пока не будут удовлетворены необходимые условия оптимальности. Пусть С 1 = 100; С 2 = 10; n = 50. Значенияp t имеют вид: T * →3, ОЗ(Т *)→366.7 Следовательно профилактический ремонт необходимо делать через T * =3 интервала времени. Критерий ожидаемого значения можно модифицировать так, что его можно будет применить и для редко повторяющихся ситуаций. Если х — с. в. с дисперсией DX, то среднее арифметическое x^ имеет дисперсию DX/n, где n — число слагаемых в x^. Следовательно, если DX уменьшается, и вероятность того, что x^ близко к MX, увеличивается. Следовательно, целесообразно ввести критерий, в котором максимизация ожидаемого значения прибыли сочетается с минимизацией ее дисперсии. Пример 2
. Применим критерий «ожидаемое значение — дисперсия» для примера 1. Для этого необходимо найти дисперсию затрат за один интервал времени, т.е. дисперсию з Т =(C 1 ∑n t +C 2 n)/T Т.к. n t , t = {1, T-1} — с.в., то з Т также с.в. С.в. n t имеет биномиальное распределение с M(n t) = np t и D(n t) = np t (1–p t). Следовательно, D(з Т) = D((C 1 ∑n t +C 2 n)/T) = (C 1 /T) 2 D(∑n t) = = (C 1 /T) 2 ∑Dn t = (C 1 /T) 2 ∑np t (1-p t) = (C 1 /T) 2 {∑p t - ∑p t 2 }, где С 2 n = const. Из примера 1 следует, что М(з Т) = М(з(Т)). Следовательно искомым критерием будет минимум выражения М(з(Т)) + к D(з Т). Замечание
. Константу «к» можно рассматривать как уровень не склонности к риску
, т.к. «к» определяет «степень возможности» дисперсии Д(з Т) по отношению к математическому ожиданию. Например, если предприниматель, особенно остро реагирует на большие отрицательные отклонения прибыли вниз от М(з(Т)), то он может выбрать «к» много больше 1. Это придает больший вес дисперсии и приводит к решению, уменьшающему вероятность больших потерь прибыли. При к=1 получаем задачу M(з(T))+D(з(T)) = n { (C 1 /T+C 1 2 /T 2)∑p t - C 1 2 /T 2 ∑p t 2 + C 2 /T } По данным из примера 1 можно составить следующую таблицу Из таблицы видно, что профилактический ремонт необходимо делать в течение каждого интервала Т * =1. Критерий предельного уровня не дает оптимального решения, максимизирующего, например, прибыль или минимизирующего затраты. Скорее он соответствует определению приемлемого
способа действий. Пример 3
. Предположим, что величина спроса x в единицу времени (интенсивность спроса) на некоторый товар задается непрерывной функцией распределения f(x). Если запасы в начальный момент невелики, в дальнейшем возможен дефицит товара. В противном случае к концу рассматриваемого периода запасы нереализованного товара могут оказаться очень большими. В обоих случаях возможны потери. Т.к. определить потери от дефицита очень трудно, ЛПР может установить необходимый уровень запасов таким образом, чтобы величина ожидаемого
дефицита не превышала A 1 единиц, а величина ожидаемых
излишков не превышала A 2 единиц. Иными словами, пусть I — искомый уровень запасов. Тогда ожидаемый дефицит = ∫(x-I)f(x)dx ≤ A 1 , ожидаемые излишки = ∫(I-x)f(x)dx ≤ A 2 . При произвольном выборе A 1 и A 2 указанные условия могут оказаться противоречивыми. В этом случае необходимо ослабить одно из ограничений, чтобы обеспечить допустимость. Пусть, например, f(x) = 20/x 2 , 10≤x≤20, f(x) = 0, x≤10 и x≥20. ∫(x-I)f(x)dx = ∫(x-I)(20/x 2)dx = 20(ln(20/I) + I/20 – 1) ∫(I-x)f(x)dx = ∫(I-x)(20/x 2)dx = 20(ln(10/I) + I/10 – 1) Применение критерия предельного уровня приводит к неравенствам ln(I) - I/20 ≥ ln(20) – A 1 /20 – 1 = 1,996 - A 1 /20 ln(I) - I/10 ≥ ln(10) – A 2 /20 – 1 = 1,302 - A 2 /20 Предельные значения A 1 и A 2 должны быть выбраны так, что бы оба неравенства выполнялись хотя бы для одного значения I. Например, если A 1 = 2 и A 2 = 4, неравенства принимают вид ln(I) - I/20 ≥ 1,896 ln(I) - I/10 ≥ 1,102 Значение I должно находиться между 10 и 20, т.к. именно в этих пределах изменяется спрос. Из таблицы видно, что оба условия выполняются для I, из интервала (13,17) Любое из этих значений удовлетворяет условиям задачи. Будем предполагать, что лицу, принимающему решение не противостоит разумный
противник. Данные, необходимо для принятия решения в условии неопределенности, обычно задаются в форме матрицы, строки которой соответствуют возможным действиям, а столбцы — возможным состояниям системы. Пусть, например, из некоторого материала требуется изготовить изделие, долговечность которого при допустимых затратах невозможно определить. Нагрузки считаются известными. Требуется решить, какие размеры должно иметь изделие из данного материала. Варианты решения таковы: Е 1 — выбор размеров из соображений максимальной долговечности; Е m — выбор размеров из соображений минимальной долговечности; E i — промежуточные решения. Условия требующие рассмотрения таковы: F 1 — условия, обеспечивающие максимальной долговечность; F n — условия, обеспечивающие min долговечность; F i — промежуточные условия. Под результатом решения e ij = е(E i ; F j) здесь можно понимать оценку, соответствующую варианту E i и условиям F j и характеризующие прибыль, полезность или надежность. Обычно мы будем называть такой результат полезностью решения
. Тогда семейство (матрица) решений ||e ij || имеет вид: Чтобы прийти к однозначному и по возможности наивыгоднейшему варианту решению необходимо ввести оценочную (целевую) функцию. При этом матрица решений ||e ij || сводится к одному столбцу. Каждому варианту E i приписывается, т.о., некоторый результат e ir , характеризующий, в целом, все последствия этого решения. Такой результат мы будем в дальнейшем обозначать тем же символом e ir . Правило выбора решения в соответствии с минимаксным критерием (ММ-критерием) можно интерпретировать следующим образом: матрица решений дополняется еще одним столбцом из наименьших результатов e ir каждой строки. Необходимо выбрать те варианты в строках которых стоят наибольшее значение e ir этого столбца. Выбранные т.о. варианты полностью исключают риск. Это означает, что принимающий решение не может столкнуться с худшим результатом, чем тот, на который он ориентируется. Это свойство позволяет считать ММ-критерий одним из фундаментальных. Применение ММ-критерия бывает оправдано, если ситуация, в которой принимается решение следующая: Обозначим через q i — вероятность появления внешнего состояния F j . Соответствующее правило выбора можно интерпретировать следующим образом: матрица решений дополняется еще одним столбцом содержащим математическое ожидание значений каждой из строк. Выбираются те варианты, в строках которых стоит наибольшее значение e ir этого столбца. При этом предполагается, что ситуация, в которой принимается решение, характеризуется следующими обстоятельствами: При достаточно большом количестве реализаций среднее значение постепенно стабилизируется. Поэтому при полной (бесконечной) реализации какой-либо риск практически исключен. Т.о. критерий Байеса-Лапласа (B-L-критерий) более оптимистичен, чем минимаксный критерий, однако он предполагает большую информированность и достаточно длительную реализацию. a ij:= max i (e ij) - e ij e ir:= max i (a ij) = max j (max i (e ij) - e ij) Величину a ij можно трактовать как максимальный дополнительный выигрыш, который достигается, если в состоянии F j вместо варианта E i выбирать другой, оптимальный для этого внешнего состояния вариант. Величину a ij можно интерпретировать и как потери (штрафы) возникающие в состоянии F j при замене оптимального для него варианта на вариант E i . В последнем случае e ir представляет собой максимально возможные (по всем внешним состояниям F j , j = {1,n}) потери в случае выбора варианта E i . Соответствующее критерию Сэвиджа правило выбора теперь трактуется так: Требования, предъявляемые к ситуации, в которой принимается решение, совпадают с требованием к ММ-критерию. Из требований, предъявляемых к рассмотренным критериям становится ясно, что в следствии их жестких исходных позиций они применимы только для идеализированных практических решений. В случае, когда возможна слишком сильная идеализация, можно применять одновременно поочередно различные критерии. После этого среди нескольких вариантов ЛПР волевым методом выбирает окончательное решение. Такой подход позволяет, во-первых, лучше проникнуть во все внутренние связи проблемы принятия решений и, во-вторых, ослабляет влияние субъективного фактора. Пример
. При работе ЭВМ необходимо периодически приостанавливать обработку информации и проверять ЭВМ на наличие в ней вирусов. Приостановка в обработке информации приводит к определенным экономическим издержкам. В случае же если вирус вовремя обнаружен не будет, возможна потеря и некоторой части информации, что приведет и еще к большим убыткам. Варианты решения таковы: Е 1 — полная проверка; Е 2 — минимальная проверка; Е 3 — отказ от проверки. ЭВМ может находиться в следующих состояниях: F 1 — вирус отсутствует; F 2 — вирус есть, но он не успел повредить информацию; F 3 — есть файлы, нуждающиеся в восстановлении. Результаты, включающие затраты на поиск вируса и его ликвидацию, а также затраты, связанные с восстановлением информации имеют вид: Согласно ММ-критерию следует проводить полную проверку. Критерий Байеса-Лапласа, в предположении, что все состояния машины равновероятны. Пример специально подобран так, что каждый критерий предлагает новое решение. Неопределенность состояния, в котором проверка застает ЭВМ, превращается в неясность, какому критерию следовать. Поскольку различные критерии связаны с различными условиями, в которых принимается решение, лучшее всего для сравнительной оценки рекомендации тех или иных критериев получить дополнительную информацию о самой ситуации. В частности, если принимаемое решение относится к сотням машин с одинаковыми параметрами, то рекомендуется применять критерий Байеса-Лапласа. Если же число машин не велико, лучше пользоваться критериями минимакса или Севиджа. Стараясь занять наиболее уравновешенную позицию, Гурвиц предположил оценочную функцию, которая находится где-то между точкой зрения крайнего оптимизма и крайнего пессимизма: max i (e ir) = { C⋅min j (e ij) + (1-C)⋅max j (e ij) }, где С — весовой множитель. Правило выбора согласно критерию Гурвица, формируется следующим образом: матрица решений ||e ij || дополняется столбцом, содержащим среднее взвешенное наименьшего и наибольшего результатов для каждой строки. Выбираются только те варианты, в строках которых стоят наибольшие элементыe e ir этого столбца. При С=1 критерий Гурвица превращается в ММ-критерий. При С = 0 он превращается в критерий «азартного игрока» max i (e ir) = max i (max j (e ij)), т.е. мы становимся на точку зрения азартного игрока, делающего ставку на то, что «выпадет» наивыгоднейший случай. В технических приложениях сложно выбрать весовой множитель С, т.к. трудно найти количественную характеристику для тех долей оптимизма и пессимизма, которые присутствуют при принятии решения. Поэтому чаще всего С:=1/2. Критерий Гурвица применяется в случае, когда: Этот критерий опирается одновременно на ММ-критерий и критерий Баеса-Лапласа. С помощью параметра n выражается степень доверия к используемому распределений вероятностей. Если доверие велико, то доминирует критерий Баеса-Лапласа, в противном случае — ММ-критерий, т.е. мы ищем max i (e ir) = max i {v⋅∑e ij ⋅q i + (1-v) min j (e ir)}, 0 ≤ n ≤ 1. Правило выбора, соответствующее критерию Ходжа-Лемана формируется следующим образом: матрица решений ||e ij || дополняется столбцом, составленным из средних взвешенных (с весом v≡const) математическое ожиданиями и наименьшего результата каждой строки (*). Отбираются те варианты решений в строках которого стоит набольшее значение этого столбца. При v = 1 критерий Ходжа-Лемана переходит в критерий Байеса-Лапласа, а при v = 0 становится минимаксным. Выбор v субъективен т. к. Степень достоверности какой-либо функции распределения — дело темное. Для применения критерия Ходжа-Лемана желательно, чтобы ситуация в которой принимается решение, удовлетворяла свойствам: Этот критерий ориентирован на величину потерь, т.е. на отрицательные значения всех e ij . При этом max i (e ir) = max i (min j (e ij)q j) . Т.к. в хозяйственных задачах преимущественно имеют дело с ценами и затратами, условиеe e ij <0 обычно выполняется. В случае же, когда среди величин e ij встречаются и положительные значения, можно перейти к строго отрицательным значениям с помощью преобразования e ij -a при подходящем образом подобранном a>0. При этом оптимальный вариант решения зависит от а. Правило выбора согласно критерию Гермейера формулируется следующим образом: матрица решений ||e ij || дополняется еще одним столбцом содержащим в каждой строке наименьшее произведение имеющегося в ней результата на вероятность соответствующего состояния F j . Выбираются те варианты в строках которых находится наибольшее значениеe e ij этого столбца. В каком-то смысле критерий Гермейера обобщает ММ-критерий: в случае равномерного распределения q j = 1/n, j={1,n}, они становятся идентичными. Условия его применимости таковы: Если функция распределения известна не очень надежно, а числа реализации малы, то, следуя критерию Гермейера, получают, вообще говоря, неоправданно большой риск. Стремление получить критерии, которые бы лучше приспосабливались к имеющейся ситуации, чем все до сих пор рассмотренные, привело к построению так называемых составных критериев. В качестве примера рассмотрим критерий, полученный путем объединения критериев Байеса-Лапласа и минимакса (BL(MM)-критерий). Правило выбора для этого критерия формулируется следующим образом: матрица решений ||e ij || дополняется еще тремя столбцами. В первом из них записываются математические ожидания каждой из строк, во втором — разность между опорным значением e i 0 j 0 = max i (max j (e ij)) и наименьшим значением соответствующей строки. В третьем столбце помещаются разности между наибольшим значением каждой строки и наибольшим значением max j (e i 0 j) той строки, в которой находится значение e i 0 j 0 . Выбираются те варианты, строки которых (при соблюдении приводимых ниже соотношений между элементами второго и третьего столбцов) дают наибольшее математическое ожидание. А именно, соответствующее значение e i 0 j 0 - max j (e ij) из второго столбца должно быть или равно некоторому заранее заданному уровню риска E доп. Значение же из третьего столбца должно быть больше значения из второго столбца. Применение этого критерия обусловлено следующими признаками ситуации, в которой принимается решение: BL(MM)-критерий хорошо приспособлен для построения практических решений прежде всего в области техники и может считаться достаточно надежным. Однако заданные границы риска E доп и, соответственно, оценок риска E i не учитывает ни число применения решения, ни иную подобную информацию. Влияние субъективного фактора хотя и ослаблено, но не исключено полностью. max j (e ij)-max j (e i 0 j)≥E i существенно в тех случаях, когда решение реализуется только один или малое число раз. В этих условиях недостаточно ориентироваться на риск, связанный только с невыгодными внешними состояниями и средними значениями. Из-за этого, правда, можно понести некоторые потери в удачных внешних состояниях. При большом числе реализаций это условие перестает быть таким уж важным. Оно даже допускает разумные альтернативы. При этом не известно, однако, четких количественных указаний, в каких случаях это условие следовало бы опускать. max i (e ir):= max i (∏e ij) Правило выбора в этом случае формулируется так: Матрица решений ||e ij || дополняется новым столбцом, содержащим произведения всех результатов каждой строки. Выбираются те варианты, в строках которых находятся наибольшие значения этого столбца. Применение этого критерия обусловлено следующими обстоятельствами: Критерий произведений приспособлен в первую очередь для случаев, когда все e ij положительны. Если условие положительности нарушается, то следует выполнять некоторый сдвиг e ij +а с некоторой константой а>|min ij (e ij)|. Результат при этом будет, естественно зависеть от а. На практике чаще всего а:= |min ij (e ij)|+1. Если же никакая константа не может быть признана имеющей смысл, то критерий произведений не применим. Рассмотрим тот же пример, что и ранее (см. выше). Построение оптимального решения для матрицы решений о проверках по критерию Гурвица имеет вид (при С=0, в 10 3): В данном примере у решения имеется поворотная точка относительно весового множителя С: до С=0,57 в качестве оптимального выбирается Е 3 , а при больших значениях — Е 1 . Применение критерия Ходжа-Лемана (q=0,33, v=0, в 10 3): Критерий Ходжа-Лемана рекомендует вариант Е 1 (полная проверка) — так же как и ММ-критерий. Смена рекомендуемого варианта происходит только при v=0,94. Поэтому равномерное распределение состояний рассматриваемой машины должно распознаваться с очень высокой вероятностью, чтобы его можно было выбрать по большему математическому ожиданию. При этом число реализаций решения всегда остается произвольным. Критерий Гермейера при q j = 0.33 дает следующий результат (в 10 3): В качестве оптимального выбирается вариант Е 1 . Сравнение вариантов с помощью величинe e ir показывает, что способ действия критерия Гермейера является даже более гибким, чем у ММ-критерия. В таблице, приведенной ниже, решение выбирается в соответствии с BL(MM)-критерием при q 1 =q 2 =q 3 =1/2 (данные в 10 3). Вариант Е 3 (отказ от проверки) принимается этим критерием только тогда, когда риск приближается к E возм = 15⋅10 3 . В противном случае оптимальным оказывается Е 1 . Во многих технических и хозяйственных задачах допустимый риск бывает намного ниже, составляя обычно только незначительный процент от общих затрат. В подобных случаях бывает особенно ценно, если неточное значение распределения вероятностей сказывается не очень сильно. Если при этом оказывается невозможным установить допустимый риск E доп заранее, не зависимо от принимаемого решения, то помочь может вычисление ожидаемого риска E возм. Тогда становится возможным подумать, оправдан ли подобный риск. Такое исследование обычно дается легче. Результаты применения критерия произведения при а = 41⋅10 3 и а = 200⋅10 3 имеют вид: Условие e ij > 0 для данной матрицы не выполнимо. Поэтому к элементам матрицы добавляется (по внешнему произволу) сначала а = 41⋅10 3 , а затем а = 200⋅10 3 . Для а = 41⋅10 3 оптимальным оказывается вариант Е 1 , а для а = 200⋅10 3 — вариант Е 3 , так что зависимость оптимального варианта от а очевидна. Задача:
Найти решение матричной игры, а именно: Шаг:1
Найдем в каждой строке платежной матрицы минимальный
элемент и запишем его в дополнительный столбец (Выделен желтым цветом см. Табл.1). Затем найдем максимальный
элемент дополнительного столбца (отмечен звездочкой), это и будет нижняя цена игры. Таблица 1
В нашем случае нижняя цена игры равна: α
= 3
, и для того чтобы гарантировать себе
выигрыш не хуже чем 3 мы должны придерживаться стратегии A 1 Шаг:2
Найдем в каждом столбце платежной матрицы максимальный
элемент и запишем его в дополнительную строку снизу (Выделена желтым цветом см. Табл.2). Затем найдем минимальный
элемент дополнительной строки (отмечен плюсом), это и будет верхняя цена игры. Таблица 2
В нашем случае верхняя цена игры равна: β
= 5
, и для того чтобы гарантировать себе
проигрыш не хуже чем 5 противник (игрок "B") должен придерживаться стратегии B 2 Шаг:3
Смешанная стратегия
, это чередуемые случайным образом чистые стратегии,
с определенными вероятностями (частотами). Смешанную стратегию игрока "А" будем обозначать где B 1
, B 2
- стратегии игрока "B", а q 1
, q 2
- соответственно вероятности, с которыми эти стратегии применяются,
причем q 1
+ q 2
= 1. Оптимальная смешанная стратегия для игрока "А" та, которая обеспечивает ему максимальный выигрыш.
Соответственно для "B" - минимальный проигрыш. Обозначаются эти стратегии S
A
*
и S
B
* соответственно. Пара оптимальных стратегий образует решение игры. В общем случае в оптимальную стратегию игрока могут входить не все исходные стратегии, а только некоторые из них.
Такие стратегии называются активными стратегиями
. Шаг:4
Из теории игр известно, что если игрок "А" использует свою оптимальную стратегию, а игрок "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
)
В данной задаче: Из теории игр известно, что если игрок "B" использует свою оптимальную стратегию, а игрок "A" остается в рамках своих активных
стратегий, то средний выигрыш остается неизменным и равным цене игры v
независимо от того как игрок
"А" использует свои активные стратегии. Поэтому если предположить, что игрок "A" будет пользоваться чистой стратегией A 1 ,
то средний выигрыш v
составит: k 11
q 1
+ k 12
q 2
= v
(4) В данной задаче: Рисунок 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.
В реальной игре, когда разумный игрок "В" пользуется всеми своими стратегиями, наш выигрыш будет изменяться по ломаной линии, показанной
на Рис.2 красным цветом. Эта линия определяет так называемую нижнюю границу выигрыша
. Очевидно, что самая высокая точка этой ломанной
соответствует нашей оптимальной стратегии. В данном случае, это точка пересечения линий стратегий B 1
и B 2
.
Обратите внимание, что если выбрать частоту p
2
равной ее абсциссе, то наш выигрыш будет оставаться
неизменным и равным v
при любой стратегии игрока "B", кроме того он будет максимальным который мы
можем себе гарантировать. Частота (вероятность) p
2
, в этом случае,
есть соответствующая частота нашей оптимальной смешанной стратегии. Кстати из рисунка 2 видна и частота p
1
,
нашей оптимальной смешанной стратегии, это длина отрезка [p
2
; 1] на оси абсцисс.
(Это потому, что p
1
+ p
2
= 1
) Совершенно аналогично рассуждая, можно найти и частоты оптимальной стратегии для игрока "В", что иллюстрируется на рисунке 3. Рисунок 3.
Только для него следует построить так называемую верхнюю границу проигрыша
(красная ломаная линия) и искать на ней
самую низкую точку, т.к. для игрока "В" цель, это минимизация проигрыша. Аналогично значение частоты q
1
,
это длина отрезка [q
2
; 1] на оси абсцисс. Теория
игр является математической теорией
оптимального поведения в условиях
конфликтной ситуации. Предмет ее
изучения – формализованная модель
конфликта или так называемая «игра».
Основная задача теории игр – определение
оптимальных стратегий поведения
участников. Область применения теории
игр сосредоточена в основном вокруг
сложных поведенческих аспектов
управления, вытекающих из различия
целей и наличия определенной свободы
решений у участников конфликта. Конфликтная
ситуация или "конфликт" определяется
как наличие у элементов системы
нескольких целей и связанное с этим
различие интересов и образов действий
или стратегий в стремлении к достижению
этих целей. Конфликты разделяются на
антагонистические, когда два лица
преследуют противоположные интересы
и неантагонистические, когда интересы
хотя и разные, но не противоположные.
В последнем случае конфликты выражаются
не в виде борьбы двух лиц, а в виде
несовместимости целей в системе или
различного (противоположного) характера
использования ресурсов, при участии в
игре неопределенных факторов "природы"
,в ситуациях с соревнованием и т.д. В
задачах исследования операций как
говорилось выше, мы ищем всегда
оптимальное решение. Наша "операция"
как совокупность действий направленных
на достижение некоторой цели проводится
на основе теоретических методов
оптимизации в некотором наилучшем
смысле по отношению к реальным условиям
и может рассматриваться как "борьба"
с этими условиями, которые выступают
в качестве "противника". В такой
постановке мы также достигаем своего
успеха как бы за счет ущерба "противника". Однако
исследование операций берется решать
такие задачи только в тех случаях, когда
образ действий “противника” в ходе
операции не меняется и в той или оной
степени нам известен. В основу выбора
стратегии обычно кладется принцип
гарантированного результата: какое бы
решение ни принял противник, некоторый
выигрыш должен быть нам гарантирован.
Однако подобная конфликтная ситуация
предметом исследования не является и
рассматривается как фон, на котором
проходят действия сторон. Исследование
операции занимает позицию только одной
стороны. Математическая
теория игр также изучает выбор стратегии
независимо от того, идет ли речь о
реальном противнике или другая сторона
представлена природой, однако здесь
обе стороны выступают как равноправные
партнеры. Теория игр изучает внутреннюю
сущность конфликта с учетом мотивов
поведения обоих сторон в динамике их
противоборства. Формальные
игры, рассматриваемые в теории игр
весьма разнообразны. Аналогично
исследованию операций разработаны и
разные методы поиска оптимальных
стратегий. Однако в этом случае связь
метода и реальной ситуации гораздо
более тесная, по сути дела определяющая.
Абстрактная схема игры с одной стороны
аналогична модели ситуации, с другой
стороны является материалом для
применения того или иного формального
метода. В
каждой игре решаются три основных
вопроса: В
чем состоит оптимальность поведения
каждого из игроков в данной игре? Реализуемо
ли такое понимание оптимальности?
Существуют ли соответствующие стратегии? Если
оптимальные стратегии существуют, то,
как их найти? В
результате положительного решения
всех трех вопросов определяется путь
решения задачи и построения соответствующей
модели. Теория
игр является очень молодой дисциплиной
и запас теоретически разработанных
методов и моделей значительно ступает
исследованию операций. При этом
сказывается и значительная сложность
задач теории игр. Не имея возможности
подробно рассматривать весь известный
комплекс моделей, укажем лишь на
некоторые простейшие из них. 1) Игры
с нулевой суммой. Любые стратегии
игроков приводят к результату, когда
выигрыш одной стороны в точности равен
проигрышу другой. Матрица выигрышей
имеет все положительные элементы и для
всех возможных комбинаций стратегий
можно рекомендовать каждой стороне
оптимальный вариант. Данный вид игры
является антагонистическим. 2) Игры
с ненулевой суммой. Общий вид игры. Если
не существует никакой связи между
сторонами и стороны не могут составлять
коалиции, то игра является антагонистической,
в противном случае - коалиционной игрой
с не противоположными интересами.
Анализ таких игр в большинстве случаев
сложен, в особенности для сложных систем
и рекомендации по выбору стратегий
зависят от многих факторов. Важным
видом в условиях АСУ являются коалиционные
или кооперативные игры. Такая игра
предполагает выполнение участниками
определенных договорных обязательств
(передачи части выигрыша партнерам,
обмен информацией и т.д.). При этом
возникает вопрос устойчивости такой
коалиции в случае, если одна сторона в
выгодной ситуации попытается нарушить
договор. Отсюда возникает вариант с
введением третьего контрольного органа
для наказания возможных сепаратистов.
Оно требует затрат уменьшающих выигрыши
коалиционеров. Очевидно, что игра сильно
усложнится, однако практическая ценность
таких задач не вызывает сомнений.3. Дилемма заключенного
—
Кооперация
Отказ от кооперации
Кооперация
3, 3
0, 5
Отказ от кооперации
5, 0
1, 1
Равновесие по Нэшу.
A
B
C
A
0, 0
25, 40
5, 10
B
40, 25
0, 0
5, 15
C
10, 5
15, 5
10, 10
Фирма 1
Фирма 2
Низкий уровень загрязнения
Высокий уровень загрязнения
Низкий уровень загрязнения
А
100,100
В
-30,120
Высокий уровень загрязнения
С
120,-30
D
100,100
Пример решения матричной игры в чистых стратегиях
Задача.
Предприятие 1
Предприятие 2
10
10
10
1
10
6
8
2
10
2
6
3
6
10
8
2
6
6
6
3
6
2
4
4
2
10
6
3
2
6
4
4
2
2
2
5
Решение задачи
B 1
B 2
B 3
Min j
A 1
0,17
0,62
0,24
0,17
A 2
0,3
-1,5
-0,8
-1
A 3
0,9
0,5
0,4
0,4
Max i
3
0,62
0,4
Критерии принятия решения
Принятие решений в условиях риска.
1. Критерий ожидаемого значения.
T
р t
∑р t
ОЗ(Т)
1
0.05
0
50(100⋅0+10)/1=500
2
0.07
0.05
375
3
0.10
0.12
366.7
4
0.13
02
400
5
0.18
0.35
450
Критерий «ожидаемое значение — дисперсия».
T
p t
p t 2
∑p t
∑p t 2
М(з(Т))+D(з(Т))
1
0,05
0,0025
0
0
500.00
2
0,07
0,0049
0,05
0,0025
6312,50
3
0,10
0,0100
0,12
0,0074
6622,22
4
0,13
0,0169
0,2
0,0174
6731,25
5
0,18
0,0324
0,35
0,0343
6764,00
3. Критерий предельного уровня
I
10
11
12
13
14
15
16
17
18
19
20
ln(I) - I/20
1,8
1,84
1,88
1,91
1,94
1,96
1,97
1,98
1,99
1,99
1,99
ln(I) - I/10
1,3
19
18
16
14
11
1,17
1,13
1,09
1,04
0,99
Принятие решений в условиях неопределенности
F 1
F 2
...
F n
E 1
e 11
e 12
...
e 1n
E 2
e 21
e 22
...
e 2n
...
...
...
...
...
E m
e m1
e m2
...
e mn
Классические критерии принятия решений
1. Минимаксный критерий.
2. Критерий Байеса—Лапласа.
3. Критерий Сэвиджа.
4. Пример и выводы.
F 1
F 2
F 3
ММ-критерий
критерий B-L
e ir = min j (e ij)
max i (e ir)
e ir = ∑e ij
max i (e ir)
E 1
-20,0
-20
-25,0
-25,0
-25,0
-22,33
E 2
-14,0
-23,0
-31,0
-31,0
-22,67
E 3
0
-24.0
-40.0
-40.0
-21.33
-21.33
F 1
F 2
F 3
Критерий Сэвиджа
e ir = min j (a ij)
min j (e ir)
E 1
+20,0
0
0
+20,0
E 2
+14,0
+1,0
+6,0
+14,0
+14,0
E 3
0
+2,0
+15,0
+15,0
Производные критерии.
1. Критерий Гурвица.
2. Критерий Ходжа–Лемана.
3. Критерий Гермейера.
4. Объединенный критерий Байеса-Лапласа и минимакса.
5. Критерий произведений.
Пример.
||e ij ||
С⋅min j (e ij)
(1-С)⋅max j (e ij)
e ir
max i (e ir)
-20,0
-22,0
-25,0
-12,5
-10.0
-22,5
-14,0
-23.0
-31.0
-15,5
-7.0
-22,5
0
-24.0
-40.0
-20.0
0
-20.0
-20.0
∑e ij ⋅q j
min j (e ij)
v⋅∑e ij ⋅q j
(1-v)⋅∑e ij ⋅q j
e ir
max i (e ir)
-22,33
-25,0
-11,17
-12,5
-23,67
-23,67
-22,67
-31,0
-11,34
-15,5
-26,84
-21,33
-40,0
-10,67
-20,0
-30,76
||e ij ||
||e ij q j ||
e ir = min j (e ij q j)
max i (e ir)
-20,0
-22,0
-25,0
-6,67
-7,33
-8,33
-8,33
-8,33
-14,0
-23,0
-31,.0
-4,67
-7,67
-10,33
-10,33
0
-24,0
-40,0
0
-8,0
-13,33
-13,33
||e ij ||
∑e ij q j
e i 0 j 0 - min j (e ij)
max j (e ij)
max j (e ij) - max j (e i 0 j)
-20,0
-22,0
-25,0
-23,33
0
-20,0
0
-14,0
-23,0
-31,0
-22,67
+6,0
-14,0
+6,0
0
-24,0
-40,0
-21,33
+15,0
0
+20,0
a
||e ij + a||
e ir = ∏ j e ij
max i e ir
41
+21
+19
+16
6384
6384
+27
+18
+10
4860
+41
+17
+1
697
200
+180
+178
+175
5607
+186
+177
+169
5563
+200
+176
+160
5632
5632
Матричная игра задана следующей платежной матрицей:
Стратегии "B"
Стратегии "A"
B 1
B 2
A 1
3
5
A 2
6
3
2
- найти верхнюю цену игры;
- нижнюю цену игры;
- чистую цену игры;
- указать оптимальные стратегии игроков;
- привести графическое решение (геометрическую интерпретацию), при необходимости.Определим нижнюю цену игры - α
Нижняя цена игры
α
- это максимальный
выигрыш, который мы можем гарантировать себе, в игре против разумного противника, если на протяжении всей игры будем использовать одну и только одну стратегию
(такая стратегия называется "чистой").
Стратегии "B"
Стратегии "A"
B 1
B 2
Минимумы строк
A 1
3
5
3
*
A 2
6
3
2
3
2
Определим верхнюю цену игры - β
Верхняя цена игры
β
- это минимальный
проигрыш, который может гарантировать себе игрок "В", в игре против разумного противника, если на протяжении всей игры он будет использовать одну и только одну стратегию.
Стратегии "B"
Стратегии "A"
B 1
B 2
Минимумы строк
A 1
3
5
3
*
A 2
6
3
2
Сравним нижнюю и верхнюю цены игры, в данной задаче они различаются, т.е. α
≠ β
,
платежная матрица не содержит седловой точки. Это значит, что игра не имеет решения в чистых минимаксных стратегиях,
но она всегда имеет решение в смешанных стратегиях.S
A
=
где: p
1
, p
2
- вероятности (частоты) с которыми
применяются соответственно стратегии A 1 и A 2
Откуда несложно найти оптимальную частоту стратегии A 1
:p
1 =
k
22
- k
21
k
11
+ k
22
- k
12
- k
21
(3)
p
1 =
3
2
-
6
3
+
3
2
-
5
-
6
=
9
13
Вероятность р
2
найдем вычитанием р
1
из единицы:p
2 = 1 - p
1 =
1
-
9
13
=
+
6
·
где: q
1
, q
2
- вероятности (частоты) с которыми
применяются соответственно стратегии B 1 и B 2
Поскольку цена игры v
нам уже известна и учитывая, что q
1 + q
2 = 1
, то оптимальная частота стратегии B 1 может быть найдена как:q
1 =
v
- k
12
k
11
- k
12
(5)
q
1 =
51
13
-
5
3
-
5
=
7
13
Вероятность q
2
найдем вычитанием q
1
из единицы:q
2 = 1 - q
1 =
1
-
7
13
=
6
13
Ответ:
Нижняя цена игры:
α
=
3
Верхняя цена игры:
β
=
5
Цена игры:
v
=
51
13
Оптимальная стратегия игрока "А" :
S
A
* =
A 1
A 2
9
13
4
13
Оптимальная стратегия игрока "B" :
S
B
* =
B 1
B 2
7
13
6
13
Геометрическая интерпретация (графическое решение):
Дадим геометрическую интерпретацию рассмотренной игре. Возьмем участок оси абсцисс единичной длины и проведем через его концы
вертикальные прямые 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).
График зависимости выигрыша k
от частоты р 2
, при использовании противником стратегии B 1
.
v
и оптимальной частоты р 2
для игрока "А"
.
Графическое определение цены игры v
и оптимальной частоты q 2
для игрока "В"
.
