Основные понятия теории игр. Классификация игр

Основные понятия теории игр. Классификация игр. Ситуация, в которой эффективность принимаемого одной стороной решения зависит от действий другой стороны, называется конфликтной. Конфликт всегда связан с определенного рода разногласиями (это не обязательно антагонистическое противоречие). Конфликтная ситуация называется антагонистической, если увеличение выигрыша одной из сторон на некоторую величину приводит к уменьшению выигрыша другой стороны на такую же величину, и наоборот. В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. Например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Каждый из них имеет свои интересы и стремится принимать оптимальные решения, помогающие достигнуть поставленных целей в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнера и учитывать решения, которые эти партнеры будут принимать (они заранее могут быть неизвестны). Чтобы в конфликтных ситуациях принимать оптимальные решения, создана математическая теория конфликтных ситуаций, которая называется теорией игр. Стороны, участвующие в конфликте, называются игроками. Исход конфликта называется выигрышем. Правила игры – это система условий, определяющая варианты действий игроков; объем информации каждого игрока о поведении партнеров; выигрыш, к которому приводит каждая совокупность действий. Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух. Мы будем рассматривать только парные игры. Игроки обозначаются A и B. Игра называется антагонистической (с нулевой суммой), если выигрыш одного из игроков равен проигрышу другого. Выбор и осуществление одного из вариантов действий, предусмотренных правилами, называется ходом игрока. Ходы могут быть личными и случайными. Личный ход – это сознательный выбор игроком одного из вариантов действий (например, в шахматах). Случайный ход – это случайно выбранное действие (например, бросание игральной кости). Мы будем рассматривать только личные ходы. Стратегия игрока – это совокупность правил, определяющих поведение игрока при каждом личном ходе. Обычно в процессе игры на каждом этапе игрок выбирает ход в зависимости от конкретной ситуации. Возможно также, что все решения приняты игроком заранее (т. е. игрок выбрал определенную стратегию). Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной – в противном случае. Цель теории игр – разработать методы для определения оптимальной стратегии каждого игрока. Стратегия игрока называется оптимальной, если она обеспечивает этому игроку при многократном повторении игры максимально возможный средний выигрыш (или минимально возможный средний проигрыш независимо от поведения противника). В экономической практике часто имеют место конфликтные ситуации. Игровые модели - это, в основном, упрощенные математические модели конфликтов. В отличие от реального конфликта игра ведётся по четким правилам. Для моделирования конфликтных ситуаций разработан специальный аппарат - математическая теория игр. Стороны, участвующие в конфликте, называются игроками. Каждая формализованная игра (модель) характеризуется: 1. количеством субъектов - игроков, участвующих в конфликте; 2. вариантом действий для каждого из игроков, называемых стратегиями; 3. функциями выигрыша или проигрыша (платежа) исхода конфликта; Игра, в которой участвуют два игрока A и B называется парной. Если же количество игроков больше двух, то это игра множественная. Мы будем рассматривать модели только парных игр. Игра, в которой выигрыш одного из игроков точно равен проигрышу другого, называется антагонистической игрой или игрой с нулевой суммой. С рассмотрения моделей антагонистических игр мы и начнём. Смоделировать (решить) антагонистическую игру - значит, для каждого игрока указать стратегии, удовлетворяющие условию оптимальности, т.е. игрок A должен получить максимальный гарантированный выигрыш, какой бы своей стратегии не придерживался игрок B, а игрок B должен получить минимальный проигрыш, какой бы своей стратегии не придерживался игрок A. Оптимальные стратегии характеризуются устойчивостью, то есть ни одному из игроков не выгодно отклоняться от своей оптимальной стратегии. Матрица выигрышей. Пусть у игрока A есть m возможных ходов (стратегий) A1, A2,... Am, а у игрока B n возможных ходов (стратегий) B1, B2, ... Bn. Если игрок A сделает ход Ai, а игрок B сделает ход Bj, то эти ходы Ai и Bjоднозначно определяют исходы игры aij для игрока А и bij для игрока В. Полные наборы исходов игры записываются в виде платёжных матриц размером mⅹn, стратегии игрока А соответствуют строкам матриц, а стратегии игрока В соответствуют столбцам матриц. В общем случае у каждого игрока своя платёжная матрица и игра называется биматричной. Две матрицы могут быть преобразованы в одну - биматрицу, каждый элемент которой состоит из двух чисел, выигрыша игрока А и проигрыша игрока В. Поскольку мы ограничились рассмотрением антагонистическими играми, при которых выигрыш одного из игроков точно равен проигрышу другого, то на матрицы А и В налагается условие А + В = 0 (или А = - В, aij = - bij ). В этом случае можно ограничиться только одной матрицей - матрицей А. Такие игры называются матричными. Итак, математической моделью антагонистической игры является матричная игра с матрицей A, в которой ходы (стратегии) игрока A расположены по строкам, а ходы (стратегии) игрока B расположены по столбцам. В самой матрице записаны выигрыши игрока A при соответствующих ходах игроков A и B (отрицательный выигрыш - это проигрыш). Пример 1. Рассмотрим антагонистическую игру, в которой участвуют два игрока, каждый из которых имеет две стратегии. Выигрыши каждого из игроков определены следующими правилами: если оба из игроков выбирают стратегии с одинаковыми номерами, то первый выигрывает одну условную единицу. Если игроки выбирают разные стратегии, то выигрывает второй игрок условную единицу. В этом случае платёжная матрица имеет вид: А = Пример 2. Игроки A и B играют в следующую игру. Игрок A записывает одно из чисел 6, 7, 9, а игрок B записывает одно из чисел 4, 5. Если сумма чисел четная, то это выигрыш игрока А. Если сумма чисел нечётная, то это выигрыш игрока В (проигрыш игрока А). Найти платёжную матрицу игры А. Имеем три стратегии первого игрока. А1 = 6, А2 = 7, А3 = 9, В1 = 4, В2 = 5. Матрица игры: А = С платёжной матрицей A = (aij) связано несколько основных понятий теории игр (игровых моделей). Миксиминные и минимаксные стратегии. Нижняя и верхняя цена игры. Определение 1. Нижней ценой игры V* называется величина, являющаяся максиминным значением платёжной матрицы: V* = max min aij (сначала находится минимум в каждой строке, а затем из полученных минимумов находят максимум). Нижняя цена игры - это гарантированный выигрыш первого игрока А при любой стратегии игрока В. Определение 2. Верхней ценой игры V* называется величина, являющаяся минимаксным значением платёжной матрицы: V* = min max aij (сначала находится максимум в каждом столбце, а затем из полученных максимумов находят минимум). Верхняя цена игры - это гарантированный проигрыш второго игрока B при любой стратегии игрока A. В силу того, что игра антагонистическая, всегда V* ≤ V*. Если V* = V*= V, то просто говорят о цене игры, такая игра называется вполне определённой, игрой с седловой точкой, поскольку значение элемента платёжной матрицы, равное V = V* = V* является минимальным в своей строке и максимальным в своём столбце. Соответствующие этой цене игры стратегии называются оптимальными, поскольку второй игрок не может понизить нижнюю цену игры, а первый игрок не может повысить верхнюю цены игры. Пример 3. Платёжная матрица игры: А = . Определим, существует ли седловая точка. Для этого находим минимум в каждой строке матрицы. Минимальным числом в первой строке будет 3, во второй -- 4 и в третьей -- 2. Из полученных минимумов находим максимум: V* = max(3,4,2) = 4 Находим максимум в каждом столбце. Это числа 6, 7, 4 соответственно. Из полученных максимумов находим минимум: V* = min(6,7,4) = 4 Следовательно, исходя из данного выше определения цены игры, в данном случае цена игры V = V* = V* = 4, седловая точка существует, и это есть элемент платёжной матрицы a23 = 4. Ей соответствуют единственная оптимальная стратегии - A2 первого игрока и единственная оптимальная стратегия - B3 второго игрока. В общем случае в игре может быть несколько седловых точек и, следовательно, несколько оптимальных стратегий (решений) игровой задачи. Пример 4. Задана платёжная матрица игры, необходимо найти оптимальное решение игры. А = Определим, существует ли седловая точка. Для этого находим минимумы в каждой строке матрицы. Минимальным числом в первой строке будет 1, во второй это 2 и в третьей тоже 2. Из полученных минимумов находим максимум: V*= max(1,2,2) = 2 Находим максимум в каждом столбце. Это числа 4, 2, 2 соответственно. Из полученных максимумов находим минимум: V*=min(4,2,2) = 2 Следовательно, исходя из данного выше определения цены игры, в данном случае цена игры V = V* = V* = 2. Ей соответствуют стратегии A2 , А4 первого игрока, и стратегии В2, B3второго игрока (так как a22= а23 = а32 = а33 = 2). Из приведённого анализа следует, что в рассматриваемой платёжной матрице A существуют четыре седловых точек a22 , а23 , а32 , а33, поскольку каждый из этих элементов является минимальным элементом в своей строке и максимальным элементом в своём столбце. Данная игра будет иметь четыре оптимальных решения, которыми являются следующие пары стратегий: · 2-я стратегия первого соответствует элемент а22; · 2-я стратегия первого соответствует элемент а23; · 3-я стратегия первого соответствует элемент а32; игрока и 2-я игрока и 3-я игрока и 2-я стратегия стратегия стратегия второго второго второго игрока, игрока, игрока, которым которым которым · 3-я стратегия первого игрока и 3-я стратегия второго игрока, которым соответствует элемент а33. Данный пример иллюстрирует тот факт, что конечная антагонистическая игра может иметь множество оптимальных решений (множество пар оптимальных стратегий). Пример 5. Задана платёжная матрица игры A, необходимо найти решение игры. A = В данной игре V* = max (min aij)= 3aij V* = min (max aij) = 4 Поскольку V* < V* - выполняется соотношение строгого неравенства, следовательно, седловая точка в игре отсутствует, ситуации равновесия не существует. Очевидно, что для данной игры рассмотренный выше подход к нахождению оптимального решения неприменим, а максиминная и минимаксная стратегия игроков не являются решением игры. Приведённые выше примеры иллюстрируют тот факт, что антагонистические игры делятся на два класса: вполне определённые игры, т.е. те, в которых существует седловая точка, ситуация равновесия и решение игры в чистых стратегиях; не вполне определенные игры, т.е. те, в которых не существует седловой точки, ситуации равновесия и решения игры в чистых стратегиях. Для не вполне определённых игр принцип решения в той форме, для которой он изложен для вполне определённых игр, неприменим. Найдем наилучшую стратегию игрока A, для чего проанализируем последовательно все его стратегии. Выбирая стратегию Ai, мы должны рассчитывать, что игрок B ответит на нее такой стратегией Bj, для которой выигрыш A будет минимальным. Поэтому среди чисел первой строки выбираем минимальное, обозначим его , запишем его в добавочный столбец. Аналогично для каждой стратегии Ai выбираем , т.е. αi – минимальный выигрыш при применении стратегии Ai. В примере 1: α1 = min {0, –1, –2} = –2; α2 = min {1, 0, –1} = –1; α3 = min {0, –1, –2} = 0. Эти числа запишем в добавочном столбце. Какую же стратегию должен выбрать игрок A? Конечно же, ту стратегию, для которой αi максимально. Обозначим . Это гарантированный выигрыш, который может обеспечить себе игрок A, т.е. ; этот выигрыш называется нижней ценой игры или максимином. Стратегия Ai, обеспечивающая получение нижней цены игры, называетсямаксиминной (перестраховочной). Если игрок A будет придерживаться этой стратегии, то ему гарантирован выигрыш ≥α при любом поведении игрока B. В примере 1 . Это означает, что если A будет писать «3», то он хотя бы не проиграет. Игрок B заинтересован уменьшить выигрыш A. Выбирая стратегию B1, он из соображений осторожности учитывает максимально возможный при этом выигрыш A. Обозначим . Аналогично при выборе стратегии Bj максимально возможный выигрыш A– ; запишем эти числа в добавочной строке. Чтобы уменьшить выигрыш A, надо из чисел βj выбрать наименьшее . Число называется верхней ценой игры или минимаксом. Это гарантированный проигрыш игрока B (т. е. он проиграет не больше, чем β). Стратегия игрока B, обеспечивающая выигрыш ≥ - β, называется его минимаксной стратегией. В примере 1: Это означает, что оптимальная стратегия B – писать «3», тогда он хотя бы не проиграет. B A B 1 B 2 B 3 A1 – 1 – 2 –2 A2 1 – 1 –1 A3 2 1 2 1 0 0 Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника. В примере 1 α = β. Если , т.е. минимакс совпадает с максимином, то такая игра называется игрой с седловой точкой. Седловая точка – это пара оптимальных стратегий ( Ai, Bj). В примере 1 игра имеет седловую точку (А3, B3). В этом случае число α = β называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце. В примере 1 это элемент 0. Цена игры равна 0. Оптимальные стратегии в любой игре обладают важным свойством, а именно – устойчивостью. Это означает, что каждый из игроков не заинтересован в отходе от своей оптимальной стратегии, т. к. это ему невыгодно. Отклонение от оптимальной стратегии игрока А приводит к уменьшению его выигрыша, а одностороннее отклонение игрока В – к увеличению проигрыша. Говорят, что седловая точка дает положение равновесия. Пример 2. Первая сторона (игрок А) выбирает один из трех типов вооружения – А1, А2, А3, а противник (игрок В) – один из трех видов самолетов: В1, В2, В3. Цель В – прорыв фронта обороны, цель А – поражение самолета. Вероятность поражения самолета В1 вооружением А1 равна 0,5, самолета В2 вооружением А1 равна 0,6, самолета В3 вооружением А1 равна 0,8 и т.д., т.е. элемент aij платежной матрицы – вероятность поражения самолета Вj вооружением Аi. Платежная матрица имеет вид: В А Вид самолета В1 В2 В3 Тип вооружения А 1 0,5 0,6 0,8 А 2 0,9 0,7 0,8 А 3 0,7 0,5 0,6 Решить игру, т.е. найти нижнюю и верхнюю цену игры и оптимальные стратегии. Решение. В каждой строке находим минимальный элемент и записываем его в добавочном столбце. В каждом столбце находим максимальный элемент и записываем его в добавочной строке. В А В1 В2 В3 αi А1 0,5 0,6 0,8 0,5 А2 0,9 0,7 0,8 0,7 А3 0,7 0,5 0,6 0,5 βj 0,9 0,7 0,8 0,7 0,7 В добавочном столбце находим максимальный элемент = 0,7, в добавочной строке находим минимальный элемент = 0,7. Ответ: = 0,7. Оптимальные стратегии – А2 и В2. Пример 3. Игра в орлянку. Каждый игрок при своем ходе может выбирать одну из двух стратегий: орел или решка. При совпадении выбранных стратегий А получает выигрыш +1, при несовпадении Bполучает выигрыш 1 (т. е. А получает выигрыш –1). Платежная матрица: В А В1 (орел) В2 (решка) А1 (орел) 1 -1 А2 (решка) -1 1 Найти нижнюю и верхнюю цену игры. Имеет ли игра седловую точку? Решение. В А В1 В2 А1 1 -1 -1 А2 -1 1 1 1 1 -1 1 α = -1, β = 1, т. е. А проиграет не больше 1, и B проиграет не больше 1. Так как α ≠ β, игра не имеет седловой точки. Положения равновесия в этой игре не существует, и оптимального решения в чистых стратегиях найти нельзя. Решение игры с седловыми точками. Седловая точка – это пара оптимальных стратегий (Ai, Bj). В этом случае число a=b называется (чистой) ценой игры (нижняя и верхняя цена игры совпадают). Это означает, что матрица содержит такой элемент, который является минимальным в своей строке и одновременно максимальным в своем столбце. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях. Игрок и 1 2 3 4 a = min(Ai) A1 0 Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = (0,5,0) = 5, которая указывает на максимальную чистую стратегию A2. Верхняя цена игры b = min(bj) = (8,8,5,10) = 5. Седловая точка (2, 3) указывает решение на пару альтернатив (A2,B3). Цена игры равна 5. Парную игру с нулевой суммой удобно исследовать, если она описана в виде матрицы. Предположим, что игрок A имеет m стратегий (обозначим их А1, А2, …, Am), а игрок B (противник) – n стратегий (B1, B2, …, Bm). Такая игра называется игрой размерности m х n. Пусть игрок A выбрал одну из своих возможных стратегий Ai. Игрок B, не зная результата выбора игрока A, выбрал стратегию Bj. Для каждой пары стратегий (Ai, Bj) определен платеж aij второго игрока первому, т.е. выигрыш игрока A. Выигрышем игрока B будет соответственно (– aij). Никакой дискриминации по отношению ко второму игроку здесь нет, т. к. величины aij могут быть и отрицательны, тогда –aij > 0. Например, a13 = –2 – выигрыш A, –a13 = 2 – выигрыш B. Такая игра называется матричной; матрица, составленная из чисел aij , называется платежной. В примере 1 платежная матрица имеет вид . Строки этой матрицы соответствуют стратегиям игрока A, а столбцы – стратегиям игрока B. Общий вид такой матрицы B A B1 B2 … Bj … Bn A1 a11 a12 … a1j … a1n A2 a21 a22 … a2j … a2n … … Ai ai1 ai2 … aij … ain … … … … … … … Am am1 am2 … amj … amn Доминирование и дублирование стратегий. Рассмотрим несколько методов упрощения платёжных матриц. Первый метод, используемый для уменьшения размерности матрицы, основан на одном из важнейших понятий в теории игр - понятии доминирования стратегий. Если i-я строка поэлементно не меньше (≥) j-й строки, то говорят, что i-я строка доминирует над j-й строкой. Поэтому игрок A не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии, вне зависимости от того, как играет игрок B. Аналогично, если i-й столбец поэлементно не меньше (≥) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок B не использует i-ю стратегию, так как его проигрыш (равный выигрышу игрока A) при j-й стратегии не больше (≤), чем при i-й стратегии, вне зависимости от того, как играет игрок A. Стратегии, над которыми доминируют другие стратегии, надо отбросить и приписать им нулевые вероятности. На цене игры это никак не скажется. Зато размер матрицы игры понизится. С этого и нужно начинать решение игры. Частный случай доминирования является дублирование стратегий. Если платёжная матрица игры содержит несколько одинаковых строк (столбцов), то из них оставляем только одну строку (один столбец то из них оставляем только одну строку ()овых строк ()ешение к уменьшению среднего выигрыша игрока ), а остальные строки (столбцы) отбрасываем. Отброшенным стратегиям припишем нулевые вероятности. Упрощение (уменьшение размерности) платёжных матриц за счёт исключения заведомо невыгодных чистых стратегий возможно в силу справедливости следующей Теоремы о доминирующих стратегиях: Пусть I - игра, в матрице которой i -я стратегия первого игрока доминирует над i +1, а G - игра, матрица которой получена из матрицы I исключением i + 1 стратегии (строки). Тогда: 1. цена игры I равна цене игры G; 2. оптимальная смешенная стратегия Q*= (q1*,q2*,…,qn*) второго игрока в игре G является также его оптимальной смешанной стратегией в игре I; 3. если P*= (p1*,p2*,…,pi*, p*i+2,…, pm*) оптимальная смешенная стратегия первого игрока в игре G, то его смешенная стратегия P = (p1 ,p2 ,…,pi , p*i+2,…, pm ) является оптимальной в игре I. Из выше сказанного следует, что как первому, так и второму нет смысла использовать доминируемую стратегию, поэтому все доминируемые стратегии могут быть отброшены, т.е. фактически отброшены строки и столбцы исходной матрицы A, соответствующие этим строкам. Это преобразование уменьшает размерность исходной платёжной матрицы A, тем самым упрощается поиск оптимального решения. Рассмотрим ряд примеров. Пример 1. Платёжная матрица игры задана в виде: . Упростим игру (упростим платёжную матрицу). 1-я и 4-я строки равны. Поэтому отбросим 4-ю строку. Вероятность p4 = 0. Получим матрицу: . 2-я строка доминирует над 3-й строкой (6 > 3, 5 > 4, 8 = 8, 7 > 6). Поэтому отбросим 3-ю строку. Вероятность p3 = 0. Получим матрицу: . 2-й столбец доминирует над 3-м столбцом (9 = 9, 5 < 8). Поэтому отбросим 3-й столбец. Вероятность q3 = 0. Получим матрицу: . Строки между собой не сравнимы (8 > 6, 4 < 7), столбцы тоже (8 < 9, 6 > 5; 8 > 4, 6 < 7; 9 > 4, 5 < 7). Дальнейшее упрощение невозможно. Мы свели игру 4Ч4 к игре 2Ч3. Пример 2. Матрица игры . Упростить игру. Введём вероятностные векторы: P = (p1, p2, p3, p4), Q = (q1, q2, q3, q4). 1 - ый шаг: A1 доминирует A2: вычёркиваем 2- ю строку, в результате получаем р2= 0 и платёжную матрицу: 2-ой шаг: A3 доминирует A1: вычёркиваем 1- ю строку, в результате получаем р1= 0 и платёжную матрицу: 3-ий шаг: B2 доминирует B1 вычёркиваем 1- ый столбец, в результате получаем q1 = 0 и платёжную матрицу: 4-ый шаг: B4 доминирует B3 вычёркиваем 2 - ый столбец, в результате получаем q3 = 0 и платёжную матрицу: 5 -ый шаг: A3 доминирует A4: вычёркиваем 4 - ю строку, в результате получаем p4= 0 и платёжную матрицу: 6 - ой шаг: B2 доминирует B4 вычёркиваем 4 - ый столбец, в результате получаем q4 = 0 и платёжную матрицу: В результате упрощения платёжной матрицы выяснилось, что игра имеете единственное оптимальное решение в чистых стратегиях, о чём говорят векторы вероятностей P и Q: P = (0, 0, p3, 0), Q = (0, q2, 0, 0). В результате упрощения платёжной матрицы было установлено также наличие седловой точки и получено оптимальное решение в чистых стратегиях: первый игрок A должен действовать, все время, выбирая стратегию A3, а игрок B выбирает стратегию B2. Тот же результат получается, если использовать максиминную стратегию. V* = max min aij = max{4,3,6,3}= 6 i j V* = min max aij = min{8,6,10,8}= 6 ji V* = V* = 6, элемент матрицы а32 является седловой точкой. Смешанные стратегии. В общем случае V* ≠ V* - седловой точки не существует. Оптимальное решение в чистых стратегиях также не существует. Однако, если расширить понятие чистой стратегии введением понятия смешанной стратегии, то удаётся реализовать алгоритм нахождения оптимального решения не вполне определённой игровой задачи, аналогичный рассмотренному выше. В такой ситуации предлагается использование статистического (вероятностного) подхода к нахождению оптимального решения антагонистической игры. Для каждого игрока, наряду с данным набором возможных для него стратегий, вводится неизвестный вектор вероятностей (относительных частот), с которыми следует применять ту или иную стратегию. Обозначим вектор вероятностей (относительных частот) выбора заданных стратегий игрока A следующим образом: P = (p1, p2,…, pm), где pi≥ 0, p1 + p2 +…+ pm= 1. Величина pi называется вероятностью (относительной частотой) применения стратегии Ai. Аналогично для игрока B вводится неизвестный вектор вероятностей (относительных частот) имеет вид: Q = (q1, q2,…, qn), где qj≥ 0, q1 + q2 +…+ qn = 1. Величина qj называется вероятностью (относительной частотой) применения стратегии Bj. Совокупность (комбинация) чистых стратегий A1, A2, …Am и B1, B2, …Bn в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями. Критерии и свойства оптимальных стратегий. Основной теоремой в теории конечных антагонистических игр является Теорема фон Неймана: каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий. Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P*и Q*, таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии. Средний выигрыш игрока A определяется математическим ожиданием: Если вероятность (относительная частота) применения стратегии отлична от нуля, то такая стратегия называется активной. Стратегии P*, Q*называются оптимальными смешанными стратегиями, если MA(P, Q*) ≤ MA(P*, Q*) ≤ MA(P*, Q) (1) В этом случае MA(P*, Q*) называется ценой игры и обозначается через V (V* ≤ V ≤ V ). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B. Аналитическое решение игры 2Х2. Покажем на примере платёжной матрицы размерностью 2Х2 реализацию алгоритма построения оптимального решения игровой задачи в смешанных стратегиях. Пример 1. Найдем решение матричной игры . V* = -1, V* = 1, V* ≠V* - решения в чистых стратегиях не существует. Припишем строкам платёжной матрицы неизвестные вероятности p1 и p2 (вероятности выбора стратегий A1 и A2) соответственно: . Поскольку p1 + p2 =1 → p2 = 1 - p1. Обозначим p1 = p, тогда p2 =1 - p. В результате получим: Умножим столбец поэлементно на 1-й столбец и, сложив произведения, получим - математическое ожидание (среднее значение) выигрыша первого игрока A, при условии, что второй игрок B следует первой стратегии. M1(p) = 1∙p + (-1)(1-p) = 2p-1 Умножим столбец поэлементно на 2-й столбец и, сложив произведения, получим линейную зависимость - математическое ожидание (средний выигрыш) игрока A при применении игроком B второй стратегии M2(p) = (-1)∙p + 1(1-p) = -2p+1 Поскольку мы разыскиваем оптимальное решение первого игрока A, которое не должно зависеть от выбора стратегий вторым игроком B, приравняем полученные зависимости средних выигрышей: 2p-1 = -2p+1 Отсюда, p= Ѕ, 1-p = Ѕ, то есть оптимальная смешанная стратегия игрока A - это P = (Ѕ, Ѕ ) (каждую из стратегий надо применять с относительной частотой 1/2). Подставив в любую из зависимостей , i =1,2 найдем цену игры: V=Mi(1/2) = 0. Теперь припишем столбцам вероятности q1 и q2 соответственно, а поскольку: q1 + q2 =1 →q2 = 1 - q1. Обозначим q1 = q, тогда q2 =1 - q. В результате получим: . Умножив строку (q, 1-q) на 1-ю строку и сложив произведения, получим линейную зависимость - математическое ожидание: W1(q) = 1· q + (-1) ·(1-q) = 2q - 1 Это средний выигрыш игрока A (равный проигрышу игрока B) при применении игроком A 1-й стратегии. Умножив строку (q, 1-q) на 2-ю строку и сложив произведения, получим линейную зависимость - математическое ожидание: W2 = (-1) · q + 1· (1-q) = -2q + 1 Это средний выигрыш игрока A (равный проигрышу игрока B) при применении игроком A 2-й стратегии. Приравняем полученные зависимости: 2q -1 = -2q + 1 Отсюда, q = Ѕ, 1 - q = Ѕ , то есть оптимальная смешанная стратегия игрока B - это Q = (1/2, 1/2) (каждую из стратегий надо применять с относительной частотой 1/2). Решение о конкретном выборе одной из своих стратегий каждый из игроков может принимать с помощью подбрасывания монеты или бинарного датчика случайных чисел. Как показывает приведённый пример, оптимальные смешанные стратегии сравнительно легко находятся для игр, имеющих небольшую размерность платёжной матрицы (небольшие m и n), т.е. для игр, в которых каждый из игроков имеет небольшое число стратегий. В то же время для игр, имеющих большую размерность, поиск решения становится достаточно сложным. Поэтому до построения оптимального решения в смешанных стратегиях проводят предварительный анализ платёжной матрицы на предмет её упрощения, исключения из неё дублирующих и доминируемых стратегий, что позволяет существенно упростить поиск решения игровой задачи в смешанных стратегиях. Геометрическое решение игры 2Х2. Пусть игра задана платежной матрицей . По оси абсцисс отложим единичный отрезок А1 А2, где точка А1 (0, 0) изображает стратегию А1, А2 (1, 0) – стратегию А2, а каждая промежуточная точкаSA этого отрезка изображает смешанную стратегию первого игрока PA = (p1, p2), где p1– расстояние от точки SA до A2, p2– расстояние от точки SA до A1. Выигрыш игрока A будем откладывать на вертикальных отрезках. Случай 1. Если игрок B применит стратегию В1, то выигрыш игрока A при стратегии А1 равен а11, поэтому на оси ординат отложим отрезок А1В1 = а11. При применении игроком A стратегии А2выигрыш равен а21, отложим этот отрезок на перпендикуляре из точки А2, обозначим полученную точку В1'. Ордината любой точки М1 отрезка В1В1′ равна среднему выигрышу игрока A при применении смешанной стратегии SA (действительно, этот выигрыш равен математическому ожиданию случайной величины, т.е. a11p1 + a21p2). Запишем уравнение прямой В1В1′: , т. е. , тогда при x = p2 получим y = a11 + p2a21 – p2a11 = a11(1-p2) + p2a21 = a11p1 + a21p2 Случай 2. Если отрезки а12 и а22 и игрок B применяет стратегию В2, получаем отрезок В2В2′. Ордината то аналогично откладываем любой точки М2 отрезка В2В2′ – выигрыш игрока A, если A применяет смешанную стратегию SA, а B – стратегию В2. Построим нижнюю границу выигрыша игрока А – ломаную В1 NВ2′. Ординаты точек этой ломаной показывают минимальные выигрыши игрока А при использовании им любой смешанной стратегии. Оптимальное решение игры определяет точка N, в которой выигрыш игрока А принимает наибольшее значение. Ордината точки N равна цене игры. Проекция этой точки на ось ОХ показывает оптимальную стратегию (р1, р2). Аналогично находится оптимальная стратегия Q = (q1 , q2) игрока B, только в соответствии с принципом минимакса надо находить верхнюю границу выигрыша, т. е. строить ломаную А2NА1′ и брать точку N с наименьшей ординатой. Абсцисса точки N определяет оптимальную стратегию игрока B, т. е. Q = (q1 , q2). Пример. Решить игру, заданную платежной матрицей , графоаналитическим способом. Решение. Нижняя цена игры a = 1,5, верхняя цена игры b = 2. Так как , седловой точки нет. Так как a1 = 1,5, a21 = 2 строим точки B1(0;1,5) и B2(1;2), соединяем их отрезком. Так как a21 = 3, a22 = 1 строим точки B2(0;3) и B2’(1;1), соединяем их отрезком. Уравнение прямой В1В1′: , т. е. y = 0,5x + 1,5; уравнение В2В2′: , т. е. y = 3-2x. Найдем точку N пересечения прямых В1В1′ и В2В2′, для чего решим систему уравнений: т. е. N(0,6; 1,8), откуда p2= 0,6; p1= 0,4; Аналогично строим точки А1(0; 1,5) и А1′(1;3), А2(0; точку M пересечения прямых А1А1′ и А2А2′. Ответ: смешанная стратегия игрока А: PA= (0,4; 0,6), игрока В: QB = (0,8; 0,2); цена игры 1,8. Решение игр вида 2хn и mх2 Графо-аналитический метод. У таких игр всегда имеется решение, содержащее не более двух активных стратегий для каждого из игроков. Если найти эти активные стратегии, то игра 2 х n или m х 2 сводится к игре 2 х 2, которую мы уже умеем решать. Поэтому игры 2 х n и m х 2 решают обычно графоаналитическим методом. Рассмотрим решение матричной игры на примере. Пример. Решение. a = 2, b=4, , поэтому игра не имеет седловой точки, и решение должно быть в смешанных стратегиях. 1. Строим графическое изображение игры. Если игрок B применяет стратегию В1, то выигрыш игрока A при применении стратегии А1 равен а11 = 1, а при использовании А2 выигрыш равен а21 = 6, поэтому откладываем отрезки А1В1 = 1, А2В1 = 6 на перпендикулярах в А1 и А2 и соединяем их отрезком. Аналогично для стратегий В2 и В3 строим отрезки В2 В2 и В3 В3 . 2. Выделяем нижнюю границу выигрыша В1М N В3 и находим наибольшую ординату этой нижней границы, ординату точки М, которая равна цене игрыγ. 3. Определяем пару стратегий, пересекающихся в точке оптимума М. В этой точке пересекаются отрезки В2В2′ и В1В1′, соответствующие стратегиям В1 и В2 игрока B. Следовательно, стратегию В3 ему применять невыгодно. Исключаем из матрицы третий столбец и решаем игру 2 x 2 аналитически: ; ; . Ответ: γ = 7/2; PA = (1/2; 1/2); QB = (1/6; 5/6; 0). Правила решения игры 2xn ♦ строится графическое изображение игры; ♦ выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы, которая равна цене игры γ; ♦ определяется пара стратегий, пересекающихся в точке оптимума M. Эти стратегии являются активными стратегиями игрока B. Если в точке оптимума пересекаются более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них; ♦ решается полученная игра 2x2. Решение игры mx2 осуществляется аналогично. Вместо пункта 2 применяется; ♦ выделяется верхняя граница выигрыша, и на ней находится точка оптимума с наибольшей ординатой. Пример. Решение. a= 0,5, b= 1,0. Седловой точки нет. 1. строим графическое изображение игры относительно игрока В. Если А применяет А1, то при использовании игроком В стратегии В1 выигрыш игрока А равен 0,4, а выигрыш А при стратегии В2 равен 1,0, поэтому на перпендикулярах строим такие отрезки. Видно, что стратегия А4 заведомо невыгодная по сравнению со стратегией А3 (выигрыш меньше). 2. Выделяем верхнюю границу выигрыша А3NА1 ; точка с наименьшей ординатой – N. 3. В этой точке пересекаются отрезки А1А1 и А3А3 , соответствующие активным стратегиям А1 и А3. Стратегия А2 не является активной, поэтому из матрицы исключаем вторую и четвертую строки: . 4. решаем игру: 13p3 = 6; p3 =6/13; p1 = 7/13 q2 = 6/13. Ответ: γ = 44/65; PA = (7/13; 0; 6/13; 0); QB = (7/13; 6/13). Примечание: Игроку А не выгодно отклоняться от спектра своих активных стратегий. Игры с "природой" Термин "природа" в теории игр понимается в широком смысле. Это могут быть действительные природные физические (климатические), биологические, химические, социальные и т.п. процессы, которые сопровождают экономическую деятельность. Под "природой" может также пониматься рынок, противостоящий предпринимателю, конкурирующая среда, монополия и т.п. "Природа" может выступать как антагонистическая сторона, а может как кооперативная среда. "Природа" в виде природных процессов, как часть экономики, не стремиться "специально" навредить предпринимателю, но она несёт определённый урон от его экономической деятельности и этот "проигрыш"для неё должен быть минимален, если, вообще, без него для окружающей среды нельзя обойтись. Игрок A в таких играх - это экономические субъекты, а игрок B - это "природа". Откуда средства у физической "природы"? Проигрыш игрока B, физической "природы", должен компенсироваться из вне, например, государственными дотациями либо заложенными в инвестиционные проекты средствами на возобновление природных ресурсов. Знание оптимальных стратегий "природы" позволяет определить наиболее неблагоприятные условия для игрока A (предпринимателя), которые его ожидают ("надейся на лучшее, но готовься к худшему"), и оценить необходимые ресурсы на восстановление природных ресурсов, дающих ему возможность получить гарантированный доход. Если "природа" подразумевает конкурентную среду - то проигрыш второго игрока есть цена борьбы с конкурентами на рынке. Задача принятия решений в условиях риска. Предположим, что ЛПР (лицо, принимающее решения) рассматривает несколько возможных решений: i = 1,…,m. Ситуация, в которой действует ЛПР, является неопределенной. Известно лишь, что наличествует какой-то из вариантов: j = 1,…, n. Если будет принято i-e решение, а ситуация есть j-я , то фирма, возглавляемая ЛПР, получит доход qij. Матрица Q = (qij) называется матрицей последствий (возможных решений). Какое же решение нужно принять ЛПР? В этой ситуации полной неопределенности могут быть высказаны лишь некоторые рекомендации предварительного характера. Они не обязательно будут приняты ЛПР. Многое будет зависеть, например, от его склонности к риску. Но как оценить риск в данной схеме? Допустим, мы хотим оценить риск, который несет i-e решение. Нам неизвестна реальная ситуация. Но если бы ее знали, то выбрали бы наилучшее решение, т.е. приносящее Математическое ожидание M[Qi] и есть средний ожидаемый доход, обозначаемый . Правило рекомендует принять решение, приносящее максимальный средний ожидаемый доход. Предположим, что в схеме из предыдущего примера вероятности есть (1/2, 1/6, 1/6, 1/6). Тогда Максимальный средний ожидаемый доход равен 7, соответствует третьему решению. Правило минимизации среднего ожидаемого риска. Риск фирмы при реализации i-го решения, является случайной величиной Ri с рядом распределения ri1 ri2 p1 p2 … … rin pn Математическое ожидание M[Ri] и есть средний ожидаемый риск, обозначаемый также . Правило рекомендует принять решение, влекущее минимальный средний ожидаемый риск. Вычислим средние ожидаемые риски при указанных выше вероятностях. Получаем Минимальный средний ожидаемый риск равен 7/6, соответствует третьему решению. Анализ принимаемых решений по двум критериям: среднему ожидаемому доходу и среднему ожидаемому риску и нахождение решений, оптимальных по Парето, аналогично анализу доходности и риска финансовых операций. В примере множество решений, оптимальных по Парето операций, состоит только из одного 3-его решения. В случае, если количество Парето-оптимальных решений больше одного, то для определения лучшего решения применяется взвешивающая формула . Принятие решений в условиях неопределенности. Не все случайное можно "измерить" вероятностью. Неопределенность – более широкое понятие. Неопределенность того, какой цифрой вверх ляжет игральный кубик отличается от неопределенности того, каково будет состояние российской экономики через 15 лет. Кратко говоря, уникальные единичные случайные явления связаны с неопределенностью, массовые случайные явления обязательно допускают некоторые закономерности вероятностного характера. Ситуация полной неопределенности характеризуется отсутствием какой бы то ни было дополнительной информации. Какие же существуют правила-рекомендации по принятию решений в этой ситуации? Правило Вальда (правило крайнего пессимизма). Рассматривая i-e решение будем полагать, что на самом деле ситуация складывается самая плохая, т.е. приносящая самый малый доход ai Но теперь уж выберем решение i0 с наибольшим ai0. Итак, правило Вальда рекомендует принять решение i0, такое что Так, в вышеуказанном примере, имеем a1 = 2, a2 = 2, a3 = 3, a4 = 1. Из этих чисел максимальным является число 3. Значит, правило Вальда рекомендует принять 3-е решение. Правило Сэвиджа (правило минимального риска). При применении этого правила анализируется матрица рисков R = (rij). Рассматривая i-e решение будем полагать, что на самом деле складывается ситуация максимального риска bi = max [rij] Но теперь уж выберем решение i0 с наименьшим bi0. Итак, правило Сэвиджа рекомендует принять решение i0, такое что В рассматриваемом примере имеем b1 = 8, b2 = 6, b3 = 5, b4 = 7. Минимальным из этих чисел является число 5. Т.е. правило Сэвиджа рекомендует принять 3-е решение. Правило Гурвица (взвешивающее пессимистический и оптимистический подходы к ситуации). Принимается решение i, на котором достигаетсямаксимум ,где0≤ λ ≤1. Значение λ выбирается из субъективных соображений. Если λ приближается к 1, то правило Гурвица приближается к правилу Вальда, при приближении λ к 0, правило Гурвица приближается к правилу "розового оптимизма" (догадайтесь сами, что это значит). В вышеуказанном примере при λ= 1/2 правило Гурвица рекомендует 2-е решение. Планирование эксперимента в играх с природой. Пример 1. (Планирование посевов). Фермер, имеющий ограниченный участок земельных угодий, может его засадить тремя различными культурами A1, A2, A3. Урожай этих культур зависит главным образом от погоды ("природы"), которая может находиться в трёх различных состояниях: B1, B2, B3. Фермер имеет информацию (статистические данные) о средней урожайности этих культур (количество центнеров культуры, получаемого в одного гектара земли) при трёх различных состояниях погоды, которая отражена в таблице: Вид ы культур Возможные состояния погоды Цен ы Засуха B1 Нормальна я B2 Дождливая B3 A1 20 15 10 5 A2 7 15 5 7 A3 0 5 10 10 Тогда матрица доходов (платёжная матрица) фермера A имеет вид: Элемент матрицы A - (aij) показывает, какой доход может получить фермер с одного гектара земли, если он посеет культуру i (i =1, 2, 3), а погода будет находиться в состоянии j (j = 1, 2, 3). Необходимо определить пропорции, в которых фермер должен засеять имеющийся участок земли, чтобы получить максимальный гарантированный доход вне зависимости от того, какие погодные условия будут реализованы. Данная задача может быть сведена к антагонистической игре. В данном случае в качестве первого игрока выступает фермер, а в качестве второго игрока - природа. Будем предполагать, что природа, как игрок, может вести себя таким образом, чтобы максимально навредить фермеру, преследуя тем самым противоположные интересы (эти предположения позволяют оценить тот доход, который он может получить в том случае, если погодные условия будут для него максимально неблагоприятные). В этом случае фермер имеет в своём распоряжении три чистые стратегии: · первая чистая стратегия предполагает, что весь участок земли буде засеян культурой A1; · вторая чистая стратегия предполагает, что весь участок земли будет засеян культурой A2; · третья чистая стратегия предполагает, что весь участок будет засеян культурой A3. Как игрок, природа может также использовать три возможные стратегии: · засушливую погоду, которая соответствует первой чистой стратегии B1; · нормальную погоду, которая соответствует второй чистой стратегии B2; · дождливую погоду, которая соответствует третьей чистой стратегии B3. Решение 1. Проанализируем платёжную матрицу A. Матрица A не имеет доминируемых стратегий и не может быть упрощена. 2. Проверим, имеет ли данная игра седловую точку. Найдём нижнюю и верхнюю цену игры: V*=maxi minjaij = 50. V*=minjmaxiaij = 100. Поскольку V* ≠V*, то данная антагонистическая игра не имеет седловой точки и решения в чистых стратегиях. 3. Решение игры следует искать в смешанных стратегиях. Сведём игровую задачу к задаче линейного программирования. Если первый игрок - фермер - применяет свою оптимальную смешанную стратегию P*, а второй игрок - природа - применяет последовательно свои чистые стратегии, то математическое ожидание дохода, который фермер может получить со своего участка, будет не меньше цены игры V. Следовательно, должна выполняться следующая система неравенств: Разделим каждое из неравенств, входящих в систему на V и введём новые переменные: . В результате получим новую систему неравенств: Разделим равенство: p*1 + p*2 + p*3 = 1 на V, получим, что новые переменные y1, y2, y3 удовлетворяют условию: y1 + y2 + y3 = 1/V Поскольку цель первого игрока - максимизация его выигрыша, а математическое ожидание его выигрыша не меньше цены игры, то первый игрок будет стремиться максимизировать цену игры, которая эквивалентна минимизации величины 1/V. Итак, для первого игрока (фермера) задача об определении оптимальной стратегии поведения свелась к задаче линейного программирования: найти минимум функции F = y1 + y2 + y3 при следующих функциональных ограничениях: и прямых ограничениях: y1 ≥ 0, y2≥ 0, y3≥ 0 Переходим ко второму игроку, к природе. Если второй игрок - природа - будет применять свою оптимальную смешанную стратегию Q*,а первый игрок - фермер будет последовательно применять свои чистые стратегии, то математическое ожидание проигрыша второго игрока будет не больше цены игры. Следовательно, должна выполняться следующая система неравенств: Разделим каждое из неравенств, входящих в систему на V и введём новые переменные: . В результате получим новую систему неравенств: Разделим равенство: q*1 + q*2 + q*3 = 1 на V, получим, что новые переменные q1 , q2 , q3 удовлетворяют условию: q1 + q2 + q3 = 1/V Поскольку цель второго игрока - природы - минимизация его проигрыша, а математическое ожидание его проигрыша не больше цены игры, то второй игрок будет стремиться минимизировать цену игры, которая эквивалентна максимизации величины 1/V. Итак, для второго игрока (природы) задача об определении оптимальной стратегии поведения свелась к задаче линейного программирования: найти максимум функции F/ = x1 + x2 + x3 при следующих функциональных ограничениях: и прямых ограничениях: x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 Таким образом, для того чтобы найти оптимальную смешенную стратегию второго игрока, необходимо также решить задачу линейного программирования. Задачи обоих игроков свелись к паре двойственных задач линейного программирования: Задача первого игрока решается симплекс-методом. Результаты счёта: у1 0,0 p1 0,6 = 1 = 7 у2 0 p2 0,0 = = 0 у3 0,0 p3 0,3 = 05 = 3 0,0 66, F = 15 V =67 Задача второго игрока решается также симплекс-методом. Результаты счёта: x1 0,0 p1 0,3 Выводы. В соответствии с полученными = 05 = 3 результатами фермеру гарантирован средний x2 p2 0,0 доход в размере 66,67 единиц с каждого гектара = 0 = 0 используемой под культурами земли при самых x3 0,0 p3 0,6 неблагоприятных условиях. Оптимальная = 1 = 7 стратегия для него - выращивание двух 0,0 66, культур, A1 и A3, причём, под первую культуруему F = 15 V =67 следует отвести 0,67 часть всей земли, а под третью культуру 0,33 часть всей земли. Природа "грозит" фермеру жарой 0,33 часть сезона возделывания культур и 0,67 часть сезона дождями. Пример 2. (Планирование выпуска продукции при разных состояниях природы - рынка спроса) Предприятие может выпускать 4 вида продукции: A1, A2, A3, A4, получая при этом прибыль. Её величина определяется состоянием спроса (природой рынка), который может находиться в одном из четырёх возможных состояний: B1, B2, B3, B4. Зависимость величины прибыли от вида продукции и состояния рынка представлено в таблице: A4 3 5 1 3 Платёжная матрица имеет вид: Элемент матрицы A - {aij} характеризует, какую прибыль может получить предприятие, если оно будет выпускать i- й вид продукции(i =1, 2, 3, 4) при j-м спросе(j = 1, 2, 3, 4). Необходимо определить оптимальные пропорции выпускаемых предприятием видов продукции, продажа которой обеспечила бы ему максимально возможную выручку вне зависимости от того, какое состояние спроса будет реализовано Эта задача может быть сведена к антагонистической игре. В данном случае в качестве первого игрока выступает предприятие, а в качестве второго игрока - природа, которая влияет на состояние спроса и может сделать его максимально неблагоприятным для предприятия. Будем предполагать, что природа, как игрок, будет вести себя таким образом, чтобы максимально навредить предприятию, преследуя тем самым противоположные интересы. В этом случае конфликт двух сторон может характеризоваться, как антагонистический, а использование модели этого конфликта позволяет предприятию. оценить выручку, которую оно может получить вне зависимости от того, какое состояние спроса будет реализовано. Выступая в качестве первого игрока, предприятие может использовать четыре стратегии: · первую чистую продукции A1 · вторую чистую продукции A2 · третью чистую продукции A3 стратегию, стратегию, стратегию, соответствующую соответствующую соответствующую выпуску выпуску выпуску предприятием только предприятием только предприятием только · четвёртую чистую стратегию, соответствующую выпуску предприятием только продукции A4 Выступая в качестве второго игрока, природа может использовать также четыре стратегии: · первую чистую стратегию, при которой реализуется состояние спроса B1; · вторую чистую стратегию, при которой реализуется состояние спроса B2; · третью чистую стратегию, при которой реализуется состояние спроса B3; · четвёртую чистую стратегию, при которой реализуется состояние спроса B4. Решение 1. Проанализируем платёжную матрицу A. Матрица A не имеет доминируемых стратегий и не может быть упрощена. 2. Проверим, имеет ли данная игра седловую точку. Найдём нижнюю и верхнюю цену игры: V*=maxi minj aij = 3. V*=minj maxiaij = 4. Поскольку V* ≠V*, то данная антагонистическая игра не имеет седловой точки и решения в чистых стратегиях. Решение игры следует искать в смешанных стратегиях. Сведём рассматриваемый антагонистический конфликт к прямой и двойственной задаче линейного программирования. Если первый игрок - предприятие -применяет свою оптимальную смешанную стратегию P*, а второй игрок - природа - применяет последовательно свои чистые стратегии, то математическое ожидание дохода, который предприятие может получить, будет не меньше цены игры V. И наоборот, если второй игрок - природа - будет применять свою оптимальную смешанную стратегию Q*,а первый игрок - предприятие будет последовательно применять свои чистые стратегии, то математическое ожидание проигрышавторого игрока будет не больше цены игры. Следовательно, должна выполняться следующая система неравенств: Применяя симплекс-метод для решения задачи первого игрока, получим: Y*= (y1* = 0,182; y2* = 0; y3* = 0; y4* =0,091) F= y1*+ y2*+ y3*+y4*= 0,273 Из соотношения y1*+ y2*+ y3*+y4*=1/V найдём V: Из соотношений: Найдём: p*1 = y*1V = 0,67 , p*2 = y*2V = 0 , p*3 = y*3V = 0 , p*4 = y*4V =0,33 Окончательно имеем: Р* = (р*1 =0,67; р*2 = 0; р*3 = 0; р*4 = 0,33), V = 3.67 На основании решения, найденного для двойственной задачи линейного программирования, найдём решение исходной задачи - задачи второго игрока: X*= (x1* = 0,121; x2* =0,121; x3* = 0,03; x4*= 0) F/ = x1*+ x2*+ x3*+x4*= 0,273 Из соотношения x1*+ x2*+ x3*+x4* = 1/V найдём V: Из соотношений: Найдём: q*1 = x*1V = 0,445 , q*2 = x*2V = 0,444 , q*3 = x*3V = 0,111 , q*4 = x*4V = 0. Окончательно имеем: Q*= (q*1= 0,445; q*2=0,444; q*3= 0,111; q*4= 0), V = 3.67