Математические модели в теории игр.

Математические модели в теории игр. На практике часто приходится сталкиваться с задачами, в которых необходимо принимать решения в условиях неопределенности, т. е. возникают ситуации, в которых две стороны преследуют различные цели и результаты действия каждой из сторон зависят от мероприятий противника (или партнера). Ситуация, в которой эффективность принимаемого одной стороной решения зависит от действий другой стороны, называется конфликтной. Конфликт всегда связан с определенного рода разногласиями (это не обязательно антагонистическое противоречие). Конфликтная ситуация называется антагонистической, если увеличение выигрыша одной из сторон на некоторую величину приводит к уменьшению выигрыша другой стороны на такую же величину, и наоборот. В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. Например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Каждый из них имеет свои интересы и стремится принимать оптимальные решения, помогающие достигнуть поставленных целей в наибольшей степени. При этом каждому приходится считаться не только со своими целями, но и с целями партнера и учитывать решения, которые эти партнеры будут принимать (они заранее могут быть неизвестны). Чтобы в конфликтных ситуациях принимать оптимальные решения, создана математическая теория конфликтных ситуаций, которая называется теорией игр. Возникновение этой теории относится к 1944 г., когда была издана монография Дж. фон Неймана «Теория игр и экономическое поведение» Игра – это математическая модель реальной конфликтной ситуации. Стороны, участвующие в конфликте, называются игроками. Исход конфликта называется выигрышем. Правила игры – это система условий, определяющая варианты действий игроков; объем информации каждого игрока о поведении партнеров; выигрыш, к которому приводит каждая совокупность действий. Игра называется парной, если в ней участвуют два игрока, и множественной, если число игроков больше двух. Мы будем рассматривать только парные игры. Игроки обозначаются A и B. Игра называется антагонистической (с нулевой суммой), если выигрыш одного из игроков равен проигрышу другого. Выбор и осуществление одного из вариантов действий, предусмотренных правилами, называется ходом игрока. Ходы могут быть личными и случайными. Личный ход – это сознательный выбор игроком одного из вариантов действий (например, в шахматах). Случайный ход – это случайно выбранное действие (например, бросание игральной кости). Мы будем рассматривать только личные ходы. Стратегия игрока – это совокупность правил, определяющих поведение игрока при каждом личном ходе. Обычно в процессе игры на каждом этапе игрок выбирает ход в зависимости от конкретной ситуации. Возможно также, что все решения приняты игроком заранее (т. е. игрок выбрал определенную стратегию). Игра называется конечной, если у каждого игрока имеется конечное число стратегий, и бесконечной – в противном случае. Цель теории игр – разработать методы для определения оптимальной стратегии каждого игрока. Стратегия игрока называется оптимальной, если она обеспечивает этому игроку при многократном повторении игры максимально возможный средний выигрыш (или минимально возможный средний проигрыш независимо от поведения противника). Пример 1. Каждый из игроков, A или B , может записать, независимо от другого, цифры 1, 2 и 3. Если разность между цифрами, записанными игроками, положительна, то A выигрывает количество очков, равное разности между цифрами. Если разность меньше 0, выигрывает B. Если разность равна – ничья. У игрока A три стратегии (варианта действия): A1= 1 (записать 1), A2= 2, A3= 3, у игрока тоже три стратегии: B1, B2, B3. B1= 1 B2= 2 B3= 3 A1 = 1 -1 -2 A2= 2 1 -1 A3= 3 2 1 B A Задача игрока A – максимизировать свой выигрыш. Задача игрока B – минимизировать свой проигрыш, т. е. минимизировать выигрыш A. Это парная игра с нулевой суммой. Основные понятия теории игр В экономической практике часто имеют место конфликтные ситуации. Игровые модели - это, в основном, упрощенные математические модели конфликтов. В отличие от реального конфликта игра ведётся по четким правилам. Для моделирования конфликтных ситуаций разработан специальный аппарат - математическая теория игр. Стороны, участвующие в конфликте, называются игроками. Каждая формализованная игра (модель) характеризуется: 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-я стратегия первого игрока и 2-я стратегия второго игрока, которым соответствует элемент а22; · 2-я стратегия первого игрока и 3-я стратегия второго игрока, которым соответствует элемент а23; · 3-я стратегия первого игрока и 2-я стратегия второго игрока, которым соответствует элемент а32; · 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 BA 1 B 2 B 3 – – A1 A2 1 A3 2 1 2 1 1 –2 2 – –1 1 Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника. В примере 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 0,5 0,6 0,8 0,9 0,7 0,8 0,7 0,5 0,6 1 А Тип вооружения 2 А 3 Решить игру, т.е. найти нижнюю и верхнюю цену игры и оптимальные стратегии. Решение. В каждой строке находим минимальный элемент и записываем его в добавочном столбце. В каждом столбце находим максимальный элемент и записываем его в добавочной строке. ВА В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 (орел) В1 (орел) В2 (решка) 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 B B B B a = 3 4 min(Ai) A1 8 7 0 6 0 A2 6 8 5 b max(Bi ) = 8 8 5 1 1 5 Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(a i) = (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 ij V* = min max aij = min{8,6,10,8}= 6 ji V* = V* = 6, элемент матрицы а32 является седловой точкой. Замечание. Если игра m×n имеет седловую точку, то после упрощений платёжной матрицы мы всегда получим игру 1×1. Продолжим рассмотрение методов упрощения платёжной матрицы. Другой метод преобразования матрицы выигрышей (платёжной матрицы) основывается на доказываемой в теории игр теореме об аффинных преобразованиях. Теорема об аффинных преобразованиях. Аффинное преобразование (преобразование подобия и сдвига) платежной матрицы, т.е. преобразование всех элементов матрицы A вида: aq  k  aq  b , где k ≠ 0 и b -любая константа, не ' изменяет решение игры. Кроме того, цена преобразованной игры получена из цены первоначальной игры V по тому же правилу: может быть Это означает, в частности, что для задания игры в принципе безразлично, в каких единицах измеряется выигрыш, например, в рублях или другой валюте. Прибавление (вычитание) некоторой фиксированной суммы bк каждому из элементов aij платёжной матрицы A изменит на такую же сумму выигрыш (проигрыш) каждого из игроков, не меняя при этом решения игры. Это свойство может быть использовано для преобразования исходной матрицы игры к более удобному виду. Так, например, если элементы платежной матрицы представляют собой дроби с общим знаменателем, то каждый элемент матрицы aij можно умножить на некоторую константу, в результате чего элементы преобразованной матрицы будут представлять собой целые числа; если же большинство клеток матрицы заполнены одинаковыми элементами, то их можно вычесть из каждого элемента матрицы для получения нулей, которым будут равны соответствующие элементы матрицы. Кроме того, цену игры всегда можно сделать положительной, т.е. , чем мы воспользуемся при сведении игровой задачи к задаче линейного программирования. В завершении данного параграфа приведём формулу пересчёта от преобразованной цены игры к исходной V: Пример 3. Задана платёжная матрица игры:  400  300 600    A =   200  400 500   800 700  100   Необходимо упростить матрицу игры. 1 - ый шаг: умножим каждый из элементов матрицы A на k = 0.01, получим: 2 - ой шаг: к каждому элементу матрицы A' прибавим b = 4, получим матрицу: = Таким образом, мы получили платёжную матрицу с положительными элементами и небольшими по абсолютной величине. Работа с такой матрицей проще, чем с исходной матрицей. Элементы матрицы получены преобразованием. Смешанные стратегии В общем случае 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. Решение игры в смешанных стратегиях геометрическим методом Пусть игра задана платежной матрицей . По оси абсцисс отложим единичный отрезок А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. Если игрок B применяет стратегию В2, то аналогично откладываем отрезки а12 и а22 и получаем отрезок В2В2′. Ордината любой точки М2 отрезка В2В2′ – выигрыш игрока A, если A применяет смешанную стратегию S A, а B – стратегию В2. Построим нижнюю границу выигрыша игрока А – ломаную В1 NВ2′. Ординаты точек этой ломаной показывают минимальные выигрыши игрока А при использовании им любой смешанной стратегии. Оптимальное решение игры определяет точка N, в которой выигрыш игрока А принимает наибольшее значение. Ордината точки N равна цене игры. Проекция этой точки на ось ОХ показывает оптимальную стратегию (р1, р2). Аналогично находится оптимальная стратегия Q = (q 1 , 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,8 – цена игры. Аналогично строим точки А1(0; 1,5) и А1′(1;3), А2(0; 2) и А2′(1; 1) и находим точку M пересечения прямых А1А1′ и А2А2′. Ответ: смешанная стратегия игрока А: PA= (0,4; 0,6), игрока В: QB = (0,8; 0,2); цена игры 1,8. Решение игры 2×2 Покажем на примере платёжной матрицы размерностью 2×2 реализацию алгоритма построения оптимального решения игровой задачи в смешанных стратегиях. Пример 1. Найдем решение матричной игры . V* = -1, V* = 1, V* ≠V* - решения в чистых стратегиях не существует. Припишем строкам платёжной матрицы неизвестные p2 (вероятности выбора стратегий A1 и A2) соответственно: вероятности p1 и . Поскольку 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хn и mх2 Графо-аналитический метод. У таких игр всегда имеется решение, содержащее не более двух активных стратегий для каждого из игроков. Если найти эти активные стратегии, то игра 2 х n или m х 2 сводится к игре 2 х 2, которую мы уже умеем решать. Поэтому игры 2 х n и m х 2 решают обычно графоаналитическим методом. Рассмотрим решение матричной игры на примере. Пример. Решение. 1 4 7 1 6 3 2 2 6 4 7 2 4 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 применяется; ♦ выделяется верхняя граница выигрыша, и на ней находится точка оптимума с наибольшей ординатой. Пример. Решение. 0,4 1,0 0,4 0,5 0,5 0,5 1,0 0,3 0,3 0,8 0,3 0,3 1,0 1,0 0,5 1,0 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 = Ответ: γ = 44/65; PA = (7/13; 0; 6/13; 0); QB = (7/13; 6/13). 6/13. Примечание: Игроку А не выгодно отклоняться от спектра своих активных стратегий. Игры с "природой" Термин "природа" в теории игр понимается в широком смысле. Это могут быть действительные природные физические (климатические), биологические, химические, социальные и т.п. процессы, которые сопровождают экономическую деятельность. Под "природой" может также пониматься рынок, противостоящий предпринимателю, конкурирующая среда, монополия и т.п. "Природа" может выступать как антагонистическая сторона, а может как кооперативная среда. "Природа" в виде природных процессов, как часть экономики, не стремиться "специально" навредить предпринимателю, но она несёт определённый урон от его экономической деятельности и этот "проигрыш"для неё должен быть минимален, если, вообще, без него для окружающей среды нельзя обойтись. Игрок A в таких играх - это экономические субъекты, а игрок B - это "природа". Откуда средства у физической "природы"? Проигрыш игрока B, физической "природы", должен компенсироваться из вне, например, государственными дотациями либо заложенными в инвестиционные проекты средствами на возобновление природных ресурсов. Знание оптимальных стратегий "природы" позволяет определить наиболее неблагоприятные условия для игрока A (предпринимателя), которые его ожидают ("надейся на лучшее, но готовься к худшему"), и оценить необходимые ресурсы на восстановление природных ресурсов, дающих ему возможность получить гарантированный доход. Если "природа" подразумевает конкурентную среду - то проигрыш второго игрока есть цена борьбы с конкурентами на рынке. Перейдём к примерам содержательных постановок задач игры с "природой". 1. Антагонистические игры Пример 1. (Планирование посевов). Фермер, имеющий ограниченный участок земельных угодий, может его засадить тремя различными культурами A1, A2, A3. Урожай этих культур зависит главным образом от погоды ("природы"), которая может находиться в трёх различных состояниях: B1, B2, B3. Фермер имеет информацию (статистические данные) о средней урожайности этих культур (количество центнеров культуры, получаемого в одного гектара земли) при трёх различных состояниях погоды, которая отражена в таблице: Вид ы культур Возможные состояния погоды Засуха B1 Нормальна я B2 A1 A2 A3 Цен ы 20 7 Дождливая B3 15 15 5 10 5 10 5 7 10 Тогда матрица доходов (платёжная матрица) фермера A имеет вид: Элемент матрицы A - (aij) показывает, какой доход может получить фермер с одного гектара земли, если он посеет культуру i (i =1, 2, 3), а погода будет находиться в состоянии j (j = 1, 2, 3). Необходимо определить пропорции, в которых фермер должен засеять имеющийся участок земли, чтобы получить максимальный гарантированный доход вне зависимости от того, какие погодные условия будут реализованы. Данная задача может быть сведена к антагонистической игре. В данном случае в качестве первого игрока выступает фермер, а в качестве второго игрока - природа. Будем предполагать, что природа, как игрок, может вести себя таким образом, чтобы максимально навредить фермеру, преследуя тем самым противоположные интересы (эти предположения позволяют оценить тот доход, который он может получить в том случае, если погодные условия будут для него максимально неблагоприятные). В этом случае фермер имеет в своём распоряжении три чистые стратегии: · первая чистая стратегия предполагает, что весь участок земли буде засеян культурой A1; · вторая чистая стратегия предполагает, что весь участок земли будет засеян культурой A2; · третья чистая стратегия предполагает, что весь участок будет засеян культурой A 3. Как игрок, природа может также использовать три возможные стратегии: · засушливую погоду, которая соответствует первой чистой стратегии B 1; · нормальную погоду, которая соответствует второй чистой стратегии B 2; · дождливую погоду, которая соответствует третьей чистой стратегии B 3. Решение 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 Таким образом, для того чтобы найти оптимальную смешенную стратегию второго игрока, необходимо также решить задачу линейного программирования. Задачи обоих программирования: игроков свелись к паре двойственных задач линейного Задача второго игрока Задача первого игрока минимизация проигрыша V Целевая функция максимизация выигрыша V F/ = x1+x2+x3 = → max Функциональные ограничения F = y1+y2+y3 = Прямые ограничения x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 → min y1 ≥ 0, y2 ≥ 0, y3 ≥ 0 Задача первого игрока решается симплекс-методом. Результаты счёта: у1 = 0,0 1 у2 p1 = 0,6 7 p2 0,0 = = у3 = 0,0 05 p3 = 0,3 3 0,0 F = 15 66, V = 67 Задача второго игрока решается также симплекс-методом. Результаты счёта: Выводы. В соответствии с полученными = 05 = 3 результатами фермеру гарантирован средний x2 p2 0,0 доход в размере 66,67 единиц с каждого гектара = 0 = используемой под культурами земли при самых x3 0,0 p3 0,6 неблагоприятных условиях. Оптимальная = 1 = 7 стратегия для него выращивание двух 0,0 66, культур, A1 и A3, причём, под первую культуруему F = 15 V = 67 следует отвести 0,67 часть всей земли, а под третью культуру 0,33 часть всей земли. x1 0,0 p1 0,3 Природа "грозит" фермеру жарой 0,33 часть сезона возделывания культур и 0,67 часть сезона дождями. Пример 2. (Планирование выпуска продукции при разных состояниях природы - рынка спроса) Предприятие может выпускать 4 вида продукции: A1, A2, A3, A4, получая при этом прибыль. Её величина определяется состоянием спроса (природой рынка), который может находиться в одном из четырёх возможных состояний: B 1, B2, B3, B4. Зависимость величины прибыли от вида продукции и состояния рынка представлено в таблице: Виды продукции A1 A2 A3 A4 Возможные состояния рынка спроса B1 B2 B3 4 3 5 2 6 1 3 7 3 5 1 B4 6 5 2 3 Платёжная матрица имеет вид: Элемент матрицы A - {aij} характеризует, какую прибыль может получить предприятие, если оно будет выпускать i- й вид продукции(i =1, 2, 3, 4) при j-м спросе(j = 1, 2, 3, 4). Необходимо определить оптимальные пропорции выпускаемых предприятием видов продукции, продажа которой обеспечила бы ему максимально возможную выручку вне зависимости от того, какое состояние спроса будет реализовано Эта задача может быть сведена к антагонистической игре. В данном случае в качестве первого игрока выступает предприятие, а в качестве второго игрока - природа, которая влияет на состояние спроса и может сделать его максимально неблагоприятным для предприятия. Будем предполагать, что природа, как игрок, будет вести себя таким образом, чтобы максимально навредить предприятию, преследуя тем самым противоположные интересы. В этом случае конфликт двух сторон может характеризоваться, как антагонистический, а использование модели этого конфликта позволяет предприятию. оценить выручку, которую оно может получить вне зависимости от того, какое состояние спроса будет реализовано. Выступая в качестве первого игрока, предприятие может использовать четыре стратегии: · первую чистую стратегию, соответствующую выпуску предприятием только продукции A1 · вторую чистую стратегию, соответствующую выпуску предприятием только продукции A2 · третью чистую стратегию, соответствующую выпуску предприятием только продукции A3 · четвёртую чистую стратегию, соответствующую выпуску предприятием только продукции A4 Выступая в качестве второго игрока, природа может использовать также четыре стратегии: · первую чистую стратегию, при которой реализуется состояние спроса B1; · вторую чистую стратегию, при которой реализуется состояние спроса B 2; · третью чистую стратегию, при которой реализуется состояние спроса B 3; · четвёртую чистую стратегию, при которой реализуется состояние спроса B4. Решение 1. Проанализируем платёжную матрицу A. Матрица A не имеет доминируемых стратегий и не может быть упрощена. 2. Проверим, имеет ли данная игра седловую точку. Найдём нижнюю и верхнюю цену игры: V*=maxi minj aij = 3. V*=minj maxiaij = 4. Поскольку V* ≠V*, то данная антагонистическая игра не имеет седловой точки и решения в чистых стратегиях. Решение игры следует искать в смешанных стратегиях. Сведём рассматриваемый антагонистический конфликт к прямой и двойственной задаче линейного программирования. Если первый игрок - предприятие * применяет свою оптимальную смешанную стратегию P , а второй игрок - природа применяет последовательно свои чистые стратегии, то математическое ожидание дохода, который предприятие может получить, будет не меньше цены игры V. И наоборот, если второй игрок - природа - будет применять свою оптимальную смешанную стратегию Q*,а первый игрок предприятие будет последовательно применять свои чистые стратегии, то математическое ожидание проигрышавторого игрока будет не больше цены игры. Следовательно, должна выполняться следующая система неравенств: Задача второго игрока Задача первого игрока минимизация проигрыша V Целевая функция максимизация выигрыша V F/ = x1+x2+x3+x4 = → max Функциональные ограничения F = y1+y2+y3 +y4 = Прямые ограничения x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0 → min y1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0 Применяя симплекс-метод для решения задачи первого игрока, получим: 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 Задача принятия решений в условиях неопределенности Предположим, что ЛПР (лицо, принимающее решения) рассматривает несколько возможных решений: i = 1,…,m. Ситуация, в которой действует ЛПР, является неопределенной. Известно лишь, что наличествует какой-то из вариантов: j = 1,…, n. Если будет принято i-e решение, а ситуация есть j-я , то фирма, возглавляемая ЛПР, получит доход qij. Матрица Q = (qij) называется матрицей последствий (возможных решений). Какое же решение нужно принять ЛПР? В этой ситуации полной неопределенности могут быть высказаны лишь некоторые рекомендации предварительного характера. Они не обязательно будут приняты ЛПР. Многое будет зависеть, например, от его склонности к риску. Но как оценить риск в данной схеме? Допустим, мы хотим оценить риск, который несет i-e решение. Нам неизвестна реальная ситуация. Но если бы ее знали, то выбрали бы наилучшее решение, т.е. приносящее наибольший доход. Т.е. если ситуация есть j-я , то было бы принято решение, дающее доход qij. Значит, принимая -e решение мы рискуем получить неqj, а только qij, значит принятие i-го решения несет риск недобрать rij = qj - qij. Матрица R = (rij) называется матрицей рисков. Пример 1. Пусть матрица последствий есть Составим матрицу рисков. Имеем q1 = max(qi1) = 8, q2 = 5, q3 = 8, q4 = 12.. Следовательно, матрица рисков есть Принятие решений в условиях полной неопределенности Не все случайное можно "измерить" вероятностью. Неопределенность – более широкое понятие. Неопределенность того, какой цифрой вверх ляжет игральный кубик отличается от неопределенности того, каково будет состояние российской экономики через 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-е решение. Принятие решений в условиях частичной неопределенности Предположим, что в рассматриваемой схеме известны вероятности pj того, что реальная ситуация развивается по варианту j. Именно такое положение называется частичной неопределенностью. Как здесь принимать решение? Можно выбрать одно из следующих правил. Правило максимизации среднего ожидаемого дохода. Доход, получаемый фирмой при реализации i-го решения, является случайной величиной Qi с рядом распределения qi1 qi2 … qin p1 p2 … pn Математическое ожидание M[Qi] и есть средний ожидаемый доход, обозначаемый . Правило рекомендует принять решение, приносящее максимальный средний ожидаемый доход. Предположим, что в схеме из предыдущего примера вероятности есть (1/2, 1/6, 1/6, 1/6). Тогда Максимальный средний ожидаемый доход равен 7, соответствует третьему решению. Правило минимизации среднего ожидаемого риска. Риск фирмы при реализации i-го решения, является случайной величиной Ri с рядом распределения ri1 ri2 … rin p1 p2 … pn Математическое ожидание M[Ri] и есть средний ожидаемый риск, обозначаемый также Правило рекомендует принять решение, влекущее минимальный средний ожидаемый риск. Вычислим средние ожидаемые риски при указанных выше вероятностях. . Получаем Минимальный средний ожидаемый риск равен 7/6, соответствует третьему решению. Анализ принимаемых решений по двум критериям: среднему ожидаемому доходу и среднему ожидаемому риску и нахождение решений, оптимальных по Парето, аналогично анализу доходности и риска финансовых операций. В примере множество решений, оптимальных по Парето операций, состоит только из одного 3-его решения. В случае, если количество Парето-оптимальных решений больше одного, то для определения лучшего решения применяется взвешивающая формула . Правило Лапласа Иногда в условиях полной неопределенности применяют правило Лапласа, согласно которому все вероятности pj считают равными. После этого можно выбрать какое-нибудь из двух приведенных выше правил-рекомендаций принятия решений. ГЛОССАРИЙ Автономная модель – часть системы моделей, которую можно анализировать независимо от других частей. Этот подход применим всюду, где отдельные хозяйственные звенья обладают самостоятельностью в своих действиях. Однако в экономике все связано, поэтому автономность частичных моделей всегда относительна. Агрегирование – объединение, укрупнение показателей по какому-либо признаку. С математической точки зрения агрегирование рассматривается как преобразование модели в модель с меньшим числом переменных и ограничений (агрегированную модель), дающую приближенное (по сравнению с исходным) описание изучаемого процесса или объекта. Адаптация – приспособление системы к реальным условиям. Различают адаптацию пассивную – реагирование системы на изменение среды и активную – воздействие системы на среду. Адекватность модели – соответствие модели моделируемому объекту или процессу. Алгоритм – формализованная последовательность действий по решению задачи. Антагонистические игры – игры, в которых интересы игроков строго противоположны, т. е. выигрыш одного игрока – проигрыш другого. Базисное решение – допустимое решение задачи линейного программирования, находящееся в вершине области допустимых решений. Вероятность – численная мера возможности события. Геометрическая интерпретация задачи линейного программирования – интерпретация зависимостей, имеющих место в задаче линейного программирования в виде геометрических фигур (точек, прямых, полуплоскостей, многоугольников) в декартовой системе координат. Двойственные оценки определяют дефицитность используемых ресурсов и показывают, насколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества соответствующего ресурса на единицу. Детерминированные величины – исходные данные, заданные определенными величинами. Динамические модели экономики – модели, описывающие экономику в развитии (в отличие от статических, характеризующих ее состояние в определенный момент). Динамическое программирование – методы решения задач, в которых процесс нахождения решения является многоэтапным. Дисперсия характеризует разброс значений случайной величины. Допустимый план – решение, удовлетворяющее системе ограничений, но не обязательно оптимальное. Достоверное событие – событие, которое непременно должно произойти. Задача оптимизации – задача, решение которой сводится к нахождению максимума или минимума целевой функции. Игра – формализованная модель конфликтной ситуации. Игра n лиц с постоянной суммой – игры, в которых принимает участие n игроков, существует n множеств стратегий и n действительных платежных функций от n переменных, каждая из которых является элементом соответствующего множества стратегий. Каждый игрок знает всю структуру игры и в своем поведении неизменно руководствуется желанием получить максимальный средний выигрыш. Игра двух лиц с ненулевой суммой – игры, в которых сумма выирышей двух игроков после каждой партии не равна нулю. Игра двух лиц с нулевой суммой – игры, в которых интересы двух игроков строго противоположны, т.е. выигрыш одного есть проигрыш другого. Игра против природы – игры, где одним из определяющих факторов является внешняя среда или природа, которая может находиться в одном из состояний, которые неизвестны лицу, принимающему решение. Игра с нулевой суммой – игры, в которых сумма выигрыша игроков после каждой партии составляет ноль. Игрок – участник игровой модели. Коалиции игроков – объединение m игроков в игре n лиц (m меньше n) с целью получения максимального выигрыша и выработке соответствующих стратегий. Коэффициенты линейных ограничений – нормы расхода ресурсов. Линейное программирование – методы решения задач математического программирования, в которых ограничения и целевая функция линейны. Линейно-независимые уравнения – уравнения, которые не могут быть получены умножением, делением, сложением, вычитанием исходных уравнений. Линейные зависимости – зависимости, в которые переменные входят в первой степени, и в которых нет их произведения. Математическое ожидание характеризует среднее значение случайной величины. Модель – математическое или логическое описание компонентов и функций, отображающих существенные свойства моделируемого объекта или процесса (обычно рассматриваемых как системы или элементы системы). Ограничение – неравенства, устанавливающие зависимости для ресурсов. Оптимальное решение – вариант, для которого принятый критерий принимает наилучшее решение. Парная игра – игровая модель с двумя участниками. Переменная – величина, принимающая различные значения. Платежная матрица – прямоугольная таблица размерности m на n, i=1,...,n j=1,...,m (i,j)ый элемент которой есть значение выигрыша (пригрыша) игроков в случае i-го хода первого игрока и j-го хода второго игрока. Равновесие (экономической системы) – 1) состояние, которое характеризуется равенством спроса и предложения всех ресурсов; 2) состояние, когда ни один из многих взаимосвязанных участников системы не заинтересован в изменении этого состояния, так как при этом он не может ничего выиграть, но может проиграть. Симплекс-метод – метод решения задач линейного программирования, заключающийся в последовательном улучшении плана и позволяющий осуществлять переход от одного допустимого базисного решения к другому таким образом, что значение целевой функции непрерывно возрастают и за конечное число шагов находится оптимальное решение. Случайная величина – данные, которые зависят от ряда случайных факторов. Случайный ход – результат, получаемый не решением игрока, а каким-либо механизмом случайного выбора (покупательский спрос, задержка с поставкой материалов и т.п.). Событие – всякий факт, который в результате опыта может произойти или не произойти. Сознательный ход – выбор игроком одного из возможных вариантов действия (стратегия) и принятие решения о его осуществлении. Среднеквадратическое отклонение характеризует разброс значений случайной величины от ее среднего значения. Стационарность – постоянство во времени характеристик некоторого процесса. Стратегия – правило действий в каждой ситуации процесса принятия решения. Теория игр занимается методами обоснования решений в условиях неопределенности и риска, вырабатывает рекомендации для различного поведения игроков в конфликтной ситуации. Целевая функция – критерий оптимизации, признак, характеризующий качество принимаемого решения (максимум прибыли, минимум затрат).