«26 сентября 2008 г. Содержание Предисловие 1 1 Вводная лекция 6 Тест для самоконтроля к лекции 1................. 14 I Принятие решений в условиях определённости 16 2 Экстремум функций одной переменной ...»

Аксиоматический подход к вопросу сравнения лотерей по предпочтению впервые был предпринят Нейманом и Моргенштерном [41]. Основной их результат в этом направлении может быть описан следующим образом.

Пусть — отношение нестрогого предпочтения лотерей (которое представляет собой объединение строгого предпочтения * и отношения безразличия * ). Для отношений вводятся две аксиомы (1) и (2), где аксиома (1) носит чисто математический характер и выражает непрерывность отношения, а смысл аксиомы (2) состоит в том, что при "смешивании"двух безразличных лотерей с любой третьей получающиеся лотереи будут безразличными. Результат Неймана и Моргенштерна состоит в следующем.

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

Замечание. Полезно сравнить этот результат с правилом 7.2, характеризующим способы установления полного ранжирования векторных оценок.

V. В последних двух лекциях раздела II для ЗПР в условиях риска рассматриваются способы уменьшения риска. В лекции 11 излагается способ уменьшения риска, осуществляемый за счет перехода к смешанным стратегиям. Пусть {1,..., } — множество альтернатив (чистых стратегий) в задаче принятия решения в условиях риска. Смешанной стратегией называется вектор = (1,..., ), где 0, Смешанная стратегия может быть реализована одним из следующих трех способов: (a) введением механизма случайного выбора; (b) как "физическая смесь"чистых стратегий; (c) как доля соответствующих чистых стратегий при многократном принятии решения.

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

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

Важным примером реализации принципа "смешивания стратегий"в экономике является распределение капитала на рынке ценных бумаг. Если инвестор распределяет свой капитал между ценными бумагами видов так, что есть доля капитала, вложенного в ценные бумаги –го вида, то вектор = (1,..., ) (определяющий структуру портфеля инвестора), представляет собой с математической точки зрения смешанную стратегию инвестора. В возникающей здесь задаче принятия решения в условиях риска в качестве состояний среды выступают будущие значения курсовых стоимостей ценных бумаг всех видов, обращающихся на рынке. Предположим, что курсовые стоимости ценных бумаг видов и связаны таким образом, что всякое приращение курсовой стоимости ценных бумаг вида сопровождается пропорциональным приращением курсовой стоимости ценных бумаг вида (с некоторым постоянным коэффициентом пропорциональности ). Тогда при > 0 имеет место полная прямая корреляция, а при < 0 — полная обратная корреляция.

Остановимся на задаче оптимизации портфеля инвестора. Эффективность портфеля инвестора, имеющего структуру = (1,..., ), характеризуется векторной оценкой ( (), ()), где () — ожидаемый доход (доход портфеля), () — показатель риска (риск портфеля). Поэтому задача оптимизации портфеля является непрерывной задачей 2– критериальной оптимизации. Один из методов, который может быть использован для решения задачи оптимизации портфеля инвестора — метод субоптимизации; здесь он реализуется следующим образом. Задается некоторое пороговое значение 0 для ожидаемого дохода и среди всех смешанных стратегий ищется такая, которая обеспечивает ожидаемый доход 0 с наименьшим возможным риском. Для практического решения этой задачи требуются данные в форме вектора ожидаемых доходов ценных бумаг каждого вида, а также матрицы показателей ковариации (приближенно эти данные могут быть получены на основе сведений о биржевом курсе ценных бумаг).

VI. Важный для практики способ уменьшения риска при принятии решения состоит в проведении эксперимента. Поскольку проведение эксперимента связано с материальными затратами, возникает проблема соотнесения выгоды от дополнительной информации, получаемой в результате проведения эксперимента, и затрат на его проведение. Одна из методик, направленная на решение этой проблемы, основана на известной в теории вероятностей формуле Байеса. В схематическом виде эта методика состоит в следующем. Рассмотрим ЗПР в условиях риска, в которой {1,..., } — множество альтернатив принимающего решение, {1,..., } — множество состояний среды, ( = 1, ; = 1, ) — матрица выигрышей. Предполагается, что события {1,..., } образуют полную группу событий, причем для каждого = 1,..., принимающему решение известна вероятность ( ) наступления события. Если проводится эксперимент, в результате которого наблюдается событие, и, кроме того, известны условные вероятности (), ( = 1,..., ), то уточненные (послеопытные) вероятности каждого состояния среды могут быть найдены по формуле Байеса. Знание уточненных вероятностей состояний среды позволяет уточнить оптимальную стратегию принимающего решение. На практике условные вероятности () могут быть приближенно получены на основании статистических данных.

VII. Дадим краткую характеристику задач раздела II. Задача № демонстрирует применение критериев Лапласа, Вальда, Гурвица, Сэвиджа при принятии решения в условиях неопределенности (формулировка задачи взята из [11]). Задача № 12 иллюстрирует способы принятия решений в условиях риска по паре критериев (, ). Задача № 13 представляет собой схематический пример задачи принятия решения, в которой сравнение альтернатив по предпочтению производится с помощью построения эмпирической функции полезности. Задача № 14 — это классическая задача распределения инвестиций, постановка которой принадлежит американскому математику Г.Марковицу (за решение этой задачи он был удостоен Нобелевской премии по экономике). Подробный разбор решения этой задачи содержится в книге [15]. Задача № 15 является упрощенным примером, демонстрирующим применение байесовского подхода к ЗПР в условиях риска с возможностью проведения эксперимента (формулировка задачи заимствована нами из [47]).

VIII. Упражнения.

1. Для задачи аренды отеля (пример 8.1) построить матрицу выигрышей, взяв в качестве множества состояний среды следующие значения среднегодового спроса: {5, 10, 15,..., 50}. В полученной ЗПР в условиях неопределенности найти оптимальные решения по критериям Лапласа, Вальда, Гурвица, Сэвиджа.

2. Для задачи выбора проекта электростанции (задача № 11) найти оптимальное решение по критерию Гурвица с показателем пессимизма = 0.3 и = 0.9.

3. Показать, что если альтернатива 1 является оптимальной по одному из критериев: Лапласа, Вальда, Гурвица, Сэвиджа, и 2 доминирует 1, то альтернатива 2 также будет оптимальной по соответствующему критерию.

4. Для задачи выбора продаваемого товара (пример 9.1) найти оптимальную альтернативу по обобщенному критерию =, взяв в качестве свой (субъективный) показатель несклонности к риску.

5. Найти оптимальное решение для задачи № 12, используя:

a) метод субоптимизации;

b) метод лексикографической оптимизации.

a) по критерию (предварительно построить по 5–ти точкам свою кривую денежных эквивалентов);

b) по обобщенному критерию =, взяв в качестве свой показатель несклонности к риску.

7. Для задачи выбора продаваемого товара (пример 9.1) найти оптимальную альтернативу по критерию ожидаемой полезности (предварительно построить по 5-ти точкам график эмпирической функции полезности денежного критерия).

8. Для задачи № 12 найти ожидаемый выигрыш и показатель риска при использовании смешанной стратегии, в которой первые чистых стратегий выбираются равновероятно, а остальные стратегии отбрасываются ( = 1, 2,..., 6). Предполагается, что случайные величины, являющиеся результатом выбора чистых стратегий, попарно не коррелируют.

9. Для задачи выбора продаваемого товара (пример 9.1) найти максимально допустимую стоимость идеального эксперимента.

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

ЛИТЕРАТУРА К РАЗДЕЛУ II: [2,3,11,12,15,22,27,29,30,41,47]

ТЕОРЕТИКО–ИГРОВЫЕ МОДЕЛИ

ПРИНЯТИЯ РЕШЕНИЙ

