Систематизированный процесс принятия решений

Введение Решения в условиях определенности, риска и неопределенности Решение – выбор альтернативы. В управлении принятие решений является систематизированным процессом. Решения, принимаемые руководителем для выполнения обязанностей, обусловленных занимаемой должностью называют организационными решениями. Организационные решения квалифицируют как запрограммированные и незапрограммированные. Запрограммированным решением называют решение, принятое как результат реализации определенной последовательности действий или шагов. Как правило, число возможных альтернатив ограничено, и выбор должен быть сделан в пределах направлений, заданных предприятием. Незапрограммированные решения – решения, принимаемые в ситуациях, которые в определенной степени новы, внутренне не структурированы или сопряжены с неизвестными факторами. Очень редко решения, принимаемые руководителем, могут рассматриваться как запрограммированные или незапрограммированные в чистом виде. Даже самое структурированное решение подразумевает некоторую личную инициативу лица, принимающего решение, а для принятия незапрограммированного решения почти всегда могут быть использованы моменты методологии принятия запрограммированных решений. Процесс принятия решений – процесс психологический. Решения варьируются от спонтанных до высокологичных. Поэтому процессы принятия решений делятся на имеющий интуитивный, основанный на суждениях и рациональный характер, хотя решение редко относится к какой либо одной категории. Интуитивное решение – это решение, принятое только на основе того, что руководитель имеет ощущение того, что оно правильно. Рациональное решение – это решение, обоснованное с помощью объективного аналитического процесса. Кроме всего вышеперечисленного на процесс принятия решений влияют такие факторы как личностные оценки руководителя, среда принятия решений, информационные ограничения, поведенческие ограничения и т.д. Решение принимается в условиях определенности, когда руководитель может с точностью определить результат каждого альтернативного решения, возможного в данной ситуации. Уровень определенности при принятии решений зависит от внешней среды. Он увеличивается при наличии твердой правовой базы, ограничивающей количество альтернатив и снижающей уровень риска. К решениям, принимаемым в условиях риска, относятся такие решения, результаты которых не являются определенными, но вероятность каждого возможного результата можно определить. Вероятность определяется в промежутке от 0 до 1 и представляет собой степень возможности совершения данного события. Сумма вероятностей всех альтернатив должна быть равна единице. Риск при принятии решений может быть различным. В экономике различают несколько типов риска: страховой, валютный, кредитный и т.д. В зависимости от типа риска, вероятность его можно определить математическими и статистическими методами. Наиболее желательный способ определения вероятности – объективность. Вероятность объективна, когда ее можно определить математическими методами или путем статистического анализа накопленного опыта. Вероятность может быть объективно определена, если поступит достаточно релевантной информации для того, чтобы прогноз оказался статистически достоверным. Во многих случаях предприятие не располагает достаточной информацией для объективной оценки вероятности. В таком случае часто руководители используют суждения о возможности совершения альтернатив с той или иной субъективной или предполагаемой вероятностью. 1 Решение принимается в условиях неопределенности, когда невозможно оценить вероятность потенциальных результатов. Это имеет место, когда требующие учета факторы настолько новы и сложны, что невозможно получить достаточно релевантной информации, позволяющей объективно определить вероятность, либо имеющаяся ситуация не подчиняется известным закономерностям. Поэтому вероятность определенного последствия невозможно предсказать с достаточной степенью достоверности. Неопределенность характерна для некоторых решений, принимаемых в быстро меняющихся условиях. Для принятия оптимальных решений необходимо использовать научный метод. В науке управления научный метод подразумевает наличие определенной структуры процесса принятия решений и использование различных методов и моделей принятия решений. Модель – это представление объекта, системы или процесса в форме отличной от оригинала, но сохраняющей основные его характеристики. В науке управления используются следующие модели принятия решений: - теория игр; - модели теории очередей; - модели управления запасами; - модель линейного программирования; - транспортные задачи; - имитационное моделирование; - сетевой анализ; - экономический анализ. Теория игр. Данный метод служит для моделирования оценки воздействия принятого решения на конкурентов. Изначально была разработана военными с тем, чтобы в стратегии учесть возможные действия противника. В бизнесе игровые модели используются для прогнозирования реакции конкурентов на изменение цен, модификацию и освоение новой продукции, предложения дополнительного обслуживания и т.д. Теория игр используется реже, чем другие модели, так как ситуации в реальном мире очень сложны и часто меняются. Модели теории очередей, или модели оптимального обслуживания используются для определения оптимального числа каналов обслуживания по отношению к потребности в них. Применяется в различных ситуациях, где есть клиенты и пункты их обслуживания (резервирование билетов по телефону, обслуживание клиентов в банке, количество разгрузочных площадок на складах и т.д.). Используются для уравновешивания расходов на дополнительные каналы обслуживания и потерь от обслуживания на уровне ниже оптимального. Модели управления запасами используются для определения времени размещения заказов на ресурсы и их количества, а также массы готовой продукции на складах. Цель данной модели оптимизация запасов на предприятии. Чрезмерное их накопление хотя помогает избежать потерь, обусловленных их нехваткой, во многих случаях сводит к минимуму издержки на размещение заказов, так как они размещаются в больших количествах, но также ведет к дополнительным издержкам на хранение, перегрузку, потери от порчи, уменьшение оборотных средств, что уменьшает мобильность предприятия в принятии решений при возникновении новой ситуации на рынке. Модели линейного программирования применяют для определения оптимального способа распределения дефицитных ресурсов при наличии конкурирующих потребностей. Данный вид модели наиболее распространен на промышленных предприятиях. Он заключается в том, что помогает максимизировать прибыль при наличии одного нескольких ресурсов, каждый из которых используется для производства нескольких видов товара. Обычно при решении оптимизации данного типа моделей обычно используется Симплексметод. Транспортные задачи – это задачи, с помощью которых оптимизируется доставка ресурсов при наличии нескольких пунктов отправки и нескольких пунктов получения при 2 различной стоимости доставки в различные пункты. Является частным видом задач линейного программирования. Имитационное моделирование означает процесс создания модели и ее экспериментальное использование для определения изменений реальной ситуации. Имитация используется в ситуациях, слишком сложных для математических методов типа линейного программирования. Экспериментируя на модели системы, можно установить, как она будет реагировать на определенные изменения или события, в то время, когда отсутствует возможность наблюдать эту систему в реальности. Сетевой анализ. Из сетевого анализа в основном используется теория графов. Теория графов позволяет составлять оптимальные графики осуществления различных проектов. Это позволяет минимизировать как время осуществления проекта, так и затраты по нему. Экономический анализ один из самых распространенных методов моделирования, хотя он и не воспринимается как моделирование. Экономический анализ вбирает в себя почти все методы оценки издержек и экономических выгод, а также относительной рентабельности деятельности предприятия. Экономический анализ включает в себя анализ безубыточности, определение прибыли на инвестированный капитал, величину чистой прибыли на данный момент времени и т.д. эти модели широко применяются в бухгалтерском и финансовом учете. При принятии решения вне зависимости от применяемых моделей существуют некоторые правила принятия решений. Правило принятия решения – это критерий, по которому выносится суждение об оптимальности данного конкретного исхода. Существует два типа правил. Один не использует численные значения вероятных исходов, второй – использует данные значения. Методы принятия решений: - платежная матрица; - дерево решений; - методы прогнозирования. Платежная матрица – один из методов статистической теории решений, оказывающий помощь руководителю в выборе одного из нескольких вариантов. В самом общем виде матрица означает, что платеж зависит от определенных событий, которые фактически совершаются. Если событие или состояние природы не случается на деле, платеж неизменно будет другим. Руководитель должен иметь возможность объективно оценить вероятность релевантных событий и рассчитать ожидаемое значение такой вероятности. Вероятность прямо влияет на определение ожидаемого значения – основного понятия платежной матрицы. Ожидаемое значение альтернативы или варианта – это сумма возможных значений, умноженных на соответствующие вероятности. Дерево решений – метод науки управления – схематичное представление проблемы принятия решений – используется для выбора наилучшего направления действий из имеющихся вариантов. Метод дерева решений может применяться как в ситуациях, в которых применяется платежная матрица, так и в более сложных ситуациях, в которых результаты одного решения влияют на последующие решения. То есть дерево решений – удобный метод для принятия последовательных решений. Методы прогнозирования. Прогнозирование – метод, в котором используется как накопленный в прошлом опыт, так и текущие допущения насчет будущего с целью его определения. Результат качественного прогнозирования может служить основой планирования. Существуют различные разновидности прогнозов: экономические прогнозы, прогнозы развития технологии, прогнозы развития конкуренции, прогнозы на основе опросов и исследований, социальное прогнозирование. Все типы прогнозов используют различные методы прогнозирования. Методы прогнозирования включают в себя: 3 - неформальные методы; - количественные методы; - качественные методы. Неформальные методы включают в себя следующие виды информации: 1. Вербальная информация – это наиболее часто используемая информация для анализа внешней среды. Сюда относят информацию из радио- и телепередач, от поставщиков, от потребителей, от конкурентов, на различных совещаниях и конференциях, от юристов, бухгалтеров и консультантов. Данная информация легко доступна, затрагивает все основные факторы внешнего окружения, представляющие интерес для предприятия. Однако она очень изменчива и нередко неточна. 2. Письменная информация – это информация из газет, журналов, информационных бюллетеней, годовых отчетов. Эта информация обладает теми же достоинствами и недостатками, что и вербальная информация. 3. Промышленный шпионаж. Количественные методы прогнозирования используются исходя из предположения, что деятельность в прошлом имела определенную тенденцию, которая может продолжиться и в будущем, и когда достаточно информации для выявления таких тенденций. К количественным методам относятся: 1. Анализ временных рядов. Он основан на допущении, согласно которому случившееся в прошлом дает достаточно хорошее приближение к оценке будущего. Проводится с помощью таблицы или графика. 2. Причинно-следственное (казуальное) моделирование. Наиболее математически сложный количественный метод прогнозирования. Используется в ситуациях с более чем одной переменной. Казуальное моделирование – прогнозирование путем исследования статистической зависимости между рассматриваемым фактором и другими переменными. Из казуальных прогностических моделей самыми сложными являются эконометрические модели, разработанные с целью прогнозирования динамики экономики. Качественные методы прогнозирования подразумевает прогнозирование будущего экспертами. Существует четыре наиболее распространенных метода качественного прогнозирования: 1. Мнение жюри – соединение и усреднение мнений экспертов в релевантных сферах. Неформальная разновидность данного метода – «мозговой штурм». 2. Совокупное мнение сбытовиков. Мнение дилеров или предприятий сбыта очень ценно, так как они имеют дело непосредственно с конечными потребителями и знают их потребности. 3. Модель ожидания потребителя – прогноз, основанный на результатах опроса клиентов предприятия. 4. Метод экспертных оценок. Он представляет собой процедуру, позволяющую группу экспертов приходить к согласию. По данному методу эксперты из различных областей заполняют опросник по данной проблеме. Затем им дают опросники, заполненные другими экспертами, и просят пересмотреть свое мнение либо аргументировать первоначальное. Процедура проходит 3-4 раза, пока в результате не будет выработано общее решение. Причем все опросники анонимны, как и анонимны сами эксперты, то есть эксперты не знают, кто еще входит в группу. ТЕМА 1. МАТРИЧНЫЕ ИГРЫ Лекция 1. Матричные игры В экономике и управлении встречаются ситуации, когда сталкиваются две и более стороны, преследующие различные цели. Причем результат, полученный каждой из сторон при реализации определенной стратегии, зависит от действий других сторон. Такие ситуации называются конфликтными. 4 Примеры: борьба фирм за рынок сбыта, аукцион, спортивные состязания, военные операции, парламентские выборы при наличии нескольких кандидатов, карточные игры. Простейшим примером конфликтной ситуации является игра с нулевой суммой или антагонистическая игра, в которой выигрыш одной стороны конфликта в точности совпадает с проигрышем другой стороны. Рассмотрим конфликт двух участников с противоположными интересами, математической моделью которого является игра с нулевой суммой. Участники игры – лица, принимающие решения, - называются игроками. Стратегия игрока – осознанный выбор одного из множества возможных вариантов его действий. Рассмотрим конечные игры, в которых множества стратегий игроков конечны: стратегии первого игрока пронумеруем числами от 1 до m, стратегии второго игрока – от 1 до n. Если первый игрок выбрал свою i-ую стратегию, а второй игрок – свою j-тую стратегию, то результатом такого совместного выбора будет платеж 𝑎𝑖𝑗 второго игрока первому. В качестве платежа может выступать не только денежная сумма, но и оценка полезности результата выбора игроками своих стратегий i и j. Таким образом, конечная игра с нулевой суммой однозначно определяется матрицей 𝑎11 𝑎12 … 𝑎1𝑛 𝑎21 𝑎22 … 𝑎2𝑛 ⋮ ⋮ ⋮ ⋮ 𝐴= , (1.1) 𝑎(𝑚−1)1 𝑎(𝑚−1)2 … 𝑎(𝑚−1)𝑛 𝑎𝑚2 … 𝑎𝑚𝑛 ) ( 𝑎𝑚1 которая называется платежной матрицей или матрицей выигрышей. Строки этой матрицы соответствуют стратегиям первого игрока, а столбцы – стратегиям второго игрока. Конечные игры с нулевой суммой называются матричными, т.к. целиком определяются своими платежными матрицами. Игра происходит партиями. Партия игры состоит в том, что игроки одновременно называют свой выбор: первый игрок называет некоторый номер строки матрицы А, а второй игрок - некоторый номер столбца этой матрицы (по своему выбору или случайно). После этого происходит «расплата». Пусть первый игрок назвал номер i, а второй – j. Тогда второй игрок платит первому сумму 𝑎𝑖𝑗 , и партия игры заканчивается. Если 𝑎𝑖𝑗 > 0, то это означает, что при выборе первым игроком i-й стратегии, а вторым – j-й, выигрывает первый игрок; если 𝑎𝑖𝑗 < 0, то выигрывает второй игрок. Цель каждого игрока – выиграть как можно большую сумму в результате большого числа партий. Смысл названий «конфликт с противоположными интересами» и «игра с нулевой суммой» состоит в том, что выигрыш каждого из игроков противоположен выигрышу противника, т.е. сумма выигрышей игроков равна нулю. Стратегия называется чистой, если выбор игрока неизменен от партии к партии. У первого игрока есть m чистый стратегий, у второго – n. При анализе игр противник считается сильным, т.е. разумным. Рассмотрим описанную конфликтную ситуацию с точки зрения первого игрока. Если первый игрок выбирает свою i-ую стратегию или i-ую строку матрицы А, то второй игрок, будучи разумным, выберет такую стратегию j, которая обеспечит ему наибольший выигрыш, а первому игроку соответственно наименьший, т.е. второй игрок выберет такой столбец j матрицы А, в котором платеж 𝑎𝑖𝑗 второго игрока первому минимален. Перебирая все свои стратегии i=1, 2, …m и первый игрок выбирает ту из них, при которой второй игрок, действуя максимально разумно, заплатит ему наибольшую сумму. Величина 𝛼 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑎𝑖𝑗 называется нижней ценой игры, а соответствующая 𝑖=1,2,…𝑚 𝑗=1,2,…𝑛 ей стратегия первого игрока – максиминной. Аналогичные рассуждения с точки зрения второго игрока определяют верхнюю цену игры 𝛽 = min max 𝑎𝑖𝑗 и соответствующую ей минимаксную стратегию второго игрока. 𝑗=1,2,…𝑛 𝑖=1,2,…𝑚 5 Нижняя цена игры 𝛼 представляет собой максимальный гарантированный выигрыш первого игрока, т.е. первый игрок обеспечивает себе выигрыш не меньше 𝛼, а верхняя цена игры 𝛽 – минимальный гарантированный проигрыш второго игрока, т.е. второй игрок обеспечивает себе проигрыш не больше 𝛽 или выигрыш не меньше (- 𝛽). Если 𝛼 = 𝛽, то говорят, что игра имеет седловую точку в чистых стратегиях, общее значение 𝛼 и 𝛽 называется ценой игры и обозначается 𝑣 = 𝛼 = 𝛽. При этом стратегии игроков, соответствующие седловой точке, называются оптимальными чистыми стратегиями, т.к. эти стратегии являются наиболее выгодными сразу для обоих игроков, обеспечивая первому – гарантированный выигрыш не менее v, а второму – гарантированный проигрыш не более –v, Отклонение от этих стратегий не выгодно. Пример 1.1. В платежной матрице 0,1 0,4 0,2 𝐴 = (0,5 0,4 0,3 ) 0,3 0,2 0,1 Указано, какую долю рынка выиграет предприятие у своего единственного конкурента, если оно будет действовать согласно каждой из возможных трех стратегий, а конкурент – согласно каждой из своих возможных трех стратегий. Определить, имеет ли данная игра седловую точку в чистых стратегиях. Решение. Припишем справа от строк платежной матрицы минимальные элементы этих строк (соответствующие выигрышу первого игрока в том случае, когда он выберет стратегию, соответствующую данной строке, а второй игрок при этом выберет стратегию, соответствующую наилучшему для него выигрышу); под столбцами платежной матрицы напишем максимальные элементы этих столбцов (соответствующие проигрышу второго игрока в том случае, когда он выберет стратегию, соответствующую данному столбцу, а первый игрок при этом выберет стратегию соответствующую наилучшему для него выигрышу): 0,1 0,4 0,2 0,1 (0,5 0,4 0,3 ) 0,3 = 𝛼 0,3 0,2 0,1 0,1 0,5 0,4 0,3 || 𝛽 Нижняя цена игры 𝛼 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑎𝑖𝑗 = 𝑚𝑎𝑥{0,1, 0,3, 0,1} = 0,3, соответствует 𝑖=1,2,…𝑚 𝑗=1,2,…𝑛 второй стратегии первого игрока. Верхняя цена игры 𝛽 = 𝑚𝑖𝑛 𝑚𝑎𝑥 𝑎𝑖𝑗 = 𝑚𝑖𝑛{0,5, 0,4, 0,3} = 0,3, соответствует 𝑗=1,2,…𝑛 𝑖=1,2,…𝑚 третьей стратегии второго игрока, поэтому если первый игрок будет действовать со второй стратегией, а второй игрок – с третьей, то игроки могут гарантировать себе: первый – выигрыш не менее 𝑣 = 𝛼 = 𝛽 = 0,3 = 30% рынка, а второй – что первый выиграет не более 𝑣 = 30% рынка. Таким образом, данная игра имеет седловую точку в чистых стратегиях (в платежной матрице седловая точка обведена рамкой), при этом оптимальная чистая стратегия первого игрока – вторая, оптимальная чистая стратегия второго игрока – третья, а цена игры равна 𝑣 = 0,3. Если первый игрок будет следовать своей оптимальной чистой стратегии (второй), а второй игрок отклонится от своей оптимальной чистой стратегии (третьей), то он ухудшит свое положение и будет проигрывать не 30%, а 50% или 40% рынка. Первому игроку также невыгодно отклоняться от своей второй стратегии, если второй игрок будет придерживаться третьей. Матричная игра не всегда имеет седловую точку в чистых стратегиях. Пример 1.2 Игра «Угадывание монеты». Правила игры следующие: первый игрок прячет в кулаке одну из двух монет – 1 руб. или 5 руб. – по своему выбору и незаметно от 6 второго игрока, а второй игрок пытается угадать, какая монета спрятана. Если угадывает, то получает эту монету, если нет, то платит первому игроку 3 руб. Доказать, что данная игра не имеет седловой точки в чистых стратегиях. Решение. Платежная матрица имеет вид: −1 3 А=( ) 3 −5 Нижняя цена игры 𝛼 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑎𝑖𝑗 = 𝑚𝑎𝑥{−1, −5} = −1. 𝑖=1,2,…𝑚 𝑗=1,2,…𝑛 Верхняя цена игры 𝛽 = 𝑚𝑖𝑛 𝑚𝑎𝑥 𝑎𝑖𝑗 = 𝑚𝑖𝑛{3, 3} = 3. 𝑗=1,2,…𝑛 𝑖=1,2,…𝑚 Таким образом, 𝛼 ≠ 𝛽 и седловой точки в чистых стратегиях в игре нет. Теорема. В любой матричной игре нижняя цена не превосходит верхнюю цену игры: 𝛼 ≤ 𝛽. Доказательство. Любой элемент 𝑎𝑖𝑗 платежной матрицы не меньше минимального элемента i-й строки: 𝑎𝑖𝑗 ≥ 𝑚𝑖𝑛 𝑎𝑖𝑗 и не больше максимального элемента j-го столбца: 𝑎𝑖𝑗 ≤ 𝑗=1,2,…𝑛 𝑚𝑎𝑥 𝑎𝑖𝑗 . Таким образом, 𝑖=1,2,…𝑚 𝑚𝑖𝑛 𝑎𝑖𝑗 ≤ 𝑎𝑖𝑗 ≤ 𝑚𝑎𝑥 𝑎𝑖𝑗 , откуда 𝑗=1,2,…𝑛 𝑖=1,2,…𝑚 𝑚𝑖𝑛 𝑎𝑖𝑗 ≤ 𝑚𝑎𝑥 𝑎𝑖𝑗 . 𝑗=1,2,…𝑛 𝑖=1,2,…𝑚 Левая часть этого неравенства зависит от номера строки i, а правая часть не зависит, поэтому для любого столбца j 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑎𝑖𝑗 ≤ 𝑚𝑎𝑥 𝑎𝑖𝑗 или 𝛼 ≤ 𝑚𝑎𝑥 𝑎𝑖𝑗 (одновременно для 𝑖=1,2,…𝑚 𝑗=1,2,…𝑛 всех j). Но это означает, что 𝛼 ≤ 𝑚𝑖𝑛 𝑖=1,2,…𝑚 𝑖=1,2,…𝑚 𝑚𝑎𝑥 𝑎𝑖𝑗 или 𝛼 ≤ 𝛽, что и требовалось доказать. 𝑗=1,2,…𝑛 𝑖=1,2,…𝑚 Рассмотрим ситуацию, когда нижняя цена игры строго меньше верхней, т.е. когда в игре отсутствует седловая точка. Смешанной стратегией первого игрока называется вектор 𝑝 = (𝑝1 , 𝑝2 , … , 𝑝𝑚 ), где все 𝑝𝑖 ≥ 0 (𝑖 = 1, 2, … , 𝑚), а ∑𝑚 𝑖=1 𝑝𝑖 = 1. При этом 𝑝𝑖 – вероятность, с которой первый игрок выбирает свою i-ую стратегию. Аналогично определяется смешанная стратегия 𝑞 = (𝑞1 , 𝑞, … , 𝑞𝑛 ) второго игрока. Чистая стратегия также подпадает под определение смешанной – в этом случае все вероятности равны нулю, кроме одной, равной единице. Математическое ожидание дискретной случайной величины – это взвешенное среднее всех ее возможных значений, причем в качестве весового коэффициента берется вероятность соответствующего исхода, т.е. сумма произведений всех возможных значений случайной величины на их вероятности. Предположим, что х может принимать n конкретных значений (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) и что вероятность получения хi равна pi. Тогда 𝑀(𝑥)=∑𝑛𝑖=1 𝑥𝑖 𝑝𝑖 Пример. Число очков, выпадающее при бросании одной игральной кости. В данном случае возможны шесть исходов, каждый из которых имеет вероятность 1/6, поэтому 1 1 1 1 1 1 𝑀(𝑥) = ∑6𝑖=1 𝑥𝑖 𝑝𝑖 = 1 × 6 + 2 × 6 + 3 × 6 + 4 × 6 + 5 × 6 + 6 × 6 = 3,5 Математическое ожидание случайной величины часто называют ее средним по генеральной совокупности. Для случайной величины х это значение часто обозначается как µ. Если игроки играют со своими смешанными стратегиями 𝑝 = (𝑝1 , 𝑝2 , … , 𝑝𝑚 ) и 𝑞 = (𝑞1 , 𝑞, … , 𝑞𝑛 ) соответственно, то математическое ожидание выигрыша первого игрока равно: 𝑚 𝑛 𝑀(𝑝, 𝑞) = ∑ ∑ 𝑎𝑖𝑗 𝑝𝑖 𝑞𝑗 𝑖=1 𝑗=1 И совпадает с математическим ожиданием проигрыша второго игрока. Стратегии 𝑝∗ = (𝑝1 ∗ , 𝑝2 ∗ , … , 𝑝𝑚 ∗ ) и 𝑞 ∗ = (𝑞1 ∗ , 𝑞2 ∗ , … , 𝑞𝑛 ∗ ) называются оптимальными смешанными стратегиями соответственно первого и второго игрока, если 𝑀(𝑝, 𝑞 ∗ ) ≤ 𝑀(𝑝∗ , 𝑞 ∗ ) ≤ 𝑀(𝑝∗ , 𝑞). Если у обоих игроков есть оптимальные смешанные стратегии, то пара (𝑝∗ , 𝑞 ∗ ) называется решением игры (или седловой точкой в смешанных стратегиях), а число 7 𝑣 = 𝑀(𝑝∗ , 𝑞 ∗ ) - ценой игры. Теорема фон Неймана. Каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий. Лекция 2. Матричные игры (продолжение) Дублирование и доминирование стратегий Если матрица игры содержит несколько одинаковых строк (столбцов), то из них оставляют только одну строку (один столбец), а остальные строки (столбцы) отбрасываются. Отброшенным стратегиям приписываются нулевые вероятности. Это – дублирование стратегий. Если i-я строка поэлементно не меньше (≥) j-й строки, то говорят, что i-я строка доминирует на j-й строкой. Поэтому игрок 𝐴 не использует j-ю стратегию, так как его выигрыш при i-й стратегии не меньше, чем при j-й стратегии. Вне зависимости от того, как играет игрок 𝐵. Аналогично, если i-й столбец поэлементно не меньше (≥) j-го столбца, то говорят, что j-й столбец доминирует над i-м столбцом. Поэтому игрок 𝐵 не использует i-ю стратегию. Так как его проигрыш (равный выигрышу игрока 𝐴) при j-й стратегии не больше (≤), чем при i-й стратегии, вне зависимости от того, как играет игрок 𝐴. Это – доминирование стратегий. Если игра 𝑚 × 𝑛 имеет седловую точку, то после упрощения получится игра 1×1. Пример 1.3. Следует упростить матрицу игры: 8 9 9 4 6 5 8 7 𝐴=( ). 3 4 8 6 8 9 9 4 Первая и четвертая строки равны, поэтому отбросим четвертую строку, а вероятность будет 𝑝4 = 0. 8 9 9 4 Получим матрицу (6 5 8 7). 3 4 8 6 Вторая строка доминирует на третьей строкой (6 > 3, 5 > 4, 8 = 8, 7 > 6). Поэтому отбросим третью строку, а вероятность будет 𝑝3 = 0. 8 9 9 4 Получим матрицу ( ). 6 5 8 7 Второй столбец доминирует на третьим (9 = 9, 5 < 8). Поэтому отбросим третий столбец, а вероятность будет 𝑞3 = 0. 8 9 4 Получим матрицу ( ). 6 5 7 Строки между собой несравнимы (8 > 6, 4 < 7), столбцы тоже (8 < 9, 6 > 5, 8 > 4, 6 < 7, 9 > 4, 5 < 7). Дальнейшее упрощение невозможно. Игра сведена от 4 × 4 к игре 2 × 3. Решение игры 𝟐 × 𝟐 1 −1 ) −1 1 Припишем строкам вероятности 𝑝 и (1 − 𝑝) соответственно. 𝑝 1 −1 ). (1 − 𝑝) (−1 1 Пример 1.4. Найдем решение матричной игры ( 8 𝑝 Умножив столбец ((1 − 𝑝)) поэлементно на первый столбец и сложив произведения, получим линейную зависимость 𝑣1 (𝑝) = 1 × 𝑝 + (−1) × (1 − 𝑝) = 2𝑝 − 1. Это средний выигрыш игрока 𝐴 при применении игроком 𝐵 своей первой стратегии. 𝑝 Умножив столбец ((1 − 𝑝)) поэлементно на второй столбец и сложив произведения, получим линейную зависимость 𝑣2 (𝑝) = (−1) × 𝑝 + 1 × (1 − 𝑝) = −2𝑝 + 1. Это средний выигрыш игрока 𝐴 при применении игроком 𝐵 своей второй стратегии. Приравняем полученные зависимости: 2𝑝 − 1 = −2𝑝 + 1. Получим 𝑝 = 1⁄2, (1-𝑝) = 1⁄2, т.е. оптимальная смешанная стратегия игрока 𝐴 𝑝∗ = (1⁄2 , 1⁄2). Подставив 𝑝∗ в любую из зависимостей, получим цену игры 𝑣 = 𝑀(1⁄2) = 0. Припишем столбцам вероятности 𝑞 и (1 − 𝑞) соответственно. 𝑞 (1 − 𝑞) 1 −1 ( ). −1 1 Умножив строку (𝑞, (1 − 𝑞)) на первую строку и сложив произведения, получим линейную зависимость 𝜇1 (𝑞) = 1 × 𝑞 + (−1) × (1 − 𝑞) = 2𝑞 − 1. Это средний выигрыш игрока 𝐴 (проигрыш игрока 𝐵) при применении игроком 𝐴 своей первой стратегии. Умножив строку (𝑞, (1 − 𝑞)) на вторую строку и сложив произведения, получим линейную зависимость 𝜇2 (𝑞) = (−1) × 𝑞 + 1 × (1 − 𝑞) = −2𝑞 + 1. Это средний выигрыш игрока 𝐴 (проигрыш игрока 𝐵) при применении игроком 𝐴 своей второй стратегии. Приравняем полученные зависимости: 2𝑞 − 1 = −2𝑞 + 1. Имеем 𝑞 = 1⁄2, (1 − 𝑞) = 1⁄ , т.е. оптимальная смешанная стратегия игрока 𝐵 𝑞 ∗ = (1⁄ , 1⁄ ). 2 2 2 Таким образом, каждую стратегию необходимо применять с частотой 1⁄2. Пример 1.5. Найти решение игры из примера 1.2 в смешанных стратегиях. Решение. Платежная матрица, построенная ранее: −1 3 А=( ) 3 −5 Пусть первый игрок выбирает свою первую стратегию с вероятностью 𝑝 ∋ [0,1], а вторую – с вероятностью (1 − 𝑝), т.е. первый игрок играет со смешанной стратегией 𝑝 = (𝑝, 1 − 𝑝). Обозначим 𝑣𝑗 (𝑝) ожидаемый выигрыш, т.е. математическое ожидание выигрыша, первого игрока, если второй игрок при этом выберет свою j-ю стратегию. В рассматриваемом примере 𝑣1 = (−1)𝑝 + 3(1 − 𝑝), 𝑣2 = 3𝑝 + (−5)(1 − 𝑝). Построим графики этих функций, представленные на рисунке 1.1. 4 𝑣𝑗 (𝑝) 𝑣1 (𝑝) 3 𝑣2 (𝑝) 2 1 -1 -2 0,1 0,2 0,3 0,4 0,5 0,6 0,7 2 𝑝∗ = 3 0,8 0,9 1 𝑝 -3 -4 -5 -6 а) гарантированный выигрыш первого игрока в зависимости от его смешанной стратегии 9 4 𝜇𝑗 (𝑞) 𝜇1 (𝑝) 3 𝜇2 (𝑝) 2 1 -1 -2 0,1 0,2 0,3 0,4 0,5 0,6 0,7 2 ∗ 𝑞 = 3 0,8 0,9 1 𝑝 -3 -4 -5 -6 б) верхняя граница проигрыша второго игрока в зависимости от его смешанной стратегии Рис. 1.1. – Гарантированный выигрыш первого игрока и верхняя граница проигрыша второго игрока в игре «Угадывание монеты» в зависимости от их смешанных стратегий» Второй игрок так выбирает свои стратегии, чтобы обеспечить первому минимальный выигрыш: 𝑣(𝑝) = min{𝑣1 (𝑝), 𝑣2 (𝑝)}. Эта функция отмечена на рисунке 1.1. а) жирной линией. Второй игрок в любом случае заставит первого выиграть как можно меньше, т. е. в рассматриваемой игре: - при 𝑝 ≤ 𝑝∗ , где 𝑝∗ соответствует максимуму функции 𝑣(𝑝), второй игрок будет выбирать свою вторую стратегию, и первый игрок будет выигрывать 𝑣2 (𝑝) - при 𝑝 ≥ 𝑝∗ второй игрок будет выбирать первую стратегию, и первый игрок будет выигрывать 𝑣1 (𝑝). Наилучший для первого игрока выбор соответствует 𝑣 = max 𝑣(𝑝), т. е. 𝑝 ≥ 𝑝∗ , при 𝑝∈[0.1] этом цена игры равна 𝑣. 2 В рассматриваемом примере 𝑝∗ = 3, определяемая из условия 𝑣1 (𝑝) = 𝑣2 (𝑝) или −𝑝 + 3(1 − 𝑝) = 3𝑝 − 5(1 − 𝑝). Таким образом, оптимальной смешанной стратегией первого игрока является 2 1 2 2 1 стратегия 𝑝∗ = (3 ; 3), при этом цена игры равна 𝑣 = 𝑣1 (3) = 𝑣2 (3) = 3. Вне зависимости от того, какую стратегию выберет второй игрок, первый игрок будет выигрывать в среднем за 1 большое число партий по 3 руб. за одну партию. Найдем оптимальную смешанную стратегию второго игрока. Пусть второй игрок выбирает первую стратегию с вероятностью 𝑞 ∋ [0,1], а вторую – с вероятностью (1 − 𝑞), т. е. вектор смешанной стратегии второго игрока имеет вид 𝑞 = (𝑞, 1 − 𝑞). Тогда проигрыш второго игрока, представленный на рисунке 1.1 б), равен: 𝜇1 (𝑞) = −𝑞 + 3(1 − 𝑞), если первый игрок выбирает свою первую стратегию, 𝜇2 (𝑞) = 3𝑞 − 5(1 − 𝑞), если первый игрок выбирает свою вторую стратегию. Наилучшее с точки зрения второго игрока значение 𝑞 определяется из условия min max{𝜇1 (𝑞), 𝜇2 (𝑞)}. 𝑞∋[0.1] 2 Как видно из рис. 1.1, б, в данном случае 𝜇1 (𝑞) = 𝜇2 (𝑞), откуда 𝑞 ∗ = 3. 2 1 Поэтому оптимальная смешанная стратегия второго игрока равна 𝑞 ∗ = (3 ; 3). 10 Решение игры 𝟐 × 𝒏 Приписав первой строке вероятность 𝑝, а второй строке – вероятность 1 − 𝑝, получим n линейных зависимостей. Изобразим их графики. Возьмем нижнюю огибающую, т.е. такую ломаную из отрезков построенных прямых, что вся картинка лежит выше этой ломаной. Точка с наибольшей координатой 𝑣𝑖 (𝑝) дает нам 𝑝 (первая координата) и цену игры 𝑣 (вторая координата). Пусть это точка пересечения i-й и j-й прямых. Тогда припишем i-му столбцу вероятность 𝑞, а j-му столбцу – вероятность (1 − 𝑞). Всем остальным столбцам припишем нулевые вероятности. Находим 𝑞 и (1 − 𝑞). Пример 1.6. Найдем решение матричной игры: −1 1 −1 2 𝐴=( ). 0 −1 2 −2 Первый столбец доминирует над третьим столбцом. Поэтому отбросим третий −1 1 2 столбец. Вероятность 𝑞3 = 0. Получим матрицу ( ). 0 −1 −2 Припишем строка вероятности 𝑝 и (1 − 𝑝) соответственно. 𝑝 −1 1 2 (1 − 𝑝) ( 0 −1 −2). Получим линейные зависимости 𝑣1 (𝑝) = (−1) × 𝑝 + 0 × (1 − 𝑝) = −𝑝; 𝑣2 (𝑝) = 1 × 𝑝 + (−1) × (1 − 𝑝) = 2𝑝 − 1; 𝑣3 (𝑝) = 2 × 𝑝 + (−2) × (1 − 𝑝). Изобразим их графики. 0 ≤ 𝑝 ≤ 1. 2,5 2 𝑣𝑗 (𝑝) (3) 1,5 (2) 1 0,5 1 -0,5 B -1 C 𝑝 (1) -1,5 -2 -2,5 А Рис. 1.2 – Графики функций линейных зависимостей 𝑣1 , 𝑣2 , 𝑣3 и нижней огибающей ломаной прямой Возьмем нижнюю огибающую. Это ломаная ABC. Точка B – это точка пересечения прямых (1) и (3). Поэтому припишем первому столбцу вероятность 𝑞, а третьему столбцу – вероятность (1 − 𝑞). Всем остальным столбцам припишем нулевые вероятности. Найдем координаты точки B. −𝑝 = 4𝑝 − 2, 𝑝 = 2⁄5 (вероятность применения игроком А своей первой стратегии), (1 − 𝑝) = 3⁄5 (вероятность применения игроком А своей второй стратегии). Все цифры игрок А делит на полноценные «пятерки». Первые две цифры относятся к первой стратегии, а три последние – ко второй стратегии: первая стратегия (1,2,6,7) и вторая 11 стратегия (3,4,5,8,9,0). Перед своим очередным ходом игрок А смотрит в таблицу случайных чисел. Если «выпадает» 1,2,6,7, то он играет первую стратегию; если «выпадает» 3,4,5,8,9,0, то он играет вторую стратеги. Цена игры 𝑣 = 𝑣1 (2⁄5) = − 2⁄5. Примечание. Математическая функция СЛЧИС мастера формул 𝑓𝑥 пакета Excel возвращает случайное число; 𝑓𝑥 → математические → СЛЧИС →ОК. У этой функции не оргументов. ОК. После этого в ячейке появится десятичная дробь из интервала (0,1). Исследователь берет нужное число знаков после запятой. После нажатия клавиши F9 десятичная дробь в ячейке изменится. Найдем ненулевые вероятности выбора стратегий игроком B. Используем матрицу 𝑞 (1 − 𝑞) −1 1 2 ( ). 0 −1 −2 Имеем (−1) × 𝑞 + 1 × 0 + 2 × (1 − 𝑞) = 0 × 𝑞 + (−1) × 0 + (−2) × (1 − 𝑞), т.е. 𝑞 = 4⁄ , (1 − 𝑞) = 1⁄ . 5 5 Для игрока А 𝑝∗ = (2⁄5 , 3⁄5); для игрока B 𝑞 ∗ = (4⁄5 , 0,0, 1⁄5). 4 2 −1 Задача: Найти решение матричной игры ( ). Ответ: v=4/11, −4 0 2 6 5 3 8 𝑝∗ = (11 , 11) , 𝑞 ∗ = (11 , 0, 11). Пример 1.7. Рассмотрим игру с платежной матрицей −2 3 4 1 ( ) 2 −4 −3 −1 Требуется найти оптимальные смешанные стратегии игроков. Решение. Проверим, имеет ли данная игра седловую точку в чистых стратегиях. Нижняя цена игры 𝛼 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑎𝑖𝑗 = 𝑚𝑎𝑥{−2, −4} = −2 𝑖=1,2,…𝑚 𝑗=1,2,…𝑛 Верхняя цена игры 𝛽 = 𝑚𝑖𝑛 𝑚𝑎𝑥 𝑎𝑖𝑗 = 𝑚𝑖𝑛{2, 3, 4, 1} = 1 𝑗=1,2,…𝑛 𝑖=1,2,…𝑚 т. е. 𝛼 ≠ 𝛽, значит, седловой точки в чистых стратегиях в игре нет. Пусть первый игрок играет со смешанной стратегией 𝑝 = (𝑝, 1 − 𝑝). Обозначим 𝑣𝑗 (𝑝) ожидаемый выигрыш первого игрока, если второй игрок при этом выберет свою j-ю стратегию. В рассматриваемом примере 𝑣1 = (−2)𝑝 + 2(1 − 𝑝), 𝑣2 = 3𝑝 + (−4)(1 − 𝑝), 𝑣3 = 4𝑝 + (−3)(1 − 𝑝), 𝑣4 = 𝑝 + (−1)(1 − 𝑝). Графики этих функций построены на рис.1.3. Второй игрок так выбирает свои стратегии, чтобы обеспечить первому минимальный выигрыш: 𝑣(𝑝) = 𝑚𝑖𝑛{𝑣1 (𝑝), 𝑣2 (𝑝), 𝑣3 (𝑝), 𝑣4 (𝑝)}. Эта функция отмечена на рис. 1.3 жирной линией. 6 При 𝑝 ∈ [0.1), где 𝑝∗ = определяется из условия 𝑣1 (𝑝) = 𝑣2 (𝑝), второй игрок будет 11 выбирать свою вторую стратегию, и первый игрок будет выигрывать 𝑣2 (𝑝); При 𝑝 ∈ (0.1], второй игрок будет выбирать первую стратегию, и первый игрок будет выигрывать 𝑣1 (𝑝). Наилучший для первого игрока выбор при этом соответствует 𝑣 = max 𝑣(𝑝). 𝑝∈[0.1] 12 5 4 3 𝑣3 (𝑝) 2 𝑣4 (𝑝) 1 -1 -2 -3 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 𝑣1 (𝑝) 𝑣2 (𝑝) -4 Рис. 1.3. Гарантированный выигрыш первого игрока в примере 1.4 при различном выборе смешанной стратегии Таким образом, оптимальной смешанной стратегией первого игрока является 6 5 6 6 2 стратегия 𝑝∗ = (11 ; 11), при этом цена игры равна 𝑣 = 𝑣1 (11) = 𝑣2 (11) = − 11. Величина 2 6 − 11 получается путем подстановки величины 11 в уравнения 𝑣1 = (−2)𝑝 + 2(1 − 𝑝), 𝑣2 = 3𝑝 + (−4)(1 − 𝑝), Второй игрок, действуя разумно, никогда не будет выбирать третью и четвертую стратегии, увеличивающие выигрыш первого игрока, поэтому вектор оптимальной смешанной стратегии второго игрока имеет вид 𝑞 = (𝑞, 1 − 𝑞, 0, 0). Тогда проигрыш второго игрока равен: 𝜇1 (𝑞) = −2𝑞 + 3(1 − 𝑞), если первый игрок выбирает свою первую стратегию, 𝜇2 (𝑞) = 2𝑞 − 4(1 − 𝑞), если первый игрок выбирает свою вторую стратегию. 7 Значение 𝑞 ∗ определяется из условия 𝜇1 (𝑞) = 𝜇2 (𝑞), оно равно 𝑞 ∗ = 11. Следовательно, оптимальная смешанная стратегия второго игрока равна 𝑞 ∗ = 7 4 7 (11 ; 11 , 0,0). Если подставить 11 в уравнения 𝜇1 (𝑞) = −2𝑞 + 3(1 − 𝑞), 𝜇2 (𝑞) = 2𝑞 − 4(1 − 2 𝑞), получим цену игры 𝑣 = − 11. Решение игры 𝒎 × 𝟐 Приписав первому столбцу вероятность 𝑞, а второму столбцу – вероятность 1 − 𝑞, получим 𝑚 линейных зависимостей. Изобразим их графики. Возьмем верхнюю огибающую, т.е. такую ломаную из отрезков построенных прямых, что вся картинка лежит ниже этой ломаной. Точка с наименьшей координатой 𝜇 дает нам 𝑞 (первая координата) и цену игры 𝑣 (вторая координата). Пусть это точка пересечения i-й и j-й прямых. Тогда припишем i-й строке вероятность 𝑝, а j-й строка вероятность (1 − 𝑝). Всем остальным строкам припишем нулевые вероятности. Находим 𝑝 и (1 − 𝑝). Пример 1.8. Найти решение матричной игры 1 4 𝐴 = (3 −2). 5 Припишем столбцам вероятности 𝑞 и (1 − 𝑞) соответственно: 13 𝑞 (1 − 𝑞) 1 4 (3 −2 ) 5 Получим линейные зависимости 𝜇1 (𝑞) = 1 × 𝑞 + 4 × (1 − 𝑞) = 4 − 3𝑞 (1), 𝜇2 (𝑞) = 3 × 𝑞 + (−2) × (1 − 𝑞) = 5𝑞 − 2 (2), 𝜇3 (𝑞) = 000 × 𝑞 + 5 × (1 − 𝑞) = 5 − 5𝑞 (3). Изобразим их графики. 0 ≤ 𝑞 ≤ 1. 6 D 5 4 3 C 2 (2) B A (1) 1 (3) -1 -2 -3 Возьмем верхнюю огибающую. Это ломаная ABCD. Точка В – это точка с наименьшей второй координатой на этой огибающей. Точка В – это точка пересечения прямых (1) и (2). Поэтому припишем первой строке вероятность p, а второй строке – вероятность 1 – p. Всем остальным строкам припишем нулевые вероятности. Найдем координаты точки В. 4 – 3q = 5q – 2, q = 3⁄4 (вероятность применения игроком В своей первой стратегии), 1 – q = 1⁄4 (вероятность применения игроком В своей второй стратегии). Все цифры игрок В делит на полноценные «четверки». Первые три цифры относятся к первой стратегии, а последняя – ко второй стратегии: первая стратегия (1, 2, 3, 5, 6, 7) и вторая стратегия (4, 8). Перед своим очередным ходом игрок А смотрит в таблицу случайных чисел. Если 3 7 «выпадает» 4, 8, то он играет вторую стратегию. Цена игры v = w4 = 4. Цифры 0 и 9 игнорируются. 𝑝 1 4 Найдем решение для игрока А: 1 − 𝑝 (3 −2 ). 5 5 3 1 × 𝑝 + 3 × (1 − 𝑝) + 0 × 0 = 4 × 𝑝 + (−2) × (1 − 𝑝) + 5 × 0, то есть p = 8 , 1 - p = 8. 5 Для игрока А p* = ( 8 , 3 8 3 1 , 0), для игрока В q* = ( 4 , 4). 3 1 5 2 1 Задача: Найти решение матричной игры (−1 3). Ответ: 𝑣 = 3 ,𝑝∗ = (3 , 3 , 0) , −2 2 1 1 ∗ 𝑞 = (3 , 3). В данной лекции были рассмотрены два примера матричных игр, в которых у первого игрока ровно две стратегии, а у второго игрока произвольное количество стратегий. Такие игры можно решить графическим способом. Разберем теорему, дающую способ решения матричных игр, в которых и у первого, и у второго игрока произвольное количество стратегий. В общем случае любая матричная игра 14 с произвольным числом стратегий у игроков может быть сведена к паре взаимно двойственных задач линейного программирования, и эти задачи имеют оптимальные решения. Теорема. В любой матричной игре у игроков есть оптимальные смешанные стратегии. Доказательство. Пусть рассматривается игра с платежной матрицей A (1.1), все элементы которой строго положительны; 𝑝 = (𝑝1 , 𝑝2 , … , 𝑝𝑚 ) и 𝑞 = (𝑞1 , 𝑞2 , … , 𝑞𝑛 ) — смешанные стратегии первого и второго игрока. 𝑛 Математическое ожидание выигрыша первого игрока 𝑀(𝑝, 𝑞) = ∑𝑚 𝑖=1 ∑𝑗=1 𝑎𝑖𝑗 𝑝𝑖 𝑞𝑗 при любом выборе игроками своих смешанных стратегий р и q будет положительным, так как все элементы платежной матрицы положительны, среди неотрицательных 𝑝𝑖 есть хотя бы одно строго положительное число и среди неотрицательных 𝑞𝑗 также есть хотя бы одно строго положительное. Пусть первый игрок выбирает такую стратегию р, чтобы математическое ожидание его выигрыша независимо от того, какую стратегию выберет второй игрок, было не меньше некоторой гарантированной величины r (нижняя цена игры 𝛼 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑎𝑖𝑗 > 0, поскольку все платежи 𝑎𝑖𝑗 > 0, r не меньше 𝛼, поэтому 𝑟 > 0): 𝑖=1,2,…𝑚 𝑗=1,2,…𝑛 𝑎11 𝑝1 + 𝑎21 𝑝2 + ⋯ + 𝑎𝑚1 𝑝𝑚 ≥ 𝑟 𝑎12 𝑝1 + 𝑎22 𝑝2 + ⋯ + 𝑎𝑚2 𝑝𝑚 ≥ 𝑟 . . . {𝑎1𝑛 𝑝1 + 𝑎2𝑛 𝑝2 + ⋯ + 𝑎𝑚𝑛 𝑝𝑚 ≥ 𝑟 (1.2) При этом 𝑝𝑖 > 0; 𝑖 = 1,2, … , 𝑚; ∑𝑚 𝑖=1 𝑝𝑖 = 1 Введем новые обозначения 𝑝 𝑥𝑖 = 𝑟𝑖, = 1,2, … , 𝑚 и разделим все неравенства системы (1.2) на положительное число r, получим следующую систему: 𝑎11 𝑥1 + 𝑎21 𝑥 + ⋯ + 𝑎𝑚1 𝑥𝑚 ≥ 1 𝑎12 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎𝑚2 𝑥𝑚 ≥ 1 . (1.3) . . {𝑎1𝑛 𝑥1 + 𝑎2𝑛 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑚 ≥ 1 𝑝 ∑𝑚 𝑝 1 𝑖 𝑚 𝑖=1 𝑖 При этом 𝑥𝑖 > 0; 𝑖 = 1,2, … , 𝑚; ∑𝑚 = 𝑟. 𝑖=1 𝑥𝑖 = ∑𝑖=1 𝑟 = 𝑟 Если бы 𝑟 ≤ 0, то переход от (1.2) к (1.3) был бы невозможен, т.к. при делении неравенства на отрицательное число знак меняется на противоположный, а на нуль делить нельзя. Цель первого игрока – максимизировать свой гарантированный выигрыш r или, 1 соответственно, минимизировать величину ∑𝑚 𝑖=1 𝑥𝑖 = 𝑟 . Следовательно, приходим к задаче линейного программирования для первого игрока: ∑𝑚 𝑖=1 𝑥𝑖 → 𝑚𝑖𝑛, ∑𝑚 (1.4) 𝑖=1 𝑎𝑖𝑗 𝑥𝑖 ≥ 1, 𝑗 = 1,2, … , 𝑛 𝑥𝑖 ≥ 0; 𝑖 = 1,2, … , 𝑚 Аналогичные рассуждения с позиции второго игрока приводят к задаче линейного программирования, двойственной к задаче для первого игрока: 15 ∑𝑚 𝑖=1 𝑦𝑗 → 𝑚𝑎𝑥, ∑𝑚 (1.5) 𝑖=1 𝑎𝑖𝑗 𝑦𝑗 ≤ 1, 𝑖 = 1,2, … , 𝑚 𝑦𝑖 ≥ 0; 𝑗 = 1,2, … , 𝑛 Поскольку все 𝑎𝑖𝑗 ≥ 0, можно подобрать такие достаточно большие положительные числа 𝑥1 , 𝑥2 , … , 𝑥𝑚 , чтобы для всех 𝑗 = 1,2, … , 𝑛 выполнялись неравенства ∑𝑚 𝑖=1 𝑎𝑖𝑗 𝑥𝑖 ≥ 1. Например, 𝑥1 = 𝑚𝑖𝑛{𝑎 1 11 , 𝑎12 ,…,𝑎1𝑛 } , 𝑥2 = 𝑥3 = ⋯ = 𝑥𝑚 = 0 Следовательно, задача (1.4) имеет допустимое решение. Допустимым решением задачи (1.5) является, очевидно, нулевой вектор. Лекция 3. Матричные игры (продолжение) Так как каждая из пары двойственных задач (1.4) и (1.5) имеет допустимое решение, то согласно теории двойственных задач линейного программирования обе эти задачи имеют некоторые оптимальные решения 𝑥 ∗ = (𝑥1 ∗ , 𝑥2 ∗ , … , 𝑥𝑚 ∗ ) и 𝑦 = (𝑦1 ∗ , 𝑦2 ∗ , … , 𝑦𝑛 ∗ ) при этом оптимальные значения целевых функций данных задач равны: 𝑚 ∗ ∗ ∑𝑚 𝑖=1 𝑥𝑖 = ∑𝑖=1 𝑦𝑗 . 1 Покажем, что цена игры 𝑣 = ∑𝑚 ∗ 𝑖=1 𝑥𝑖 = ∑𝑛 1 ∗ 𝑗=1 𝑦𝑗 , а оптимальные смешанные стратегии игроков равны соответственно: 1 𝑥1 ∗ 𝑥2 ∗ 𝑥𝑚 ∗ ∗ ∗ ∗ ∗ ∗ 𝑝 = 𝑣𝑥 = 𝑚 ∗ (𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = ( 𝑚 ∗ , 𝑚 ∗ , … , 𝑚 ∗ ) ∑𝑘=1 𝑥𝑘 ∑𝑘=1 𝑥𝑘 ∑𝑘=1 𝑥𝑘 ∑𝑘=1 𝑥𝑘 𝑦2 ∗ 𝑦𝑛 ∗ 𝑞 = 𝑣𝑦 = 𝑛 (𝑦 , 𝑦 , … , 𝑦𝑛 ) = ( 𝑛 , ,…, 𝑛 ) ∑𝑙=1 𝑦𝑙∗ 1 2 ∑𝑙=1 𝑦𝑙∗ ∑𝑛𝑙=1 𝑦𝑙∗ ∑𝑙=1 𝑦𝑙∗ ∗ ∗ 1 ∗ ∗ 𝑦∗ ∗ Действительно, пусть 𝑝 = (𝑝1 , 𝑝2 , … , 𝑝𝑚 ) и 𝑞 = (𝑞1 , 𝑞2 , … , 𝑞𝑛 ) – произвольные смешанные стратегии игроков, тогда 𝑦 ∗ 𝑗 𝑛 𝑀(𝑝, 𝑞 ∗ ) = ∑𝑚 𝑖=1 ∑𝑗=1 𝑎𝑖𝑗 𝑝𝑖 ∑𝑛 𝑦 ∗ = = ∑𝑛 1 𝑙=1 𝑙 ∑𝑚 𝑝 ∑𝑛 𝑎 𝑦 ∗ ≤ 𝑛 ∑ 𝑦 ∗ 𝑖=1 𝑖 𝑗=1 𝑖𝑗 𝑗 1 ∗ 𝑙=1 𝑦𝑙 𝑙=1 𝑙 𝑥𝑖 ∗ 𝑛 𝑀(𝑝∗ , 𝑞) = ∑𝑚 𝑖=1 ∑𝑗=1 𝑎𝑖𝑗 𝑞𝑗 ∑𝑛 = ∑𝑛 1 ∗ 𝑘=1 𝑥𝑘 ∗ 𝑘=1 𝑥𝑘 ∗ ∑𝑛𝑗=1 𝑞𝑗 ∑𝑚 𝑖=1 𝑎𝑖𝑗 𝑥𝑖 ≥ ∑𝑛 𝑥𝑖 ∗ 1 ∗ 𝑙=1 𝑦𝑙 =𝑣 1 ∑𝑛𝑗=1 𝑞𝑗 = 𝑛 ∑ 𝑦𝑗 ∗ 1 ∗ 𝑘=1 𝑥𝑘 =𝑣 (1.7) = ∗ ∑𝑛 𝑙=1 𝑦𝑙 1 1 𝑚 𝑛 ∗ ∗ ∗ 𝑛 ∗ 2 𝑚 ∗ ∑𝑛 𝑦 ∗ ∑𝑖=1 𝑥𝑖 ∑𝑗=1 𝑎𝑖𝑗 𝑦𝑗 = 𝑣 ∑𝑖=1 𝑥𝑖 ∑𝑗=1 𝑎𝑖𝑗 𝑦𝑗 ∑𝑛 𝑥 𝑘=1 𝑘 𝑙=1 𝑙 ∗ 𝑘=1 𝑥𝑘 (1.6) = ∗ 𝑘=1 𝑥𝑘 𝑛 𝑀(𝑝∗ , 𝑞 ∗ ) = ∑𝑚 𝑖=1 ∑𝑗=1 𝑎𝑖𝑗 ∑𝑛 = ∑𝑚 𝑖=1 𝑝𝑖 = ∑𝑛 (1.8) Из (1.6) следует, что 𝑀(𝑝, 𝑞 ∗ ) ≤ 𝑣, из (1.7) следует, что 𝑀(𝑝∗ , 𝑞) ≥ 𝑣, а из (1.8) следует, что одновременно ∗ ∗ 2 𝑛 𝑀(𝑝∗ , 𝑞 ∗ ) ≥ 𝑣 (так как 𝑀(𝑝∗ , 𝑞 ∗ ) = 𝑣 2 ∑𝑛𝑗=1 𝑦𝑗∗ ∑𝑚 𝑖=1 𝑎𝑖𝑗 𝑥𝑖 ≥ 𝑣 ∑𝑗=1 𝑦𝑗 = 𝑣2 ∗ 𝑛 ∗ ∗ 2 𝑚 𝑀(𝑝∗ , 𝑞 ∗ ) ≤ 𝑣 (так как 𝑀(𝑝∗ , 𝑞 ∗ ) = 𝑣 2 ∑𝑚 𝑖=1 𝑥𝑖 ∑𝑗=1 𝑎𝑖𝑗 𝑦𝑗 ≤ 𝑣 ∑𝑖=1 𝑥𝑖 = 𝑣2 и 𝑣 𝑣 = 𝑣) = 𝑣), 16 Значит 𝑀(𝑝∗ , 𝑞 ∗ ) = 𝑣. Итак, 𝑀(𝑝∗ , 𝑞 ∗ ) ≥ 𝑣, 𝑀(𝑝∗ , 𝑞 ∗ ) ≤ 𝑣, 𝑀(𝑝∗ , 𝑞 ∗ ) = 𝑣, поэтому 𝑀(𝑝, 𝑞 ∗ ) ≤ 𝑀(𝑝∗ , 𝑞 ∗ ) ≤ 𝑀(𝑝∗ , 𝑞). Таким образом, пара (𝑝∗ , 𝑞 ∗ ) образует седловую точку данной игры в смешанных стратегиях, и 𝑀(𝑝∗ , 𝑞 ∗ ) = 𝑣 – цена данной игры. Если же в платежной матрице 𝐴 = (𝑎𝑖𝑗 ) есть отрицательные элементы или нули, то можно добавить ко всем элементам матрицы одно и то же достаточно большое положительное число b, так чтобы все элементы матрицы 𝐴′ = (𝑎𝑖𝑗 + 𝑏) были положительными. 𝑛 Обозначим 𝑀(𝑝, 𝑞) = ∑𝑚 математическое ожидание выигрыша 𝑖=1 ∑𝑗=1 𝑎𝑖𝑗 𝑝𝑖 𝑞𝑗 𝑛 ′ первого игрока в игре с платежной матрицей 𝐴, а 𝑀′ (𝑝, 𝑞) = ∑𝑚 𝑖=1 ∑𝑗=1 𝑎 𝑖𝑗 𝑝𝑖 𝑞𝑗 – математическое ожидание выигрыша первого игрока в игре с платежной матрицей 𝐴′ . При этом 𝑛 𝑚 𝑛 𝑚 𝑛 ′ 𝑀′ (𝑝, 𝑞) = ∑𝑚 𝑖=1 ∑𝑗=1 𝑎 𝑖𝑗 𝑝𝑖 𝑞𝑗 = ∑𝑖=1 ∑𝑗=1(𝑎𝑖𝑗 + 𝑏)𝑝𝑖 𝑞𝑗 = 𝑀(𝑝, 𝑞) + 𝑏 ∑𝑖=1 𝑝𝑖 ∑𝑗=1 𝑞𝑗 = 𝑀(𝑝, 𝑞) + 𝑏, игра с платежной матрицей 𝐴′ имеет седловую точку (𝑝∗ , 𝑞 ∗ ) в смешанных стратегиях: 𝑀′ (𝑝, 𝑞 ∗ ) ≤ 𝑀′ (𝑝∗ , 𝑞 ∗ ) ≤ 𝑀′ (𝑝∗ , 𝑞) или 𝑀(𝑝, 𝑞 ∗ ) + 𝑏 ≤ 𝑀(𝑝∗ , 𝑞 ∗ ) + 𝑏 ≤ 𝑀(𝑝∗ , 𝑞) + 𝑏, откуда 𝑀(𝑝, 𝑞 ∗ ) ≤ 𝑀(𝑝∗ , 𝑞 ∗ ) ≤ 𝑀(𝑝∗ , 𝑞), т. е. игра с платежной матрицей 𝐴 также имеет седловую точку (𝑝∗ , 𝑞 ∗ ) в смешанных стратегиях, а цена игры с матрицей 𝐴 равна 𝑣 = 𝑀(𝑝∗ , 𝑞 ∗ ) = 𝑀′ (𝑝∗ , 𝑞 ∗ ) − 𝑏. Пример 1.8. Требуется найти оптимальные смешанные стратегии в игре из примера 1.7, сведя эту игру к паре взаимно двойственных задач линейного программирования. Решение. От платежной матрицы −2 3 4 1 𝐴=( ) 2 −4 −3 −1 путем добавления положительного числа 𝑏 = 5 перейдем к матрице, 3 8 9 4 𝐴′ = ( ) 7 1 2 6 все элементы которой положительны. Сведем данную матричную игру к паре двойственных задач программирования (согласно теореме 1.2): 𝑥1 + 𝑥2 → 𝑚𝑖𝑛 линейного 3𝑥1 + 7𝑥2 ≥ 1 8𝑥 + 𝑥2 ≥ 1 { 1 9𝑥1 + 2𝑥2 ≥ 1 4𝑥1 + 6𝑥2 ≥ 1 𝑥1 ≥ 0, 𝑥2 ≥ 0 𝑦1 + 𝑦2 + 𝑦3 + 𝑦4 → 𝑚𝑎𝑥 { 3𝑦1 + 8𝑦2 + 9𝑦3 + 4𝑦4 ≤ 1 7𝑦1 + 1𝑦2 + 2𝑦3 + 6𝑦4 ≤ 1 17 𝑦1 ≥ 0, 𝑦2 ≥ 0, 𝑦3 ≥ 0, 𝑦4 ≥ 0. Решаем уравнения из первой системы уравнений первое и второе, так как третье и четвертое дает отрицательные значения х, получаем: 3𝑥1 + 7(1 − 8𝑥1 ) = 1 𝑥1 = 6⁄53 𝑥2 = 1 − 8𝑥1 𝑥2 = 5⁄53. Так как выбрали в системе x первые два уравнения, то в системе y зануляются 𝑦3 и 𝑦4 . 3𝑦1 + 8(1 − 7𝑦1 ) = 1 𝑦1 = 7⁄53 𝑦2 = 1 − 7𝑦1 𝑦2 = 4⁄53 . Поскольку оптимальные решения этих задач равны 𝑥 ∗ = (6⁄53 ; 5⁄53) и 𝑦 ∗ = (7⁄53 ; 4⁄53), оптимальные смешанные стратегии игроков 1 𝑝∗ = 6 (6⁄53 ; 5⁄53) = (6⁄11 ; 5⁄11) 5 ⁄53+ ⁄53 и 𝑞∗ = 7 1 ⁄53+4⁄53+0+0 (7⁄53 ; 4⁄53 ; 0; 0) = (7⁄11 ; 4⁄11 ; 0; 0), а цена игры 1 𝑣=6 − 5 = − 2⁄11. 5 ⁄53+ ⁄53 Приближенный метод решения матричных игр Если точное решение матричной игры оказывается громоздким, можно ограничиться приближенным решением. В основе этого метода лежит предположение, что игроки выбирают свои стратегии в очередной партии, руководствуясь накапливающимся опытом уже сыгранных партий. Достоинство метода – его простота. Пример 1.9. Найти приближенное решение матричной игры, смоделировав 10 0,7 0,9 0,7 партий: (0,9 0,7 0,8 ). 0,7 0,8 0,8 Решение. Чтобы избавиться от дробей, умножим все элементы матрицы на 10. От этого оптимальные стратегии игроков не изменятся, а цена игры тоже умножится на 10. 7 9 7 Получим матрицу (9 7 8 ). Составляем таблицу. 7 8 8 Стратегия 1 2 3 А1 А2 А2 Игрок В Накопленный выигрыш при различных стратегиях игрока В В1 В2 В3 7 16 25 9 16 23 7 15 23 Стратегия Номер партии Игрок А В1 В3 В2 Накопленный выигрыш при различных стратегиях игрока А Приближенные значения цены А1 А2 А3 α β v= = (α + β)/2 7 14 23 9 17 24 7 15 23 7 15/2 23/3 9 17/2 24/3 8 8 47/6 18 4 5 6 7 8 9 10 А2 А1 А1 А2 А2 А2 А3 34 41 48 57 66 75 82 30 39 48 55 62 69 77 31 38 45 53 61 69 77 В2 В3 В3 В3 В3 В2 В2 32 39 46 53 61 70 79 31 39 47 55 63 70 77 31 39 47 55 63 71 79 30/4 38/5 45/6 53/7 61/8 69/9 7,7 32/4 39/5 47/6 55/7 63/8 71/9 7,9 62/8 77/10 92/12 108/14 124/16 140/18 7,8 Ниже описано как заполняется таблица. Игрок А начинает со своей первой стратегии. Соответствующие выигрыши (первая строка матрицы) запишем в столбцы В1, В2, В3 и определим среди них минимальный: min (7, 9, 7) = 7 (в случае, когда их несколько, берем тот, что расположен левее). Этот минимум выделим. Он соответствует стратегии В1. Поэтому соответствующие выигрыши (первый столбец матрицы) запишем в столбцы А1, А2, А3 и определим среди них максимальный: max (7, 9, 7) = 9 (в случае, когда их несколько, берем тот, что расположен левее). Этот максимум выделим. Он соответствует стратегии А2. Поэтому во второй партии игрок А ответит стратегией А2. Соответствующие выигрыши (вторая строка) надо прибавить к числам в столбцах В1, В2, В3 предыдущей строки игрока А и определить минимальное среди полученных: min (16, 16, 15) = 15, что соответствует стратегии В3. Поэтому соответствующие выигрыши (третий столбец) надо прибавить к числам в столбцах А1, А2, А3 предыдущей строки игрока В и определить среди них максимальный: max (14, 17, 15) = 17, что соответствует стратегии А2. И т.д. Приближенное значение нижней цены игры в каждой партии α = (выделенное число в столбцах В1, В2, В3)/(номер партии). Приближенное значение верхней цены игры в каждой партии β = (выделенное число в столбцах А1, А2, А3)/(номер партии). После 10 партий v ≈ 7,8. Поэтому для исходной матрицы v ≈ 7,8/10 = 0,78. pi ≈ (число использования стратегии Аi)/(число партий). qi ≈ (число использования стратегии Bj)/(число партий). Число использования стратегии Аi = число отмеченных элементов в столбце Аi. Число использования стратегии Вj = число отмеченных элементов в столбце Вj. После 10 партий p1 ≈ 3/10, p2 ≈ 6/10, p3 ≈ 1/10 (за 10 партий игрок А 3 раза воспользовался стратегией А1, 6 раз – стратегией А2, 1 раз – стратегией А3). q1 ≈ 1/10, q2 ≈ 4/10, q3 ≈ 5/10. Лекция 4. Принятие решений в условиях неопределенности Предположим, что лицо, принимающее решение, может выбрать одну из возможных альтернатив, обозначенных номерами 𝑖 = 1,2, … 𝑚. Ситуация является полностью неопределенной, т. е. известен лишь набор возможных вариантов состояний внешней (по отношению к лицу, принимающему решение) среды, обозначенных номерами 𝑗 = 1,2, … 𝑛. Если будет принято i-e решение, а состояние внешней среды соответствует j-й ситуации, то лицо, принимающее решение, получит доход 𝑞𝑖𝑗 . Матрица 𝑄 = (𝑞𝑖𝑗 ) ∈ 𝑅 𝑚×𝑛 называется матрицей последствий (от реализации возможных решений). В ситуации с полной неопределенностью могут быть высказаны лишь некоторые рекомендации предварительного характера относительно того, какое решение нужно принять. Эти рекомендации не обязательно будут приняты. Многое будет зависеть, например, от склонности к риску лица, принимающего решение. Допустим, оценим риск, который несет i-e решение. Реальная ситуация не известна. Однако если есть информация, что осуществляется j-е состояние внешней среды, то лицо, 19 принимающее решение, выбрало бы наилучшее решение, т. е. приносящее наибольший доход 𝑞𝑗 = 𝑚𝑎𝑥 𝑞𝑘𝑗 . 𝑘=1,2,…,𝑚 Значит, принимая i-e решение, есть риск получить не 𝑞𝑗 , а только 𝑞𝑖𝑗 , т. е. если принимается i-е решение, а во внешней среде реализуется j-е состояние, то будет не дополучен доходе в размере 𝑟𝑖𝑗 = 𝑞𝑗 − 𝑞𝑖𝑗 = 𝑚𝑎𝑥 𝑞𝑘𝑗 − 𝑞𝑖𝑗 (2.1) 𝑘=1,2,…,𝑚 по сравнению с тем, как если бы точно было известно, что реализуется j-е состояние внешней среды, и выбрали бы решение, приносящее наибольший доход 𝑞𝑗 = 𝑚𝑎𝑥 𝑞𝑘𝑗 . 𝑘=1,2,…,𝑚 Матрица 𝑅 = (𝑟𝑖𝑗 ) ∈ 𝑅 𝑚×𝑛 где сожаления 𝑟𝑖𝑗 рассчитаны по формуле (2.1), называется матрицей сожалений (или матрицей рисков). Не все случайное можно «измерить» вероятностью. Неопределенность – более широкое понятие. Неопределенность того, какой цифрой вверх ляжет игральный кубик, отличается от неопределенности того, каково будет состояние российской экономики через 15 лет. Кратко говоря, уникальные единичные случайные явления связаны с неопределенностью, а массовые случайные явления обязательно допускают некоторые закономерности вероятностного характера. Ситуация с полной неопределенностью характеризуется отсутствием какой бы то ни было дополнительной информации. Существуют следующие правила – рекомендации по принятию решений в таких ситуациях. На практике вероятность возможных сценариев развития ситуации не известна. Предположим, что руководитель предприятия имеет п альтернатив или сценариев решения ситуации (А1, А2, …Аn, n ∈ (1,n)). Результат выбора зависит от сценария развития ситуации. Предположим, что руководитель предприятия выделяет m сценариев развития ситуации, которые обозначим (S1, S2, …Sm, m ∈ (1,m)). Данные варианты в теории принятия решений называют «Состояниями природы», т.к. в большинстве реальные задачи этого типа связаны с погодными, климатическими, социальными, политическими, техническими и другими неопределенностями. Допустим, что известен результат, выраженный количественно при каждой альтернативе Аi и сценарии развитии ситуации Sj , обозначенный 𝑎𝑖𝑗 , в результате чего получается матрица 𝐴 = (𝑎𝑖𝑗 ), называемая матрицей выигрышей или матрицей потерь, в зависимости от того, максимизируется или минимизируется результат. В соответствии с реальными условиями, существует несколько критериев принятия решений в условиях неопределенности. Рассмотрим пример использования сценарного метода экономического анализа, когда показатели привлекательности 𝑎𝑖𝑗 чем больше, тем лучше для руководителя предприятия. Пример 2.1. Директор предприятия, продающего телевизоры марки «Zarya» решил открыть представительство в областном центре. У него имеются альтернативы либо создавать собственный магазин в отдельном помещении, либо организовывать сотрудничество с местными торговыми центрами. Всего можно выделить 5 альтернатив решения: А1, А2, А3, А4, А5. Успех предприятия зависит от того, как сложится ситуация на рынке предоставляемых услуг. Эксперты выделяют 4 возможных сценария развития ситуации: S1, S2, S3, S4. Прибыль предприятия для каждой альтернативы при каждом сценарии развития ситуации представлена матрицей выигрышей 𝑎𝑖𝑗 (млн. рублей /год). Альтернатива S1 S2 S3 S4 Сценарий А1 8 12 14 5 А2 9 10 11 10 А3 2 4 9 22 А4 12 14 10 1 20 А5 15 6 7 14 Рассмотрим основные критерии, позволяющие выбирать оптимальную альтернативу для принятия решения. 1) Критерий Лапласа, основанный на предположении, что каждый сценарий развития ситуации (состояния «природы») равновероятен. Поэтому, для принятия решения, необходимо рассчитать функцию полезности Fi для каждой альтернативы, равную среднеарифметическому показателей привлекательности по каждому «состоянию природы»: 1 𝐹𝑖 = 𝑚 ∑𝑚 𝑗=1 𝑎𝑖𝑗 . 1 𝐹1 = 4 (8 + 12 + 14 + 5) = 9,75; 1 1 𝐹2 = 4 (9 + 10 + 11 + 10) = 10; 1 1 𝐹3 = 4 (15 + 6 + 7 + 14) = 9,25; 𝐹4 = 4 (12 + 14 + 10 + 1) = 9,25; 𝐹5 = 4 (2 + 4 + 9 + 22) = 10,5 Выбирается та альтернатива, для которой функция полезности максимальна, т.е. альтернатива А5. 2) Критерий Вальда, основанный на принципе максимального пессимизма, то есть на предположении, что произойдет наиболее худший сценарий развития ситуации и риск наихудшего варианта нужно свести к минимуму. Для применения критерия нужно для каждой альтернативы выбрать наихудший показатель привлекательности 𝑎𝑖 (наименьшее число в каждой строке матрицы выигрышей) и выбрать ту альтернативу, для которой этот показатель максимальный. 𝑎1 = 5, 𝑎2 = 9, 𝑎3 = 2, 𝑎4 = 1, 𝑎5 = 6. Видно, что наилучшим из наихудших показателей обладает альтернатива А2, для нее 𝑎2 = 9 - наибольшее. 3) Критерий максимального оптимизма. Наиболее простой критерий, основывающийся на идее, что руководитель предприятия, имея возможность в некоторой степени управлять ситуацией, рассчитывает, что произойдет такое развитие ситуации, которое для него является наиболее выгодным. В соответствии с критерием принимается альтернатива, соответствующая максимальному элементу матрицы выигрышей. Для приведенного примера это 𝑎34 = 22, поэтому выбирается альтернатива А3. 4) Критерий Сэвиджа, основанный на принципе минимизации потерь, связанных с тем, что руководитель предприятия принял не оптимальное решение. Для решения задачи составляется матрица потерь, которая называется матрицей рисков 𝑟𝑖𝑗 , которая получается из матрицы выигрышей 𝑎𝑖𝑗 путем вычитания из максимального элемента каждого столбца всех остальных элементов. Альтернатива S1 S2 S3 S4 Сценарий А1 7 2 17 А2 6 4 3 12 А3 13 10 5 А4 3 4 21 А5 8 7 8 Далее, для каждой альтернативы определяем величины 𝑏𝑖 , равные максимальному риску (наибольшее число в каждой строке матрицы рисков) и выбирают ту альтернативу, для которой максимальный риск минимален. 𝑏1 = 17, 𝑏2 = 12, 𝑏3 = 13, 𝑏4 = 21, 𝑏5 = 8. 𝑏5 = 8 – минимально, поэтому выбирается альтернатива А5. 5) Критерий Гурвица. Это самый универсальный критерий, который позволяет управлять степенью «оптимизма - пессимизма» руководителя. Введем некоторый коэффициент α, который назовем коэффициентом доверия или коэффициентом оптимизма. Этот коэффициент можно интерпретировать как вероятность, с которой произойдет наилучший для руководителя предприятия исход. Исходя из этого, наихудший вариант можно ожидать с вероятностью (1-α). Коэффициент доверия a показывает, насколько руководитель предприятия может управлять ситуацией и в той или иной степени рассчитывает на благоприятный для него исход. Если вероятности благоприятного и неблагоприятного сценария развития ситуации равны, то следует принять α=0,5. 21 Для реализации критерия определяются наилучшие 𝑎𝑖+ и наихудшие 𝑎𝑖− значение каждой альтернативе по формулам: 𝑎𝑖+ = 𝑚𝑎𝑥 𝑎𝑖𝑗 , 𝑎𝑖− = 𝑚𝑖𝑛 𝑎𝑖𝑗 . Далее, вычисляются 𝑗 𝑗 функции полезности по формуле: 𝐹𝑖 = 𝑎𝑖+ × 𝛼 + 𝑎𝑖− × (1 − 𝛼). Выбирается та альтернатива, для которой функция полезности максимальна. Предположим, что для нашего примера руководитель достаточно уверен в положительном результате и оценивает вероятность максимального успеха в α=0,7. 𝐹1 = 14 × 0,7 + 5 × 0,3 = 11,3; 𝐹2 = 11 × 0,7 + 9 × 0,3 = 10,4; 𝐹3 = 22 × 0,7 + 2 × 0,3 = 16,0; 𝐹4 = 14 × 0,7 + 1 × 0,3 = 10,1; 𝐹5 = 15 × 0,7 + 6 × 0,3 = 12,3 В соответствии с расчетами следует выбрать альтернативу А3. Если же, руководитель не очень уверен в положительном исходе и расценивает его вероятность порядка α=0,2, то функции полезности равны: 𝐹1 = 14 × 0,2 + 5 × 0,8 = 6,8 ; 𝐹2 = 11 × 0,2 + 9 × 0,8 = 9,4; 𝐹3 = 22 × 0,2 + 2 × 0,8 = 6; 𝐹4 = 14 × 0,2 + 1 × 0,8 = 3,6; 𝐹5 = 15 × 0,2 + 6 × 0,8 = 7,8 Видно, что в этом случае следует принять А2, для которого функция полезности максимальна. Следует отметить, что при α=0, критерий Гурвица переходит в пессимистический критерий Вальда, а при α=1 – в критерий максимального оптимизма. Лекция 5. Принятие решений в условиях неопределенности (продолжение) Рассмотрим пример использования сценарного метода экономического анализа, когда показатели привлекательности 𝑎𝑖𝑗 чем меньшее, тем лучше для руководителя предприятия, например, затраты, риск и т.д. Критерий Лапласа определяет оптимальное решение по минимальной функции полезности. Применяя критерий Вальда необходимо вычислять максимальный показатель каждой альтернативы (строки) 𝑎𝑖 и принимать альтернативу, где этот показатель минимален. Критерий максимального оптимизма позволяет определить оптимальное решение, соответствующее минимальному элементу матрицы выигрышей (которую в случае минимизации часто называют матрицей потерь). Матрица рисков в критерии Сэвиджа получается в результате вычитания из каждого элемента матрицы потерь aij минимального элемента каждого столбца. Для реализации критерия Гурвица вычисляются максимальные и минимальные показатели для каждой альтернативы 𝑎𝑖+ = 𝑚𝑎𝑥 𝑎𝑖𝑗 , 𝑎𝑖− = 𝑚𝑖𝑛 𝑎𝑖𝑗 . Далее, 𝑗 𝑗 вычисляются функции полезности по формуле: 𝐹𝑖 = 𝑎𝑖− × 𝛼 + 𝑎𝑖+ × (1 − 𝛼). Выбирается альтернатива с наименьшей функцией полезности. Пример 2.2. Нефтяная компания собирается построить в районе крайнего севера нефтяную вышку. Имеется 4 проекта A, B, C и D. Затраты на строительство (млн. руб.) зависят от того, какие погодные условия будут в период строительства. Возможны 5 вариантов погоды: S1, S2, S3, S4, S5. Матрица затрат имеет вид: Альтернатива S1 S2 S3 S4 S5 Сценарий А1 7 12 8 10 5 А2 9 10 7 8 9 А3 6 8 15 9 7 А4 9 10 8 11 7 1) Критерий Лапласа: 1 1 𝐹1 = 5 (7 + 12 + 8 + 10 + 5) = 8,4; 𝐹2 = 5 (9 + 10 + 7 + 8 + 9) = 8,6; 𝐹3 = 5 (6 + 8 + 15 + 1 1 9 + 7) = 9; 𝐹4 = 5 (9 + 10 + 8 + 11 + 7) = 9; 22 2) Критерий Вальда: среди наихудших вариантов 𝑎1 = 12, 𝑎2 = 10, 𝑎3 = 15, 𝑎4 = 11, , наилучший соответствует 𝑎2 = 10, следовательно, принимаем альтернативу А2. 3) Критерий максимального оптимизма. Соответствует альтернативе, для которой 𝑎15 = 5 - минимальное. 4) Критерии Сэвиджа рассчитывается по матрице рисков: Альтернатива S1 S2 S3 S4 S5 Сценарий А1 1 4 1 2 А2 3 2 4 А3 8 1 2 А4 3 2 1 3 2 Максимальные элементы для каждого критерия матрицы рисков равны 𝑏1 = 4, 𝑏2 = 4, 𝑏3 = 8, 𝑏4 = 3. Принимаем альтернативу, соответствующую минимальному значению 𝑏4 = 3, то есть А4. 5) В соответствии с критерием Гурвица на уровне a = 0,6 , функции полезности равны: 𝐹1 = 5 × 0,6 + 12 × 0,4 = 7,8; 𝐹2 = 7 × 0,6 + 10 × 0,4 = 8,2; 𝐹3 = 6 × 0,6 + 15 × 0,4 = 9,6; 𝐹4 = 7 × 0,6 + 11 × 0,4 = 8,6 Принимаем альтернативу А2 с наименьшей функцией полезности. Предположим, что в рассмотренной схеме известны вероятности 𝑝𝑗 того, что реальная ситуация развивается по варианту 𝑗. Именно такое положение называется частичной неопределенностью. При принятии решений в таких ситуациях можно выбрать одно из следующих правил. Правило максимизации ожидаемого дохода. Доход, получаемый при принятии i-го решения, является случайной величиной 𝑄𝑖 с рядом распределения … 𝑄𝑖 𝑞𝑖1 𝑞𝑖2 𝑞𝑖𝑛 p … 𝑝1 𝑝2 𝑝𝑛 Ожидаемый доход при принятии i-го решения оценивается математическим ожиданием 𝑀𝑄𝑖 соответствующей случайной величины 𝑄𝑖 . Правило максимизации ожидаемого дохода рекомендует принять решение, приносящее максимальный ожидаемый доход 𝑀𝑄𝑖0 = 𝑚𝑎𝑥 𝑀𝑄𝑖 = 𝑚𝑎𝑥 (∑𝑛𝑗=1 𝑞𝑖𝑗 𝑝𝑗 ) . 𝑖=1,2,…,𝑚 𝑖=1,2,…,𝑚 Правило минимизации ожидаемых сожалений. Сожаления при реализации i-го решения представляются случайной величиной 𝑅𝑖 с рядом распределения … 𝑅𝑖 𝑟𝑖1 𝑟𝑖2 𝑟𝑖𝑛 p … 𝑝1 𝑝2 𝑝𝑛 Ожидаемые сожаления оценивается математическим ожиданием 𝑀𝑅𝑖 соответствующей случайной величины 𝑅𝑖 . Правило минимизации ожидаемых сожалений рекомендует принять решение, влекущее минимальные ожидаемые сожаления 𝑀𝑅𝑖0 = 𝑚𝑖𝑛 𝑀𝑅𝑖 = 𝑚𝑖𝑛 (∑𝑛𝑗=1 𝑟𝑖𝑗 𝑝𝑗 ) 𝑖=1,2,…,𝑚 𝑖=1,2,…,𝑚 Теорема эквивалентности правил максимизации ожидаемого дохода и минимизации ожидаемых сожалений. Решения, рекомендуемые правилами максимизации ожидаемого дохода и минимизации ожидаемых сожалений, всегда совпадают. Доказательство. Имеем: 𝑚𝑖𝑛 𝑀𝑅𝑖 = 𝑚𝑖𝑛 (∑𝑛𝑗=1 𝑟𝑖𝑗 𝑝𝑗 ) = 𝑖=1,2,…,𝑚 𝑖=1,2,…,𝑚 23 = = = 𝑚𝑖𝑛 (∑𝑛𝑗=1 (𝑚𝑎𝑥 𝑞𝑘𝑗 − 𝑞𝑖𝑗 ) 𝑝𝑗 ) = 𝑖=1,2,…,𝑚 𝑖=1,2,…,𝑚 𝑚𝑖𝑛 (∑𝑛𝑗=1 𝑝𝑗 𝑚𝑎𝑥 𝑞𝑘𝑗 − ∑𝑛𝑗=1 𝑞𝑖𝑗 𝑝𝑗 = 𝑖=1,2,…,𝑚 𝑖=1,2,…,𝑚 𝑚𝑖𝑛 ∑𝑛𝑗=1 𝑝𝑗 𝑚𝑎𝑥 𝑞𝑘𝑗 − 𝑚𝑎𝑥 ∑𝑛𝑗=1 𝑞𝑖𝑗 𝑝𝑗 = 𝑖=1,2,…,𝑚 𝑖=1,2,…,𝑚 𝑖=1,2,…,𝑚 = ∑𝑛𝑗=1 𝑝𝑗 𝑚𝑎𝑥 𝑞𝑘𝑗 − 𝑚𝑎𝑥 𝑀𝑄𝑖 , 𝑖=1,2,…,𝑚 𝑖=1,2,…,𝑚 так как ∑𝑛𝑗=1 𝑝𝑗 𝑚𝑎𝑥 𝑞𝑘𝑗 не зависит от i. Поэтому 𝑚𝑎𝑥 𝑀𝑄𝑖 на том же решении, что и 𝑚𝑖𝑛 𝑀𝑅𝑖 . 𝑖=1,2,…,𝑚 𝑖=1,2,…,𝑚 𝑖=1,2,…,𝑚 В заключение следует отметить, что решения, предлагаемые различными правилами, не всегда совпадают. Лицу, принимающему решение, следует понимать, что оно будет нести ответственность за последствия Лекция 6. Биматричные игры Не все конфликтные ситуации можно представить как игры с нулевой суммой, потому что интересы участников таких конфликтов не всегда противоположны. Обобщением игр с нулевой суммой на случай не противоположных интересов участников являются игры с ненулевой суммой. Рассмотрим конечную игру с ненулевой суммой, т. е. такую, в которой множества стратегий игроков конечны: будем считать, что первый игрок может выбрать одну из m своих стратегий, обозначенных номерами 𝑖 = 1,2, … , 𝑚, а второй игрок – одну из n своих стратегий, обозначенных номерами 𝑗 = 1,2, … , 𝑛. Если первый игрок выбрал свою i-ю стратегию, а второй игрок – свою 𝑗 -ю стратегию, то в результате такого совместного выбора первый игрок получает выигрыш 𝑎𝑖𝑗 , а второй игрок – выигрыш 𝑏𝑖𝑗 . При этом не обязательно, чтобы 𝑏𝑖𝑗 = −𝑎𝑖𝑗 , как в матричных играх. Таким образом, конечная игра с ненулевой суммой полностью определяется двумя матрицами 𝑏11 𝑏12 𝑎11 𝑎12 … 𝑎1𝑛 … 𝑏1𝑛 𝑎21 𝑎22 … 𝑎2𝑛 𝑏21 𝑏22 … 𝑏2𝑛 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ А= и 𝐵= , 𝑎(𝑚−1)1 𝑎(𝑚−1)2 … 𝑎(𝑚−1)𝑛 𝑏(𝑚−1)1 𝑏(𝑚−1)2 … 𝑏(𝑚−1)𝑛 𝑎𝑚2 … 𝑎𝑚𝑛 ) … 𝑏𝑚𝑛 ) 𝑏𝑚2 ( 𝑎𝑚1 ( 𝑏𝑚1 поэтому называется биматричной. Допустим, матрицы игры выглядят следующим образом: 𝐵1 𝐵2 𝐵1 𝐵2 𝐴1 𝑎11 𝑎12 𝐴1 𝑏11 𝑏12 𝐴= ( )и 𝐵= ( ). 𝐴2 𝑎21 𝑎22 𝐴2 𝑏21 𝑏22 Припишем стратегиям 𝐴1 , 𝐴2 (𝐵1 , 𝐵2 ) вероятности 𝑝, 1 − 𝑝 (𝑞, 1 − 𝑞) соответственно. 𝑞 (1 − 𝑞) 𝑝 𝑎11 𝑎12 𝐴 = (1 − 𝑝) (𝑎 ) 21 𝑎22 𝑞 (1 − 𝑞) 𝑝 𝑏11 𝑏12 и 𝐵 = (1 − 𝑝) ( ). 𝑏21 𝑏22 Тогда средний выигрыш игрока 𝐴 (первого игрока) равен: 𝑀1 (𝑝, 𝑞) = 𝑎11 𝑝𝑞 + 𝑎12 𝑝(1 − 𝑞) + 𝑎21 𝑞(1 − 𝑝) + 𝑎22 (1 − 𝑝)(1 − 𝑞). 24 Средний выигрыш игрока 𝐵 (второго игрока) равен: 𝑀2 (𝑝, 𝑞) = 𝑏11 𝑝𝑞 + 𝑏12 𝑝(1 − 𝑞) + 𝑏21 𝑞(1 − 𝑝) + 𝑏22 (1 − 𝑝)(1 − 𝑞). Биматричная игра, как и матричная, происходит партиями. Цель каждого игрока – выиграть как можно большую сумму в результате большого числа партий. Понятия чистых и смешанных стратегий игроков в биматричных играх вводятся аналогично тому, как это было сделано в матричных играх. Если матричные игры являются играми со строгим соперничеством, поскольку выигрыш одного игрока в точности равен проигрышу другого, то в биматричных играх интересы игроков могут быть в большей или меньшей степени близки. В зависимости от того, запрещено или разрешено сотрудничество игроков, различают некооперативные и кооперативные игры. Анализ биматричной игры в некооперативном варианте сводится к поиску максиминных стратегий игроков, т. е. стратегий, которые обеспечивают игрокам получение максимально возможного гарантированного выигрыша вне зависимости от действий противника. Множество всевозможных пар смешанных стратегий игроков обозначим 𝑆 = {(𝑝, 𝑞)|𝑝 ∈ 𝑆1 , 𝑞 ∈ 𝑆2 }, где 𝑆1 = {𝑝 = (𝑝1 , 𝑝2 , … , 𝑝𝑚 )|𝑝𝑖 ≥ 0, 𝑖 = 1,2, … , 𝑚, ∑𝑚 𝑖=1 𝑝𝑖 = 1}, 𝑆2 = {𝑞 = (𝑞1 , 𝑞2 , … , 𝑞𝑛 )|𝑞𝑗 ≥ 0, 𝑗 = 1,2, … , 𝑛, ∑𝑛𝑗=1 𝑞𝑗 = 1}. Если два игрока выбрали смешанные стратегии 𝑝 = (𝑝1 , 𝑝2 , … , 𝑝𝑚 ) и (𝑞1 , 𝑞2 , … , 𝑞𝑛 ) соответственно, то математические ожидания выигрышей игроков равны 𝑞= 𝑛 𝑀1 (𝑝, 𝑞) = ∑𝑚 𝑖=1 ∑𝑗=1 𝑎𝑖𝑗 𝑝𝑖 𝑞𝑗 и 𝑛 𝑀2 (𝑝, 𝑞) = ∑𝑚 𝑖=1 ∑𝑗=1 𝑏𝑖𝑗 𝑝𝑖 𝑞𝑗 . Важным в теории игр является понятие равновесия. Говорят, что стратегии игроков 𝑝∗ и 𝑞 ∗ образуют равновесие Нэша, если никому из игроков не выгодно от них отклоняться при условии, что другой игрок не следует своей равновесной стратегии, т. е. если для любых стратегий 𝑝 и 𝑞. 𝑀1 (𝑝∗ , 𝑞 ∗ ) ≥ 𝑀1 (𝑝, 𝑞 ∗ ), 𝑀2 (𝑝∗ , 𝑞 ∗ ) ≥ 𝑀1 (𝑝∗ , 𝑞). Теорема существования равновесий. В любой биматричной игре существует хотя бы одно равновесие Нэша. Найти равновесные ситуации можно следующим образом. По матрице 𝐴 находим числа 𝐶 = 𝑎11 + 𝑎22 − (𝑎21 + 𝑎12 ), 𝑎 = 𝑎22 − 𝑎12 и решаем систему: (𝑝 − 1)(𝐶𝑞 − 𝑎) ≥ 0 { . 𝑝(𝐶𝑞 − 𝛼) ≥ 0 По матрице 𝐵 находим числа 𝐷 = 𝑏11 + 𝑏22 − (𝑏21 + 𝑏12 ), 𝑏 = 𝑏22 − 𝑏12 и решаем систему: (𝑞 − 1)(𝐷𝑝 − 𝑏) ≥ 0 { . 𝑞(𝐷𝑝 − 𝛽) ≥ 0 25 Изобразив обе полученные кривые в координатах (𝑝, 𝑞), найдем точки пересечения этих кривых, лежащие в квадрате 0 ≤ 𝑝, 𝑞 ≤ 1, которые определяют равновесные ситуации. Для каждой равновесной ситуации находят средние выигрыши 𝑀1 (𝑝, 𝑞) и 𝑀2 (𝑝, 𝑞). Критерий равновесия. Стратегии игроков 𝑝∗ и 𝑞 ∗ образуют равновесие Нэша тогда и только тогда, когда при условии использования первым игроком стратегии 𝑝∗ любая чистая стратегия второго игрока, соответствующая 𝑞𝑗∗ > 0, приносит второму игроку один и тот же выигрыш 𝜇, а любая чистая стратегия второго игрока, соответствующая 𝑞𝑗∗ = 0, приносит второму игроку выигрыш, не больший 𝜇, а при условии использования вторым игроком стратегии 𝑞 ∗ любая чистая стратегия первого игрока, соответствующая 𝑝𝑖∗ > 0, приносит первому игроку один и тот же выигрыш 𝑣, а любая чистая стратегия первого игрока, соответствующая 𝑝𝑖∗ = 0, приносит первому игроку выигрыш, не больший 𝑣. Доказательство. Пусть пара стратегий первого и второго игрока 𝑝∗ = (𝑝1 , 𝑝2 , … , 𝑝𝑚 ), 𝑞 ∗ = (𝑞1 , 𝑞2 , … , 𝑞𝑗1 , … , 𝑞𝑗2 , … , 𝑞𝑛 ) образуют равновесие Нэша, и пусть первый игрок действует в соответствии со стратегией 𝑝∗ , не отклоняясь от нее. Предположим, что у второго игрока существуют такие чистые стратегии с номерами 𝑗1 и 𝑗2 , что 𝑞𝑗1 > 0 и 𝑚 ∗ (2) 𝑀2 (𝑝∗ , 𝑞 (1) ) = ∑𝑚 ), 𝑖=1 𝑏𝑖𝑗1 𝑝𝑖 < ∑𝑖=1 𝑏𝑖𝑗2 𝑝𝑖 = 𝑀2 (𝑝 , 𝑞 где 𝑞 (1) = (0,0, … , 𝑞𝑗1 , … ,0, … ,0) 𝑞 (2) = (0,0, … , 0, … , 𝑞𝑗2 , … ,0). В этом случае второй игрок может отклониться от стратегии 𝑞 ∗ и выбрать стратегию 𝑞 ∗∗ = (𝑞1 , 𝑞2 , … ,0, … , 𝑞𝑗1 + 𝑞𝑗2 , … , 𝑞𝑛 ), которая обеспечит ему больший выигрыш, чем стратегия 𝑞 ∗ при условии, что первый игрок не будет отклоняться от стратегии 𝑝∗ . Действительно, 𝑀2 (𝑝∗ , 𝑞 ∗∗ ) − 𝑀2 (𝑝∗ , 𝑞 ∗ ) = ∑𝑚 𝑖=1(𝑏𝑖1 𝑝𝑖 𝑞1 + 𝑏𝑖2 𝑝𝑖 𝑞2 + ⋯ + 𝑏𝑖𝑗1 𝑝𝑖 ∙ 0 + ⋯ + +𝑏𝑖𝑗2 𝑝𝑖 ∙ (𝑞𝑗1 + 𝑞𝑗2 ) + ⋯ + 𝑏𝑖𝑛 𝑝𝑖 𝑞𝑛 ) − ∑𝑚 𝑖=1(𝑏𝑖1 𝑝𝑖 𝑞1 + 𝑏𝑖2 𝑝𝑖 𝑞2 + ⋯ + 𝑏𝑖𝑗1 𝑝𝑖 𝑞𝑗1 + ⋯ + 𝑚 +𝑏𝑖𝑗2 𝑝𝑖 𝑞𝑗2 + ⋯ + 𝑏𝑖𝑛 𝑝𝑖 𝑞𝑛 ) = −𝑞𝑗1 ∑𝑚 𝑖=1 𝑏𝑖𝑗1 𝑝𝑖 + 𝑞𝑗1 ∑𝑖=1 𝑏𝑖𝑗2 𝑝𝑖 = = 𝑞𝑗1 (𝑀2 (𝑝∗ , 𝑞 (2) ) − 𝑀2 (𝑝∗ , 𝑞 (1) )) > 0 Получили противоречие с предположением, что стратегии 𝑝∗ и 𝑞 ∗ образуют равновесие Нэша, которое доказывает теорему. Максиминные смешанные стратегии первого и второго игроков обеспечивают им гарантированные выигрыши 𝛼 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑀1 (𝑝, 𝑞) и 𝛽 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑀1 (𝑝, 𝑞) 𝑝∈𝑆1 𝑞∈𝑆2 𝑞∈𝑆2 𝑝∈𝑆1 соответственно вне зависимости от поведения противника. По-другому максиминные стратегии называются осторожными – смысл этого названия очевиден, и в некооперативном случае игрокам имеет смысл придерживаться своих осторожных стратегий. Пример 3.1. (Игра «Дилемма заключенных»). Двое преступников (первый и второй игроки), подозреваемые в совместном совершении тяжкого преступления, находятся изолированно друг от друга в предварительном заключении. Прямые улики у следствия отсутствуют, поэтому успех обвинения зависит от того, признаются ли заключенные. У каждого из заключенных есть две стратегии: признаться (первая стратегия) или не признаваться (вторая стратегия). Если оба преступника признаются, то они будут признаны виновными и приговорены к восьми годам заключения. Если ни один из них не признается, 26 то по обвинению в основном преступлении они будут оправданы, но суд все-таки признает их вину в менее значительном преступлении (например, в ношении оружия), в результате чего оба будут приговорены к одному году заключения. Если же признается только один и них, то признавшийся будет освобожден (за помощь следствию), а другой преступник будет приговорен к максимальному сроку заключения – к десяти годам. Требуется определить максиминные стратегии игроков и равновесия Нэша, если такие есть. Решение 1. Матрицы выигрышей игроков таковы: 𝑞 (1 − 𝑞) 𝑝 −8 𝐴 = (1 − 𝑝) ( ) −10 −1 и 𝑞 (1 − 𝑞) 𝑝 −8 −10 𝐵 = (1 − 𝑝) ( ) −1 Смешанные стратегии игроков представим в виде 𝒑 = (𝑝, 1 − 𝑝) и 𝒒 = (𝑞, 1 − 𝑞), где 𝑝 ∈ [0,1], 𝑞 ∈ [0,1]. При этом математическое ожидание выигрыша первого игрока равно 𝑀1 (𝑝, 𝑞) = −8𝑝𝑞 − 10(1 − 𝑝)𝑞 − (1 − 𝑝)(1 − 𝑞) = (𝑝 − 9)𝑞 + 𝑝 − 1. Аналогично определяется математическое ожидание выигрыша второго игрока: 𝑀2 (𝑝, 𝑞) = −8𝑝𝑞 − 10𝑝(1 − 𝑞) − (1 − 𝑝)(1 − 𝑞) = (𝑞 − 9)𝑝 + 𝑞 − 1. Наилучший гарантированный выигрыш первого игрока равен 𝛼 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑀1 (𝑝, 𝑞) = 𝑚𝑎𝑥 𝑚𝑖𝑛 ((𝑝 − 9)𝑞 + 𝑝 − 1) = 𝑝∈[0,1] 𝑞∈[0,1] 𝑝∈[0,1] 𝑞∈[0,1] = 𝑚𝑎𝑥 ((𝑝 − 9) ∙ 1 + 𝑞 − 1) = 𝑚𝑎𝑥 (2𝑝 − 10) = −8 𝑝∈[0,1] 𝑝∈[0,1] Учли, что (𝑝 − 9) < 0, так как 𝑝 ∈ [0,1], поэтому вне зависимости от 𝑝 min ((𝑝 − 𝑞∈[0,1] 9)𝑞 + 𝑝 − 1) будет достигаться при 𝑞 = 1, а максиминная стратегия первого игрока, соответствующая этому наилучшему гарантированному выигрышу, 𝒑 = (1,0), т. е. максиминная стратегия первого игрока – признаться и получить восемь лет заключения. Аналогично находим наилучший гарантированный выигрыш второго игрока 𝛽 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑀2 (𝑝, 𝑞) = 𝑚𝑎𝑥 𝑚𝑖𝑛 ((𝑞 − 9)𝑝 + 𝑞 − 1) = 𝑞∈[0,1] 𝑝∈[0,1] 𝑞∈[0,1] 𝑝∈[0,1] = 𝑚𝑎𝑥 ((𝑞 − 9) ∙ 1 + 𝑞 − 1) = 𝑚𝑎𝑥 (2𝑞 − 10) = −8 𝑞∈[0,1] 𝑞∈[0,1] и его максиминную стратегию 𝒒 = (1,0) – признаться. Очевидно, максиминные стратегии образуют равновесие Нэша. Решение 2. По матрице 𝐴 находим числа 𝐶 = −8 + (−1) − (−10 + 0) = 1, 𝑎 = −1 − 0 = −1 и решаем систему: (𝑝 − 1)(𝑞 + 1) ≥ 0 { . 𝑝(𝑞 + 1) ≥ 0 где получим 𝑝 = 1. По матрице 𝐵 находим числа 𝐷 = 𝑏11 + 𝑏22 − (𝑏21 + 𝑏12 ) = −8 + (−1) − (0 + (−10) = 1, 𝑏 = 𝑏22 − 𝑏12 = −1 − (−10) = 9 и решаем систему: (𝑞 − 1)(𝑝 − 9) ≥ 0 { . 𝑞(𝑝 − 9) ≥ 0 где получим 𝑞 = 1. Тогда средний выигрыш игрока 𝐴 (первого игрока) равен: 𝑀1 (𝑝, 𝑞) = −8𝑝𝑞 − 10(1 − 𝑝)𝑞 − (1 − 𝑝)(1 − 𝑞) = (𝑝 − 9)𝑞 + 𝑝 − 1 = (1 − 9) ∙ 1 + 1 − 1 = −8. Средний выигрыш игрока 𝐵 (второго игрока) равен: 27 𝑀2 (𝑝, 𝑞) = −8𝑝𝑞 − 10𝑝(1 − 𝑞) − (1 − 𝑝)(1 − 𝑞) = (𝑞 − 9)𝑝 + 𝑞 − 1 = (1 − 9) ∙ 1 + 1 − 1 = −8 . Очевидно, максиминные стратегии образуют равновесие Нэша. Пример 3.2 (Игра «семейный спор»). Два игрока (муж и жена) выбирают, где провести вечер. У каждого из них есть две стратегии: выбрать посещение футбольного матча (первая стратегия) или оперного спектакля (вторая стратегия). Полезность совместного похода в театр муж оценивает в одну единицу, а жена в две, полезность совместного похода на футбол, наоборот, жена оценивает в одну единицу, а муж в две. Если же супруги идут в разные места, вечер оказывается испорченным, что соответствует нулевым полезностям для обоих игроков. Требуется определить макси-минные стратегии игроков и равновесия Нэша, если такие есть. Решение. Составим матрицы выигрышей игроков: 𝑞 𝑝 2 𝐴 = (1 − 𝑝) ( (1 − 𝑞) ) 1 и 𝑞 𝑝 1 𝐵 = (1 − 𝑝) ( (1 − 𝑞) ) 2 Смешанные стратегии игроков представим в виде 𝒑 = (𝑝, 1 − 𝑝) и 𝒒 = (𝑞, 1 − 𝑞), где 𝑝 ∈ [0,1], 𝑞 ∈ [0,1]. При этом математические ожидания выигрышей игроков равны 𝑀1 (𝑝, 𝑞) = 2𝑝𝑞 − (1 − 𝑝)(1 − 𝑞) = (3𝑝 − 1)𝑞 − 𝑝 + 1. 𝑀2 (𝑝, 𝑞) = 𝑝𝑞 + 2(1 − 𝑝)(1 − 𝑞) = (3𝑞 − 2)𝑝 − 2𝑞 + 2. Наилучшие гарантированные выигрыши игроков 𝛼 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑀1 (𝑝, 𝑞) = 𝑚𝑎𝑥 𝑚𝑖𝑛 ((3𝑝 − 1)𝑞 − 𝑝 + 1) = 𝑝∈[0,1] 𝑞∈[0,1] 𝑝∈[0,1] 𝑞∈[0,1] = 𝑚𝑎𝑥 { 𝑚𝑎𝑥 (2𝑝), 𝑚𝑎𝑥 (1 − 𝑝)} = 2⁄3; 𝑝∈[0,1⁄3] 𝑝∈[1⁄3,0] 𝛽 = 𝑚𝑎𝑥 𝑚𝑖𝑛 𝑀2 (𝑝, 𝑞) = 𝑚𝑎𝑥 𝑚𝑖𝑛 ((3𝑞 − 2)𝑝 − 2𝑞 + 2) = 𝑞∈[0,1] 𝑝∈[0,1] 𝑞∈[0,1] 𝑝∈[0,1] = 𝑚𝑎𝑥 { 𝑚𝑎𝑥 (𝑞), 𝑚𝑎𝑥 (2 − 2𝑞)} = 2⁄3 , 𝑞∈[0,2⁄3] 𝑞∈[2⁄3,0] а соответствующие максиминные стратегии таковы: 𝒑 = (1⁄3 , 2⁄3) и 𝒒 = (2⁄3 , 1⁄3). Иным способом: По матрице 𝐴 находим числа 𝐶 = 2 + 1 = 3 = 1, 𝑎 = 1 и решаем систему: (𝑝 − 1)(3𝑞 − 1) ≥ 0 { . 𝑝(3𝑞 − 1) ≥ 0 где получим 𝑝 = 1; 𝑞 = 1⁄3. По матрице 𝐵 находим числа 𝐷 = 𝑏11 + 𝑏22 − (𝑏21 + 𝑏12 ) = 1 + 2 = 3, 𝑏 = 𝑏22 − 𝑏12 = 2 и решаем систему: (𝑞 − 1)(3𝑝 − 2) ≥ 0 { . 𝑞(3𝑝 − 2) ≥ 0 где получим 𝑞 = 1; 𝑝 = 2⁄3 Тогда средний выигрыш игрока 𝐴 (первого игрока) равен: 𝑀1 (𝑝, 𝑞) = (3𝑝 − 1)𝑞 − 𝑝 + 1 = (3 ∙ 1 − 1) ∙ 1⁄3 − 1 + 1 = 2⁄3. Средний выигрыш игрока 𝐵 (второго игрока) равен: 28 𝑀2 (𝑝, 𝑞) = (3𝑞 − 2)𝑝 − 2𝑞 + 2 = (3 ∙ 1 − 2) ∙ 2⁄3 − 2 + 2 = 2⁄3 . Это означает, что муж должен в 1⁄3 вечеров выбирать футбол и в 2⁄3 вечеров театр, а жена должна в 2⁄3 вечеров выбирать футбол и в 1⁄3 вечеров театр, тогда в среднем и муж, и жена будут выигрывать по 2⁄3 за одну партию. Равновесий Нэша в данной игре целых три: 𝑝∗ = (1,0), 𝑞 ∗ = (1,0); 𝑝∗∗ = (0,1), 𝑞 ∗∗ = (0,1); 𝑝∗∗∗ = (1⁄3 , 2⁄3), 𝑞 ∗∗∗ = (2⁄3 , 1⁄3). В отличие от матричных игр, в биматричных играх может оказаться так, что совместное отклонение двумя игроками от равновесий Нэша (или от максиминных стратегий) приводит к увеличению выигрыша обоих игроков. Это иллюстрируется следующими примерами. Если в примере 3.1 один из игроков будет придерживаться максиминной стратегии и признается, а другой игрок отклонится от своей максиминной стратегии и признаваться не будет, то тот, кто не признается, получит десять лет заключения вместо восьми (в результате его положение ухудшится, а положение его соучастника улучшится). Существенным отличием биматричных игр от матричных являются то, что возможны ситуации, когда отклонение обоих игроков от максиминных стратегий приводит к увеличению их выигрышей: если в примере 3.1 оба преступника не признаются, то оба получат всего по одному году. Это и является основой дилеммы, которая стоит перед каждым из заключенных: поскольку переговоры друг с другом невозможны, каждый из двух заключенных делает выбор, признаваться или нет, не зная, сознался ли его соучастник. В примере 3.2 ситуация еще сложнее: участники могут увеличить свои выигрыши, совместно отклонившись от максиминных стратегий, в нескольких ситуациях. Например, если вместо максиминных стратегий 𝒑 = (1⁄3 , 2⁄3) и 𝒒 = (2⁄3 , 1⁄3) игроки выберут соответственно стратегии 𝒑 = (1,0) и 𝒒 = (1,0), то их выигрыши составят 2 для мужа и 1 для жены (оба эти выигрыша больше 2⁄3). Но есть и другая ситуация: если вместо максиминных стратегий игроки выберут стратегии 𝒑 = (0,1) и 𝒒 = (0,1), то их выигрыши составят 1 для мужа и 2 для жены (что опять превышает максиминные выигрыши). Если переговоры между участниками невозможны, отклоняться от максиминных стратегий опасно, так как даже если есть возможность выиграть больше, эта возможность сопряжена с риском уменьшения выигрыша. Например, если муж выберет театр – 𝒑 = (0,1), а жена футбол – 𝒒 = (1,0), или наоборот, то выигрыши обоих игроков будут равны нулю. Выходом в таких ситуациях является кооперация игроков, т. е. сотрудничество, состоящее в том, что игроки могут договориться о совместном выборе стратегий. Перейдем к обсуждению возможностей кооперативного поведения игроков. Ранее предполагалось, что в процессе игры отсутствует явный обмен информацией между участниками. Каждый игрок определял свою линию поведения, исходя из своей функции выигрыша, и, безусловно, основываясь на том, что другие игроки действуют аналогично. При этом считалось, что игроки знают функции выигрыша друг друга, но в непосредственный контакт не вступают. Между тем в реальных экономических ситуациях участники конфликтов активно взаимодействуют друг с другом: вступают в переговоры, заключают соглашения, создают коалиции, применяют угрозы и подкупы и т. д. Все эти процессы могут в различной степени получать отражения в игровых моделях. Игры, в которых возможны непосредственные контакты между участниками, называются кооперативными. Если игроки могут вступать в переговоры и образовывать коалиции, то какие исходы могут стать результатом переговоров. 29 Рассмотрим биматричную игру, в которой выигрыши первого и второго игроков заданы матрицами 𝐴 = (𝑎𝑖𝑗 ) ∈ 𝑅 𝑚×𝑛 и 𝐵 = (𝐵𝑖𝑗 ) ∈ 𝑅 𝑚×𝑛 . Пусть 𝑝 = (𝑝1 , 𝑝2 , … , 𝑝𝑚 ) и 𝑞 = (𝑞1 , 𝑞2 , … , 𝑞𝑛 ) – смешанные стратегии игроков. Так как 𝑝𝑖 ≥ 0, 𝑖 = 1,2, … , 𝑚, ∑𝑚 𝑗 = 1,2, … , 𝑛, ∑𝑛𝑗=1 𝑞𝑗 = 1, множество всех 𝑖=1 𝑝𝑖 = 1, 𝑞𝑗 ≥ 0, возможных вариантов пар выигрышей 𝑛 𝑚 𝑛 (𝑀1 (𝑝, 𝑞), 𝑀2 (𝑝, 𝑞)) = (∑𝑚 𝑖=1 ∑𝑗=1 𝑎𝑖𝑗 𝑝𝑖 𝑞𝑗 , ∑𝑖=1 ∑𝑗=1 𝑏𝑖𝑗 𝑝𝑖 𝑞𝑗 ) представляет собой выпуклую оболочку точек плоскости с координатами (𝑎𝑖𝑗 , 𝑏𝑖𝑗 ), 𝑖 = 1,2, … , 𝑚 и 𝑗 = 1,2, … , 𝑛; эти точки (𝑎𝑖𝑗 , 𝑏𝑖𝑗 ) соответствуют парам выигрышей игроков в случае выбора ими своих чистых стратегий. При этом точка (𝑀1′ 𝑀2′ ,) доминирует точку (𝑀1′′ , 𝑀2′′ ), если 𝑀′ > 𝑀1′′ 𝑀2′ > 𝑀2′′ { 1′ или { 𝑀2 ≥ 𝑀2′′ 𝑀1′ ≥ 𝑀1′′ это означает, что при переходе от первой точки ко второй выигрыш каждого из игроков не уменьшится, и при этом хотя бы у одного из игроков выигрыш увеличится. Множество точек, оптимальных по Парето (т. е. не доминируемых другими), описывается так: Ƭ = {(𝑝∗ , 𝑞 ∗ )|𝑝∗ ∈ 𝑆1 , 𝑞 ∗ ∈ 𝑆2 , ∀𝑝 ∈ 𝑆1 𝑀1 (𝑝∗ , 𝑞 ∗ ) ≥ 𝑀1 (𝑝, 𝑞 ∗ ), ∀𝑞 ∈ 𝑆2 𝑀2 (𝑝∗ , 𝑞 ∗ ) ≥ 𝑀2 (𝑝, 𝑞 ∗ )}. Если выбрать из множества точек, оптимальных по Парето, те точки, в которых выигрыши первого и второго игроков окажутся не меньше их максиминных выигрышей α и β, то получится переговорное множество 𝑉 = {(𝑝∗ , 𝑞 ∗ ) ∈ Ƭ| 𝑀1 (𝑝∗ , 𝑞 ∗ ) ≥ 𝛼, 𝑀2 (𝑝∗ , 𝑞 ∗ ) ≥ 𝛽}. Игрокам, естественно, имеет смысл выбирать свои оптимальные стратегии, соответствующие точкам из переговорного множества. Существуют различные способы достижения игроками договоренности о совместном выборе точки из переговорного множества. Самый простой из них заключается в выборе таких чистых стратегий, которые приносят игрокам наибольший суммарный доход, из которого один из игроков платит другому оговоренную сумму. Этот способ, конечно же, предполагает полностью доверительные отношения между игроками. Если же договориться о выборе точки из переговорного множества игрокам не удается, то можно предложить им применить одну из так называемых арбитражных схем. Например, арбитражная схема Нэша предлагает игрокам выбрать из переговорного множества решение Нэша — такую пару смешанных стратегий, которая доставляет максимум функции Нэша, которая равна произведению превышений выигрышей игроков над гарантированными (минимаксными) выигрышами. Реализация алгоритма Нэша предполагает решение задачи математического программирования 𝑁 = (𝑀1 (𝑝, 𝑞) − 𝛼)(𝑀2 (𝑝, 𝑞) − 𝛽) → 𝑚𝑎𝑥, (𝑝, 𝑞) ∈ 𝑉. Целевая функция этой задачи называется функцией Нэша, а оптимальное решение данной — решением Нэша. Решение этой задачи всегда существует, и если в переговорном множестве V есть хотя бы одна точка (𝑝, 𝑞) ∈ 𝑉, такая что 𝑀1 (𝑝, 𝑞) − 𝛼, 𝑀2 (𝑝, 𝑞) − 𝛽, то решение задачи единственно. Пример 3.3 (Игра «Дилемма заключенных» в кооперативном варианте). Требуется найти переговорное множество и решение Нэша в игре, описанной в примере 3.1 (Двое преступников (первый и второй игроки), подозреваемые в совместном совершении 30 тяжкого преступления, находятся изолированно друг от друга в предварительном заключении. Прямые улики у следствия отсутствуют, поэтому успех обвинения зависит от того, признаются ли заключенные. У каждого из заключенных есть две стратегии: признаться (первая стратегия) или не признаваться (вторая стратегия). Если оба преступника признаются, то они будут признаны виновными и приговорены к восьми годам заключения. Если ни один из них не признается, то по обвинению в основном преступлении они будут оправданы, но суд все-таки признает их вину в менее значительном преступлении (например, в ношении оружия), в результате чего оба будут приговорены к одному году заключения. Если же признается только один и них, то признавшийся будет освобожден (за помощь следствию), а другой преступник будет приговорен к максимальному сроку заключения – к десяти годам. Требуется определить максиминные стратегии игроков и равновесия Нэша, если такие есть) при условии, что заключенные могут обмениваться информацией. Решение. Множество всех возможных пар выигрышей игроков представлено четырехугольником ABCD на рис. 3.1. α=-8 -12 В -10 -8 Е -6 -4 -2 С -2 -4 -6 F А β=-8 -8 -10 D -12 Рис. 3.1 - Множество ожидаемых выигрышей, множество Парето и переговорное множество в кооперативном варианте игры «Дилемма заключенных» Очевидно, множество Парето соответствует ломаной BCD, а переговорное множество — ломаной ECF. Прямая, проходящая через точки B(-10, 0) и C(-1, -1), задается уравнением M2 = (-M1-10)/9, а прямая, проходящая через точки C(-1, -1) и D(0, -10), — уравнением M2 = -9M1 - 10 , поэтому функция Нэша 𝑁(𝑀1 , 𝑀2 ) = (𝑀8 + 8)(𝑀2 + 8) = 𝑀1 + 10 (𝑀1 + 8) (8 − ) , 𝑀1 ∈ [−8, −1], ={ = 9 (𝑀1 + 8)(8 − 9𝑀1 − 10), 𝑀1 ∈ [−1, − 2⁄9] −𝑀12 + 54𝑀1 496 , 𝑀1 ∈ [−8, −1], ={ 9 −9𝑀12 − 74𝑀1 − 16, 𝑀1 ∈ [−1, − 2⁄9]. 31 Функцию Нэша мы рассматриваем на переговорном множестве, т. е. на ломаной ECF, при этом отрезок EC задается уравнением M2 = (-M1 -10)/9 при M1∈ [-8, -1], а отрезок CF задается уравнением M2 = -9M1 -10 при M2 = -9M1 -10∈ [-8, -1] (или, что эквивалентно, при M1∈ [-1, -2/9]). Максимум функции Нэша на переговорном множестве достигается в точке 𝑀1∗ = -1 (график функции Нэша представлен на рис. 3.2). При этом 𝑀2∗ = -9 𝑀1∗ -10 = -1. На рис. 3.1 решение Нэша соответствует точке C, поэтому если заключенные имеют возможность переговариваться, то они могут договориться не признаваться вдвоем, и тогда получат всего по одному году заключения. N (M1) 60 50 40 30 20 10 M1 -10 -8 -6 -4 -2 -10 2 -20 Рис. 3.2 – График функции Нэша в кооперативном варианте игры «Дилемма заключенных» Пример 3.4 (Игра «Семейный спор» в кооперативном варианте). Требуется найти переговорное множество и решение Нэша в игре, описанной в примере 3.2 (Два игрока (муж и жена) выбирают, где провести вечер. У каждого из них есть две стратегии: выбрать посещение футбольного матча (первая стратегия) или оперного спектакля (вторая стратегия). Полезность совместного похода в театр муж оценивает в одну единицу, а жена в две, полезность совместного похода на футбол, наоборот, жена оценивает в одну единицу, а муж в две. Если же супруги идут в разные места, вечер оказывается испорченным, что соответствует нулевым полезностям для обоих игроков. Требуется определить максиминные стратегии игроков и равновесия Нэша, если такие есть) при условии, что игроки могут обмениваться информацией. Решение. Множество всех возможных пар выигрышей игроков представлено треугольником OAB на рис. 3.3. Очевидно, и множество Парето, и переговорное множество соответствуют отрезку AB. Прямая, проходящая через точки A(1, 2) и B(2, 1), задается уравнением M2 = 3 - M1, поэтому функция Нэша 2 2 2 2 𝑁(𝑀1 , 𝑀2 ) = (𝑀1 − ) (𝑀2 − ) = (𝑀1 − ) (3 − 𝑀1 − ) = 3 3 3 3 20 21 2 14 2 = (𝑀1 − ) ( − 𝑀1 ) = −𝑀1 + 3𝑀1 − . 3 4 3 9 Эта функция ∗ 𝑀2 = 3 - 𝑀1∗ = 1,5. достигает максимума при 𝑀1∗ = (-3)/[2×(-1)]=1,5. При этом 32 Точка (𝑀1∗ , 𝑀2∗ ) на рис. 3.3 обозначена D. Она находится ровно посередине отрезка AB, поэтому решение Нэша таково: 𝑝∗ = (1/2,1/2) и 𝑞 ∗ = (1/2,1/2). Это означает, что игроки могут договориться выбирать (случайным образом и независимо друг от друга) в половине случаев театр, и в другой половине — футбол, тогда выигрыш каждого составит в среднем 1,5 единицы за один вечер. 2,5 M2 A 2 D 1,5 1 B β=2/3 0,5 M2 0,5 α=2/3 1 1,5 2 2,5 Рис 3.3 – Множество ожидаемых выигрышей, множество Парето и переговорное множество в кооперативном варианте игры «Семейный спор» Пример 3.5. Требуется провести анализ биматричной игры, заданной матрицами 6 9 ), 8 2 𝐴= ( 𝐵= ( 9 4 7 ) 10 Решение. Пусть р = (р,1 - р) и q = (q,1 - q), где р∈[0,1], q∈[0,1], - смешанные стратегии игроков. Тогда математические ожидания выигрышей игроков равны соответственно 𝑀1 (р,q) = 6pq + 9р(1 - q) + 8(1 - p)q + 2(1 - р)(1 - q) = (6-9p)q + 7р + 2, 𝑀2 (р,q) = 9pq + 7р(1 - q) + 4(1 - p)q +10(1 - р)(1 - q) = (8q - 3)р - 6q +10. Максиминные стратегии игроков определяются из условий 𝛼 = 𝑚𝑎𝑥𝑝∈[0,1] 𝑚𝑖𝑛𝑞∈[0,1] ((6 − 3𝑝)𝑞 + 7𝑝 + 2) = 20 = 𝑚𝑎𝑥{𝑚𝑎𝑥𝑝∈[0,2/3] (7𝑝 + 2), 𝑚𝑎𝑥𝑝∈[2/3,1] (8 − 2𝑝)} = 3 (где максимум достигается при 𝑝∗ = 2/3), 𝛽 = 𝑚𝑎𝑥𝑞∈[0,1] 𝑚𝑖𝑛𝑝∈[0,1] ((8𝑞 − 3)𝑝 − 6𝑞 + 10) = 31 = 𝑚𝑎𝑥{𝑚𝑎𝑥𝑞∈[0,3/8] (2𝑞 + 7), 𝑚𝑎𝑥𝑞∈[3/8,1] (10 − 6𝑞)} = 4 (где максимум достигается при 𝑞 ∗ = 3/8). Таким образом, максиминные стратегии первого и второго игрока равны р = (2/3,1/3) и q = (3/8,5/8), а их гарантированные выигрыши составляют 20/3 и 31/4 соответственно. Множество всех возможных пар выигрышей игроков представлено четырехугольником ABCD на рис. 3.4. Очевидно, множество Парето соответствует отрезку BC, а переговорное множество — отрезку EF. Прямая, проходящая через точки B(6, 9) и C(9, 7), задается уравнением M2 = 13 - 2M1/3, поэтому функция Нэша 20 31 20 2 31 N(𝑀1 , 𝑀2 ) = (𝑀1 − 3 ) (𝑀2 − 4 ) = (𝑀1 − 3 ) (13 − 3 𝑀1 − 4 ) = 33 = (𝑀1 − 20 21 2 2 349 ) ( − 𝑀1 ) = − 𝑀12 + 𝑀 − 35 3 4 3 3 36 1 на отрезке M1∈[20/3,63/8] (т. е. на отрезке EF; при M2 = 31/4 значение M1 = 3(13 - 31 / 4) / 2 = 63/8) достигает максимума в точке 𝑀1∗ = 349/48. При этом 𝑀2∗ = 13 − 2𝑀1∗ = 587/72. Эта точка на рис. 3.4 обозначена G. 3 349 587 Точка G( 48 , 83 72 ) является выпуклой комбинацией точек B(6, 9) и C(9, 7), т. е. 349 6𝜆 + 9(1 − 𝜆) = , { 48 9𝜆 + 7(1 − 𝜆) = 587/72, откуда λ = 144. Точка В соответствует выбору обоими игроками своих первых чистых стратегий, точка C соответствует выбору первым игроком своей первой чистой стратегии, а вторым игроком — своей второй чистой стратегии, поэтому точка G соответствует тому, что первый игрок выбирает свою первую чистую стратегию, а второй игрок с вероятностью 83 𝑞 ∗ = 𝜆 = 144 выбирает первую чистую стратегию, и с вероятностью 61 1 - 𝑞 ∗ = 144— вторую чистую стратегию. Таким образом, решение Нэша таково: 𝒑∗ =(1,0), 𝑞 ∗ =(83/144,61/144). При ∗ этом средний выигрыш первого игрока равен 𝑀1 = 349/48, а средний выигрыш второго игрока — 𝑀2∗ = 587/72. 14 M2 12 А 10 В EG 8 F β=31/4 C 6 4 D 2 M1 α=20/3 2 4 6 8 10 12 Рис. 3.4 – Множество ожидаемых выигрышей, множество Парето и переговорное множество в примере 3.5 Непрерывные игры Игра с нулевой или ненулевой суммой называется непрерывной, если множества стратегий участников игры целиком заполняют некоторые отрезки. Смешанные стратегии в непрерывных играх задаются уже не наборами вероятностей, а функциями (или плотностями) распределения непрерывных случайных величин на 34 соответствующих отрезках. При этом математические ожидания выигрышей из сумм превращаются в интегралы. Можно доказать, что если в непрерывной игре с нулевой суммой функция выигрыша первого игрока непрерывна по всем переменным, то у игроков есть оптимальные смешанные стратегии. Рассмотрим пример непрерывной игры с нулевой суммой. Пример 4.1 (Игра «Шумная дуэль»). В дуэли принимают участие двое. В начальный момент дуэлянты находятся на расстоянии d0 и по команде начинают сближаться. В распоряжении каждого дуэлянта имеется один выстрел, который он может произвести в противника с любого расстояния (конечно при условии, что дуэлянт жив), он может даже подойти к противнику вплотную. Пусть функции pk(d) задают вероятности поражения противника k-м игроком (k = 1, 2) с расстояния d. Предположим, что эти функции непрерывны и убывают на отрезке [0, d0]. Рассматривается шумная дуэль, когда противники слышат выстрелы друг друга. Требуется формализовать поведение игроков в виде непрерывной игры с нулевой суммой и определить оптимальные чистые стратегии игроков (если такие стратегии существуют). Решение. Стратегии первого и второго игроков определяются выбором чисел 𝑥 ∈ [0, 𝑑0 ], 𝑦 ∈ [0, 𝑑0 ] — расстояний, с которых дуэлянты намечают произвести свои выстрелы. Выигрышем F(x, y) первого дуэлянта, если он стреляет с расстояния x, а его противник — с расстояния y, удобно считать вероятность того, что первый дуэлянт поразит второго. Очевидно, 𝑝 (𝑥), 0 ≤ 𝑦 ≤ 𝑥 ≤ 𝑑0 𝐹(𝑥, 𝑦) = { 1 1 − 𝑝2 (𝑦), 0 ≤ 𝑥 < 𝑦 ≤ 𝑑0 . (Здесь мы учли, что если x < у, и второй игрок промахнется, то первый, услышав выстрел противника, стреляет в него с расстояния 0 вместо x.) Покажем, что шумная дуэль имеет решение в чистых стратегиях: эти стратегии таковы: 𝑑∗ для первого дуэлянта, 𝑑∗ для второго, при этом цена игры равна 𝑝1 (𝑑∗ ) [здесь 𝑑∗ — единственный корень уравнения 𝑝1 (𝑑 ∗ ) = 1 − 𝑝2 (𝑑 ∗ )]. Действительно, 𝑝 (𝑥) ≤ 𝑝1 (𝑑 ∗ ), 𝑑 ∗ ≤ 𝑥 ≤ 𝑑0 , 𝐹(𝑑∗ , 𝑑 ∗ ) = 𝑝1 (𝑑 ∗ ), 𝐹(𝑥, 𝑑∗ ) = { 1 ∗ ∗ 1 − 𝑝2 (𝑑 ) = 𝑝1 (𝑑 ), 0 ≤ 𝑥 < 𝑑∗ , 𝑝 (𝑑∗ ), 0 ≤ 𝑦 < 𝑑∗ , 𝐹(𝑑∗ , 𝑦) = { 1 ∗ ∗ 𝑑 ∗ < 𝑥 ≤ 𝑑0 . 1 − 𝑝2 (𝑦) ≥ 1 − 𝑝2 (𝑑 ) = 𝑝1 (𝑑 ), Таким образом, 𝐹(𝑥, 𝑑∗ ) ≤ 𝐹(𝑑∗ , 𝑑 ∗ ) ≤ 𝐹(𝑑∗ , 𝑦) для любых 𝑥 ∈ [0, 𝑑0 ], 𝑦 ∈ [0, 𝑑0 ], откуда и следует, что (𝑑∗ , 𝑑∗ ) — седловая точка данной игры. В частности, если меткость игроков одинакова [т. е. 𝑝1 (𝑥) = 𝑝2 (𝑥)], то цена игры, очевидно, равна 1/2, а 𝑑 ∗ является корнем уравнения 𝑝1 (𝑑 ∗ ) = 1⁄2. В бесшумной дуэли игроки не слышат выстрелов друг друга, поэтому 𝑝 (𝑥), 0 ≤ 𝑦 ≤ 𝑥 ≤ 𝑑0 𝐹(𝑥, 𝑦) = { 1 𝑝1 (𝑥)(1 − 𝑝2 (𝑦)), 0 ≤ 𝑥 < 𝑦 ≤ 𝑑0 . Читателю предлагается доказать, что бесшумная дуэль не имеет решений в чистых стратегиях. Переходя к рассмотрению непрерывных игр с непротивоположными интересами, отметим, что решение Нэша (и в конечных играх, и в непрерывных) имеет серьезный недостаток, который заключается в том, что оно не принимает в расчет угрозы. Это иллюстрирует пример игры «Работодатель — работник», в которой работник имеет возможность установить интенсивность своей работы от 100% (полезность этой ситуации для работника оценивается нулем, а для работодателя прибылью 1 млн. руб.) до 0% (в этом случае работник будет голодать, и полезность этой ситуации для работника оценивается в -500 000 руб., а работодатель получит нулевую прибыль). Работодатель может поделиться с работником частью прибыли (если захочет). Минимаксные выигрыши игроков равны нулю, 35 а решение Нэша (в чем мы предлагаем убедиться читателю) состоит в том, что работодатель и работник делят прибыль поровну — по 500 тыс. руб. Однако при этом игнорируется тот факт, что работодатель находится в гораздо более выгодном положении, чем работник. Действительно, работник может воспрепятствовать работодателю, только решившись на очень трудный шаг; угроза прекратить работу с его стороны не очень правдоподобна, и в результате работник, скорее всего, будет продолжать работать за зарплату даже в том случае, если работодатель не будет делиться с ним прибылью. Угроза же работодателя уменьшить сумму, которой он делится с работником, вполне реальна. Позиционные игры Все игры, которые рассматривались до сих пор, были заданы в так называемой нормальной форме, которая предполагает, что: 1) задано множество игроков I (не ограничивая общности, можно считать, что k игроков заданы своими номерами, т. е. I = {1, 2, …, k}; 2) для каждого игрока 𝑖 ∈ 𝐼 задано множество возможных стратегий {𝑥𝑖 }; 3) для каждой ситуации (т. е. совместного выбора игроками своих стратегий: 𝑥1 — первым игроком, 𝑥2 — вторым, …, 𝑥𝑘 — k-м игроком) заданы выигрыши игроков: 𝐻1 (𝑥1 , 𝑥2 , … , 𝑥𝑘 ) — первого, 𝐻2 (𝑥1 , 𝑥2 , … , 𝑥𝑘 ) — второго, …, 𝐻𝑘 (𝑥1 , 𝑥2 , … , 𝑥𝑘 ) — k-го, т. е. заданы функции выигрышей. Пример 5.2 (Игра «Угадывание монеты» в нормальной форме»). Требуется составить нормальную форму игры из примера 1.2 (первый игрок прячет в кулаке одну из двух монет – 1 руб. или 5 руб. – по своему выбору и незаметно от второго игрока, а второй игрок пытается угадать, какая монета спрятана. Если угадывает, то получает эту монету, если нет, то платит первому игроку 3 руб.). Решение. В игре, рассмотренной в примере 1.2, множество игроков 𝐼 = {1,2}, множество стратегий первого игрока {𝑥11 = «спрятать 1 руб.», 𝑥12 = «спрятать 5 руб.»}, множество стратегий второго игрока {𝑥21 = «назвать 1 руб.», 𝑥22 = «назвать 5 руб.»}, а функции выигрышей игроков, очевидно, задаются так: 𝐻1 (𝑥11 , 𝑥21 ) = −1, 𝐻2 (𝑥11 , 𝑥21 ) = 1, 𝐻1 (𝑥11 , 𝑥22 ) = 3, 𝐻2 (𝑥11 , 𝑥22 ) = −3, 2 1 𝐻1 (𝑥1 , 𝑥2 ) = 3, 𝐻2 (𝑥12 , 𝑥21 ) = −3, 𝐻1 (𝑥12 , 𝑥22 ) = −5, 𝐻2 (𝑥12 , 𝑥22 ) = 5. Легко видеть, что 𝐻2 (𝑥1 , 𝑥2 ) = −𝐻1 (𝑥1 , 𝑥2 ). Партия игры, заданной в нормальной форме, состоит в одновременном выборе игроками своих стратегий. Во многих случаях, между тем, игроки делают выбор последовательно. Такие игры называются позиционными. Процесс позиционной игры состоит в последовательном переходе от одной позиции к другой, который осуществляется либо путем выбора игроками возможных альтернатив в соответствии с правилами игры, либо случайным образом (в этом случае говорят о случайном ходе). Множество позиций в такой игре можно представить в виде упорядоченного множества, которое называется деревом игры, и представляет собой граф без циклов, в котором некоторые из вершин называются окончательными и соответствуют моменту окончания партии и расплаты — известны выигрыши каждого из игроков при достижении этих вершин; каждая из неокончательных вершин соответствует либо выбору конкретным игроком одной из возможных альтернатив, либо случайному ходу; среди неокончательных вершин выделена начальная вершина (соответствующая началу партии игры). Различают позиционные игры с полной информацией и с неполной. В играх с полной информацией каждый игрок при своем ходе знает, в какой позиции дерева игры он 36 находится. В играх с неполной информацией игрок, делающий ход, не знает точно, в какой именно позиции он находится, игроку известно лишь информационное множество — некоторое множество позиций, включающее не только ту позицию, в которой фактически находится игрок, но также и другие позиции (в которых игрок мог бы находиться). Пример 5.2 (Позиционная игра «угадывание монеты» с полной информацией). Требуется проанализировать игру, описанную в примере 1.2 (первый игрок прячет в кулаке одну из двух монет – 1 руб. или 5 руб. – по своему выбору и незаметно от второго игрока, а второй игрок пытается угадать, какая монета спрятана. Если угадывает, то получает эту монету, если нет, то платит первому игроку 3 руб.), в ситуации, когда второй игрок имеет возможность подглядеть, какую монету спрятал первый. Решение. Дерево игры изображено на рис. 5.1. Серым цветом на рис. 5.1 выделены информационные множества игроков. Стратегии первого игрока таковы: 𝑥11 = «спрятать 1 руб.», 𝑥12 = «спрятать 5 руб.», а стратегию второго игрока удобно задавать в виде пары альтернатив [𝑦1 , 𝑦2 ], где 𝑦1 , 𝑦2 ∈ {𝑥21 = назвать 1 руб., 𝑥22 = "назвать 5 руб. "}, первая из этих альтернатив 𝑦1 соответствует выбору второго игрока в случае выбора первым его первой альтернативы, а вторая альтернатива 𝑦2 соответствует выбору второго игрока в случае выбора первым игроком его второй альтернативы. Очевидно, у второго игрока есть четыре чистых стратегии: [𝑥21 , 𝑥21 ], [𝑥21 , 𝑥22 ], [𝑥22 , 𝑥21 ], [𝑥22 , 𝑥22 ]. Выигрыши игроков удобно свести в матрицу −1 −1 3 3 ( ). (5.1) 3 −5 3 −5 Строки этой матрицы соответствуют выбору первым игроком своих стратегий 𝑥11 и 2 𝑥1 , а столбцы — выбору вторым игроком своих стратегий [𝑥21 , 𝑥21 ], [𝑥21 , 𝑥22 ], [𝑥22 , 𝑥21 ] и [𝑥22 , 𝑥22 ]. Элементы матрицы равны соответствующим выигрышам первого игрока (в данной игре выигрыш второго игрока противоположен выигрышу первого). спрятать 1 руб. I спрятать 5 руб. II II назвать 5 руб. назвать 5 руб. назвать 1 руб. -1, 1 назвать 1 руб. 3, -3 3, -3 -5, 5 Рис. 5.1 – Дерево позиционной игры «Угадывание монеты» с полной информацией Например, в левой верхней клетке матрицы стоит выигрыш первого игрока, если он выбрал стратегию 𝑥11 = «спрятать 1 руб.», а второй игрок выбрал стратегию [𝑥21 , 𝑥21 ] (т. е. независимо от того, какую альтернативу выбрал первый игрок, второй называет 1 руб.). Итак, первый игрок спрятал 1 руб., а второй игрок навал 1 руб., значит, выигрыш первого игрока равен -1 руб. Выигрыши в остальных ситуациях определяются точно таким же образом. 37 Данная матричная игра имеет седловую точку (-1), которая соответствует первой строке и второму столбцу платежной матрицы (5.1), т. е. выбору первым игроком своей стратегии 𝑥11 = «спрятать 1 руб.», а вторым игроком — стратегии [𝑥21 , 𝑥22 ] (т. е. назвать 1 руб., если первый игрок спрятал 1 руб., и 5 руб., если первый игрок спрятал 5 руб.). Подобная ситуация для позиционных игр с полной информацией типична — в только что рассмотренном примере содержится идея доказательства следующей теоремы. Теорема. Любая позиционная игра с полной информацией эквивалентна некоторой матричной игре, в которой существует седловая точка в чистых стратегиях. Эта теорема означает, в частности, существование оптимальных чистых стратегий в играх типа шахмат и шашек; такие оптимальные стратегии пока не известны, но лишь потому, что платежная матрица, к которой сводится, например, шахматная игра, очень велика по размеру, и ее анализ современным компьютерам пока не под силу, однако развитие технологии распределенных вычислений в интернете, по-видимому, в ближайшие десятилетия приведет к отысканию оптимальных шахматных стратегий. Иное дело обстоит с позиционными играми с неполной информацией (к таким играм относятся, например, домино и большинство карточных игр). Рассмотрим конкретный пример. Пример 5.2 (Позиционная игра «Угадывание монеты» с неполной информацией). Требуется проанализировать игру «Угадывание монеты» как позиционную игру с неполной информацией. Решение. Информационные множества игроков в таком случае закрашены серым на рис. 5.2. Теперь мы получили позиционную игру с неполной информацией: второму игроку в момент его хода известно информационное множество, но неизвестна конкретная позиция из информационного множества, в которой он находится (левая или правая на рис. 5.2). В этом случае первый игрок имеет две стратегии: 𝑥11 = «спрятать 1 руб.», 𝑥12 = «спрятать 5 руб.», и поскольку второму игроку выбор первого неизвестен, у второго игрока есть две стратегии: 𝑥21 = «назвать 1 руб.», 𝑥22 = «назвать 5 руб.». I спрятать 1 руб. спрятать 5 руб. II II назвать 5 руб. назвать 5 руб. назвать 1 руб. -1, 1 назвать 1 руб. 3, -3 3, -3 -5, 5 Рис. 5.2 – Дерево позиционной игры «Угадывание монеты» с неполной информацией Матрица −1 3 ) 3 −5 выигрышей первого игрока в зависимости от выбора игроками своих стратегий не имеет седловой точки в чистых стратегиях, а оптимальные смешанные стратегии игроков таковы: 𝒑∗ = (2/3,1/3), 𝒒∗ = (2/3,1/3), при этом цена игры равна v = 1/3. ( 38 Применим теперь аппарат теории игр к исследованию конкуренции производителя коммерческого программного обеспечения с пиратами. Пример 5.3 (Игра «Проверка легальности программного обеспечения»). Производитель программного обеспечения продает лицензии на использование своей продукции. Пользователь имеет возможность приобрести лицензионную копию программного продукта (по цене c ден. ед.) или пиратскую (по цене d ден. ед.). При этом полезность, которую приносит использование нелицензионного программного обеспечения, в точности равна полезности от использования легальной копии, а себестоимость изготовления одной копии (и легальной, и пиратской) пренебрежимо мала по сравнению со всеми остальными величинами. Поскольку значительная часть пользователей пользуются нелицензионными копиями, производитель может предпринимать определенные меры по изобличению пользователей пиратских копий и привлечению их к ответственности. При этом он понесет определенные издержки по организации проверки легальности использования программного обеспечения (в размере l ден. ед. на проверку каждого пользователя), но если будет обнаружено незаконное использование программного продукта, пользователь заплатит в пользу производителя штраф (в размере f ден. ед.). Требуется проанализировать данную конфликтную ситуацию. Решение. Очевидно, выполняются следующие соотношения: 𝑓 > 𝑙 > 𝑐 ≫ 𝑑 > 0; 𝑓 > 𝑐 + 𝑙. Будем считать также, что 𝑙 > 2𝑐. (последнее неравенство эквивалентно тому, что 𝑐 − 𝑙 > −𝑐). Данная конфликтная ситуация является типичной иллюстрацией асимметрии информации, когда пользователь знает происхождение своего программного обеспечения (легальное оно или пиратское), а производитель (и государство) не может отличить «честного» пользователя от пользователя — пирата. Рассмотрим позиционную форму игры и построим ее дерево (рис. 5.3). Первым игроком является пользователь, он осознанно принимает одно из двух решений: приобрести лицензионное или пиратское программное обеспечение. Производитель является вторым игроком, поскольку он может принять решение по инициации проверки только после того, как пользователь сделает свой ход. I использовать лицензионное программное обеспечение II инициировать проверку -c, c-l использовать нелицензионное программное обеспечение не инициировать проверку инициировать проверку -c, c -d-l, f-l II не инициировать проверку -d, 0 Рис. 5.3 – Дерево позиционной игры «Проверка легальности программного обеспечения» 39 Поскольку производитель в момент принятия решения не знает, в какой из двух точек зоны неопределенности он находится, данная конфликтная ситуация формализуется с помощью биматричной игры с матрицами выигрышей −𝑐 −𝑐 𝑐−𝑙 𝑐 (−𝑓 − 𝑑 −𝑑 ), ( ). 𝑓−𝑙 0 Строки соответствуют стратегиям первого игрока (пользователя):  использовать лицензионное программное обеспечение;  использовать нелицензионное программное обеспечение. Столбцы соответствуют стратегиям второго игрока (производителя):  инициировать проверку лицензий на использование пользователем программного обеспечения;  не инициировать такую проверку. Пусть 𝒑 = (𝑝; 1 − 𝑝), 𝒒 = (𝑞; 1 − 𝑞) – смешанные стратегии игроков: пользователь с вероятностью р приобретает лицензионное программное обеспечение [и с вероятностью (1 - р) — нелицензионное], производитель с вероятностью q инициирует проверку лицензий [и с вероятностью (1 - q) не инициирует]. Множество возможных исходов игры в зависимости от выбора игроками смешанных стратегий представлено на рис. 5.4. Максиминные выигрыши пользователя и производителя равны соответственно 𝛼 = 𝑚𝑎𝑥{−𝑐; −𝑑; −𝑓} = −𝑐, 𝛽 = 𝑚𝑎𝑥{𝑐 − 𝑙; 0} = 0. Множество Парето-оптимальных исходов — это ломаная ABC, а переговорное множество, отсекаемое от множества Парето максиминными выигрышами, — это выделенный жирным на рис. 5.4 отрезок 𝑐(𝜋1 + 𝑑) 𝐵𝐶 = {(𝜋1 ; 𝜋2 = − ) |𝜋1 ∈ [−𝑐; −𝑑]}. 𝑐−𝑑 Решение Нэша определяется максимумом функции Нэша: 𝑚𝑎𝑥 𝑁(𝜋1 ; 𝜋2 ) = 𝑚𝑎𝑥 ((𝜋1 − 𝛼)(𝜋2 − 𝛽)) = (𝜋1 ,𝜋2 )∈𝐵𝐶 𝑚𝑎𝑥 𝜋1 ∈[−𝑐;−𝑑] ((𝜋1 − (−𝑐)) (− (𝜋1 ,𝜋2 )∈𝐵𝐶 𝑐(𝜋1 + 𝑑) 𝑐(𝜋1 + 𝑑)(𝜋1 + 𝑐) 𝑐(𝑐 − 𝑑) − 0)) = 𝑚𝑎𝑥 (− )= , 𝜋1 ∈[−𝑐;−𝑑] 𝑐−𝑑 𝑐−𝑑 4 который достигается при 𝜋1 = − 𝑐+𝑑 2 , 𝑐 𝜋2 = 2, что соответствует смешанным стратегиям игроков 1 1 𝒑𝑁 = ( ; ), 𝒒𝑁 = (0; 1). 2 2 Итак, рациональный потребитель в половине случаев предпочтет использование нелицензионного программного обеспечения, а рациональному производителю никогда не выгодно инициировать проверку лицензий. Если считать функции полезности и пользователя, и производителя строго возрастающими, принципиальных изменений в конфликтной ситуации не произойдет. Таким образом, вне зависимости от склонности производителей и пользователей программного обеспечения к риску, рациональный пользователь только в половине случаев предпочтет приобрести лицензионное программное обеспечение, а рациональный производитель никогда не будет инициировать проверку легальности использования его продукта пользователями. 40 Так будет всегда, пока цена лицензии с будет больше цены пиратской копии d. В случае же, когда c = d, очевидно, пользователь предпочтет приобрести легальную копию, но при этом прибыль производителя существенно сократится (если не превратится в убытки). 𝜋2 𝑓 𝐴 𝑓−𝑙 𝐵 −𝑐 𝛽=0 𝑐 𝐶 −𝑑 −𝑑 − 𝑓 𝑑 𝜋1 −𝑐 𝐷 𝑐−𝑙 𝛼 = −𝑐 Рис. 5.4 – Множество возможных исходов игры «Проверка легальности программного обеспечения» Контрольные вопросы и задания 1. Как на практике организовать реализацию смешанных стратегий? 2. Каждый из двух игроков (первый и второй) могут показать «камень» (кулак), «ножницы» (указательный и средний пальцы) или «бумагу» (ладонь). Камень тупит ножницы (и поэтому камень выигрывает у ножниц 1 руб.), ножницы режут бумагу (и поэтому ножницы выигрывают у бумаги 1 руб.), а бумага заворачивает камень (и поэтому бумага выигрывает у камня 1 руб.). Все остальные случаи приводят к ничьей. Каковы оптимальные стратегии игроков? 3. Для матричных игр, заданных своими платежными матрицами, найдите нижнюю и верхнюю цену, и сравните выигрыш первого игрока при оптимальной стратегии и при максиминной стратегии: 1 3 −2 1 0 −1 0 2 3 4 5 0 3 2 −1 1 1 4). а) ( ); б) (−1 2 −1 1 0); в) ( 4 1 1 −3 3 1 2 −2 7 1 −2 −1 −2 0 1 −2 5 1 4. Докажите, что если первый игрок будет играть в соответствии со своей оптимальной смешанной стратегией, а второй игрок выберет свою j-ю чистую стратегию (при условии, что j-я компонента вектора оптимальной смешанной стратегии второго игрока 41 строго больше нуля), то математическое ожидание выигрыша первого игрока будет равным цене игры. 5. Производитель премиальных кондитерских изделий ежедневно изготавливает и продает от одного до трех эксклюзивных тортов. Срок годности торта ограничен: если торт не продан за один день, его приходится утилизировать (стоимость утилизации — 500 руб.). Если спрос на торты превышает их фактически произведенное количество, недостающие торты обязательно нужно произвести, но это придется делать в сверхурочное время. При нормальном производственном цикле себестоимость одного торта составляет 5000 руб., при сверхурочной работе — 7000 руб. Все торты реализуются по цене в 10 000 руб. Вероятности того, что дневной спрос составит 1, 2 и 3 торта, равны соответственно 0,4, 0,5 и 0,1. Составьте матрицу последствий и матрицу сожалений, определите решения по критериям Вальда, Сэвиджа, максимального ожидаемого дохода и минимальных ожидаемых сожалений. 6. Две фирмы продают конкурирующие товары. Каждая из фирм должна решить, имеет ли смысл устраивать рекламную компанию. Если обе фирмы решат рекламировать свои товары, то первая фирма получит чистую прибыль в размере 10 млн. руб., а вторая фирма — в размере 6 млн. руб. Если первая фирма будет рекламировать свой товар, а вторая не будет, то первая фирма получит прибыль 15 млн. руб., а прибыль второй фирмы окажется равной нулю. Если первая фирма не будет проводить рекламную компанию, а вторая - будет, то прибыль первой фирмы будет равна 5 млн. руб., а прибыль второй фирмы — 8 млн. руб. Если же обе фирмы откажутся от проведения рекламной компании, то первая фирма получит прибыль 10 млн. руб., а вторая — 2 млн. руб. Каковы оптимальные стратегии фирм? 7. Два производителя продают на рынке один товар. Каждый из них может назначить цену товара: 400 руб. или 600 руб. Если оба производителя назначили цену 400 руб., то каждый из них получает чистую прибыль 12 млн. руб. Если оба производителя назначили цену 600 руб., то каждый из них получает чистую прибыль 16 млн. руб. Если же один назначил цену 400 руб., а другой 600 руб., то тот производитель, который назначил меньшую цену, получает прибыль 20 млн. руб., а его конкурент получает прибыль 4 млн. руб. Как должны выбирать свои стратегии игроки в зависимости от того, разрешаются или запрещаются соглашения между ними? 8. Покупатель (второй игрок) приходит на рынок за яблоками. Продавец (первый игрок) использует пружинные весы и имеет две стратегии: честно взвесить 1 кг яблок или подкрутить пружину и обвесить покупателя на 200 г. У покупателя также две стратегии: поверить продавцу или взвесить покупку на контрольных весах и в случае обмана потребовать возмещения ущерба. Предложите свой вариант матриц выигрышей и определите наиболее рациональное поведение игроков. Рассмотрите как ситуацию, в которой покупатель не способен заметить, обвешивает ли его продавец, так и ситуацию, в которой покупатель видит, честно ли ведет себя продавец. 9. В настоящее время некоторый товар на рынке продается единственным монополистом (первым игроком) по цене 100 руб. Емкость рынка составляет 1 млн. единиц товара. На этот рынок с аналогичным товаром хочет войти другая фирма (второй игрок). Для входа в отрасль вторая фирма должна произвести инвестиции в строительство завода в размере 40 млн. руб. Если вторая фирма не будет входить на рынок, то первая фирма может продолжать продавать товар по 100 руб., и тогда ее выручка составит 100 млн. руб. (а прибыль второй фирмы будет нулевой). Если же вторая фирма войдет на рынок, и при этом цена товара останется на прежнем уровне (100 руб.), то каждая из двух фирм получит по 50 млн. руб. выручки, но выигрыш второй фирмы составит 10 млн. руб. (из выручки мы вычли инвестиции в строительство завода). Первая фирма может (для защиты от входа на рынок) понизить цену до 60 руб. Если в этом случае конкурент все-таки выйдет на рынок, то выручка каждой из фирм будет равна 30 млн. руб., при этом вторая фирма проиграет 10 млн. руб. (с учетом инвестиций в строительство завода). Если же первая фирма установит 42 низкую цену (60 руб.), а вторая фирма не войдет на рынок, то прибыль первой фирмы будет равна 60 млн. руб. Каковы оптимальные стратегии фирм? 10. Две фирмы выпустили ко Дню 8 марта новые конфеты. Каждая из двух фирм позиционирует свои конфеты как самый лучший подарок к женскому празднику, при этом фирмы имеют возможность рекламировать свои товары в дневных или в вечерних телепередачах. Если обе фирмы будут рекламировать свой товар как самый лучший одновременно — в дневной (или вечерней) телепередаче, то покупатели усмотрят в этом противоречие и не станут покупать ни один, ни другой сорт конфет (выигрыши обеих фирм при этом будут равны нулю, как и в том случае, когда фирмы вовсе не будут рекламировать свои товары). Если одна фирма выступит с рекламным объявлением днем (вечером), а другая фирма в это время выступать не будет, то первая фирма привлечет столько покупателей, что ее выигрыш можно будет оценить единицей (соответственно двумя единицами). Каковы оптимальные стратегии игроков? 11. Докажите, что бесшумная дуэль не имеет седловой точки в чистых стратегиях. 12. Хорошенькая девушка Маша может прийти на дискотеку (которая продолжается четыре часа) в момент времени t∈[0,4]. Каждый из двух ее воздыхателей — Коля и Миша — приходит на дискотеку только один раз в этот вечер. Если в момент прихода одного из игроков Маша находится на дискотеке одна, то она весь вечер танцует с этим игроком (и этот игрок выигрывает у своего противника единицу). Если же в момент прихода кого-либо из воздыхателей Маши на дискотеке нет, или она уже танцует с «конкурентом», поклонник уходит и больше в этот вечер на дискотеку не возвращается. Если ни один из игроков не танцевал с Машей, то выигрыш каждого из них равен нулю. Каковы оптимальные стратегии игроков? 13. Правила игры таковы. Имеется круглый стол и бесконечно много одинаковых круглых монет. Первый и второй игроки по очереди кладут на стол по одной монете (монета должна целиком лежать на столе и не накладываться на другие монеты). Выигрывает тот, кто положит на стол последнюю монету. Каковы оптимальные стратегии игроков? 14. На аукцион выставляется 1000 руб. Два участника игры по очереди называют сумму, которую они готовы отдать за получение 1000 руб. в обмен на предложенную цену. Предложивший наибольшую заявку получает 1000 руб. в обмен на предложенную цену, а сделавший вторую по величине заявку должен отдать предложенную им сумму и не получить взамен ничего. Каковы оптимальные стратегии игроков? 15. Ведущий телешоу предлагает участнику показать на одну из трех закрытых дверей, за которыми находятся «Мерседес» и два козла. После этого ведущий открывает одну из невыбранных дверей, за которой находится козел, и вторично предлагает участнику открыть одну из оставшихся дверей. Если за этой дверью окажется «Мерседес», то он достается участнику в качестве приза, а если за дверью стоит козел, то участник ничего не получает. Каковы оптимальные стратегии ведущего и участника телешоу? 16. Игра продолжается N периодов. Первый игрок (нарушитель) хочет совершить в одном и этих периодов некоторое запрещенное действие, а второй игрок (инспектор), который желает это действие предотвратить, может провести в одном из N периодов проверку нарушителя. Выигрыш нарушителя в каждом периоде равен 1, если он провел запрещенное действие, а инспектор в этом периоде проверку не проводил, выигрыш равен -1, если инспектор поймал нарушителя, выигрыш равен нулю, если нарушитель не действует вовсе. Каковы оптимальные стратегии игроков? 17. Убедитесь в том, что в игре «Работодатель — работник» (Работник имеет возможность установить интенсивность своей работы от 100% (полезность этой ситуации для работника оценивается нулем, а для работодателя прибылью 1 млн. руб.) до 0% (в этом случае работник будет голодать, и полезность этой ситуации для работника оценивается в -500 000 руб., а работодатель получит нулевую прибыль). Работодатель может поделиться с работником частью прибыли (если захочет). Минимаксные выигрыши игроков равны нулю, а решение Нэша состоит в том, что работодатель и работник делят прибыль поровну — по 43 500 тыс. руб.), решение Нэша соответствует точке, в которой работодатель и работник делят прибыль поровну — по 500 тыс. руб. 44