Матричные игры. Нижняя и верхняя цена игры. Устойчивое поведение и седловые точки. Теорема о связи седловой точки с ценой игры. 3. Смешанное расширение матричной игры. Основные правила для функции выигрыша в смешанном расширении. 4. Теорема фон Неймана и ее следствия. 5. Задача № 16: Профилактика нежелательного события.

1. Вернемся к системному описанию задачи принятия решения (лекция 1): рассматривается некоторый объект управления, на который воздействует управляющая подсистема и среда. Управляющая подсистема всегда является целенаправленной, то есть она имеет определенную цель и ее управление направлено на достижение этой цели. Что касается среды, ее поведение может носить как целенаправленный, так и случайный характер. Если среда ведет себя как целенаправленная система, то такая ситуация принятия решения называется теоретико–игровой, а ее математическую модель принято называть игрой.

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

Однако следует различать неопределенность, имеющую случайный (или стохастический) характер, и неопределенность, имеющую целенаправленный характер. В первом случае мы получаем ЗПР в условиях неопределенности (или в условиях риска), а во втором — в теоретико–игровых условиях. Если в ЗПР в условиях неопределенности (а также в условиях риска) принятие решения рассматривается как индивидуальный выбор альтернативы управляющей подсистемой, то в теоретико–игровой модели принятие решения рассматривается как совместный выбор допустимых альтернатив (стратегий), который производится управляющей подсистемой и подсистемой, "олицетворяющей"среду. Поскольку при таком подходе различие между управляющей подсистемой и средой — в плане их воздействия на объект управления — стирается, удобно говорить о двух управляющих подсистемах; в теоретико–игровой терминологии эти управляющие подсистемы называются игроками.

В случае, когда цели управляющей подсистемы и среды противоположны, получающаяся игра называется антагонистической. Антагонистическая игра, для которой ее оценочная структура задается при помощи оценочной функции, может быть представлена в виде,,, где — множество стратегий игрока 1, — множество стратегий игрока 2, : R — целевая функция. При этом для игрока 1 функция рассматривается как функция выигрыша, а для игрока 2 — как функция потерь.

2. Если в антагонистической игре множества стратегий игроков конечны, то такая игра называется матричной. Матричная игра обычно задается в виде матрицы = ( = 1, ; = 1, ), которая называется матрицей выигрышей или платежной матрицей. В этом случае стратегии игрока 1 могут быть отождествлены с номерами строк, а стратегии игрока 2 — с номерами столбцов платежной матрицы. Число рассматривается одновременно как выигрыш игрока 1 и проигрыш игрока 2 в ситуации (, ).

Проанализируем — какие стратегии игроков в матричной игре можно рассматривать в качестве обоснованных. Если принять за основу гипотезу крайней осторожности — гипотезу антагонизма (см. лекцию 8), то тогда в качестве оценки стратегии игрока 1 выступает его минимальный возможный выигрыш при использовании им –й стратегии, то есть = min. Число представляет собой с содержательной точки зрения гарантированный уровень стратегии (то есть выбрав стратегию, игрок 1 имеет полную гарантию, что его выигрыш — независимо от того, какую стратегию выберет игрок 2, — будет не меньше, чем ).

Наибольший гарантированный выигрыш игрока 1 в данной игре есть Число 1 называется нижней ценой игры (или максимином), а стратегия, максимизирующая минимальный возможный выигрыш игрока 1, то есть стратегия *, для которой * = 1, называется максиминной стратегией игрока 1.

Теперь обратимся к игроку 2. Поскольку для него матрица представляет собой матрицу потерь, то для игрока 2 оценкой стратегии при принятии гипотезы антагонизма будет максимум возможных при этой стратегии потерь, то есть = max. Стратегия *, которая минимизирует максимальные возможные потери игрока 2, называется его минимаксной стратегией, а число называется верхней ценой игры (или минимаксом). Имеет место следующее Правило 13.1. В матричной игре нижняя цена не превосходит верхней цены: 1 2. Если нижняя и верхняя цена игры совпадают, то число = 1 = 2 называется ценой игры.

Действительно, при любых = 1,...,, = 1,..., выполняется и, откуда. Пусть * — максиминная стратегия игрока 1, * — минимаксная стратегия игрока 2. Тогда 1 = * = Практическое правило для нахождения нижней и верхней цены матричной игры состоит в следующем. Добавим к платежной матрице столбец ( )=1, строчных минимумов и строку ( )=1, столбцовых максимумов. Наибольшее из чисел будет нижней ценой, а наименьшее из чисел — верхней ценой. Этот способ продемонстрирован на примерах, приведенных ниже. В примере 13.1 игра не имеет цены (1 < 2 ), в примере 13.2 1 = 2 = — игра имеет цену.

Следующая наша задача — проанализировать "на устойчивость"ситуацию, в которой игрок 1 использует максиминную стратегию, а игрок 2 — минимаксную стратегию. Скажем, в примере 13.1 такой ситуацией будет (2, 1). Эта ситуация является неустойчивой, так как в ней игроку 2 выгодно отклонение от нее заменой стратегии 1 на стратегию 2: в этом случае его потери уменьшатся с 5 до 3. При этом ситуация (2, 1) перейдет в ситуацию (2, 2). Однако ситуация (2, 2) также неустойчива, так как в ней игроку 1 выгодно заменить стратегию 2 на стратегию 1, в результате чего игра переходит в ситуацию (1, 2). В этой ситуации выгодным является одностороннее отклонение игроку 2, которое приводит к ситуации (1, 1). Наконец, в последней ситуации одностороннее отклонение от нее выгодно игроку 1, которое осуществляется заменой стратегии на стратегию 2. В итоге игра возвращается в первоначальную ситуацию (2, 1) и т.д. до бесконечности. Таким образом, в игре примера 13.1 выбор ситуации (2, 1) приводит к "бесконечному блужданию":

что является свидетельством "неудачных"совместных решений игроков.

Напротив, в игре примера 13.2 выбор ситуации (2, 2) (первой компонентой которой является максиминная стратегия игрока 1, а второй — минимаксная стратегия игрока 2) — устойчив, так как в этой ситуации ни одному из игроков невыгодно одностороннее отклонение от нее. Учитывая, что игра примера 13.2 имеет цену, а игра примера 13.1 не имеет цены, можно связать наличие устойчивых ситуаций в матричной игре с наличием у нее цены. Теперь мы приведем формальное доказательство этого важного факта. Дадим вначале следующее Определение. Пусть — матричная игра с платежной матрицей =. Ситуация (0, 0 ) называется седловой точкой в игре, если при всех = 1,, = 1, выполняется двойное неравенство:

Соотношение 13.3 можно пояснить следующим образом.

Правило 13.2. Ситуация (0, 0 ) является седловой точкой игры тогда и только тогда, когда элемент 0 является одновременно наименьшим элементом своей строки и наибольшим элементом своего столбца.

Ясно, что устойчивые в матричной игре ситуации — это и есть ее седловые точки: одностороннее отклонение от седловой точки не выгодно ни одному из игроков.

Теорема 13.1 (связь седловой точки с ценой игры).

1) Пусть (0, 0 ) — седловая точка игры. Тогда a) 0 является максиминной стратегией игрока 1;

b) 0 является минимаксной стратегией игрока 2;

c) игра имеет цену, причем исход в седловой точке совпадает с ценой игры: 0 =.

2) Пусть игра имеет цену. Тогда любая ситуация (0, 0 ), где 0 — максиминная стратегия игрока 1, а 0 — минимаксная стратегия игрока 2, — является седловой точкой игры.

Доказательство. Для доказательства 1) рассмотрим фрагмент платежной матрицы (таблица 13.1), к которой добавлен столбец строчных минимумов ( )=1, и строка столбцовых максимумов ( )=1,. Учитывая правило 13.2, получаем равенства: 0 = 0, 0 = 0. Далее, имеют место следующие очевидные соотношения (см. таблицу 13.1):

Из (*) следует, что 0 — максиминная стратегия игрока 1, а из (**) следует, что 0 — минимаксная стратегия игрока 2. Утверждения a) и b) установлены. Далее, используя (*) и (**), имеем:

откуда 1 = 2 = 0, что и заканчивает доказательство утверждения 1).

Докажем 2). Пусть игра имеет цену: 1 = 2 =. Обозначая через максиминную стратегию игрока 1 и через 0 — минимаксную стратегию игрока 2, изобразим фрагмент платежной матрицы игры с добавленными столбцом строчных минимумов и строкой столбцовых максимумов (таблица 13.2).

При этом нижняя цена игры 1 = 0, верхняя цена игры 2 = 0.

Покажем, что (0, 0 ) — седловая точка игры. Имеем:

Итак, соотношение (13.3) установлено, что и завершает доказательство теоремы 13.1.

Отметим некоторые следствия доказанной теоремы.

Следствие 1. В матричной игре наличие седловой точки эквивалентно наличию цены игры.

Следствие 2. Исходы в седловых точках матричной игры совпадают между собой и совпадают с ценой игры.

Следствие 3. Положим * — множество максиминных стратегий игрока 1, * — множество минимаксных стратегий игрока 2, — множество седловых точек в матричной игре. Если игра имеет цену, то выполняется Свойство 13.4 иногда называют свойством прямоугольности множества седловых точек.

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

Правило 13.2. Если матричная игра имеет цену, то в ней реализуются два принципа оптимальности: принцип оптимальности стратегий (в качестве оптимальных выступают максиминные стратегии игрока 1 и минимаксные стратегии игрока 2), и принцип оптимальности ситуаций (в качестве оптимальных ситуаций выступают седловые точки).При этом оба принципа оптимальности оказываются согласованными между собой: если игроки выбирают оптимальные стратегии, то возникающая ситуация является оптимальной (то есть седловой точкой); обратно — компонентами любой седловой точки служат оптимальные стратегии игроков. Кроме того, исход в любой седловой точке равен цене игры.

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

Замечание. Хотя в любой матричной игре максиминная стратегия игрока 1 и минимаксная стратегия игрока 2 всегда существуют, их можно считать оптимальными только при наличии цены игры. Дело в том, что только в этом случае исход, гарантированный максиминной стратегией игроку 1, совпадает с исходом, гарантированным минимаксной стратегией игроку 2 (этот общий гарантированный обоим игрокам исход и есть цена игры). Если же в матричной игре нет цены, то всякий исход, удовлетворяющий условию 1 < < 2, не является гарантированным исходом ни одного из игроков; тем самым игра становится неопределенной.

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

3. По–прежнему будем обозначать через матричную игру с платежной матрицей = ( = 1, ; = 1, ). Множество смешанных стратегий игрока 1 (напомним, что смешанные стратегии рассматривались в лекции 11), есть а множество смешанных стратегий игрока 2 есть Применнение в игре игроком 1 смешанной стратегии может быть интерпретировано как проведение опыта, случайными исходами котрого являются элементы {1,..., }, причем есть вероятность выбора стратегии. Аналогично интерпретируется применение в игре смешанной стратегии игроком 2. Предположим теперь, что игрок использует смешанную стратегию, а игрок 2 — смешанную стратегию. Тогда вероятность возникновения ситуации (, ) (то есть вероятность того, что исходом первого опыта будет, а исходом второго опыта будет ) равна — по теореме умножения вероятностей — произведению.

(Заметим, что здесь предполагается независимость выборов игроками и 2 своих смешанных стратегий, то есть каждый игрок производит выбор своего вероятностного вектора, не имея информации о выборе другого игрока.) Так как в ситуации (, ) выигрыш игрока 1 равен, получаем, что при использовании игроками 1 и 2 смешанных стратегий и, соответственно, выигрыш игрока 1 становится случайной величиной вида =. Будем считать математическое ожидание этой случайной величины выигрышем игрока 1 в ситуации в смешанных стратегиях (, ).

Итак, по матричной игре построена новая игра, в которой множеством стратегий игрока 1 является множество вероятностных векторов, множеством стратегий игрока 2 является множество вероятностных векторов, а функция выигрыша определяется равенством:

Заметим, что стратегия = 1,..., игрока 1 в игре может быть отождествлена с вероятностным вектором (0,..., 1,..., 0), а стратегия = 1,..., игрока 2 — с вероятностным вектором (0,..., 1,..., 0) ; таким образом, игра является расширением игры, которое получается расширением множеств стратегий игроков и продолжением их функций выигрыша. При этом первоначальные стратегии игроков в игре, рассматриваемые как стратегии в игре, называются чистыми.

Ситуация (, ) называется ситуацией в смешанных стратегиях в игре. Построенная игра носит название смешанного расширения игры.

Рассмотрим основные правила для функции выигрыша в смешанном расширении матричной игры.

Правило 13.3 a) Если игрок 1 использует смешанную стратегию значение функции выигрыша в полученной ситуации (, ) равно взвешенной сумме элементов –го столбца платежной матрицы с весами 1,...,, соответственно:

b) Если игрок 1 использует чистую стратегию = 1,...,, а игрок — смешанную стратегию = (1,..., ), то значение функции выигрыша в полученной ситуации (, ) равно взвешенной сумме элементов –ой строки платежной матрицы с весами 1,..., :

Доказательство. a) В ситуации (, ) исходом будет случайная величина = ( = 1, ); ее математическое ожидание равно правой части формулы (13.6).

Правило 13.4 (разложение функции выигрыша по чистым стратегиям).

a) Значение функции выигрыша (, ) есть взвешенная сумма величин (, ) с весами ( = 1, ): (, ) = b) Значение функции выигрыша (, ) есть взвешенная сумма величин (, ) с весами ( = 1, ): (, ) = Докажем a). Используя правило 13.3 а), имеем:

Правило 13.5 (правило гарантирующей стратегии). Зафиксируем некоторое число.

a) Пусть 0 — смешанная стратегия игрока 1, для которой при любой чистой стратегии = 1,..., игрока 2 выполняется неравенство (0, ). Тогда и при любой смешанной стратегии будет выполняться (0, ).

b) Пусть 0 — смешанная стратегия игрока 2, для которой при любой чистой стратегии = 1,..., игрока 1 выполняется неравенство (, 0 ). Тогда и при любой смешанной стратегии игрока будет выполняться (, 0 ).

Теоретико–игровой смысл утверждения a) состоит в следующем. Если стратегия 0 гарантирует игроку 1 исход против любой чистой стратегии игрока 2, то она гарантирует ему исход также и против любой смешанной стартегии игрока 2. Аналогично интерпретируется утверждение b).

Докажем a). Пусть = (1,..., ). Умножая неравенство. По правилу 13.4 и) левая часть этого неравенства равна (0, ), а правая равна.

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

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

Замечание. Через Sp здесь и далее обозначается спектр смешанной стратегии, то есть множество номеров = 1,...,, для которых > 0. Спектр смешанной стратегии составляют те чистые стратегии, которые "используются"в ней с ненулевой вероятностью.

Доказательство. Установим справедливость правила 13.6 для наибольшего значения. Тогда для любого = 1,..., выполняется Предположим, что для некоторого Sp 0 имеет место строгое неравенство (, 0 ) < (0, 0 ). Умножая обе части (13.8) на 0, суммируя по = 1,..., и учитывая, что 0 (, 0 ) < 0 (0, 0 ), получаем к противоречию.

Аналогично формулируется правило наименьшего и наибольшего значения функции (0, ) при произвольном фиксированном 0.

4. Перейдем теперь к основному результату теории матричных игр — теореме фон Неймана, положившей начало современной теории игр.

Теорема 13.2 (теорема фон Неймана). Для любой матричной игры Другими словами, в смешанном расширении любой матричной игры нижняя и верхняя цена игры совпадают. Общее значение левой и правой части (13.9) называется ценой игры в смешанных стратегиях и обозначается через.

Укажем основную идею доказательства Теоремы 13.2. В игре с платежной матрицей исход R называется гарантированным исходом игрока 1, если у игрока 1 существует такая смешанная стратегия 0, что при любой смешанной стратегии игрока 2 выполняется неравенство (0, ). Исход называется гарантированным исходом игрока 2, если у игрока 2 существует такая смешанная стратегия 0, что при любой смешанной стратегии игрока 1 выполняется неравенство (, 0 ). Если одно из этих неравенств выполняется как строгое, то говорят, что исход строго гарантируется игроку.

Очевидно, что ни один исход R не может одновременно строго гарантироваться игроку 1 и гарантироваться игроку 2 (тогда выполнялось бы (0, 0 ) > и (0, 0 ), что невозможно).

Таким образом, множество строго гарантированных исходов игрока 1 и множество гарантированных исходов игрока 2 не пересекаются. Утверждение теоремы фон Неймана эквивалентно тому, что эти множества образуют покрытие действительной прямой, то есть каждый исход R либо строго гарантируется игроку 1, либо гарантируется игроку 2. В самом деле, ясно, что произвольный исход R строго гарантируется игроку 1 тогда и только тогда, когда < max min (, );

гарантируется игроку 2 тогда и только тогда, когда min max (, ). Если бы выполнялось max min (, ) < min max (, ), то любой исход, заключенный между ними, не являлся бы ни строго гарантированным исходом игрока 1, ни гарантированным исходом игрока 2.

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

() Существует такой вероятностный вектор 0, что для всех = 1,..., выполняется () Существует такой вероятностный вектор 0, что для всех = 1,..., выполняется Это — так называемая лемма о двух альтернативах. Доказательство этой леммы основано на теореме об отделяющей гиперплоскости. Используя эту теорему, несложно проверить (см., например, [4]), что первая альтернатива реализуется, если выпуклая оболочка системы векторов (1,...,, 1,..., ), где 1,..., — единичные векторы пространства R и 1,..., — векторы– столбцы матрицы, не содержат нулевой точки; в противном случае реализуется вторая альтернатива.

Замечание. Цена игры в смешанных стратегиях удовлетворяет двойному неравенству где 1 — нижняя цена, 2 — верхняя цена матричной игры.

Действительно, пусть * — максиминная (чистая) стратегия игрока в игре. Тогда при любом = 1,..., выполняется (*, ) 1.

По правилу гарантирующей стратегии 13.5 a) отсюда следует, что при любой смешанной стратегии выполняется (*, ) 1, откуда min (*, ) 1, значит max min (, ) 1, то есть 1.

Аналогично проверяется неравенство 2. Таким образом, если матричная игра имеет цену в чистых стратегиях, то согласно (13.10) цена игры в чистых стратегиях и цена игры в смешанных стратегиях совпадают.

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

Далее, максиминные (минимаксные) стратегии игроков в смешанном расширении матричной игры определяются тем же способом как и для матричной игры — с заменой оценочной функции = min на оценочную функцию () = min (, ) и оценочной функции = max на оценочную функцию () = max (, ). Максиминная смешанная стратегия игрока 1 характеризуется равенством а минимаксная смешанная стратегия 0 игрока 2 — равенством Доказательство теоремы 13.1 переносится на случай смешанного расширения матричной игры практически без изменений (с заменой оценочных функций и на () и ()). С учетом теоремы фон Неймана имеем следующий результат.

Теорема 13.3. (связь седловой точки с ценой игры в смешанном расширении матричной игры).

1) Пусть (0, 0 ) — седловая точка в смешанном расширении матричной игры. Тогда a) 0 является максиминной стратегией игрока 1;

b) 0 является минимаксной стратегией игрока 2;

c) исход в седловой точке равен цене игры.

2) Любая ситуация в смешанных стратегиях (0, 0 ), где 0 — максиминная стратегия игрока 1 и 0 — минимаксная стартегия игрока 2, является седловой точкой в смешанном расширении игры.

Следствие 1. Для любой матричной игры существует седловая точка в смешанных стратегиях.

Следствие 2. В смешанном расширении матричной игры исходы во всех седловых точках совпадают и равны цене игры в смешанных стратегиях.

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

a) Под оптимальной стратегией игрока 1 будем понимать его максиминную стратегию;

b) под оптимальной стратегией игрока 2 будем понимать его минимаксную стратегию;

c) под оптимальной ситуацией будем понимать седловую точку.

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

5. Задача № 16: Профилактика нежелательного события.

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

Имеется профилактических действий, направленных на уменьшение ущерба от нежелательных событий; пусть > 0 — стоимость –го профилактического действия ( = 1,..., ). Если принимающий решение выбирает профилактическое действие, а "природа"осуществляет событие, то итоговые потери для принимающего решение будут выражаться некоторой величиной ( = 1, ; = 1, ). Будем считать для простоты, что всякое профилактическое действие либо сводит ущерб от нежелательного события до нуля (защищает от последствий этого события), либо не оказывает никакого влияния на величину ущерба (не защищает от последствий нежелательного события). Тогда потери в ситуации (, ) составляют Получаем в итоге матричную игру принимающего решение (игрок 1) с природой (игрок 2), причем матрица является матрицей потерь для принимающего решение.

Рассмотрим один конкретный пример такой игры. Пусть ожидаемое нежелательное событие — наводнение, которое может иметь категорию с 1–й по 5–ю; профилактическое действие состоит здесь в строительстве дамбы. Будем считать, что имеется 5 вариантов выбора высоты дамбы 1 < 2 < 3 < 4 < 5, причем дамба высоты защищает от наводнения, имеющего категорию не выше -й и не защищает от наводнения, имеющего категорию выше -й. В таблице 13.3 указаны затраты на строительство дамбы, а в таблице 13.4 — величины ущерба от наводнения (в некоторых ден. ед.).

В получившейся матричной игре принимающий решение имеет 6 стратегий (не строить дамбу вообще или строить дамбу высоты, = 1, 2, 3, 4, 5); природа также имеет 6 стратегий (не осуществлять наводнение или осуществить наводнение –й категории, = 1, 2, 3, 4, 5). Получающаяся матрица потерь задается таблицей 13.5.

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

В полученной матричной игре имеется единственная седловая точка (5, 5).

Итак, рассматриваемая матричная игра имеет седловую точку в чистых стратегиях; стратегия * = 5 является оптимальной (максиминной) стратегией игрока 1, а стратегия * = 5 — оптимальной (минимаксной) стратегией игрока 2. Цена игры в чистых стратегиях существует и равна 10 денежным единицам.

Тест для самоконтроля к лекции 1. Игрой называется математическая модель принятия решения, в которой поведение среды носит... характер.

Варианты ответов: Детерминированный 2. В антагонистической игре X – есть множество стратегий игрока 1, Y – множество стратегий игрока 2, а целевая функция f есть отображение....

Варианты ответов: из X в Y 3. Матричная игра – это антагонистическая игра, в которой....

Варианты ответов: Множество стратегий игрока 1 конечно;

4. В матричной игре с матрицей выигрыша = ( ), где = 1,..., ; = 1,...,, гарантированным уровнем стратегии игрока 1 является число =... .

Варианты ответов: 5. Нижняя цена матричной игры 1 равна....

Варианты ответов: 6. В матричной игре наибольший возможный проигрыш игрока 2 при использовании им стратегии равен =....

Варианты ответов: 7. Верхняя цена матричной игры 2 равна....

Варианты ответов: 8. В любой матричной игре выполнено условие:

9. Найти нижнюю и верхнюю ценыматричной игры:

Варианты ответов: 1 = 22 = 10. Ситуация (0, 0 ) является седловой точкой в матричной игре тогда и только тогда, когда....

Варианты ответов: а) 0 – максиминная стратегия игрока 11. Найдите все седловые точки в матричной игре, заданной платежной матрицей A:

Варианты ответов: {2, 5} {2, 4} 12. Пусть матричная игра имеет цену и в ней имеется 4 максиминных стратегии игрока 1. Может ли число седловых точек в ней быть равным... ? Да.

Варианты ответа: 0, 2, 4, 6, 8, 10.

13. В матричной игре с платежной матрицей А:

Игрок 1 использует смешанную стратегию = (1/4, 3/4), а игрок 2 – смешанную стратегию = (2/3, 1/3). Какова вероятность того, что исход игры будет равен 2?

Варианты ответа: 1/6, 5/12, 1/2, 3/4, 7/12.

14. Смешанное расширение матричной игры есть....

Варианты ответов: Новая матричная игра;

15. При применении игроком 1 смешанной стратегии = (1,..., ) и игроком 2 – смешанной стратегии = (1,..., ) вероятность возникновения ситуации (, ) равна....

Варианты ответов: + 16. В смешанном расширении матричной игры с плаьежной матрицей = ( ) исходом в ситуации (, ) является... случайной величины, равной Варианты ответов: Наибольшее значение;

17. Теорема фон Неймана: всякая матричная игра имеет... в смешанных стратегиях.

Варианты ответов: Цену;

18. В матричной игре для ситуаций (1, 1 ) и (2, 2 ) выполнено (1, 1 ) = (2, 2 ) = 4, а (1, 2 ) = (2, 1 ) = 3. Укажите ситуации, которые могут быть седловыми точками.

19. В игре с платежной матрицей А:

цена игры в смешанных стратегиях заключена между....

20. Русть – цена игры с платежной матрицей A в чистых стратегиях, – цена этой игры в смешанных стратегиях. Всегда выполняется условие....

Лекция Методы нахождения решения матричной игры в смешанных стратегиях Основные вопросы: 1. Определение решения матричной игры. Некоторые правила, связанные с нахождением решения игры: a) переход к эквивалентной игре; b) правило дополняющей нежесткости; c) отбрасываение доминируемых стратегий. 2. Аналитический и графоаналитический метод нахождения решения матричной игры. 3. Нахождение решения матричной игры с помощью системы линейных неравенств. Сведение задачи нахождения решения матричной игры к паре двойственных задач линейного программирования. 4. Примеры экономических задач, моделируемых матричными играми. 5. Задача № 17: Выбор момента поступления товара на рынок в условиях антагонистической конкуренции. Задача № 18: Планирование посева в неопределенных погодных условиях. Задача № 19: Инспекция предприятий торговли.

1. Формально решение матричной игры в смешанных стратегиях определяется как тройка (0, 0, ), где 0 — оптимальная стратегия игрока 1, 0 — оптимальная стратегия игрока 2, — цена игры в смешанных стратегиях. Фактически нахождение решения матричной игры сводится к нахождению седловой точки (0, 0 ), так как тогда — оптимальная стратегия игрока 1, 0 — оптимальная стратегия игрока 2, (0, 0 ) = — цена игры (см. лекцию 13, п.4).

Замечание 1. Если матричная игра имеет цену в чистых стратегиях, тогда тройка (0, 0, ), где 0 — максиминная (чистая) стратегия игрока 1, 0 — минимаксная (чистая) стратегия игрока 2, = 0 — является решением игры. Случай, когда матричная игра имеет цену в чистых стратегиях, мы в дальнейшем не рассматриваем, считая его тривиальным.

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

Правило 14.1 (переход к эквивалентной игре). Пусть — матричная игра с платежной матрицей = ( = 1, ; = 1, ). Построим матрицу = ( = 1, ; = 1, ), где = + ( > 0). Тогда функции выигрыша и в смешанных расширениях этих игр связаны равенством:

Из (14.1) сразу следует, что нахождение решеня игры эквивалентно нахождению решения игры : если (0, 0, ) — решение игры, то (0, 0, ( )/) — решение игры.

Практическое использование правила 14.1 состоит в том, что от заданной платежной матрицы можно перейти к более простой платежной матрице, подбирая подходящие константы > 0 и.

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

b) в любой ситации (0, ), где Sp 0, исход равен цене игры:

(0, ) =. (Напомним, что через Sp обозначается спектр смешанной стратегии, см. лекцию 13, п. 3).

Утверждения a) и b) сразу следуют из правила 13.6: если (0, 0 ) — седловая точка, то функция (, 0 ) достигает наибольшего значения при = 0, а функция (0, ) достигает наименьшего значения при = 0. Остается заметить, что по утверждению 1 c) Теоремы 13.3 исход в седловой точке равен цене игры.

Правило 14.3 (правило отбрасывания доминируемых стратегий).

При нахождении решения матричной игры в смешанных стратегиях доминируемые стратегии игроков могут быть отброшены.

Напомним, что отношение доминирования стратегий вводилось для ЗПР в условиях неопределенности (лекция 8, п.2). При переходе к матричным играм, следует иметь в виду, что для них возможно рассмотрение доминирования стратегий как для игрока 1, так и для игрока 2. А именно, в игре с платежной матрицей = ( = 1, ; = 1, ) для стратегий 1, 2 игрока 1 условие доминирования 1 (1) 2 означает, что при всех = 1,..., выполняется 1 2 ; для стратегий 1, 2 игрока 2 условие доминирования 1 (2) 2 означает, что при всех = 1,..., имеет место 1 2.

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

Замечание 1. Можно рассматривать не только доминирование одной чистой стратегии игрока другой чистой стратегией, но также доминирование чистой стратегии игрока некоторой выпуклой комбинацией других чистых стратегий этого игрока. Например, в матричной игре стратегия 3 доминируется выпуклой комбинацией стратегий 1 и 2, если существуют такие неотрицательные числа 1, 2, где 1 + 2 = 1, что при всех имеет место 3 1 1 + 2 2.

При этом согласно правила 13.3 а) правая часть последнего неравенства может быть представлена в виде значения функции выигрыша в ситуации (, ), где = (1, 2, 0). Таким образом, условие доминирования чистой стартегии игрока выпуклой комбинацией других чистых стратегий означает доминирование этой чистой стратегии некоторой смешанной стратегией, спектр которой не содержит данной чистой стратегии.

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

Правило 14.4. Пусть чистая стратегия 0 игрока 1 строго доминируется выпуклой комбинацией чистых стратегий {1,..., }, где 0 {1,..., }. Тогда стратегия 0 не может входить в спектр какой– либо оптимальной смешанной стратегии игрока 1.

Действительно, в силу замечания 1, при всех = 1,..., справедливы строгие неравенства (0, ) < (, ), где. Пусть 0 = (1,..., ) — оптимальная стратегия игрока 2. Умножая обе части написанного неравенства на и суммируя по = 1,...,, получаем (, ). С другой стороны, по определению седловой точки (, 0 ), где — цена игры ; получаем (0, 0 ) <. В силу условия дополняющей нежесткости (правило 14.2) чистая стратегия 0 не может принадлежать спектру никакой оптимальной стратегии игрока 1.

Примеры использования правил 14.1–14.4 будут рассмотрены ниже.

2. Рассмотрим вначале нахождение решения матричной игры, в которой игроки 1 и 2 имеют по две стратегии (игры формата 2 2). Такая — компоненты оптимальной стратегии игрока 1, (1, 2 ) — компоненты оптимальной стратегии игрока 2. Тогда, исключая тривиальный случай (то есть случай наличия решения в чистых стратегиях), имеем:

По условию дополняющей нежесткости (правило 14.2) выполняется Приравнивая левые части уравнений (14.2) и подставляя 2 = 1 1, получаем Аналогично находим Цена игры находится подстановкой найденных значений 1, 2 в любое из уравнений системы (14.2).

Перейдем теперь к более общему — графоаналитическому методу, с помощью которого можно находить решение матричной игры, где один из игроков имеет две чистые стратегии. Для игры формата 2 платежная матрица имеет вид В рассматриваемом случае смешанная стратегия игрока 1 может быть отождествлена с точкой отрезка [0, 1] (компоненты такой смешанной стратегии: и 1 ). При любом фиксированном = 1,..., выигрыш игрока 1 становится функцией одной переменной ; по правилу 13.3 a) явное выражение этой функции имеет вид: (, ) = 1 + 2 (1 ).

Построим графики этих функций (рис. 14.1) в декартовой системе координат, где 0 1 (графиком функции (, ) будет прямая ()).

Далее, построим график функции () = min (, ) — им служит нижняя огибающая данного семейства прямых (жирная ломаная). Пусть * — верхняя точка нижней огибающей и * — ее первая координата (другими словами, * есть точка отрезка [0, 1], в которой функция () принимает наибольшее значение: (* ) = max ().

Заметим теперь, что в произвольной матричной игре оценочные функции () = min (, ) и () = min (, ) совпадают между собой. В самом деле, используя разложение функции выигрыша (, ) по чистым стратегиям игрока 2 (правило 13.4 a)), можем записать равенство (, ) = (, ), откуда следует, что min (, ) совпадает с min (, ) при любом фиксированном, то есть () = ().

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

Укажем теперь способ нахождение точных значений компонент оптимальных стратегий обоих игроков и цены игры. Для этого надо воспользоваться правилом дополняющей нежесткости (правило 14.2), согласно которому, если один из игроков использует оптимальную смешанную стратегию, а другой — чистую, принадлежащую спектру какой–нибудь его оптимальной стратегии, то исход будет равен цене игры. Геометрически это означает, что чистая стратегия = 1,..., может входить в спектр какой–нибудь оптимальной смешанной стратегии игрока 2, лишь тогда, когда прямая () проходит через точку * (см. рис. 14.1). Выбирая две прямые, проходящие через точку * ( в нашем случае — это прямые (2) и (3)) и оставляя в платежной матрице соответствующие столбцы, получаем в итоге игру формата 22, для которой находим точное аналитическое решение по формулам (14.3) и (14.4). Для переноса этих решений в первоначальную матричную игру с платежной матрицей достаточно компоненты оптимальной смешанной стратегии игрока 2, соответствующие номерам выброшенных столбцов, положить равными нулю.

Замечание. Графоаналитический способ применим также к играм, в которых игрок 2 имеет ровно 2 чистых стратегии (то есть к играм формата 2). В этом случае смешанная стратегия игрока 2 может быть представлена точкой отрезка [0, 1] (в качестве оси абсцисс здесь берется ось –ов). Если игрок 1 использует чистую стратегию, то исход в ситуации (, ) есть (, ) = 1 +2 (1). Построив для каждого = 1,..., соответствующую прямую, находим далее верхнюю огибающую данного семейства прямых, которая будет графиком функции () = max (, ). Нижняя точка верхней огибающей является искомой — ее первая координата приближенно определяет оптимальную смешанную стратегию игрока 2, а вторая координата — цену игры в смешанных стратегиях. Точное решение получается здесь переходом к игре формата 2 2, как в предыдущем случае.

3. Нахождение решения матричной игры при помощи системы линейных неравенств основано на следующем простом факте.

Теорема 14.1. Для того, чтобы ситуация (0, 0 ) была седловой точкой в смешанных стратегиях, необходимо и достаточно, чтобы при всех = 1,..., и = 1,..., выполнялось Теоретико–игровой смысл условия (14.6) состоит в следующем: ситуация (0, 0 ) является седловой точкой тогда и только тогда, когда она устойчива относительно всех чистых односторонних отклонений игроков.

Доказательство. Необходимость условия (14.6) очевидна, так как чистая стратегия является частным случаем смешанной. Докажем достаточность. Пусть (14.6) выполнено. Правая часть (14.6) означает, что стратегия 0 гарантирует игроку 1 исход, равный (0, 0 ), против любой чистой стратегии игрока 2. Тогда по правилу 13.5 a) стратегия гарантирует игроку 1 указанный исход также против любой смешанной стратегиии игрока 2, то есть ( ) (0, ) (0, 0 ). Аналогично, используя правило 13.5 b), получаем, что ( ) (, 0 ) (0, 0 ). Таким образом, (0, 0 ) — седловая точка игры.

Следствие. Для того, чтобы вектор 0 был оптимальной смешанной стратегией игрока 1, вектор 0 — оптимальной смешанной стратегией игрока 2 и число R — ценой игры, необходимо и досточно, чтобы выполнялась следующая система линейных На теоретико–игровом языке условие (14.7) означает, что стратегия должна гарантировать игроку 1 исход против любой чистой стратегии игрока 2, а стратегия 0 должна гарантировать игроку 2 исход против любой чистой стратегии игрока 1.

Доказательство. Необходимость сразу следует из теоремы 14.1 с учетом того, что если 0 — оптимальная стратегия игрока 1, а 0 — оптимальная стратегия игрока 2, то (0, 0 ) = — цена игры (см.

теорему 13.3). Обратно, предположим, что система неравенств (14.7) выполнена. Тогда по правилу гарантирующей стратегии (правило 13.5) получаем при произвольных, Полагая в (14.8) = 0, = 0, имеем (0, 0 ) = ; таким образом, (14.8) означает, что (0, 0 ) — седловая точка. Так как = (0, 0 ), то есть цена игры в смешанных стратегиях.

Замечание. Система условий (14.7) представляет собой систему ( + ) линейных неравенств; явное выражение левых частей этих неравенств легко получить по правилу 13.3. При практическом использовании системы (14.7) для нахождения решения матричной игры необходимо к неравенствам (14.7) добавить условия неотрицательности переменных, ( = 1, ; = 1, и условия нормировки:

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

Теорема 14.3. Смешанная стратегия = (1,..., ) является оптимальной стратегией игрока 1 тогда и только тогда, когда она гарантирует игроку 1 исход, равный цене игры, против любой чистой стратегии другого игрока:

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

Задача 1. Найти неотрицательное решение системы линейных неравенств при наибольшем возможном значении параметра, удовлетворяющее дополнительному условию 1 + · · · + = 1.

Будем здесь предполагать, что цена игры строго положительна.

(Это предположение не уменьшает общности рассуждения, так как, прибавляя ко всем элементам платежной матрицы некоторую положительную константу, мы всегда можем перейти к эквивалентной игре с положительными выигрышами, а тогда ее цена также будет положительна.) Деля каждое неравенство системы (14.10) на > 0 и полагая = / ( = 1,..., ), приходим к эквивалентной системе линейных неравенств При этом + · · · + = =. Так как максимизация параметра эквивалентна минимизации суммы + · · · +, то получаем, что сформулированная выше задача 1 эквивалентна следующей.

Задача 1 Найти min (1,..., ) = 1 +· · ·+ при неотрицательных переменных 1 0,..., 0, удовлетворяющих ограничениям (14.11).

Задача 1 есть стандартная задача линейного программирования (см.

лекцию 4, п. 1). Решив ее, находим цену игры = 1/( + · · · + ) и компоненты оптимальной смешанной стратегии игрока 1: 1 =,..., = Двойственным образом, задача нахождения оптимальной смешанной стратегиии игрока 2 эквивалентна следующей задаче линейного программирования.

Задача 2 Найти max (1,..., ) = 1 +· · ·+ при неотрицательных переменных 1 0,..., 0, удовлетворяющих ограничениям Решив задачу 2, находим компоненты оптимальной смешанной стратегии игрока 2 по формулам: 1 = 1,..., =, где = 1/(1 + · · · + Заметим, что задачи 1 и 2 являются двойственными друг другу (см.

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

Задача № 17: Выбор момента поступления товара на рынок в условиях антагонистической конкуренции.

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

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

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

Пусть фирма выставляет товар на продажу в момент времени = 1,...,, а фирма — в момент = 1,...,. Может быть три случая.

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

2) >. Тогда фирма имеет доход в течение оставшихся ( + 1) единиц времени, то есть ее доход будет равен ( + 1) ден. ед.

3) =. В этом случае считаем, что товары обеих фирм имеют одинаковый спрос, следовательно, доход каждой из них составляет ( + 1)/2 ден. ед.

Итак, получаем матричную игру фирмы и фирмы, стартегиями которых являются дискретные моменты поступления товара на рынок.

Функция выигрышей этой игры задается следующим образом:

Рассмотрим более подробно случай = 4. Тогда матрица выигрышей принимает вид, представленный таблицей 14.1.

Разделив все элементы этой матрицы на > 0, перейдем к эквивалентной игре (таблица 14.2), имеющей те же оптимальные стратегии игроков (см. правило 14.1).

Для упрощения этой игры можно использовать правило отбрасывания доминируемых стратегий (правило 14.3). Здесь 3 (1) 4 и 2 (2) 1. Отбрасывая доминируемую стратегию 4 игрока 1 и доминируемую стратегию 1 игрока 2 (то есть вычеркивая в матрице выигрышей 4–ю строку и 1–й столбец), получаем игру с матрицей 1 (номера стратегий первоначальной игры сохраняются):

В игре с матрицей 1 имеется доминирование стратегий игрока 2: 3 (2) 4; вычеркивая доминируемый столбец № 4, приходим к игре с матрицей 2. В матрице 2 2–я строка доминируется полусуммой 1–й и 3–й строки, то есть в игре с матрицей выигрышей 2 2–я чистая стратегия игрока доминируется смешанной стратегией (1/2, 0, 1/2) игрока 1. Отбрасывая доминируемую стратегию 2, получаем игру с матрицей 3, в которой нет ни доминируемых строк, ни доминируемых столбцов. Решение последней игры находим аналитическим методом (см. п. 2). По формулам (14.3), (14.4) имеем: * = 1/2, * = 1/2, 2 = 1/2, 3 = 1/2; цена игры с матрицей 3 равна 3/2. Чтобы получить решение первоначальной игры, надо компоненты оптимальных стратегий, соответствующие вычеркнутым строчкам и столбцам, положить равными нулю, а цену игры умножить на. В результате получаем решение первоначальной игры в виде: * = (1/2, 0, 1/2, 0), * = (0, 1/2, 1/2, 0), = 3/2.

Задача № 18: Планирование посева в неопределенных погодных условиях.

У фермера имеется поле, которое он может засеять культурами 1, 2, 3 в любой пропорции. Урожайность этих культур зависит от сочетания погодных факторов, главными из которых являются осадки и тепло в летний сезон. Будем считать, что по признаку "осадки"лето имеет три градации: — нормальное, — засушливое, — дождливое; по признаку "тепло— две градации: — нормальное и — жаркое.

Известна урожайность культур 1, 2, 3 (в центнерах) в зависимости от сочетания типов погодных условий (таблица 14.3), а также рыночная цена этих культур (таблица 14.4).

Примечание. Расходы, связанные с выращиванием культур 1, 2, 3, считаем одинаковыми.

Как нужно действовать фермеру, чтобы получить максимальную прибыль?

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

Рассматриваем таблицу 14.5 как матричную игру фермера (игрок 1) против природы (игрок 2); при этом всевозможные стратегии природы перенумерованы по порядку. Нахождение решения полученной игры осуществляется по следующей схеме.

1. Убеждаемся, что в данной игре нет седловой точки в чистых стратегиях.

2. Производим упрощение игры, исключая доминируемые стратегии игроков. В данном случае 1 (2) 2, 5 (2) 6. Отбрасываем столбцы и 6, соответствующие доминируемым стратегиям игрока 2, после чего появляется пара стратегий игрока 1, находящаяся в отношении доминирования: 1 (1) 3. Отбрасывая строку 3, соответствующую доминируемой стратегии игрока 1, получаем в итоге матричную игру формата 2 4, представленную таблицей 14.6.

Решение данной матричной игры находим графоаналитическим методом (см. п.2), приняв за вероятность выбора стратегии 1 и за (1 ) вероятность выбора стратегии 2.

В декартовой системе координат (рис. 14.1) строим графики функций По графику находим приближенно координаты точки * — верхней точки нижней огибающей данного семейства прямых: * 0.4, 14.

Таким образом, компоненты оптимальной смешанной стратегии игрока приближенно равны (0.4, 0.6), а цена игры в смешанных стратегиях 14. Чтобы найти точные значения этих величин, а также компоненты оптимальной смешанной стратегии игрока 2, переходим к игре формата 2 2, оставляя из чистых стратегий игрока 2 только 1–ю и 5–ю (так как только прямые (1) и (5) проходят через точку * ). Получаем в итоге (14.3) и (14.4) находим:

Перенося эти результаты в первоначальную игру, получаем ее решение в виде: * = (0.4, 0.6, 0), * = (0.8, 0, 0, 0, 0.2, 0), = 13.8.

Результат здесь может быть интерпретирован следующим образом:

оптимальная стратегия фермера состоит в том, что 40% поля засеять культурой 1, 60% — культурой 2, а культуру 3 не сеять совсем. При этом гарантированная прибыль фермера (то есть прибыль, которая получается при наименее благоприятном сочетании погодных факторов), составляет 13.8 ден. ед.

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

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

Задача № 19: Инспекция предприятий торговли.

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

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

Какие действия инспектора и фирмы будут оптимальными?

Для решения этой задачи построим вначале математическую модель описанной конфликтной ситуации. Считаем, что магазины пронумерованы по убыванию количества бракованого товара, то есть 1 > 2 > · · · > > 0. Чистой стратегией инспектора является выбор магазина = 1,...,, который будет подвергнут инспекции, а чистой стратегией фирмы является выбор магазина = 1,...,, из которого изымается бракованый товар. В итоге получается матричная игра инспектора (игрок 1) с фирмой (игрок 2). Выигрышем инспектора будем считать объем обнаруженного им бракованого товара (если бракованый товар не обнаружен, то выигрыш равен нулю); выигрыш игрока 1 одновременно является также проигрышем игрока 2. Получаем в итоге матричную игру с платежной матрицей, заданной таблицей 14.7.

дальнейшего анализа существенным является выполнение следующего неравенства:

Неравенство (14.13) всегда выполнено при = 2. Предположим, что оно выполняется не при всех 3 и пусть ( + 1) — первый номер, при котором (14.13) нарушено (3 + 1 ). Тогда Убедимся, что при всех = 1,..., имеет место Действительно, при = 1 это неравенство выполняется в силу того, что числа ( )=1, убывают. Проверим его справедливость для = 2,...,.

Имеем:

Согласно (14.14) /1 > 1. Оценим второе слагаемое. Так как последовательность ( ) убывающая, то при всех =,..., выполнено + 1) = 1 и (14.16) установлено.

положительны. Легко проверить, что их сумма равна 1. Таким образом, –компонентный вектор * = (1,...,, 0,..., 0) является смешанной стратегией игрока 2. Найдем исход игры в ситуации (, * ), где = 1,..., — чистая стратегия игрока 1. Используя правило 13.3 b), имеем для функции выигрыша при,..., :

а для + 1 с учетом убывания чисел и (14.15), получаем Рассмотрим теперь –компонентый вероятностный вектор = 1,..., получаем а для + 1 имеем:

Полагая = ( 1), получаем, что для всех, = 1, выполнено (, * ), (*, ). Согласно следствия теоремы 14.1 имеем окончательно: * есть оптимальная смешанная стратегия игрока 1, * — оптимальная смешанная стратегия игрока 2, = ( 1) — цена игры Замечание. В ходе доказательства мы предполагали, что неравенство (14.13) выполнено не при всех > 2. Случай, когда в игре это неравенство выполнено при всех = 2,...,, легко сводится к уже рассмотренному следующим способом. Добавим к системе чисел 1,..., число 0 < +1 < так, чтобы +1 / 1. Тогда в расширенной игре по доказанному выше смешанная стратегия * = (*,..., *, 0), где * = / ( = 1, ), является оптимальной стратегией игрока 1; смешанная стратегия * = (1,...,, 0), где = 1 ( 1)/ ( = 1, ) — является оптимальной стратегией игрока 2; число = ( 1) является ценой игры. Вычеркнув последние (нулевые) компоненты в * и *, получим оптимальные стратегии игроков 1 и 2 в игре.

Тест для самоконтроля к лекции 1. Тройка (0, 0, ), где (0, 0 ) – седловая точка в смешанных стратегиях, = (0, 0 ), есть....

Варианты ответов: Оптимальная стратегия игрока 1;

2. Пусть в матричной игре с платежной матрицей A 0 – максиминная стратегия игрока 1, 0 минимаксная стратегия игрока 2, = =. Является ли тройка (0, 0, ) решением игры в смешанных стратегиях?

Варианты ответов: Да, всегда;

3. Пусть Г – матричная игра с платежной матрицей = ( ), Г – матричная игра с платежной матрицей = ( ), где = + (, – постоянные, > 0). Как связаны решения игр Г и Г ?

Варианты ответов: Решения этих игр совпадают;

4.Правило дополняющей нежесткости состоит в том, что если 0 – оптимальная стратегия игрока 1, то....

Варианты ответов: – (0, ) есть наибольший выигрыш игрока 5. В матричной игре с платежной матрицей = ( ), = 1,...,, = 1,..., ; условия доминирования стратегий игрока 1((1) ) и игрока 2((2) ) означают:

Варианты ответов:

6. Какие импликации справедливы?

()1 (1) 2, 2 (1) 3 = 1 (1) ()1 (2) 2, 2 (2) 3 = 1 (2) 7. После удаления доминируемых стратегий в игре с платежной матрицей :

остаются ятратегии....

8. После удаления всех доминируемых стратегий....

Варианты ответов: Решение сокращенной игры может не быть решением 9. В матричной игре формата 2 графиком функции = (, ), где 1 – смешанная стратегия игрока 1 и – чистая стратегия игрока 2, является....

Варианты ответов: Прямая линия;

10. В матричной игре формата 2 графиком функции = (, ), где 0 1 – смешанная стратегия игрока 1 и – чистая стратегия игрока 2( = 1, ..., ), является....

Варианты ответов: Прямая линия;

11. В матричной игре формата 2 координаты точки * (верхней точки нижней огибающей) имеют следующий теоретико-игровой смысл:

Варианты ответов: (): первая координата – оптимальная стратегия игрока 1, 12. Если в матричной игре формата 2 верхняя точка нижней огибающей лежит на пересечении прямых = (, 1 ) и = (, 2 ), то...

Варианты ответов: Стратегии 1 и 2 являются оптимальными;

13. Для матричной игры формата 2 2 рассмотрим условия:

) Игра не имеет решения в чистых стратегиях;

) В игре нет доминируемых стратегий;

) Оптимальные стратегии игроков 1 и 2 имеют полный спектр.

Какие из этих условий равносильны?

Варианты ответов: 14. В какой пропорции в игре с платежной матрицей игрок 1 должен использовать свои чистые стратегии, чтобы максимизировать свой минимальный ожидаемый выигрыш?

Варианты ответов: 1: 15. Два приятеля – Иванов и Петров проживают в общежитии, где имеется телевизор. Проходя мимо киоска, где продают телепрограммы, Иванов имеет две стратегии: К – купить, Н – не купить. Аналогичные две стратегии имеет Петров. Считая, что приятели не имеют возможности договориться, кто из них купит программу, какое решение следует принять Иванову? Матрица выигрышей данной игры приведена ниже(выигрыши оценены по 5-балльной шкале).

Чередовать стратегии К и Н в пропорции....

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

Варианты ответов: (): * = ( 5, 1, 0, 0) 17. Исключая доминируемые стратегии игроков, найдите их оптимальные смешанные стратегии в игре с платежной матрицей:

18. Найдите цену игры в смешанных стратегиях:

Варианты ответа: 4, 5, 8, 10, 11.

19.Найдите цену игры в смешанных стратегиях:

Указание: исключите доминируемые стратегии игроков.

Варианты ответа: 4, 5, 5 3, 5 1, 6.

20. Конкурирующие фирмы и могут вложить свои капиталы в производство следующих товаров: 1, 2, 3, 4 (фирма ) и 1, 2, 3, 4 (фирма ). Прибыль фирмы определяется таблицей:

Считая целью фирмы максимизацию своей минимальной ожидаемой прибыли, найдите оптимальное распределение каптала для фирмы.

Указание: исключите доминирующие стратегии игроков.

Ответ:

Фирма должна вложить весь капитал в производство товаров....

21. Найдите оптимальные смешанные стратегии игроков в матричной игре,( заданной платежной матрицей.

Указание: используйте графо-аналитический метод.

22. Найдите цену матричной игры в смешанных стратегиях:

Указание: используйте графо-аналитический метод.

Варианты ответа: 4; 4 1 ; 4 4 ; 5; 6.

23. Фермер может засеять поле культурами,, в любой пропорции.

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

Культура Указание: используйте графо-аналитический метод в сочетании с отбрасыванием доминирующих стратегий.

Варианты ответов: (1, 1, 1) 24. Найдите цену игры в смешанных стратегиях, где = 2 Указание: используйте графо-аналитический метод для транспонированной матрицы(ищется низшая точка на верхней огибающей) Варианты ответа: 5; 5 6 ; 5 1 ; 5 1 ; 6 1.

Лекция Игры лиц в нормальной форме Основные вопросы: 1. Игра лиц как математическая модель совместного принятия решения в условиях несовпадения интересов. Бескоалиционные игры. Примеры экономических задач, моделируемых бескоалиционными играми. 2. Принцип оптимальности в форме равновесия по Нэшу. Некоторые особенности принципа равновесия по Нэшу. 3. Теорема Нэша о реализуемости принципа равновесия в смешанных стратегиях. 4.

–устойчивость. Формулировка условия –устойчивости в рамках системного описания и на языке стратегий. 5. Задача № 20: Задача распределения ресурсов.

1. Системное описание задачи принятия решения в общем случае отражает воздействие на объект управления со стороны управляющих подсистем, где 2. Пусть — множество альтернативных управляющих воздействий –й управляющей подсистемы, — множество исходов (в качестве которых выступают состояния управляемой подсистемы). Функция реализации в этом случае задается в виде отображения множества ситуаций = в множество исходов. Таким образом, функция реализации каждой ситуации = (1,..., ) ставит в соответствие определяемый ею исход (). В теоретико–игровой терминологии управляющие подсистемы называются игроками, множество называется множеством стратегий игрока ( = 1,..., ).

Для задания целевой структуры рассматриваемой ЗПР необходимо задать оценочную функцию : R для каждого игрока. Композиция = называется функцией выигрыша игрока, а число (1,..., ) есть оценка полезности ситуации (1,..., ) с точки зрения игрока.

Итак, математическая модель данной задачи принятия решения имеет вид где = {1,..., } — множество игроков. — множество стратегий игрока, : R — функция выигрыша игрока. Такая математическая модель называется игрой лиц в нормальной форме.

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