Основные понятия теории игр. Игры с природой. Биматричные игры

1 Юсов Анатолий Борисович Курс лекций по дисциплине Теория игр. Оглавление Лекция 1. Основные понятия теории игр. ............................................................ 2 Лекция 2. Чистые стратегии в матричных играх. .............................................. 23 Лекция 3. Смешанные стратегии в матричной игре. ......................................... 35 Лекция 4. Смешанные стратегии в матричных играх (решение матричных игр mxn)......................................................................................................................... 56 Лекция 5. Игры с природой. ................................................................................. 72 Лекция 6. Биматричные игры............................................................................... 85 Лекция 7. Позиционные игры. ............................................................................. 97 Лекция 8. Кооперативные игры. ........................................................................ 114 Разбиение матрицы на подматрицы .................................................................. 129 2 Лекция 1. Основные понятия теории игр. Теория игр – это математическая дисциплина, разрабатывающая теоретические основы построения математических моделей принятия оптимальных решений в конфликтных ситуациях, носящих характер конкурентной борьбы, в том числе и в условиях неопределенности. Использование теории игр помогает лицу, принимающему решение, произвести критический анализ ситуации и в результате более обоснованно и последовательно проводить стратегию поведения при решении сложных проблем. Это означает, что с помощью теории игр можно: • смоделировать процесс и возможные результаты будущей игры еще до ее фактического начала; • по результатам моделирования будущей игры принять решение о целесообразности участия и оптимальном поведении в реальном конфликте. Возникновение теории игр приписывают выдающемуся американскому математику XX в. Джону фон Нейману. Считается, что он пришел к идеям этой теории, наблюдая за игрой в покер. Отсюда и произошло название «теория игр». После того, как теория игр в 1940 г. была применена Джоном фон Нейманом и О. Моргенштерном к теоретическому исследованию экономики, она получила широкое распространение и повсеместное признание. В настоящее время теоретико-игровые модели используются в различных областях экономики и других наук, в частности: • для выбора эффективных стратегий в бизнесе и оптимального поведения фирмы, • для рационального управления финансами, в теории инвестирования. Кроме того, теория игр используется : • в оценке эффективности проектов, 3 • в страховании, • в управлении городским транспортом, • в области рынка жилья, • в теории инноваций, • в анализе и управлении эколого-экономическими системами, • и др. Математическая модель конфликтной ситуации называется игрой, а стороны, участвующие в конфликте, — игроками. Исход конфликта называется выигрышем. Для построения модели конфликтной ситуации фиксируются правила, определяющие: 1) варианты действий противников; 2) объем информации каждого игрока о поведении партнеров; 3) выигрыш, к которому приводит каждая совокупность действий. Выигрыш (или проигрыш) должен быть задан количественно (либо в объективных единицах, либо в условных значениях), с помощью выигрышфункции. Выигрыш функция может задаваться таблично или в аналитической форме (формула или выражение). После задания выигрыш функции для каждой конкретной ситуации, возникшей после применения правил поведения игроков, рассчитываются конкретные значения выигрышей. Рассчитанные выигрыши игроков в подавляющем числе игровых ситуаций заносятся в матрицу, в которой прописываются выигрыши по каждой из стратегий игроков. 4 В1 В2 ... Вn A1 x11 x12 ... x1n A2 x21 x22 ... x2n ... ... ... ... ... Am xm1 xm2 ... xmn Названия строк – это обозначение стратегий игрока А, m – число стратегий игрока А. Названия столбцов – это обозначение стратегий игрока В, n – число стратегий игрока В. Числа xij – выигрыш игрока в ситуации одновременных действий игроков под номером Аi и Bj. В зависимости от конфликтной ситуации таких матриц может быть либо одна, либо по числу участников. Выбор и осуществление одного из предусмотренных правилами действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход — это сознательный выбор игроком одного из возможных действий. Случайный ход — это случайно (с некоторой вероятностью) произошедшее действие. Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом ходе в зависимости от сложившейся ситуации. Стратегия может быть чистой – если игрок сознательно выбирает в качестве хода какое-либо из предусмотренных правилами действий. Стратегия может быть смешанной – если игрок комбинирует свои предусмотренные правилами действия. 5 Теория игр позволяет рассчитать возможные ходы заранее (в ответ на любую сложившуюся ситуацию). Различий в разных игровых ситуациях довольно много, поэтому классифицировать игровые ситуации можно по следующим критериям. 1. С полной информацией и с не полной информацией. Критерием деления является вид неопределенности, с которой сталкиваются игроки. В играх с полной информацией каждому игроку на каждом шаге известно, какие ходы игроки делали ранее. В играх с не полной информацией игрокам неизвестны предыдущие ходы игроков. 2. Конечные и бесконечные игры. Критерием выбора является ограниченность числа стратегий игроков. Конечная игра – это игра, в которой у каждого игрока имеется конечное число стратегий. В Бесконечной игре число стратегий не ограничено, то есть каждая новая ситуация позволяет выбрать новые стратегии. 3. Коалиционные (кооперативные) и бескоалиционные (некооперативные) игры Критерием является возможность действовать сообща некоторым игрокам. Коалиционные – игры, где возможен обмен информацией о возможных стратегиях игроков, субъектом принятия решения служит группа или коалиция, между игроками одной коалиции имеются обязывающие соглашения. Бескоалиционные – игры, где игроки принимают решения независимо друг от друга, поскольку наложен запрет на образование коалиций. 4. Парные и множественные игры Критерием выбора является число игроков. 6 Парная - участвуют два игрока. (Наиболее развитые научные наработки). Множественная - число игроков больше двух. 5. Антагонистические и неантагонистические игры. Критерием деления является взаимоотношение интересов игроков. Антагонистические игры – интересы игроков противоположны. Выигрыш одного является проигрышем второго (ИГРЫ С НУЛЕВОЙ МАТРИЦЕЙ). В неантагонистических играх выигрыш одного не означает проигрыш другого, то есть у них выигрыши вычисляются независимо, либо интересы могут совпадать, либо один из игроков может просто не иметь никаких целей (быть нейтральным) (БИМАТРИЧНЫЕ ИГРЫ). 6. Стохастические1 и нестохастические игры. Критерием деления является вид неопределенности, с которой сталкиваются игроки. В стохастических играх известны или могут быть, по крайней мере, оценены законы распределения или хотя бы числовые характеристики случайных факторов, влияющих на игровую ситуацию. В нестохастических нет никаких данных о неизвестных параметрах, влияющих на успех решения игры. В этом случае для определения параметров игровой ситуации привлекаются эксперты. На рисунке 1.1 приведена фасетно-иерархическая схема классификации игр, претендующая на полный список. Каждая игра может быть охарактеризована одним из значений 6 характеристик. Однако не все значения могут сочетаться. В данном пособии будут рассмотрены игры с полной и не полной информацией, конечные, бескоалиционные, парные, антагонистические 1 Стохастический – случайный. 7 (с нулевой матрицей) и неантагонистические, стохастические и не стохастические игры. Рисунок 1.1. Фасетно-иерархическая схема классификации игр. В этом пособии будут рассмотрены следующие игры. - Игры с нулевой матрицей (антагонистические конечные бескоалиционные парные стохастические/не стохастические игры с полной информацией). К подобным играм относятся: 1. Парные антагонистические игры. 2. Игры с природой. - Биматричные игры (неантагонистические конечные бескоалиционные парные стохастические игры с полной информацией). - Коалиционные игры (антагонистические конечные коалиционные множественные не стохастические игры с полной информацией). 8 - Позиционные игры (антагонистические конечные бескоалиционные парные не стохастические игры с полной и не полной информацией). Алгоритм формализации игровой ситуации: 1. Расписать все возможные действия каждого игрока. 2. Составить выигрыш-функцию каждого игрока (если она представима в аналитическом виде). 3. Вычислить выигрыши каждого игрока в зависимости от одновременных действий игрока и его оппонента. 4. Заполнить игровые матрицы. В качестве примера формализации игры рассмотрим ситуацию с уплатой налога бизнесом. Противоборствующие стороны: бизнес и государство в лице налогового ведомства. Бизнес может честно указать свой доход и заплатить полностью весь налог. Однако иногда, чтобы увеличить свой доход, бизнес либо скрывает свои доходы, чтобы уйти от уплаты налогов, либо занижает доходы и платит налог в меньшей сумме. Государство в лице налоговой инспекции, чтобы повысить собираемость налогов, может проконтролировать доход и взыскать с бизнеса положенный налог, если доход указан верно, либо налог и штраф, если бизнес скрыл или занизил налог. А также, чтобы уменьшить затраты на обеспечение деятельности инспекции не проводить контроль доходов и получить либо весь налог, либо заниженный налог, либо ничего. Данная ситуация представляет собой антагонистическую парную игру – игру с нулевой матрицей, поскольку выигрыш государства – это сумма отданная бизнесом (его проигрыш). Пункт 1 алгоритма формализации игровой ситуации заключается в расписывании всех возможных действия каждого игрока. Бизнес в этой ситуации может: 1. Скрыть свой доход и уйти от уплаты налогов. 9 2. Занизить свой доход и заплатить налогов меньше. 3. Честно указать свой доход и заплатить полностью весь налог. Налоговая инспекция может: 1. Проконтролировать доход и взыскать с бизнеса положенный налог, если доход указан верно, либо налог и штраф, если бизнес скрыл или занизил налог. 2. Не контролировать доход и получить либо весь налог, либо заниженный налог, либо ничего. Пункт 2 алгоритма формализации игровой ситуации заключается в составлении выигрыш-функции каждого игрока. В данном случае выигрыш функции игроков не описываются аналитическим выражением. Пункт 3 и 4 алгоритма формализации игровой ситуации совмещаем. Вычисляем выигрыши каждого игрока в зависимости от одновременных их действий. Поскольку у нас игра с нулевой матрицей, то достаточно вычислить выигрыши только игрока А. За игрока А примем бизнес. Если бизнес скроет свой доход, а государство его контролировать не будет, то бизнес заплатит в качестве налога нулевую сумму. Если бизнес скроет свой доход, а государство его проконтролирует, то бизнес заплатит весь налог и еще штраф. Если бизнес занизит свой доход, а государство его контролировать не будет, то бизнес заплатит в качестве налога заниженную сумму. Если бизнес занизит свой доход, а государство его проконтролирует, то бизнес доплатит до полного налога и заплатит штраф. Если бизнес честно укажет свой доход, а государство его государство его контролировать не будет, то бизнес заплатит только налог. Если бизнес честно укажет свой доход, проконтролирует, то бизнес заплатит только налог. а 10 Пункт 4 заключается в заполнении вычисленными суммам игровой матрицы. В результате получаем следующую игровую матрицу: Стратегии бизнеса Скрыть доход Занизить доход Честно указать доход Стратегии государства Контролировать Не контролировать -(налог+штраф) -(налог+штраф) -(заниженный налог) -(налог) -(налог) Поскольку игрок А (выигрыши располагается по строкам таблицы) в примере бизнес, все значения в матрице приведены со знаком минус. Это говорит о том, что бизнес отдает, а государство получает. В антагонистической игре с нулевой матрицей выигрыш-функции игроков связаны следующим соотношением: хjiА = FA (Aj ,Bi )=-FB (Bi ,Aj )=- хijВ а игровые матрицы соотносятся: B=-AT. (Символ Т обозначает транспонированную матрицу). Где хjiА и хijВ обозначают выигрыши соответственно игрока А при одновременном использовании им стратегии j и стратегии i игроком В и выигрыш игрока В при одновременном использовании им стратегии i и стратегии j игроком А. FA (Aj ,Bi ) и FB (Bi ,Aj ) соответственно выигрыш функции игроков А и В. Если бы игроком А было государство, то матрица выглядела бы так: Стратегии бизнеса Скрыть Занизить Честно указать доход доход доход Контролировать налог+штраф налог+штраф налог Стратегии Не заниженный налог государства контролировать налог В качестве другого примера формализации игры рассмотрим ситуацию конкурентной борьбы двух фирм. 11 Фирма В пытается вытеснить фирму А с рынка, чтобы стать на нём монополистом. Для этого она производит аналогичный товар, который поступает на рынок в один из моментов j = 1,2, …,n. Единственным законным средством фирмы В в конкурентной борьбе является выбор момента поставки товара на рынок, так как понижение цены на поставляемый товар запрещено действующими между ними соглашениями. Для вытеснения с рынка фирмы А фирма В должна минимизировать ее доходы. Технология выпуска товара такова, что чем дольше он находится в производстве и, следовательно, позже поступает на рынок, тем выше его качество (в результате, например, применения более совершенных методов производства, использования новых технологий, современного оборудования, более эффективных форм организации труда и т.п.), а реализуется товар только более высокого качества (так как цена на товары разного качества одна и та же). Таким образом, фирма А может получить прибыль: - в случае более раннего выпуска своего товара только с начала срока выпуска своего товара и до начала выхода товара фирмы В; - в случае более позднего выпуска своего товара только с момента выхода своего товара и до конца срока; - в случае одновременного выхода товара фирм А и В они делят прибыль за весь период выхода товара пополам. Пункт 1 алгоритма формализации игровой ситуации заключается в расписывании всех возможных действия каждого игрока. Фирма А может выпустить товар на рынок в любой из моментов времени (день, неделя, декада, месяц, квартал, год и пр.). Фирма B может выпустить товар на рынок в любой из таких же моментов времени (день, неделя, декада, месяц, квартал, год и пр.). 12 Пункт 2 алгоритма формализации игровой ситуации заключается в составлении выигрыш-функции каждого игрока. Поскольку у нас игра с нулевой матрицей, то достаточно составить выигрыш-функцию только игрока А. Пусть: i – период времени выхода на рынок товара фирмы А. j – период времени выхода на рынок товара фирмы В n – всего периодов времени. Тогда выигрыш- функция игрока А : i=j, (n-i+1)/2*доход за один период времени А= ij (j-i)*доход за один период времени (n-i+1)*доход за один период времени Пункт 3 алгоритма формализации игровой ситуации заключается в вычислении выигрышей каждого игрока в зависимости от одновременных действий игрока и его оппонента. Для вычисления выигрыша фирмы А примем за один период времени квартал. Всего кварталов в году 4, поэтому n=4, доход в квартал обозначим символом с. Этап 3 объединим с этапом 4 и запишем выигрыши прямо в матрицу. Пункт 4 заключается в заполнении вычисленными суммам игровой матрицы. Ниже записана полученная игровая матрица, являющаяся формализацией нашей конкурентной борьбы фирм А и В. Желтым цветом обозначены периоды, когда на рынок раньше вышла фирма А, зеленым – фирма В, а белым, когда они вышли на рынок одновременно: В(j) В1 В2 В3 В4 A1 2с с 2с 3с A2 3с 1,5с с 2с A3 2с 2с с с A4 c c c 0,5c А(i) 13 Пример. (Игра с природой). Организация предоставляет услуги работы на ПК. Угроза заражения ПК вредоносными программами требует периодической проверки на наличие вирусов, что требует приостанавливать обработку информации на ПК, что приводит к определённым экономическим издержкам. Если же вирус не будет вовремя обнаружен, возможна потеря и некоторой части информации, что приведёт к ещё большим убыткам. Стоимость полной проверки 7000 руб, при этом она занимает 3 часа, ликвидирует вирусы и восстанавливает все файлы. Стоимость минимальной проверки 2000 руб, при этом она занимает 1 час, ликвидирует вирусы, но не восстанавливает все файлы. В день ЭВМ работает 12 часов, 1 час работы приносит доход 8000 руб. Кроме того, в случае заражения вирусом носителей потребителя организация платит штраф 10000 р., а в случае отказа работы – 15000 р. Формализация ситуации. 1. Расписать все возможные действия каждого игрока. - Организация может: 1. Не проверять ПК на наличие вирусов. 2. Делать минимальную проверку на вирусы. 3. Делать полную проверку на вирусы. - Состояние среды: 1. ПК не заражены. 2. ПК заражены, но файлы не запорчены. 3. ПК заражены и файлы запорчены. 2. Составить выигрыш-функцию каждого игрока (если она представима в аналитическом виде). Выигрыш-функция аналитического вида не имеет. 14 3. Вычислить выигрыши каждого игрока в зависимости от одновременных действий игрока и его оппонента. А1-В1. Организация не проверяет ПК на наличие вирусов, ПК не заражены. Доход организации: 12*8000=96000 руб. А1-В2. Организация не проверяет ПК на наличие вирусов, ПК заражены, но файлы не запорчены. Доход организации: 12*8000-10000=86000 руб. А1-В3. Организация не проверяет ПК на наличие вирусов, ПК заражены и файлы запорчены. Доход организации: (12-3)*8000-15000-7000=72000-22000=50000 руб. А2-В1. Организация делает минимальную проверку, ПК не заражены. Доход организации: (12-1)*8000-2000=86000 руб. А2-В2. Организация делает минимальную проверку, ПК заражены, но файлы не запорчены. Доход организации: (12-1)*8000-2000=86000 руб. А2-В3. Организация делает минимальную проверку, ПК заражены и файлы запорчены. Доход организации: (12-1-3)*8000-2000-7000-15000=64000-24000=40000 руб. А3-В1. Организация делает полную проверку, ПК не заражены. Доход организации: (12-3)*8000-7000=65000 руб. А3-В2. Организация делает полную проверку, ПК заражены, но файлы не запорчены. Доход организации: (12-3)*8000-7000=65000 руб. А3-В3. Организация делает полную проверку, ПК заражены и файлы запорчены. Доход организации: (12-3)*8000-7000=65000 руб. 15 4. Заполнить игровые матрицы. В В1 В2 В3 A1 96000 86000 50000 A2 86000 86000 40000 A3 65000 65000 65000 А Замечание: если известны вероятностные оценки состояний природы, то игра является стохастической; если не известны вероятностные оценки состояний природы, то игра является не стохастической. Пример. (Игра с природой). Фермер планирует посевную , имея четыре альтернативы: A1 - выращивать кукурузу, А2– пшеницу, А3– овощи, А4– использовать землю под пастбища. Платежи, связанные с этими возможностями, зависят от количества осадков, которые условно можно разделить на четыре категории: В1- сильные осадки , в этом случае при выращивании кукурузы он потерпит убытки в размере 10 млн. руб., при выращивании пшеницы прибыль – 50 млн. руб., овощи – убытки – 40 млн. руб., под пастбища – прибыль 30 млн. руб. В2 - умеренные, в этом случае при выращивании кукурузы он получит прибыль 80 млн. руб., при выращивании пшеницы прибыль – 90 млн. руб., овощи – прибыль – 150 млн. руб., под пастбища – прибыль 45 млн. руб. 16 В3– незначительные, в этом случае при выращивании кукурузы он получает прибыль 40 млн. руб., при выращивании пшеницы прибыль – 30 млн. руб., овощи – прибыль – 60 млн. руб., под пастбища – прибыль 25 млн. руб. В4 – засушливый сезон, в этом случае при выращивании кукурузы он потерпит убытки в размере 20 млн. руб., при выращивании пшеницы ни прибыли, ни убытков он не получит, овощи – убытки – 20 млн. руб., под пастбища – прибыль 10 млн. руб. 1. Расписать все возможные действия каждого игрока. - Фермер может: A1 - выращивать кукурузу, А2– пшеницу, А3– овощи, А4– использовать землю под пастбища. - Состояние среды: В1- сильные осадки , В2 - умеренные осадки, В3– незначительные осадки, В4 – засушливый сезон. 2. Составить выигрыш-функцию каждого игрока (если она представима в аналитическом виде). Выигрыш-функция аналитического вида не имеет. 3. Вычислить выигрыши каждого игрока в зависимости от одновременных действий игрока и его оппонента. А1-В1. Фермер выращивает кукурузу при сильных осадках. Доход : -10 млн руб. А1-В2. Фермер выращивает кукурузу при умеренных осадках. Доход : +80 млн руб. А1-В3. Фермер выращивает кукурузу при незначительных осадках. 17 Доход : +40 млн руб. А1-В4. Фермер выращивает кукурузу в засушливый сезон. Доход : -20 млн руб. А2-В1. Фермер выращивает пшеницу при сильных осадках. Доход : +50 млн руб. А2-В2. Фермер выращивает пшеницу при умеренных осадках. Доход : +90 млн руб. А2-В3. Фермер выращивает пшеницу при незначительных осадках. Доход : +30 млн руб. А2-В4. Фермер выращивает пшеницу в засушливый сезон. Доход : 0 млн руб. А3-В1. Фермер выращивает овощи при сильных осадках. Доход : -40 млн руб. А3-В2. Фермер выращивает овощи при умеренных осадках. Доход : +150 млн руб. А3-В3. Фермер выращивает овощи при незначительных осадках. Доход : +60 млн руб. А3-В4. Фермер выращивает овощи в засушливый сезон. Доход : -20 млн руб. А4-В1. Фермер использует землю под пастбища при сильных осадках. Доход : +30 млн руб. А4-В2. Фермер использует землю под пастбища при умеренных осадках. Доход : +45 млн руб. А4-В3. Фермер использует землю под пастбища при незначительных осадках. Доход : +25 млн руб. А4-В4. Фермер использует землю под пастбища в засушливый сезон. Доход : +10 млн руб. 18 4. Заполнить игровые матрицы. В В1 В2 В3 В4 A1 -10 80 40 -20 A2 50 90 30 A3 -40 150 60 -20 А4 30 45 25 10 А Пример. (Биматричная игра). Две страховые компании оказывают в одном населенном пункте одинаковые страховые услуги. Каждая из них для повышения прибыли может установить один из следующих страховых тарифов: 1000 руб – низкий тариф, 2000 руб – средний тариф, 4000 руб – высокий тариф. Потребители страховых услуг разделены на бедное, среднее и богатое население. Богатые выбирают самые высокие тарифы, считая, что там выше качество и всегда страхуется. Население со средним достатком обычно выбирает пониженный тариф, но в случае наличия только повышенного тарифа отказывается от страхования. Бедное населения страхуется только по низкому тарифу, а в случае его отсутствия отказывается от страхования. Доход страховой компании вычисляется как произведение числа застрахованных на тариф. Если тарифы у компаний одинаковые, то население страхуется у них в равных количествах. Распределение количества населения по группам приведены в таблице. Население тыс. чел. Бедные 9000 Среднего достатка 10000 Богатые 1000 19 1. Расписать все возможные действия каждого игрока. - Страховая компания №1 может установить: A1 - высокий тариф, А2– средний тариф, А3– низкий тариф. - Страховая компания №2 может установить: В1 - высокий тариф, В2– средний тариф, В3– низкий тариф. 2. Составить выигрыш-функцию каждого игрока (если она представима в аналитическом виде). Тарифы совп. Число застрахованных*тариф/2 Доход = Тарифы не совп. Число застрахованных*тариф 3. Вычислить выигрыши каждого игрока в зависимости от одновременных действий игрока и его оппонента. А1-В1. 1 компания - тариф высокий, 2 компания – тариф высокий. Доход 1 компании: 1000*4000/2=2 000 000 руб. Доход 2 компании: 1000*4000/2=2 000 000 руб. А1-В2. 1 компания - тариф высокий, 2 компания – тариф средний. Доход 1 компании: 1000*4000=4 000 000 руб. Доход 2 компании: 10000*2000=20 000 000 руб. А1-В3. 1 компания - тариф высокий, 2 компания – тариф низкий. Доход 1 компании: 1000*4000=4 000 000 руб. Доход 2 компании: (10000+9000)*1000=19 000 000 руб. А2-В1. 1 компания - тариф средний, 2 компания – тариф высокий. Доход 1 компании: 10000*2000=20 000 000 руб. Доход 2 компании: 1000*4000=4 000 000 руб. 20 А2-В2. 1 компания - тариф средний, 2 компания – тариф средний. Доход 1 компании: (1000+9000)*2000/2=1 000 000 руб. Доход 2 компании: (1000+9000)*2000/2=1 000 000 руб. А2-В3. 1 компания - тариф средний, 2 компания – тариф низкий. Доход 1 компании: 1000*2000=2 000 000 руб. Доход 2 компании: (10000+9000)*1000=19 000 000 руб. А3-В1. 1 компания - тариф низкий, 2 компания – тариф высокий. Доход 1 компании: (10000+9000)*1000=19 000 000 руб. Доход 2 компании: 1000*4000=4 000 000 руб. А3-В2. 1 компания - тариф низкий, 2 компания – тариф средний. Доход 1 компании: (1000+9000)*1000=19 000 000 руб. Доход 2 компании: 1000*2000=1 000 000 руб. А3-В3. 1 компания - тариф низкий, 2 компания – тариф низкий. Доход 1 компании: (1000+9000+10000)*1000/2=10 000 000 руб. Доход 2 компании: (1000+9000+10000)*1000/2=10 000 000 руб 4. Заполнить игровые матрицы Страховая компания №1 Страховая компания №1 (млн руб) В В1 В2 В3 А В В1 В2 В3 А A1 2 4 4 A1 2 20 19 A2 20 1 1 A2 4 1 19 A3 19 19 10 A3 4 1 10 Для того чтобы найти решение игры, для каждого игрока необходимо выбрать такую стратегию, чтобы каждый из игроков должен был получить максимальный выигрыш в самой для себя неблагоприятной ситуации. 21 Такие стратегии называются оптимальными. Основой определения оптимальной стратегии является ситуация равновесия. Ситуация выбора стратегий игроками называется ситуацией равновесия по Нэшу, если при замене в данной ситуации какой-либо стратегии на произвольную, игрок может ухудшить свой выигрыш, при условии сохранении другими игроками своих оптимальных стратегий. Оптимальные стратегии удовлетворяют условию устойчивости: каждому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре, поскольку результат может существенно ухудшиться. Поэтому эти стратегии определяют точку равновесия. Решить игру – это найти все оптимальные стратегии игроков и вычислить получаемый при этом выигрыш (общее решение игры), либо какие-либо оптимальные стратегии игроков и вычислить получаемый при этом выигрыш (частное решение игры). Литература. 1. Исследование операций в экономике: учеб. Пособие /Н.Ш.Кремер, Б.А.Путко, И.М. Тришин, М. Н. Фридман; под ред. проф. Н. Ш. Кремера. – 2-е Изд., перераб. и доп.- М. : Издательство Юрайт: ИД Юрайт, 2010. - 430 с. (Глава 12) – есть в библиотеке. 2. Кремер Н.Ш., Путко Б.А., Тришин И.М. Математика для экономистов: от Арифметики до Эконометрики: учеб-справоч. пособие / под ред. проф. Н. Ш. Кремера. – 2-е изд., перераб. и доп. – М.: Издательство Юрайт: ИД Юрайт, 2010. – 646 с. (Параграфы 10.1 и 10.2) – есть в библиотеке. 3. Колобашкина Л. В. Основы теории игр : учебное пособие/Л. В. Колобашкина. — 3-е изд., испр. и доп. —М. : БИНОМ. Лаборатория знаний, 2016.— 195 с. 22 4. Лабскер Л.Г. Теория игр в экономике (практикум с решения задач) : учебное пособие / Л.Г. Лабскер, Н.А. Ященко ; под ред. Л.Г. Лабскера. – 2-е изд., стер. – М. : КНОРУС, 2013. – 264 с. 23 Лекция 2. Чистые стратегии в матричных играх. Для того чтобы найти решение подобной игры, для каждого из двух игроков необходимо выбрать стратегию, которая удовлетворяет условиям: 1. Один из игроков должен получать максимальный выигрыш, когда второй придерживается своей лучшей стратегии. 2. Второй игрок должен иметь минимальный проигрыш, если первый придерживается своей лучшей стратегии. Такие стратегии называются оптимальными. Оптимальные стратегии должны удовлетворять условию устойчивости: каждому из игроков должно быть невыгодно отказаться от своей оптимальной стратегии в этой игре, то есть если он откажется, то он или выиграет меньше, или проиграет больше. Как было указано ранее стратегия может быть чистой – если игрок выбирает одно какое-либо действие (Аi,Bj), либо стратегия может быть смешанной – если игрок комбинирует свои действия каким-либо образом. Чистые стратегии имеют меньшую степень неопределенности, смешанные – большую. Поэтому решения игры, прежде всего, находят в чистых стратегиях. Решить игру – это найти все оптимальные стратегии игроков и вычислить получаемый при этом выигрыш. Введем некоторые параметры эффективности деятельности игроков. Показателем эффективности чистой стратегии Аi считается минимальный выигрыш при этой стратегии (т.е. минимальный элемент i-той строки платежной матрицы): a i  min x ij j Максимином игры в чистых стратегиях, называется наибольший из показателей эффективности стратегий Ai (i = 1, 2,…m): 24 a  max min xij j i Максимин – это нижняя цена игры. Смысл нижней цены игры - игрок А выиграет не меньше этой суммы при любых, даже не благоприятных, обстоятельствах. Стратегия Ak, показатель эффективности которой совпадает с максимином называется максиминной стратегией игрока А. Максиминная стратегия – это наименьший гарантированный выигрыш игрока А. Если он придерживается максиминного принципа выбора стратегий, то ему при любых действиях противника гарантирован выигрыш в чистых стратегиях, не меньший максимина. Показателем неэффективности чистой стратегии Bj считается максимальный проигрыш игрока при этой стратегии (т.е. максимальный элемент j-го столбца матрицы А): в j max x ij i Минимаксом в чистых стратегиях называется наименьший из показателей неэффективности стратегий Bj, (j= 1, 2,…n): b  min max xij j i Минимакс - это верхняя цена игры. Смысл верхней цены игры - игрок В проиграет не больше этой суммы при любых, даже не благоприятных, обстоятельствах. Стратегия Bk, показатель неэффективности которой, совпадает с минимаксом называется минимаксной стратегией игрока В. Минимаксная стратегия – это наибольший проигрыш игрока В в самых неблагоприятных для него условиях. Если он придерживается минимаксного принципа выбора стратегий, то при любой игре противника А он не может проиграть больше этой величины. 25 Таким образом, нижняя цена игры – это минимальный выигрыш игрока А и минимальный проигрыш игрока B, если игроки будут придерживаться своих максиминной и минимаксной стратегий соответственно. Верхняя цена игры – это максимальный выигрыш игрока А и максимальный проигрыш игрока B, если игроки будут придерживаться своих максиминной и минимаксной стратегий соответственно. Рассмотрим ситуацию выбора стратегий Ак и Bl соответственно игроками А и В. Эта ситуация (Ак , Bl), считается удовлетворительной для игрока А, если для хil (для любого другого значения в строке платежной матрицы под номером l) выполняется неравенство: хilхkl, то есть игрок А получает максимальный выигрыш в рамках выбранной стратегии. Это число является максимальным в строке. Эта же ситуация (Ак , Bl), считается удовлетворительной для игрока В, если для хkj выполняется неравенство: хkjхkl, то есть игрок B проигрывает минимальную сумму в рамках выбранной стратегии. Это число является минимальным в столбце. Теорема 1. Ситуация (Ак , Вl) будет удовлетворительной для игрока А тогда, и только тогда, когда его выигрыш хкl совпадает с показателем неэффективности стратегии Bl игрока В: x kl  max x il =bl i (максимум в l столбце игровой матрицы). Для доказательства теоремы нам надо доказать два утверждения: 1. Если ситуация (Ак , Вl) приемлема для игрока А, то его выигрыш хкl совпадает с показателем неэффективности стратегии Bl игрока В. 26 2. Если выигрыш игрока А в ситуации (Ак , Вl) хкl совпадает с показателем неэффективности стратегии Bl игрока В, то ситуация приемлема для игрока А. Доказательство. 1. Запишем определение приемлемой ситуации (Ак , Вl) для игрока А:  xil (i=1,2,…,m) xil ≤ xkl . Это означает, что xkl максимум в столбце, а это, в свою очередь, означает, что xkl является показателем неэффективности стратегии Bl игрока В. В1 … Вl … A1 x11 … x1l … … … … … … Ak xk1 … xkl … … … … … … 2. Если xkl является показателем неэффективности стратегии Bl игрока В, то: xkl = max xil для любого i. Это означает, что  xil i (i=1,2,…,m) xil ≤ xkl . А это является определением удовлетворительной ситуации (Ак , Вl) для игрока А . Теорема доказана. Теорема 2. Ситуация (Ak , Bl) будет удовлетворительной для игрока В тогда, и только тогда, когда его проигрыш хкl совпадает с показателем эффективности стратегии Ак игрока А: x kl  min x kj =ak j (минимум в к строке игровой матрицы). Теорема 2 доказывается аналогично доказательству Теореме 1. 27 Следствие из указанных теорем: существуют такие стратегии, которые удовлетворяют обоим игрокам – являются ситуацией равновесия (консенсус). Эти две теоремы связывают оптимальные стратегии игроков с максиминными стратегиями игрока А и минимаксными стратегиями игрока В: для поиска приемлемых ситуаций необходимо игроками находить свои максиминные и минимаксные стратегии. Ситуация (Ак,Вl) является равновесной (ситуацией равновесия, устойчивой), или седловой точкой выигрыш-функции игрока А, если она удовлетворительна для каждого из игроков А и В, т.е.: xil ≤ xkl ≤ xkj, где i = 1, 2,…,m, j = 1, 2,…,n. Выигрыш xkl соответствующий ситуации равновесия (Ак,Вl ), называется седловой точкой матрицы игры. Игра, матрица которой содержит хотя бы один такой элемент, называется игрой с седловой точкой. Седловая точка – это и есть ситуация равновесия (консенсус). Седловая точка является минимальным значением в k-й строке и максимальным в l-м столбце (основа для выработки алгоритма поиска консенсуса). Теорема 3. (Свойство равнозначности седловых точек.). Если аik, и аjl (i, j {1, 2,…,m}); k,l  {1, 2,…,n}) — седловые точки, то аik, = аjl .( Все седловые точки равны между собой). Доказательство. Из определения седловой точки имеем xik ≤ atk ≤ xtj, xil ≤ asl ≤ xsj, Рассмотрим в таблице прямоугольник, ограниченный вершинами asl , xsk , atk , xtl, asl . 28 В1 … Вl … Вk A1 x11 … x1l … x1k … … … … … … As xs1 … asl … xsk … … … … … … At xt1 … xtl … atk asl ≤ xsk – поскольку asl является минимумом в строке. xsk ≤ atk – поскольку atk является максимум в столбце. atk ≤ xtl - поскольку atk является минимумом в строке. xtl≤ asl - поскольку asl является максимумом в столбце. Таким образом имеем: asl ≤ xsk ≤ atk ≤ xtl≤ asl, а это может быть только в случае asl = atk. Стратегии Ак,Вl соответственно игроков А и В, создающие равновесную ситуацию (Ак,Вl) – соответствующую седловой точке – являются оптимальными. Если нижняя цена равна верхней цене игры, то такое значение называется ценой игры в чистых стратегиях. Совокупность {(S ЧА )O, (S ЧВ )O, v} называется полным (общим) решением игры в чистых стратегиях, где: (S ЧА )O – множество чистых оптимальных стратегий игрока А; (S ЧВ )O – множество чистых оптимальных стратегий игрока В; v – цена игры. Совокупность {Ак,Вl,v} называется частным решением игры в чистых стратегиях, где Ак(S ЧА )O, Вl(S ЧВ )O, (Ак - одна из набора чистых оптимальных стратегий игрока А, а Вl – одна из набора чистых оптимальных стратегий игрока В). 29 Теорема 4. (Критерий существования цены игры в чистых стратегиях.) Для существования цены игры в чистых стратегиях необходимо и достаточно существование у матрицы этой игры седловой точки. Надо доказать: 1. Если в игре существует цена игры, то матрица игры содержит седловую точку. 2. Если матрица содержит седловую точку, то игра имеет цену. Доказательство. В1 … Вl … A1 x11 … x1l … … … … … … As xs1 … asl … … … … … … 1. Пусть в игре существует цена игры. Это означает, что нижняя и верхние цены совпадают. То есть существует такое, asl= asl= max min xij i j min max xij j i Это означает, что ситуация (As, Вl) удовлетворительная для обоих игроков, поскольку выигрыш одного и проигрыш другого совпадают с показателями эффективности и не эффективности. Наличие такой ситуации и означает наличие седловой точки. 2. Пусть матрица содержит седловую точку. То есть существует такая ситуация (As, Вl), Которая является удовлетворительной для обоих игроков, то есть: asl= max i min xij j 30 asl= min j max i xij Это означает, что цена игры существует. Теорема 5. В игре с седловой точкой множество чистых оптимальных стратегий игрока А совпадает с множеством его максиминных стратегий, а множество чистых оптимальных стратегий игрока В совпадает с множеством его минимаксных стратегий. Доказательство. Каждая седловая точка соответствует оптимальным стратегиям игроков. Кроме того, каждая седловая точка является одновременно и максиминной и минимаксной стратегией игроков. Таким образом, видно, что они совпадают. В игре без седловой точки ни у одного из игроков нет оптимальных чистых стратегий, несмотря на то, что у игрока А есть максиминные стратегии, а у игрока В – минимаксные. Алгоритмы поиска седловых точек: Алгоритм 1. 1. Находим максиминное значение выигрыша игрока А. 2. Находим минимаксное значение проигрыша игрока В. 3. Если они равны, значит седловая точка есть. 4. Все пересечения максиминных и минимаксных стратегий игроков и являются седловыми точками. Алгоритм 2. 1. Помечаем в каждой строке наименьшие элементы. 2. Отбрасываем те, которые не являются наибольшими в своих столбцах. 3. Оставшиеся элементы являются седловыми точками матрицы. В качестве примера решим следующую задачу. Финансовая компания В ведет переговоры с инициаторами трех инвестиционных проектов В1 В2 и 31 В3. Инвестиционный договор она может заключить только с одним из инициаторов проектов. Конкурирующая компания А ставит своей задачей свести переговоры компании В к отрицательному результату с тем, чтобы занять место компании В в инвестировании. Компания А для достижения своей цели может применить одно из двух средств: А1 — предложить инициаторам проектов более выгодные условия по сравнению с компанией В; А2 — предоставить материалы, компрометирующие компанию В. Действие A1 компании А приводит к отрицательному результату переговоров компании В с инициаторами проектов В1, В2 и В3 соответственно с вероятностями 0,7; 0,5; 0,3, а действие А2 — с вероятностями 0,6; 0,9; 0,4. Найти решение игры в чистых стратегиях. Распишем действия игроков. Игрок В должен выбрать один из трех проектов. Игрок А выбирает одно из двух своих действий. Игрок А имеет две чистые стратегии: А1 — предложить инициаторам проектов более выгодные условия по сравнению с компанией В; А2 — предоставить материалы, компрометирующие компанию В. Игрок В имеет три чистые стратегии: В1- выбрать первую компанию; В2- выбрать вторую компанию; В3- выбрать третью компанию; В этой игре выигрыш функции игроков не описываются аналитическим выражением. В качестве выигрыша игрока А (или проигрыша игрока В) рассмотрим вероятность отрицательного результата переговоров компании В. Игровая матрицы имеет следующий вид: 32 В В1 В2 В3 А1 0,7 0,5 0,3 А2 0,6 0,9 0,4 А Найдем максиминную стратегию игрока А. Мин(0,7;0,5;0,3)=0,3 Мин(0,6;0,9;0,4)=0,4 Макс(0,3;0,4)=0,4 – нижняя цена игры. Найдем минимаксную стратегию игрока В. Макс(0,7;0,6)=0,7 Макс(0,5;0,9)=0,9 Макс(0,3;0,4)=0,4 Мин(0,7;0,9;0,4)=0,4 – верхняя цена игры. В данной игре нижняя и верхняя цены игры равны, следовательно, игра имеет решение в чистых стратегиях и цена игры равна 0,4. Значение 0,4, как выигрыш игрока А, получается при выборе игроком А стратегий А2 и игроком В стратегии В3. Таким образом, решением игры является набор (А2, В3, 0,4). А2 — предоставить материалы, компрометирующие компанию В, В3- выбрать третью компанию. Пример. Решим задачу уплаты налога бизнесом (задача рассмотрена выше в самом первом примере). Противоборствующие стороны: бизнес и государство в лице налогового ведомства. Бизнес в этой ситуации может: 1. Скрыть свой доход и уйти от уплаты налогов. 2. Занизить свой доход и заплатить налогов меньше. 3. Честно указать свой доход и заплатить полностью весь налог. Налоговая инспекция может: 33 1. Проконтролировать доход и взыскать с бизнеса положенный налог, если доход указан верно, либо налог и штраф, если бизнес скрыл или занизил налог. 2. Не контролировать доход и получить либо весь налог, либо заниженный налог, либо ничего. В результате формализации ситуации получается следующая игровая матрица: Стратегии бизнеса Скрыть доход Занизить доход Честно указать доход Стратегии государства Контролировать Не контролировать -(налог+штраф) -(налог+штраф) -(заниженный налог) -(налог) -(налог) Найдем седловые точки первым способом (алгоритмом №1). Бизнес: Min1 =-(Налог+Штраф) Min2 =-(Налог+Штраф) Мax=-налог Min3 =-(Налог) Налоговая инспекция: Max1 =-(Налог) Мin=-налог Max2 =0 Таким образом, седловая точка есть и она равна -налог. Пересечением максимнной и минимаксной стратегий игроков является ячейка (3,1). Она и есть седловая точка. Оптимальная стратегия для бизнеса – это честно указать доход, как говорится, заплати налоги и спи спокойно. Литература 1. Исследование операций в экономике: учеб. Пособие /Н.Ш.Кремер, Б.А.Путко, И.М. Тришин, М. Н. Фридман; под ред. проф. Н. Ш. 34 Кремера. – 2-е Изд., перераб. и доп.- М. : Издательство Юрайт: ИД Юрайт, 2010. - 430 с. (Глава 12) . 2. Кремер Н.Ш., Путко Б.А., Тришин И.М. Математика для экономистов: от Арифметики до Эконометрики: учеб-справоч. пособие / под ред. проф. Н. Ш. Кремера. – 2-е изд., перераб. и доп. – М.: Издательство Юрайт: ИД Юрайт, 2010. – 646 с. (Параграфы 10.1 и 10.2). 3. Шапкин А. С. Математические методы и модели исследования операций: Учебник / А. С. Шапкин, В. А. Шапкин — 5-е изд — М: Издательско-торговая корпорация «Дашков и К», 2012. — 400 с. 4. Лабскер Л.Г. Теория игр в экономике (практикум с решения задач) : учебное пособие / Л.Г. Лабскер, Н.А. Ященко ; под ред. Л.Г. Лабскера. – 2-е изд., стер. – М. : КНОРУС, 2013. – 264 с. 35 Лекция 3. Смешанные стратегии в матричной игре. В реальности игры с седловой точкой встречаются довольно редко. Поэтому не всегда удается найти оптимальное решение игры в чистых стратегиях. В случае отсутствия оптимальной стратегии в множестве чистых стратегиях следует использовать комбинацию их. Комбинация игроком по какому-то своему правилу своих чистых стратегий называется смешанной стратегией. Введем: вероятность рi применения игроком А i-й стратегии, вероятность qj применения игроком В j-й стратегии. Набор этих вероятностей будет определять правила комбинации чистых стратегий. Поэтому смешанные стратегии определяются набором вероятностей использования чистых стратегий: Рk=(р1,р2,…,рm), k= 1, rA . Ql=(q1,q2,…,qn), l=1, rВ . То есть это вектор, координатами которого являются вероятности использования соответствующей чистой стратегии. Каждую чистую стратегию можно также рассматривать как частный случай смешанной, у которой одна координата равна 1, а все остальные равны 0. Каждая смешанная стратегия представляется линейной комбинацией чистых стратегий с коэффициентами, являющимися вероятностями использования чистых стратегии. Чистая стратегия Аi, вероятность которой в смешанной стратегии равна нулю называется пассивной относительно данной смешанной стратегии. Чистая стратегия Аi, вероятность которой в смешанной стратегии больше нуля называется активной относительно данной смешанной стратегии Введем функцию: 36 m H ( P, Q )   i 1 n pq x j 1 i j ij , определенную на декартовом произведении2 SAхSB множеств смешанных стратегий SA и SB соответственно игроков А и В. Эта функция ставит в соответствие каждой ситуации (Р, Q)SAхSB в смешанных стратегиях Р=(р1,р2,…,рm) игрока А и Q= (q1,q2,…,qn) игрока В средневзвешенный выигрыш игрока А в этой ситуации. Эта функция называется выигрышфункцией игрока А в смешанных стратегиях. Пусть у нас есть игровая матрица: В1 В2 … Вn A1 x11 x12 ... x1n A2 x21 x22 ... x2n … ... ... ... ... Am xm1 xm2 ... xmn Введем для игрока А набор смешанных стратегий: P1 p11 p21 … pm1 P2 p12 p22 … pm2 … … … … … Pra p1ra p2ra … pmra Где pki – вероятность использования чистой стратегии под номером к в смешанной под номером i. Первый столбец содержит обозначения смешанных стратегий. Число ra – определяет число смешанных стратегий игрока А. 2 Декартово произведение множеств — произведение множеств A и B, рассматриваемое как множество всех упорядоченных пар элементов (a, b), из которых a принадлежит множеству A, b множеству B. 37 Введем для игрока В набор смешанных стратегий: Q1 q11 q21 … qn1 Q2 q12 q22 … qn2 … … … … … Qrb q1rb q2rb … qnrb Где qki – вероятность использования чистой стратегии под номером k в смешанной под номером i. Число rв – определяет число смешанных стратегий игрока B. Для каждого соотношения смешанных стратегий Pk и Ql рассчитаем выигрыши игрока А по формуле: m H ( Pk , Ql )   i 1 n pq x j 1 i j ij = p1q1x11+p1q2x12+…+p1qnx1n+ p2q1x21+p2q2x22+…+ p2qnx2n m n i 1 j 1 +… pmq1xm1+pmq2xm2+…+pmqnxmn   pi  q j xij . В результате мы получаем уже другую матрицу выигрышей: Ql Q2 ... Qrb p1 H11 H12 ... H1rb p2 H21 H22 ... H2rb ... ... ... ... ... pra Hra1 Hra2 ... Hra rb Операция вычисления выигрышей игрока А при смешанных стратегий может быть произведена с помощью операций над матрицами: T H ( Pk , Ql ) = = Pk X Ql , где: k, k k Рк= (p1 p2 ,…pm ) – вектор вероятностей смешанной стратегии игрока А по номером к; 38 Х игровая матрица чистых стратегий: x11 x12 ... x1n x21 x22 ... x2n ... ... ... ... xm1 xm2 ... xmn QlT - транспонированный вектор вероятностей смешанной стратегии игрока В по номером l: q1 q2 l l . . . qn l Аналогично чистым стратегиям введём: • показатель эффективности смешанной стратегии Рi относительно множества SB смешанных стратегий игрока В – это минимальный выигрыш при этой стратегии ai  min H ( Pi , Q) ; QS B • показатель неэффективности смешанной стратегии Qj относительно множества SА смешанных стратегий игрока А – это максимальный проигрыш при этой стратегии в j  max H ( P, Q j ) . PS A Теорема 6. Показатели эффективности любой смешанной (в частности, чистой) стратегии РSA игрока А относительно множества S ЧB (чистых) и SB (смешанных) стратегий противника В равны: α(P,S ЧB ) = α(P,SB). m То есть: ak  min H ( Pk , Q)  min H ( Pk , B j ) , где H ( Pk , B j )   pik xij . QS B 1 j  n i 1 39 Теорема 7. Показатели неэффективности любой смешанной (в Ч частности, чистой) стратегии QSB игрока В относительно множеств S А Ч чистых) и SA(смешанных) стратегий противника А равны: β(Q,S А ) = β(Q,SА). n То есть l  max H ( P, Ql )  max H ( Ai , Ql ) , где H ( Аi , Ql )   q lj xij . 1i  m PS A Теоремы 6 ориентироваться и на 7 j 1 позволяют чистые при стратегии. анализе эффективности Смешанные стратегии противника неизвестны, а чистые известны. Нижней ценой, или максимином, матричной игры в смешанных стратегиях называется величина: V  max min H ( P, Q) . PS A QS B Верхней ценой, или минимаксом, матричной игры в смешанных стратегиях называется величина: V  min max H ( P, Q) . QS B PS A Теорема 8. Для любой конечной матричной игры существуют нижняя и верхняя цены игры в смешанных стратегиях. Смешанная стратегия Р°SA, максимизирующая показатель эффективности α(Р), называется максиминной смешанной стратегией игрока А. Смешанная стратегия Q°SB, минимизирующая показатель неэффективности β(Q), называется минимаксной смешанной стратегией игрока В. Теорема 9. Нижняя цена игры α и верхняя цена игры β в чистых стратегиях, нижняя цена игры V и верхняя цена игры V в смешанных стратегиях удовлетворяют следующим неравенствам: α ≤ V ≤ V ≤ β. Данная теорема говорит, что максиминные и минимаксные смешанные стратегии не могут ухудшить результат игры. 40 Если нижняя V и верхняя V цены игры в смешанных стратегиях совпадают, то их общее значение V = V = V называется ценой игры в смешанных стратегиях. Нижняя и верхняя цены игры в чистых стратегиях α и β и цена игры в смешанных стратегиях V связаны между собой неравенствами α ≤ V ≤ β. Стратегии P° и Q° соответственно игроков А и В, удовлетворяющие равенствам V=α(Р°)=β(Q°) называются оптимальными смешанными стратегиями соответственно игроков А и В. Оптимальные смешанные стратегии Р° и Q° соответственно игроков A и В обладают свойством: если один из игроков придерживается своей оптимальной стратегии, то противнику невыгодно отклоняться от своей оптимальной стратегии. Полным решением игры трехэлементная совокупность в смешанных стратегиях называется {(SA)°,(SB)°,V}, где (SA)° - множество всех оптимальных смешанных стратегий игрока А, (SB)°- множество всех оптимальных смешанных стратегий игрока В. Любая пара отдельных оптимальных стратегий РО и Q0 соответственно игроков А и В и цена игры в смешанных стратегиях V образуют частное решение в смешанных стратегиях {Р° , Q0 ,V}. Теорема 10. (Основная теорема матричных игр Дж. фон Неймана.) Любая матричная игра имеет решение в смешанных стратегиях, т.е. существуют цена игры в смешанных стратегиях V u оптимальные смешанные стратегии Р° u Q° соответственно игроков А и В, т.е. V = V  max min H ( P, Q) = V  min max H ( P, Q) = α(Р°) = β(Q°) = Н(Р°, Q0). PS A QS B QS B PS A Поиск оптимальных смешанных стратегий имеет смысл, если в игре нет седловых точек. 41 Теорема 11. (Критерии оптимальных стратегий.) Пусть V — цена игры, Н(Р, Q) — выигрыш-функция, SA u SB — множества смешанных стратегий соответственно игроков А и В. 1. Для того чтобы стратегия Р° игрока А была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство Н(Р°, Q)≥V для любого QSB, т.е. выбор игроком А оптимальной стратегии Р° гарантирует ему выигрыш Н(Р°,Q), не меньший цены игры V, при любой стратегии Q игрока В. 2. Для того чтобы стратегия Q0 игрока В была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство Н(Р, Q0) ≤ V для любого РSA, т.е. выбор игроком В оптимальной стратегии Q0 гарантирует ему проигрыш Н(Р, Q0), не больший цены игры V, при любой стратегии Р игрока А. Теорема 12. (Критерии оптимальных стратегий.) Пусть V—цена игры, H(Р, Q)—выигрыш-функция, SA= {A1, А2, …, Аn} и SB = {В1,В2,…,Вm} — множества чистых стратегий соответственно игроков А и В. 1. Для того чтобы стратегия Р° игрока А была оптимальной, необходимо и достаточно, чтобы выполнялось неравенство H(P°,Bj)≥V, j = 1,2,…,m 2. Для того чтобы стратегия Qo игрока В была оптимальной, необходимо и достаточно, чтобы H(Ai,Q0)≤V, i = 1,2,..., n Теорема 13. (Критерий частного решения игры в смешанных стратегиях.) Для того чтобы V было ценой игры, а Р° и Q° — оптимальными стратегиями соответственно игроков А и В ({Р°, Q°, V} было частным 42 решением игры), необходимо и достаточно выполнение двойного неравенства H(P,Q°) ≤ V ≤ H(P°,Q) для любых PSA u QSB. Теорема 14. (Критерий частного решения игры в смешанных стратегиях.) Для того чтобы V было ценой игры, а Р° u Q° — оптимальными стратегиями соответственно игроков А и В, необходимо и достаточно выполнение двойного неравенства H(Ai,Q°) ≤ V ≤ H(P°,Bj), i= 1,2,...,n, j = 1,2,..., m. В этой теореме множество смешанных стратегий SA и SB заменены соответственно на множество чистых стратегий. Это позволяет при поиске оптимальных смешанных стратегиях оперировать чистыми стратегиями противника. Теорема 15. (Об активных3 стратегиях.) Пусть V — цена игры, Р° = (р1°,р2°,…,рn°) и Q° = (q1°, q2°,…, qm°) оптимальные стратегии соответственно игроков A и В. Тогда справедливы следующие утверждения: 1. Для любой активной стратегии Ак, (k=1,2,...,n) относительно оптимальной стратегии Р° игрока А выполняется равенство H(Ак, Q° ) = V. 2. Для любой активной стратегии Bl (l=1,2,...,m) относительно оптимальной стратегии Q0 игрока В выполняется равенство H(Р°, Bl) = V. Теорема 19 дает алгоритм вычисления выигрыша игроков в смешанных стратегиях на основе активных стратегий игроков. 3 Чистая стратегия Аi - называется пассивной или активной относительно стратегии Р° = (р1°, р2°, ..., рn°) в зависимости от того, р° = 0 или р° > 0. смешанной оптимальной 43 Аналитическое решение игр с нулевой матрицей 2х2 Теорема 16. Пусть игровая матрица размером 2x2 не имеет седловой точки: В1 В2 А1 x11 x12 А2 x21 x22 Тогда каждый из игроков А и В обладает единственной оптимальной смешанной стратегией: Р° =(р1°, р2°) и Q° =(q1°, q2°), где p1o  х22  х21 ( х11  х22 )  ( х12  х21 ) p2o  1  p1o  q1o  х11  х12 ( х11  х22 )  ( х12  х21 ) х22  х12 ( х11  х22 )  ( х12  х21 ) q2o  1  q1o  х11  х21 ( х11  х22 )  ( х12  х21 ) При этом цена игры равна V х11 х22  х12 х21 ( х11  х22 )  ( х12  х21 ) Доказательство: Поскольку у игроков по две чистых стратегии, они же активные, поскольку у матрицы нет седловой точки, то любая смешанная стратегия имеет вид (р, 1-р) и (q, 1-q), А цены игры игрока А равна V =х11p+ х21(1-p) V = х12p+ х22(1-p) Приравниваем эти выражения: 44 х11p+ х21(1-p)= х12p+ х22(1-p) отсюда получаем х11p+ х21-х21р=х12p+ х22- х22p далее получаем х11p-х21p - х12p + х22р= х22- х2 p х22  х21 . ( х11  х22 )  ( х12  х21 ) Запишем формулу цены игры игрока В V =х11q+ х12(1-q) V = х21q+ х22(1-q) Делаем аналогичные преобразования х11q+ х12(1-q)= х21q+ х22(1-q) х11q+ х12-х12q=х21q+ х22- х22q х11q-х12q- х21q + х22q= х22- х12 q х22  х12 ( х11  х22 )  ( х12  х21 ) Пример. Цех-заготовитель поставляет в сборочный цех детали двух видов «а» и «b». По договору между цехами определены два срока поставок этих деталей в течении рабочего дня. При поставке в первый срок деталей вида «а» сборочный цех платит заготовительному премию 50 руб., при поставке этого же изделия во второй срок выплачивается премия равная 20 руб. При поставке изделий вида «b» в первый срок премия составляет 30 руб., а во второй – 40 руб. Определить оптимальные стратегии поставок и получения деталей. Цех-заготовитель – игрок А. Сборочный цех – игрок В. Стратегиями игрока А является поставка деталей «а» или «b». Стратегиями игрока В – срок получения этих деталей. В результате формализации игры получаем матрицу: 45 1 срок 2 срок Детали «а» 50 20 Детали «b» 30 40 Ищем оптимальную чистую стратегию (седловую точку): α= max min β= min j xij=30 j i max xij=40 i Седловой точки нет, следовательно, можно применить теорему 11. p1o  х22  х21 40  30 10    0,25 . ( х11  х22 )  ( х12  х21 ) (50  40)  (30  20) 40 p2o  1  p1o  1  0,25  0,75 . q1o  х22  х12 40  20 20    0,5 . ( х11  х22 )  ( х12  х21 ) (50  40)  (20  30) 40 q2o  1  q1o  0,5 . V х11 х22  х12 х21 50 * 40  20 * 30 1400    35 . ( х11  х22 )  ( х12  х21 ) (50  40)  (20  30) 40 Цена игры в смешанных стратегиях – 35 рублей премии в день. Общее решение {(0,25;0,75) (0,5;0,5) 35} Вывод: сроки поставки необходимо равномерно чередовать, при этом детали вида «b» необходимо поставлять в три раза чаще Графический способ решения нулевой матрицы 2хn Пусть дана матрица 2хn: В1 В2 … Bn А1 x11 x12 … x1n А2 x21 x22 … x2n Отложим горизонтальный отрезок, считая его отрезком длины 1. 46 На границах слева и справа отложим вертикальные отрезки длиной не меньше максимального значения нашей платежной матрицы. Если в матрице есть значения меньше нуля, то две вертикальные линии продолжаем вниз с учетом этих значений. Левый отрезок обозначает стратегию А1, а правый А2. На отрезках А1 и А2 соответственно отложим значения одноименных стратегий (то есть числа строк нашей матрицы). Соединим значения этих отрезков так, чтобы получились линии, соответствующие стратегиям В1,. В2….. Вn. Далее проводим нижнюю огибающую кривую (на рисунке 3.1 она обозначена красным цветом). x1n x11 Вn x22 В1 Цена игры В2 x12 А1 x21 x2n z чистые стратегии 1 А2 Рисунок 3.1. Поскольку у игрока 2 стратегии, то вероятность стратегии А1 р1=р, а вероятность стратегии А2 р2=1-р. 47 Обозначаем нижнюю огибающую кривую (на рисунке 3.1 она отмечена красным цветом). Находим максимум нижней огибающей. Её значение на оси абсцисс (ось х) обозначено точкой z. Значение этой точки на оси ординат (ось у) равно цене игры. В данном случае могут возникнуть следующие ситуации: Ситуация 1. Точку максимума нижней огибающей образует пересечение двух и более отрезков (как указано на рисунке 3.1). В этой ситуации выделяются две любые из соответствующих этим отрезкам стратегии игрока В. Записываем формулу выигрыша игрока А если он использует оптимальную смешанную стратегию с вероятностями р и 1-р, а игрок В выделенные чистые стратегии. На рисунке 2 – это стратегии В1 и В2. B1=x11*р+x21*(1-р) B2= x12*р+x22*(1-р) Эти выигрыши должны быть равны, поэтому приравниваем их между собой (B1=B2) и находим значение р. Далее подставив найденное значение р в любую из записанных формул находим цену игры. Ситуация 2. Точки максимума находятся на отрезке (см. рисунок 3.2). В этом случае оптимальных стратегий бесконечно много. Вероятность р2 находится в интервале [zн,zk], вероятность р1 = 1- р2. Для нахождения значений zн и zk необходимо воспользоваться тем же алгоритмом, как и в случае нахождения р в указанной выше ситуации 1. В ситуации, изображенной на рисунке 3.2 zн находим из равенства В1=В2, а zк из равенства В1=Вn. Цена игры равна координатам отрезка, на котором находятся точки максимума нижней огибающей кривой. В ситуации, изображенной на рисунке 3.2 это координаты отрезка В1 (х11 или х21). 48 х1n Вn В2 х22 х11 В1 х21=Цена игры х12 х2n z А1 zн чистые стратегии zк 1 А2 Рисунок 3.2. Ситуация 3. Точка максимума находится на вертикальных отрезках, соответствующих чистым стратегиям игрока А (см. рисунок 3.3 и рисунок 3.4). В этой ситуации есть оптимальная чистая стратегия игрока А (есть седловая точка), соответствующая максимальной точке нижней огибающей кривой. 49 x11 В1 x12 В2 А1 x21 x22 1 А2 чистые стратегии Рисунок 3.3. Кривые не пересекаются. x11 В1 x12 А1 В2 чистые стратегии x21 x22 1 А2 Рисунок 3.4. Линии пересекаются, но максимум нижней огибающей находится на вертикальной оси. . 50 Пример. Пусть дана игровая матрица: В1 В2 В3 В4 А1 1 3 6 2,5 А2 5 3 2 4 Найти оптимальную смешанную стратегию игрока А. Произведем все необходимые построения используя Excel (см. рисунок 3.5). Zн ZК Рисунок 3.5. Нижняя огибающая образована тремя кривыми: В1, В2 и В3. Найдём zн : В1=В2  1-zн+5zн=3-3zн+3zн 4 zн=2 zн=0,5. zк: В2=В3  3-3zк+3zк =6-6zк+2zк  4zк=3 zк=0,75. Таким образом, частным решением игры в смешанных стратегиях игрока А может быть набор (0,4;0,6; при цене игры 3). 51 Графический способ решения матриц mх2 В1 В2 А1 x11 x12 А2 x21 x22 … … xm1 xm2 Am Графический метод решения матриц mx2 основывается на свойстве оптимальных смешанных стратегий игроков: оптимальные смешанные стратегии соответственно игроков А и В P° и Q° удовлетворяют равенствам V = α(Р°) = β(Q°). Поэтому для нахождения цены игры достаточно определить показатель неэффективности оптимальной смешанной стратегии игрока В - β(Q°), а после рассмотреть те чистые стратегии игрока А, на которых достигается цена игры равная показателю не эффективности оптимальной смешанной стратегии игрока В. Для этого действуем аналогично игре 2хn, но по отношению к игроку В. Отложим горизонтальный отрезок, считая его отрезком длины 1. На границах слева и справа отложим вертикальные отрезки длиной не меньше максимального значения нашей платежной матрицы. Если в матрице есть значения меньше нуля, то две вертикальные линии продолжаем вниз с учетом этих значений. Левый отрезок обозначает стратегию В1, а правый В2. На отрезках В1 и В2 соответственно отложим значения одноименных стратегий (то есть числа столбцов матрицы). Соединим значения этих отрезков так, чтобы получились линии, соответствующие стратегиям А1,. А2….. Аm. 52 Далее проводим верхнюю огибающую кривую и ищем минимум верхней огибающей (см. рисунок 3.6). xm1 Am x11 x22 A2 A1 Цена игры x21 x12 xm2 z B1 чистые стратегии 1 B2 Рисунок 3.6. Далее выделяем активные стратегии игрока А – это стратегии, дающие при пересечении цену игры, после чего решаем игру 2х2 только с активными стратегиями игрока А. Рассмотрим пример игры с игровой матрицей: В1 В2 А1 1 4 А2 3 1 А3 2 2,5 A4 5 Все необходимые графические построения изображены на рисунке 3.7. 53 Оптимальными стратегиями у А являются чистые стратегии, дающие при использовании цену игры (минимум верхней огибающей кривой) – это А1 и А4. Следовательно, они будут активными, а остальные будут пассивными, а оптимальное решение будет иметь вид P=(p1,0,0,p4o). 5 3 А4 4 А1 А2 А3 2,5 2 1 1 В1 z чистые стратегии 1 В2 Рисунок 3.7. Убираем пассивные стратегии игрока А и решаем как игру 2х2. p1o  В1 В2 А1 1 4 A4 5 х22  х21 05 5    0,625 ( х11  х22 )  ( х12  х21 ) (1  0)  (5  4)  8 P=(0,625;0;0;0,375 ). 54 V х11 х22  х12 х21 1* 0  4 * 5  20    2,5 ( х11  х22 )  ( х12  х21 ) 8 8 В решении графическим способом игры mx2 может возникнуть случай, когда минимум верхней огибающей находится на прямой (см. рисунок 3.8. Am x x A1 x 11 x 22 12 = Цена игры A2 21 x B1 zк zн чистые стратегии m2 1 B2 Рисунок 3.8. В этом случае цена игры равна выигрышу при той стратегии, на которой находится минимум верхней огибающей и эта же стратегия игрока А является активной, а остальные пассивной. В случае ситуации рисунка 3.8 оптимальная смешанная стратегия игрока А будет такой ро=(1;0;0;…;0), а цена игры х12 = х11. Решение игр с матрицей mxn Для решения таких матриц существуют свои методы. 1. Метод линейного программирования, 2. Метод Брауна-Робинсона . 55 Кроме того существуют методы упрощения матриц на основе свойства доминирования, приводящие игры к описанным ранее методам. Литература 1. Исследование операций в экономике: учеб. Пособие /Н.Ш.Кремер, Б.А.Путко, И.М. Тришин, М. Н. Фридман; под ред. проф. Н. Ш. Кремера. – 2-е Изд., перераб. и доп.- М. : Издательство Юрайт: ИД Юрайт, 2010. - 430 с. (Глава 12) . 2. Кремер Н.Ш., Путко Б.А., Тришин И.М. Математика для экономистов: от Арифметики до Эконометрики: учеб-справоч. пособие / под ред. проф. Н. Ш. Кремера. – 2-е изд., перераб. и доп. – М.: Издательство Юрайт: ИД Юрайт, 2010. – 646 с. (Параграфы 10.1 и 10.2). 3. Шапкин А. С. Математические методы и модели исследования операций: Учебник / А. С. Шапкин, В. А. Шапкин — 5-е изд — М: Издательско-торговая корпорация «Дашков и К», 2012. — 400 с. 4. Лабскер Л.Г. Теория игр в экономике (практикум с решения задач) : учебное пособие / Л.Г. Лабскер, Н.А. Ященко ; под ред. Л.Г. Лабскера. – 2-е изд., стер. – М. : КНОРУС, 2013. – 264 с. 56 Лекция 4. Смешанные стратегии в матричных играх (решение матричных игр mxn) Методы упрощения матриц (принцип доминирования). Принцип доминирования Определение. Вектор а0 называется выпуклой комбинацией векторов а1; а2,...,аn, если существуют такие числа λ1, λ2,..., λn что: n a0   к a k k 1 при условии λk>0,  к 1. Если и для двух выпуклых комбинаций строк матрицы А (1) (2) выполняется неравенство то говорят, что строка (2) доминирует строку (1), а строка (1) доминируется строкой (2). В случае строгого неравенства говорят, что строка (2) строго доминирует строку (1), а строка (1) строго доминируется строкой (2). В случае равенства строки (1) и (2) называют дублирующими. Каждая стратегии выпуклая комбинация строк соответствует смешанной игрока А. Следовательно в данном случае мы говорим о доминировании и дублировании смешанных стратегий. При таких соотношениях стратегия Р" = (р1",р"2,...,р"т) доминирует (дублирует) стратегию Р' = (р1',р'2,...,р'т). 57 Если и для двух выпуклых комбинаций столбцов матрицы А (3) (4) выполняется неравенство то говорят, что столбец (3) доминирует столбец (4), а столбец (4) доминируется столбцом (3). В случае строгого неравенства присутствует строгое доминирование. В случае равенства как и со строками присутствует дублирование столбцов. Каждая выпуклая комбинация столбцов соответствует смешанной стратегии игрока В. Следовательно в данном случае мы говорим о доминировании и дублировании смешанных стратегий. При таких соотношениях стратегия Q' = (q1' ,q'2,...,q'n) доминирует (дублирует) стратегию . Q" = (q1",q"2,...,q"т) Теорема 17. Справедливы следующие предложения: 1. Если к-я строка матрицы Х игры доминируется некоторой выпуклой комбинацией остальных ее строк, то существует оптимальная смешанная стратегия Рo = {рo1,рo2,...,рoт) игрока А, относительно которой k-я чистая стратегия Ак является пассивной, т.е. входит в смешанную стратегию Рo с нулевой вероятностью: р o к = 0. 2. Если к-я строка матрицы Х игры строго доминируется некоторой выпуклой комбинацией остальных ее строк, то относительно любой оптимальной смешанной стратегии Р°=(р°1,р°2,…,Р°т) игрока А чистая k-я 58 стратегия Ак является пассивной, т.е. входит в стратегию Р° с нулевой вероятностью: р o к = 0. 3. Если l-й столбец матрицы Х игры доминируется некоторой выпуклой комбинацией остальных ее столбцов, то существует оптимальная смешанная стратегия Qo =(qo1,qo2,…, qon) игрока В, относительно которой l-я чистая стратегия является пассивной, т.е. входит в стратегию Qo с нулевой вероятностью: qol= 0. 4. Если l-й столбец матрицы А игры строго доминируется некоторой выпуклой комбинацией остальных ее столбцов, то относительно любой оптимальной смешанной стратегии Qo =(qo1,qo2,…, qon) игрока В чистая l-я стратегия является пассивной, т.е. входит в стратегию Qo с нулевой вероятностью: qol= 0. Следствие 1. 1. Если к-я строка матрицы игры доминируется некоторой другой строкой, то существует оптимальная смешанная стратегия игрока А, относительно которой чистая стратегия Ак является пассивной, т.е. входит в эту смешанную стратегию с нулевой вероятностью. 2. Если к-я строка матрицы игры строго доминируется некоторой другой строкой, то относительно любой оптимальной смешанной стратегии игрока А k-я чистая стратегия Ак является пассивной, т.е. входит в любую смешанную стратегию с нулевой вероятностью. 3. Если l-й столбец матрицы игры доминируется некоторым другим столбцом, то существует оптимальная смешанная стратегия игрока В, относительно которой чистая стратегия Вl является пассивной, т.е. входит в эту смешанную стратегию с нулевой вероятностью. 4. Если l-й столбец матрицы игры строго доминируется некоторым другим столбцом, то относительно любой оптимальной смешанной стратегии игрока В чистая стратегия Вl является пассивной, т.е. входит в любую оптимальную смешанную стратегию с нулевой вероятностью. 59 Следствие 2. (О дублирующих чистых стратегиях.) Одну из двух дублирующих чистых стратегий можно удалить. Эти следствия позволяют перед нахождением смешанных стратегий удалять из матрицы дублирующие или домируемые (те которые доминируются другими стратегиями) чистые стратегии игроков. Таким образом можно уменьшить размер матрицы. А убранные стратегии использовать в оптимальной с вероятностью 0. Изоморфные и аффинные преобразования матричных игр С помощью изоморфных и афинных преобразований можно матрицу игры привести к более удобному виду. Изоморфные преобразования Изоморфным преобразованием игры называется перенумерация чистых стратегий игрока А и (или) игрока В. Эти преобразования сводятся к перестановки строк и столбцов: В В1 В3 В2 A5 4 5 4 2 A1 3 4 1 -6 5 A4 3 4 1 3 1 4 A2 -4 2 4 4 5 A3 5 5 -6 В1 В2 В3 A1 3 1 4 A2 -4 A3 5 A4 A5 А Матрица А В А Матрица А При этом исходная матрица (А) называется прообраз, а конечная (А)– образ. В результате этих преобразований преобразуются и смешанные стратегии: Р в P', Q в Q‘. 60 Теорема 18. При изоморфном преобразовании справедливы следующие утверждения: 1. Значение функции выигрыша Н' в игре с матрицей А' на образе (P',Q') ситуации (Р, Q) в смешанных стратегиях Р и Q равно значению функции выигрыша Н в игре с матрицей А в ситуации (Р, Q) H'(P',Q') = H(P,Q), PSА, QSB. 2. Показатели эффективности смешанных стратегий Р и Р' равны a'(P') = a(P),PSA. 3. Показатели неэффективности смешанных стратегий Q и Q' равны  '(Q') = (Q). 4. Образы и прообразы оптимальных стратегий являются оптимальными стратегиями. 5. Цена игры V c матрицей А равна цене игры V' с матрицей А'. Афинные преобразования Аффинными преобразованиями матрицы Х в матрицу Х’ называются такие преобразования элементов матрицы, которые осуществляются по правилу: х'ij=λxij+μ (i =1,2,..., т; j =1,2,..., n); где x’ij - элементы матрицы X', xij – элемент матрицы Х, λ>0 и μ действительные произвольные фиксированные числа. Подобное преобразование не меняет вероятности выбора игроками чистых стратегий в смешанных, т.е. смешанные стратегии будут преобразовываться тождественным образом: Р=(р1,р2,…,рm) преобразуется в Р’=(р’1,р’2,…,р’m) так что рi=p’i. Q=(q1,q2,…,qn) преобразуется в Q’=(q’1,q’2,…,q’n) так что qi=q’i. При этом Р’ является образом смешанной стратегии Р, а Р является прообразом смешанной стратегии Р’. 61 Также и Q’ является образом смешанной стратегии Q, а Q является прообразом смешанной стратегии Q’. Теорема 19. При аффинном преобразовании справедливы следующие утверждения: 1. Если H и H' — выигрыш функции игр соответственно с матрицами X и X', то H'(P',Q') = λH(P,Q) + μ. 2. Для показателей эффективности смешанных стратегий Р, Р' и показателей неэффективности смешанных стратегий Q, Q' имеют место равенства: a'(P') = λa(P)+μ, PSA, ’(Q')=λ(Q)+μ, QSB. 3. Образы и прообразы оптимальных стратегий являются оптимальными. 4. Если V u V’ - цены игр соответственно с матрицами X и X', то V'= λV +μ. Теорема 19 дает возможность преобразования матрицы: 1. Можно изменить масштаб измерения выигрышей (по сути игры безразлично, в каких денежных единицах измерять выигрыши, например в рублях, евро или долларах). 2. Если матрица игры содержит дробные элементы, то аффинным преобразованием ее можно редуцировать к матрице с целыми элементами. 3. Если матрица игры содержит достаточно много элементов, равных какому-либо числу а, то аффинным преобразованием ее можно преобразовать в матрицу с большим количеством нулей. 4. Если матрица игры содержит неположительные элементы, то ее можно привести к матрице только с положительными элементами. 62 Сведение матричной игры к задаче линейного программирования (ЗЛП). Теорема 20. Решение матричной игры mхn с матрицей X (xij>0), эквивалентно решению следующей пары двойственных друг другу стандартных задач линейного программирования: m а) найти min  zi , при ограничениях zi 0 (i =1,2,..., т); i 1 и системе ограничений m  х z ,1, ij i i 1 m б) найти max  wi , при ограничениях wj0 (j =1,2,..., n); (j =1,2,..., n); i 1 и системе ограничений m  x w 1, (i =1,2,..., m). i 1 где zi= рj V , wj= qj V ij i . Докажем эту теорему, чтобы ясней был алгоритм сведения подобной игры к задаче линейного программирования. Согласно теорем об оптимальных стратегиях, если стратегия Р° игрока А оптимальная, то выполнялось неравенство: H(P°,Bj)≥V, где j = 1,2,…,n, а Вj – чистые стратегии игрока В. Распишем выигрыш функцию игрока А и получим следующую систему неравенств: H(P°,B1)=p1x11+ p2x21+…+ pmxm1≥V H(P°,B2)=p1x12+ p2x22+…+ pmxm2≥V . . . H(P°,Bn)=p1x1n+ p2x2n+…+ pmxmn≥V Кроме того p1+ p2+…+ pm=1 и p10 p20… pm 0. В системе неравенств, как в правой части, так и в левой, есть неизвестные – вероятности и цена игры. Поделим в неравенствах и последней сумме обе части на цену игры V. 63 Получим следующую систему неравенств, у которых неизвестные стоят только в левой части, и последнее равенство: H(P°,B1)=z1x11+ z2x21+…+ zmxm1≥1 H(P°,B2)=z1x12+ z2x22+…+ zmxm2≥1 . . . H(P°,Bn)=z1x1n+ z2x2n+…+ zmxmn≥1 z1+ z2+…+ zm= где zi= рj V 1 V . Поскольку игрок А заинтересован в максимизации своего выигрыша, то он должен стремиться к максимизации цены игры, то есть Vmax. В этом случае 1 1 min, а это означает, что z1+ z2+…+ zm= min. V V Таким образом, получаем следующий набор условий и неравенств, являющихся, по сути, ограничениями: Необходимо найти такие zi, что: z1+ z2+…+ zmmin, при ограничениях: z1x11+ z2x21+…+ zmxm1≥1, z1x12+ z2x22+…+ zmxm2≥1, . . . z1x1n+ z2x2n+…+ zmxmn≥1 Если принять еще условие: zi 0, то написанное выше становится формулировкой задачи линейного программирования. Если в доказательстве заменить игрока А на игрока В, то не меняя, в основном, всех объяснений можно прийти к соответствующей формулировке (пункт б теоремы 20). Правда при этом следует иметь в виду, что мы исходим из свойства оптимальной стратегии игрока В - H(Ai,Q°) ≤ V. Цель игрока В минимизировать проигрыш, то есть цену игры V. В этом случае 1 max. V 64 Проделав указанные выше изменения в доказательстве, мы придем к соответствующей формулировке (пункт б теоремы 20). Замечание. Условие: zi 0 может не выполняться для произвольной игры с нулевой матрицей, так как цена игры V может быть числом отрицательным. Однако, следует иметь ввиду, что цена игры всегда находится в диапазоне значений игровой матрицы: min xij Vmax xij. Поэтому если произвольную игровую матрицу преобразовать в матрицу с неотрицательными значениями, то это условие выполняться будет. Поэтому, прежде чем свести игру к задаче линейного программирования, необходимо сначала проверить её на неотрицательность, и, если в ней есть отрицательные значения, преобразовать матрицу с помощью афинных преобразований. Алгоритм решения игры с помощью аппарата линейного программирования игроком А. Пусть есть игровая матрица В1 ... Вn A1 x11 ... x1n ... ... ... ... Am xm1 ... xmn 1. Делаем, если необходимо афинные преобразования. 2. Выписываем целевую функцию: z1+ z2+…+ zmmin, где zi= 3. Записываем ограничения: z1x11+ z2x21+…+ zmxm1≥1, z1x12+ z2x22+…+ zmxm2≥1, . . . , z1x1n+ z2x2n+…+ zmxmn≥1, zi 0, (j =1,2,..., m). рj V . 65 4. Находим с помощью метода линейного программирования все zi, (j =1,2,..., m). 5. Находим цену игры V  1 . z1  z 2  ...  z m 6. Находим вероятности p1  z1  V , p2  z 2  V , ..., pm  z m  V . 7. Делаем, если надо, обратное преобразование V V'   Алгоритм решения игры с помощью аппарата линейного программирования игроком В. 1. Делаем, если необходимо афинные преобразования. 2. Выписываем целевую функцию: w1+ w2+…+ wnmax, где wi= qj V 3. Записываем ограничения: w1x11+ w2x12+…+ wnx1n1, w1x21+ w2x22+…+ wnx2n1 . . . , w1xm1+ w2xm2+…+ wnxmn1 wi 0, (j =1,2,..., n). 4. Находим с помощью метода линейного программирования все wi, (j =1,2,..., n). 5. Находим цену игры V  1 . w1  w2  ...  wn . 66 6. Находим вероятности q1  w1  V q 2  w2  V , ..., qn  wn V . 7. Делаем, если надо обратное преобразование V V'   Решим следующую задачу. (Поставка товаров). На каждой из двух торговых баз ассортиментный минимум составляет один и тот же набор из 4 видов товаров. Каждая база должна поставить в свой магазин только один из этих видов товара. Магазины (A и В) конкурируют между собой. Один и тот же вид товара в обоих магазинах продается по одной и той же цене. Однако товар, поставляемый в магазин В, более высокого качества. Если магазин А завезет с базы товар i-го вида, отличный от товара j-го вида, завезенного в магазин В, то товар i-го вида будет пользоваться спросом и магазин от его реализации получит прибыль сi денежных единиц (д.е.). Если же в магазины А и В завезены товары одинакового вида i=j, товар i-го вида в магазине А спросом пользоваться не будет, поскольку такой же товар, по такой же цене, но более высокого качества можно купить в магазине В. Поэтому магазин А понесет убытки по транспортировке, хранению и, возможно, порче товара iго вида в размере di д.е. Найти оптимальную стратегию магазина А при следующих данных (с1= 300, с2= 500, с3= 250, с4=400, d1=-300, d2=-150, d3=-170, d4=-220. Пункт 1 алгоритма формализации игровой ситуации заключается в расписывании всех возможных действия каждого игрока. Чтобы максимизировать выигрыш магазин А должен завести товар отличный от товара магазина В. Магазину В нет разницы какой товар завозить, так как товар в его магазине лучшего качества. 67 Пункт 2 алгоритма формализации игровой ситуации заключается в составлении выигрыш-функции каждого игрока. Поскольку у нас игра с нулевой матрицей, то достаточно составить выигрыш-функцию только игрока А. Пусть: i – вид товара, завезенного в магазин А. j – вид товара, завезенного в магазин В Тогда выигрыш- функция игрока А : i=j, при i=1 -300, при i=2 -150, при i=3 -170, при i=4 -220 А= ij, при i=1 300, при i=2 500, при i=3 250, при i=4 400 Пункт 3 объединим с этапом 4 и запишем выигрыши прямо в матрицу. В(j) В1 В2 В3 В4 A1 -300 300 300 300 A2 500 -150 500 500 A3 250 250 -170 250 A4 400 400 400 -220 А(i) Седловой точки матрица не имеет, поэтому найдем оптимальные смешанные стратегии магазина А с помощью методов линейного программирования. Однако матрица имеет отрицательные значения, поэтому преобразуем ее с помощью афинных преобразований: Х’=X+301. В результате получаем матрицу: 68 В(j) В1 В2 В3 В4 A1 1 601 601 601 A2 801 151 801 801 A3 551 551 131 551 A4 701 701 701 81 А(i) 1. Целевая функция имеет следующий вид: z1+ z2+ z3+ z4min. 2. Записываем ограничения: z1+801 z2+551 z3+ 701 z4≥1, 601 z1+151 z2+551 z3+ 701 z4≥1, 601 z1+801 z2+131 z3+ 701 z4≥1, 601 z1+801 z2+551 z3+ 81 z4≥1, z1 0, z20, z3 0, z40. 3. Находим с помощью метода линейного программирования все zi,: z1= 0,000747 z2= 0,00069 z 3= 0 z4= 0,00064 4. Находим цену игры: V 1 1   482 . z1  z 2  z 4 0,000747  0,00069  0,00064 По теореме 17 V=V’-301=181. 5. Находим вероятности: p1  z1  V   0,000747 * 482  0,36 , p 2  z 2  V   0,00069 * 482  0,33 , p3  z1  V   0 * 482  0 , p 4  z 2  V   0,00064 * 482  0,31 . 69 Пример решения игровой задачи в MS-Excel. Цех-заготовитель поставляет в сборочный цех детали двух видов «а» и «b». По договору между цехами определены два срока поставок этих деталей в течении рабочего дня. При поставке в первый срок деталей вида «а» сборочный цех платит заготовительному премию 50 руб., при поставке этого же изделия во второй срок выплачивается премия равная 20 руб. При поставке изделий вида «b» в первый срок премия составляет 30 руб., а во второй – 40 руб. Цех-заготовитель – игрок А. Сборочный цех – игрок В. Стратегиями игрока А является получение деталей «а» или «b». Стратегиями игрока В – срок поставки. В результате формализации игры получаем матрицу: 1 срок 2 срок Детали «а» 50 20 Детали «b» 30 40 Как было установлено раньше эта матрица не имеет седловой точки. 1. Целевая функция имеет следующий вид: z1+ z2min, где zi= рj V . 2. Записываем ограничения: 50z1+30z2≥1, 20z1+ 40z2≥1, z1 0, z20. 3. Находим с помощью метода линейного программирования все zi,: - Запускаем Excel. - В ячейки А1 и В1 записываем обозначение неизвестных переменных z1и z2. - В ячейку С2 записываем формулу целевой функции «=А2+В2». 70 - В ячейку С3 записываем формулу первого ограничения С4 записываем формулу второго ограничения «=50*А2+30*В2». - В ячейку «=20*А2+40*В2». - Переходим на вкладку Данные - Запускаем Поиск решения (находится справа на ленте. Если этой команды нет, то её необходимо включить через Параметры – Надстройки). - В параметрах поиска решений: в качестве целевой функции указываем её адрес (ячейка С2); в качестве условия оптимизации указать «минимум»; в качестве изменяемых ячеек указать адреса ячеек z1и z2 (А2 и В2); в качестве ограничений последовательно добавляем условия: A20, B20, C31, C41. - Нажимаем кнопку «Найти решение» и получаем z1= 0,007; z2=0,021. 4. Находим цену игры V  1 1 1    35 . z1  z 2 0,007  0,021 0,028 5. Находим вероятности: p1  z1  V  0,007 * 35  0,25 , p 2  z 2  V  0,021 * 35  0,75 . Литература 1. Исследование операций в экономике: учеб. Пособие /Н.Ш.Кремер, Б.А.Путко, И.М. Тришин, М. Н. Фридман; под ред. проф. Н. Ш. 71 Кремера. – 2-е Изд., перераб. и доп.- М. : Издательство Юрайт: ИД Юрайт, 2010. - 430 с. (Глава 12) . 2. Кремер Н.Ш., Путко Б.А., Тришин И.М. Математика для экономистов: от Арифметики до Эконометрики: учеб-справоч. пособие / под ред. проф. Н. Ш. Кремера. – 2-е изд., перераб. и доп. – М.: Издательство Юрайт: ИД Юрайт, 2010. – 646 с. (Параграфы 10.1 и 10.2). 3. Шапкин А. С. Математические методы и модели исследования операций: Учебник / А. С. Шапкин, В. А. Шапкин — 5-е изд — М: Издательско-торговая корпорация «Дашков и К», 2012. — 400 с. 4. Лабскер Л.Г. Теория игр в экономике (практикум с решения задач) : учебное пособие / Л.Г. Лабскер, Н.А. Ященко ; под ред. Л.Г. Лабскера. – 2-е изд., стер. – М. : КНОРУС, 2013. – 264 с. 72 Лекция 5. Игры с природой. Игры с «природой» являются вырожденным случаем антагонистической игры двух лиц, когда одна сторона имеет возможность строить осмысленные стратегии поведения, а вторая сторона («природа») лишена такой возможности, то есть у второго игрока все ходы являются случайными. Рассматриваемые ситуации не имеют конфликтной окраски. Никто никому сознательно не противодействует. В В1 В2 ... Вn A1 x11 x12 ... x1n A2 x21 x22 ... x2n ... ... ... ... ... Am xm1 xm2 ... xmn А Набор (А1, А2,…, Аm) – стратегии игрока А. Набор (В1, В2,…, Вn) – состояния среды. При этом n>1 и m>1, xij – выигрыш игрока А при соответствующем состоянии среды и выборе i – той стратегии игроком А. В случае известности вероятности состояний природы (qj) оптимальная чистая стратегия определяется по максимальному математическому ожиданию (критерий Байеса-Лапласа): w  max (M ( Ai ))  max ( xi1q1  xi 2 q2  ...  xinqn ) i 1,.... m i 1,.... m Критерии принятия решений в играх «с природой» (в случае неизвестности вероятности состояний природы). 1. Критерий Лапласа. 73 При неизвестных вероятностях состояний «природы» можно принять, что все они равновероятны: q j  1 n Выбор решения определяется формулой: w  max ( i 1 n  xij ) n j 1 (максимум среднего выигрыша по всем стратегиям). 2. Максиминный критерий Вальда. При максиминном критерии Вальда оптимальной считается та стратегия, которая обеспечивает максимум минимального выигрыша по каждой стратегии: w  max min xij . i 1,..., m j 1,..., n Этот критерий отражает принцип гарантированного результата, т. е. лицо принимающее решение (ЛПР) выбирает такую стратегию, которая максимизировала бы его выигрыш в самой неблагоприятной ситуации. 3. Критерий минимаксного риска Сэвиджа. Критерий минимаксного риска Сэвиджа основывается на понятии риска, который интерпретируется как упущенная выгода. Риском игрока при использовании стратегии Ai в состоянии Вj называется разность между выигрышем, который он получил бы, если бы точно знал состояние среды, и выигрышем, который он получит в том же состоянии среды, применяя стратегию Аi. В В1 В2 ... Вn A1 x11 x12 ... x1n A2 x21 x22 ... x2n ... ... ... ... ... Am xm1 xm2 ... xmn А 74 Пусть x21 - максимум первого столбца, xm2 -максимум второго столбца. ... x1n – максимум последнего столбца тогда матрица рисков имеет следующий вид: В В1 В2 ... Вn A1 x21-x11 xm2-x12 ... x1n-x1n A2 x21-x21 xm2-x22 ... x1n-x2n ... ... ... ... ... Am x21-xm1 xm2-xm2 ... x1n-xmn минимаксного риска А Критерий Сэвиджа предполагает, что оптимальной является та стратегия, при которой величина риска в наихудшем случае минимальна: w  min max (rij ) i 1,.... m j 1,.... n (минимум максимумов рисков по каждой стратегии) Критерий Сэвиджа, также как и критерий Вальда, является критерием крайнего пессимизма. Этот критерий отражает принцип гарантированного результата, т. е. лицо принимающее решение (ЛПР) выбирает такую стратегию, которая максимизировала бы его выигрыш в самой неблагоприятной ситуации. 4. Критерий пессимизма-оптимизма Гурвица. Выбор конкретного значения параметра определяется, скорее всего, субъективными факторами: чем опаснее ситуация, тем больше надо «подстраховываться» и тем ближе к единице выбирается значение . 75 При отсутствии каких-либо явных предпочтений вполне логично выбрать  = 0.5. Пример. Режим проверок наличия вируса. Стоимость полной проверки 6000 руб, при этом она занимает 3 часа, ликвидирует вирусы и восстанавливает все файлы. Стоимость минимальной проверки 1500 руб, при этом она занимает 1 час, ликвидирует вирусы, но не восстанавливает все файлы. В день ЭВМ работает 12 часов, один час работы приносит доход в размере 8000 руб. Кроме того, в случае заражения вирусом носителей потребителя организация платит штраф 10000 р., а в случае отказа работы – 15000 р. Строим модель. Расписываем все стратегии и состояния среды. Организация может: 1. Не проводить проверку на вирусы. 2. Делать минимальную проверку на вирусы. 3. Делать полную проверку на вирусы. Состояние среды: 1. ПК не заражены. 2. ПК заражены, но файлы не запорчены. 3. ПК заражены и запорчены файлы. Строим платежную матрицу. Ср. Орг. В1 В2 В3 A1 12*8000=96000 96000-10000= 86000 (12-3)*8000-15000-6000= 51000 A2 11*8000-1500= 86500 11*8000-1500= 86500 (12-1-3)*8000-600015000=43000 A3 9*8000-6000= 66000 9*8000-6000= 66000 9*8000-6000= 66000 76 1. Критерий Лапласа (максимум среднего выигрыша по всем стратегиям). w  max ( i 1 n  xij ) n j 1 Ср. В1 В2 В3 A1 96000 86000 51000 68500 A2 86500 86500 43000 72000 A3 66000 66000 66000 66000 Орг. макс 2. Максиминный критерий Вальда (максимум минимального выигрыша по всем стратегиям). w  max min xij i 1,..., m В1 В2 В3 мин A1 96000 86000 51000 51000 A2 86500 86500 43000 43000 A3 66000 66000 66000 66000 Орг. Ср. j 1,..., n 3. Критерий минимаксного риска Сэвиджа. Ср. В1 В2 В3 A1 96000 86000 51000 A2 86500 86500 43000 A3 66000 66000 66000 Орг. 77 Строим матрицу рисков: Ср. В1 В2 В3 макс A1 500 15000 15000 A2 9500 23000 23000 A3 30000 20500 30000 Орг. 4. Критерий пессимизма-оптимизма Гурвица. w  max ( min ( хij )  (1   ) max ( хij )) j 1,.... n i 1,.... m j 1,.... n Примем =0,5 В1 В2 В3 A1 96000 86000 51000 73500 A2 86500 86500 43000 64750 A3 66000 66000 66000 66000 Орг. Ср. w Получаем: 1. Критерий Лапласа (максимум среднего стратегиям) выигрыша по всем - A2 . 2. Максиминный критерий Вальда (максимум минимального выигрыша по всем стратегиям) – A3. 3. Критерий минимаксного риска Сэвиджа – А1. 4. Критерий пессимизма-оптимизма Гурвица – А1. Допускается использовать в игре с «природой» и смешанные стратегии в случае возможности интерпретации. То есть можно объяснить чередование чистых стратегий во времени или в пространстве. Пример. Агрофирма выращивает культуры: пшеницу, кукурузу и лён. Средняя урожайность (ц/га) культур в зависимости от погоды и стоимость 1 центнера в рублях приведены в таблице. 78 Культура Засушливое лето Нормальное лето Дождливое лето Средняя стоимость Пшеница 20 75 50 1300 Кукуруза 30 54 40 850 Лён 60 30 1950 52 Найти наиболее эффективную схему использования пашни с точки зрения максимума выручки с 1 га. 1. Расписать все возможные действия каждого игрока. Стратегии агрофирмы: А1 - выращивать пшеницу; А2 - выращивать кукурузу; А3 - выращивать лён. Состояние среды: В1 - засушливое лето; В2 - нормальное лето; В3- дождливое лето. 2. Составить выигрыш-функцию каждого игрока (если она представима в аналитическом виде). Выручка с 1 га=Урожайность (ц/га)*Стоимость 1 ц. 3. Вычислить выигрыши каждого игрока в зависимости от одновременных действий игрока и его оппонента. 4. Заполнить игровые матрицы. В1 В2 В3 A1 26000 97500 65000 A2 25500 45900 34000 A3 101400 117000 При решении этой игры получаем: 58500 79 p1=0,17, p2=0,00, p3=0,83; V=59628,1(выручка с 1 га). Таким образом, получаем: для получения максимальной выручки (59628,1 рублей с 1 га) необходимо: 17% площадей засеять пшеницей; 83% площадей засеять льном. При принятии решений в условиях неопределенности существенную помощь может оказать эксперимент, цель которого — уточнить условия в определенной ситуации. Проблема заключается в том, что проведение эксперимента предполагает наличие определенных затрат. Целесообразность эксперимента определяется сравнением между собой суммой необходимых затрат на его проведение и величиной ожидаемого выигрыша. Случай «идеального» эксперимента. «Идеальным» называется эксперимент, который приводит к точному знанию состояния «природы» на момент реализации решения. Пусть заданы: Матрица выигрышей. В В1 ... Вn A1 x11 ... x1n ... ... ... ... Am xm1 ... xmn А Вероятности различных cостояний «природы» Q=(q1, q2, …, qn). Затраты на проведение эксперимента C. Сравним средний выигрыш без проведения эксперимента и средний выигрыш с проведением этого эксперимента. 80 Если эксперимент не проводить, то в качестве решения надо выбрать стратегию, при которой достигается максимальное математическое ожидание выигрыша: w  max (M ( Ai ))  max ( xi1q1  xi 2 q2  ...  xinqn ) i 1,.... m i 1,.... m Это выигрыш без проведения эксперимента. Пусть мы провели эксперимент, в результате которого узнали действительное состояние «природы». Поэтому при подсчете полученного выигрыша после эксперимента будем ориентироваться на максимум выигрыша по каждому состоянию «природы». Максимальный выигрыш при каждом состоянии «природы» равен максимуму по столбцам: w j  max ( xij ) . i 1,.... m Средний выигрыш по всем состояниям «природы» равен ~  w q  w q  ...  w q математическому ожиданию выигрышей – w 1 1 2 2 n n Далее вычтем из среднего выигрыша затраты (С) и получим выигрыш ~ С . от эксперимента: wэ  w Эксперимент проводить целесообразно, если: wэ  w , то есть выигрыш, который можно получить после эксперимента, превосходит выигрыш, который можно было бы получить до эксперимента. Раскроем формулу w  w . э ~ С  w max ( xi1q1  xi 2q2  ... xinqn ) i 1,.... m w1q1  w2 q2  ...  wn qn  С  max ( xi1q1  xi 2 q2  ...  xinqn ) i 1,.... m w1q1  w2 q2  ...  wn qn  max ( xi1q1  xi 2 q2  ...  xinqn )  C i 1,.... m Рассмотрим левую часть последней формулы. В ней из суммы максимумов по столбцам вычитается максимум сумм по строкам. Подобное 81 выражение эквивалентно минимуму сумм строк, в которых стоит разности максимума в столбце с элементом строки. w1q1  w2 q2  ...  wn qn  max ( xi1q1  xi 2 q2  ...  xinqn )  i 1,.... m min ((w  x 1 i 1,.... m i1 )q1  ( w2  xi 2 q2 )  ...  ( wn  xin )qn ) . Формулу w1q1  w2 q2  ...  wn qn  max ( xi1q1  xi 2 q2  ...  xinqn )  C i 1,.... m n переписываем в следующем виде min ( q j (w j xij ))  C . i 1,.... m j 1 n Разность wj-xij =rij – является риском. Формула q r j 1 j ij определяет средний риск. Таким образом условие проведения эксперимента звучит следующим образом: эксперимент имеет смысл проводить, если минимум среднего риска по чистым стратегиям превосходит затраты на эксперимент. n min ( q r )  C i 1,.... m j 1 j ij Алгоритм определения целесообразности проведения эксперимента, который приводит к точному знанию состояния «природы» (идеального эксперимента».   1. Строим матрицу рисков. rij 2. Рассчитываем значение среднего риска по каждой чистой стратегии: n q r j 1 j j 3. Находим минимум. 4. Сравниваем эксперимента: полученный минимум со стоимостью проведения 82 если затраты на эксперимент меньше полученной суммы, то эксперимент проводить целесообразно. Пример. Предприятие желает освоить новый рынок сбыта для своей продукции - творожков с фруктовой начинкой. В качестве начинки предлагается черника, вишня и брусника. Потребительский спрос на эту продукцию имеет следующие вероятностные параметры: потребители предпочтут творожки: с черничной начинкой с вероятностью 0,4; с вишнёвой начинкой с вероятностью 0,25, с брусничной начинкой с вероятностью 0,35. Прибыль (тыс.руб.) от продажи творожков при условии разного предпочтения потребителей приведена в таблице: Предпочитают творог с черникой Предпочитают творог с вишней Предпочитают творог с брусникой Творог черникой с 800 400 500 Творог вишней с 200 850 300 Творог с брусникой 250 350 900 Для уменьшения неопределенности предприятие предполагает провести маркетинговое исследование, стоимость которого равна 200 тыс. руб. Определить целесообразность этого исследования. 1. Расписать все возможные действия каждого игрока. Стратегии предприятия: А1 Выйти на рынок с творожками с черничной начинкой. А2 Выйти на рынок с творожками с вишнёвой начинкой. А3 Выйти на рынок с творожками с брусничной начинкой. 83 Состояния среды: В1 Предпочитают творожки с черничной начинкой (0,4). В2 Предпочитают творожки с вишнёвой начинкой (0,25). В3 Предпочитают творожки с брусничной начинкой (0,35). 2. Составить выигрыш-функцию каждого игрока (если она представима в аналитическом виде). 3. Вычислить выигрыши каждого игрока в зависимости одновременных действий игрока и его оппонента. 4. Заполнить игровые матрицы. В В1 В2 В3 A1 800 400 500 A2 200 900 300 A3 250 350 850 Q 0,4 0,25 0,35 А Вычислим матрицу рисков: Ср. В1 В2 В3 A1 500 350 A2 600 550 A3 550 550 Макс 800 900 850 Орг. Рассчитываем значение среднего риска по каждой чистой стратегии: от 84 Ср. Орг. В1 В2 В3 n  q (w j 1 j A1 500 350 247,5 A2 600 550 432,5 A3 550 550 357,5 Макс 800 900 850 Q 0,4 0,25 0,35 Находим минимум j xij ) 247,5 Маркетинговое исследование проводить целесообразно поскольку минимум среднего риска превосходит затраты на исследование - 200 тыс. руб. Литература 1. Колобашкина Л. В. Основы теории игр : учебное пособие/Л. В. Колобашкина. — 3-е изд., испр. и доп. —М. : БИНОМ. Лаборатория знаний, 2016.— 195 с. 85 Лекция 6. Биматричные игры. Биматричной называется конечная бескоалиционная игра двух лиц, выигрыш-функция которых описывается отдельными матрицами для каждой конфликтующей стороны. Пара чистых стратегий (k, l) является ситуацией равновесия в биматричной игре, если выполняются неравенства: akl≥ ail , i = 1, . . . , m, bkl ≥ bkj, j = 1, . . . , n. Алгоритм поиска равновесной ситуации в чистых стратегиях в биматричной игре: 1. В каждом столбце матрицы A пометьте максимальные элементы. 2. В каждой строке матрицы В пометьте максимальные элементы. 3. Выпишите адреса всех ячеек, у которых адрес в матрице А совпал с адресом в матрице В. Пример. Две страховые компании оказывают в одном населенном пункте одинаковые страховые услуги. Каждая из них для повышения прибыли может установить один из следующих страховых тарифов: 1000 руб – низкий тариф, 2000 руб – средний тариф, 4000 – высокий тариф. Потребители страховых услуг разделены на бедное, среднее и богатое население. Население Бедные Среднего достатка Богатые 9000 10000 1000 86 Богатые выбирают самые высокие тарифы, считая, что там выше качество и всегда страхуются. Население со средним достатком обычно выбирает тариф ниже, но по повышенному тарифу не страхуются. Бедное населения страхуется только по низкому тарифу, а в случае его отсутствия отказывается от страхования. Доход страховой компании вычисляется как произведение числа застрахованных на тариф. Если тарифы у компаний одинаковые, то население страхуется у них в равных количествах. Составим платежные матрицы: Игрок А В 1000 2000 Игрок В 4000 А В 1000 2000 4000 А 1000 10 млн 19 млн 19 млн 1000 10 млн 2 млн 4 млн 2000 2 млн 11 млн 20 млн 2000 19 млн 11 млн 4 млн 4000 4 млн 4 млн 2 млн 4000 19 млн 20 млн 2 млн Ситуацией равновесия являются стратегии (А1, В1). Ситуация равновесия не самая лучшая ситуация, но она устойчивая. Теорема Нэша (основная теорема биматричных игр). Каждая биматричная игра имеет хотя бы одну ситуацию равновесия, возможно, в смешанных стратегиях. Ситуация равновесия в смешанных стратегиях для биматричной игры представляет собой пару таких смешанных стратегий р=(р 1,р2,…,рm) и q=(q1,q2,…,qn), которые удовлетворяют неравенствам: Aq(pTAq)(1)m1 =HA(1)m1 Втp (pтВq)(1)n1 =HB(1)nx1 87 рi=1 qj=1 где (1)m1, (1)n1— векторы размерности (mx1), (nx1) соответственно, состоящие из одних единиц: 1    1   ...   1    Отношения доминирования в биматричных играх Отношения доминирования в биматричной игре отличаются от отношений доминирования в антагонистической игре поскольку каждая матрица содержит выигрыши (доминируемые всегда больше). В биматричной игре механизм упрощения матриц зависит не только от доминирования чистых стратегий, но и от критериев задачи. Критерии задачи: 1. Сторона А (В) хочет максимизировать свой выигрыш и минимизировать выигрыш противной стороны. 2. Каждая из сторон хочет максимизировать свой выигрыш. 3. Каждая из сторон хочет минимизировать выигрыш противника. Алгоритм упрощения задачи: Критерий 1 относительно игрока А (сторона А хочет максимизировать свой выигрыш и минимизировать выигрыш В). - Максимизация своего выигрыша. 1. Определяем, с какой матрицей будем работать. Поскольку речь идет о выигрышах стороны А, выбираем для сокращения ту матрицу, которая содержит данные выигрыши, т. е. матрицу А. 2. Активной (или действующей) в данном критерии является сторона А, следовательно, управлять она может только своими стратегиями, выигрыши при которых располагаются по строкам. Следовательно, сравнивать между собой мы будем элементы соответствующих строк. 88 3. Так как сторона А хочет максимизировать свой выигрыш, то свои стратегии, которые содержат меньший выигрыш, она применять не будет. Таким образом, удалению из матрицы А подлежат доминируемые строки. 4. Поскольку сторона А отказалась от использования некоторых своих стратегий, то соответствующие ей строки удаляется также и из матрицы В, независимо от ее элементов. - Минимизация выигрыша другой стороны. 1. Поскольку речь идет о выигрышах стороны В, выбираем для сокращения ту матрицу, которая содержит данные выигрыши, т. е. матрицу В. 2. Активной (или действующей) в данном критерии является сторона А, следовательно, управлять она может только своими стратегиями, выигрыши по которым располагаются по строкам. Следовательно, сравнивать между собой мы будем элементы соответствующих строк матрицы В. 3. В связи с тем что сторона А хочет минимизировать выигрыш стороны В, т.е. свои стратегии, которые содержат больший выигрыш для противника, она применять не будет. Таким образом, удалению из матрицы В подлежат доминирующие строки. 4. Поскольку сторона А отказалась от использования некоторых своих стратегий, то соответствующие им строки удаляется также и из матрицы А. Критерий 2 (стороны хотят максимизировать свой выигрыш). - Максимизация выигрыша игроком А. 1. Определяем, с какой матрицей будем работать. Поскольку речь идет о выигрышах стороны А, выбираем для сокращения ту матрицу, которая содержит данные выигрыши, т. е. матрицу А. 2. Активной (или действующей) в данном критерии является сторона А, следовательно, управлять она может только своими стратегиями, выигрыши при которых располагаются по строкам. Следовательно, сравнивать между собой мы будем элементы соответствующих строк. 89 3. Так как сторона А хочет максимизировать свой выигрыш, то свои стратегии, которые содержат меньший выигрыш, она применять не будет. Таким образом, удалению из матрицы А подлежат доминируемые строки. 4. Поскольку сторона А отказалась от использования некоторых своих стратегий, то соответствующие ей строки удаляется также и из матрицы В, независимо от ее элементов. - Максимизация выигрыша игроком В. 1. Определяем, с какой матрицей будем работать. Поскольку речь идет о выигрышах стороны В то выбираем для сокращения ту матрицу, которая содержит данные выигрыши, т. е. матрицу В. 2. Активной (или действующей) в данном критерии является сторона В, следовательно, управлять она может только своими стратегиями, выигрыши которых располагаются по столбцам. Следовательно, сравнивать между собой мы будем элементы соответствующих столбцов. 3. Так как сторона В хочет максимизировать свой выигрыш, то свои стратегии, которые содержат меньший выигрыш, она применять не будет. Таким образом, удалению из матрицы В подлежат доминируемые столбцы. 4. Поскольку сторона В отказалась от использования некоторых своих стратегий, то соответствующие ей строки удаляется также и из матрицы А, независимо от ее элементов. Критерий 3 (каждая из сторон хочет минимизировать выигрыш противника). - Минимизация игроком А выигрыша игрока В. 1. Поскольку речь идет о выигрышах стороны В, выбираем для сокращения ту матрицу, которая содержит данные выигрыши, т. е. матрицу В. 2. Активной (или действующей) в данном критерии является сторона А, следовательно, управлять она может только своими стратегиями, выигрыши по которым располагаются по строкам. Следовательно, сравнивать между собой мы будем элементы соответствующих строк. 90 3. Так как сторона А хочет минимизировать выигрыш стороны В, то свои стратегии, которые содержат больший выигрыш для противника, она применять не будет. Таким образом, удалению из матрицы В подлежат доминирующие строки. 4. Поскольку сторона А отказалась от использования некоторых своих стратегий то соответствующие им строки удаляется также и из матрицы А. - Минимизация игроком В выигрыша игрока А. 1. Так как речь идет о выигрышах стороны А, выбираем для сокращения ту матрицу, которая содержит данные выигрыши, т. е. матрицу А. 2. Активной в данном критерии является сторона В. Следовательно, управлять она может только своими стратегиями, выигрыши по которым располагаются по столбцам. Следовательно, сравнивать между собой мы будем элементы соответствующих столбцов. 3. Поскольку сторона В хочет минимизировать выигрыш стороны А, то свои стратегии, которые содержат больший выигрыш для противника, она применять не будет. Таким образом, удалению из матрицы А подлежат доминирующие столбцы. 4. В связи с тем что сторона В отказалась от использования некоторых своих стратегий, то соответствующие им столбцы и из матрицы В. Пример. Каждая из сторон хочет максимизировать свой выигрыш. В 1000 2000 4000 А В 1000 2000 4000 А 1000 10 млн 19 млн 19 млн 1000 10 млн 2 млн 4 млн 2000 2 млн 11 млн 20 млн 2000 19 млн 11 млн 4 млн 4000 4 млн 4 млн 2 млн 4000 19 млн 20 млн 2 млн 91 - Максимизация выигрыша игроком А. Стратегия А3 (тариф 4000 руб.) доминируется стратегией А1 (тариф 1000 руб.), следовательно её игрок А не будет применять ни когда, поэтому её можно удалить из матрицы. Поскольку эту стратегию не будет применять игрок А ни когда, то и у игрока В ни когда не будут достигнуты выигрыши последней сроки его матрицы, поэтому и у этой матрицы можно удалить последнюю строку. В результате получаем: В 1000 2000 4000 А В 1000 2000 4000 А 1000 10 млн 19 млн 19 млн 1000 10 млн 2 млн 4 млн 2000 2 млн 11 млн 20 млн 2000 19 млн 11 млн 4 млн На этом максимизация выигрыши игроком А заканчивается, поскольку у него нет больше доминируемых стратегий. - Максимизация выигрыша игроком В. Стратегия В1(тариф 1000 руб.) строго доминирует обе другие стратегии, поэтому из его матрицы можно удалить столбцы 2 и 3. Соответственно и в матрице игрока А можно удалить столбцы 2 и 3 поскольку эти выигрыши А не получит, так как эти стратегии ни когда не применит игрок В. В результате получаем: В 1000 А В 1000 А 1000 10 млн 1000 10 млн 2000 2 млн 2000 19 млн В этой ситуации игрок А всегда будет использовать 1 стратегию, что является точкой равновесия. 92 Методы нахождения смешанных стратегий биматричных игр. Аналитическое решение биматричных игр 2×2 (метод 1) В В1 В2 А В В1 В2 А А1 а11 а12 А1 в11 в12 А2 а21 а22 А2 в21 в22 Поскольку у игроков по две чистых стратегии, то любая смешанная стратегия имеет вид (р, 1-р) и (q, 1-q). Запишем формулы платежных функций HA=(pTAq) =a11pq+ a12p(1-q)+ a21(1-p)q+ a22(1-p)(1-q)= a11pq+ a12p-a12pq+ a21q-a21pq+ a22-a22p-a22q+a22pq (1) HВ=(pтВq)=в11pq+ в12p(1-q)+ в21(1-p)q+ в22(1-p)(1-q)= в11pq+ в12p-в12pq+ в21q-в21pq+ в22-в22p-в22q+в22pq (2) Для нахождения максимумов этих функций необходимо найти производные их и приравнять производные 0. (HA)р =(a11pq+ a12p-a12pq+ a21q-a21pq+ a22-a22p-a22q+a22pq)р= a11q+ a12- a12q- a21q- a22 +a22q=0. (HВ)q =(в11pq+ в12p-в12pq+ в21q-в21pq+ в22-в22p-в22q+в22pq)q= в11p -в12p + в21 -в21p -в22 +в22p=0. Таким образом получаем: (HA)р =a11q+a12-a12q-a21q-a22+a22q=0 (HВ)q =в11p-в12p+ в21-в21p-в22+в22p=0 Отсюда: p в22  в21 (в11  в22 )  (в12  в21 ) q a22  a12 (a11  a22 )  (a12  a21 ) Выигрыши (цену игры) находим, подставив значения p и q в выражения (1) и (2). 93 Пример. На каждой из двух торговых баз ассортиментный минимум составляет один и тот же набор из 2 видов товара. Каждая база должна поставить в свой магазин только один из этих видов товара. Магазины (A и В) конкурируют между собой. Один и тот же вид товара в обоих магазинах продается по одной и той же цене. Однако товар, поставляемый в магазин В, более высокого качества. Если магазин А завезет с базы товар отличный от товара, завезенного в магазин В, то этот товар будет пользоваться спросом и магазин от его реализации получит прибыль: при товаре 1 типа 40 у.д.е. , при товаре 2 типа – 25 у.д.е. Если же в магазины А и В завезены товары одинакового вида то этот товар в магазине А спросом пользоваться не будет, поскольку такой же товар, по такой же цене, но более высокого качества можно купить в магазине В, поэтому а этом случае магазин А прибыль не получит. Магазин В продает товар лучшего качества, однако в случае если в магазинах товары одного типа, то прибыль магазина В будет меньше, чем если бы в магазинах были товары разного типа. Прибыль магазина: для товара 1 типа в случае наличия такого же типа товара 25 у.д.е., при отсутствии – 30 у.е.д. Для товара 2 типа соответственно – 15 у.е.д. и 27 у.д.е. Составим платежные матрицы: 1 тип 2 тип 1 тип 40 2 тип 25 1 тип 2 тип 1 тип 25 27 2 тип 30 15 94 p в22  в21 15  30  15 15     0,88 (в11  в22 )  (в12  в21 ) (15  25)  (27  30)  17 17 q a22  a12 0  40  40 8     0,6 (a11  a22 )  (a12  a21 ) (0  0)  (25  40)  65 13 HA=a11pq+ a12p-a12pq+ a21q-a21pq+ a22-a22p-a22q+a22pq=  0 15 8 15 15 8 8 15 8 8 15 15 8   40 *  40 *   25 *  25 *   0 *  0 *  0 *   17 13 17 17 13 13 17 13 13 17 17 13  40 * 15 15 8 8 15 8  40 *   25 *  25 *   15,38462 17 17 13 13 17 13 HВ=в11pq+ в12p-в12pq+ в21q-в21pq+ в22-в22p-в22q+в22pq =  25  15 8 15 15 8 8 15 8 8 15 15 8   27 *  27 *   30 *  30 *   15 *  15 *  15 *   17 13 17 17 13 13 17 13 13 17 17 13 =29,04977 Метод 2. 1. С помощью аппарата линейного программирования находятся оптимальные стратегии игрока В. 2. Оптимальные стратегии игрока А находятся как в игре с природой c известными состояниями (максимум математического ожидания выигрыша). Пример. Две страховые компании оказывают в одном населенном пункте одинаковые страховые услуги. Каждая из них для повышения прибыли может установить один из следующих страховых тарифов: 1000 руб – низкий тариф, 2000 руб – средний тариф, 4000 руб – высокий тариф. Потребители страховых услуг разделены на бедное, среднее и богатое население. Богатые выбирают самые высокие тарифы, считая, что там выше качество и всегда страхуется. Население со средним достатком обычно выбирает пониженный тариф, но в случае наличия только повышенного тарифа отказывается от страхования. Бедное населения страхуется только по низкому тарифу, а в случае его отсутствия отказывается от страхования. 95 Доход страховой компании вычисляется как произведение числа застрахованных на тариф. Если тарифы у компаний одинаковые, то население страхуется у них в равных количествах. Составляем игровые матрицы: Страховая компания №1 Страховая компания №1 (млн руб) В В1 А В2 В3 В В1 А В2 В3 A1 2 4 4 A1 2 20 19 A2 20 1 1 A2 4 1 19 A3 19 19 10 A3 4 1 10 В результате решения задачи для игрока В методом линейного программирования находим: q1 =0,905, q2=0,095, q3=0. Цена игры для игрока В равна 3,714 млн.руб. Используем полученные вероятности для нахождения лучшей чистой стратегии игрока А. В В1 В2 В3 М(Аi) A1 2 20 19 3,710 A2 4 1 19 3,715 A3 4 1 10 3,715 0,095 0,000 А q 0,905 Максимум математического ожидания выигрыша достигается на стратегиях А2 и А3. 96 Метод 3. Используя способы упрощения матриц свести её к задаче 2х2. Метод 4. Алгоритм Лемке-Хоусона (в пособии не рассматривается). Литература 1. Колобашкина Л. В. Основы теории игр : учебное пособие/Л. В. Колобашкина. — 3-е изд., испр. и доп. —М. : БИНОМ. Лаборатория знаний, 2016.— 195 с. 2. Невежин В.П. Теория игр. Примеры и задачи: учебное пособие / В.П. Невежин. — М. : ФОРУМ : ИНФРА-М, 2016. — 128 с. 97 Лекция 7. Позиционные игры. Позиционной игрой называется бескоалиционная игра, моделирующая процессы последовательного принятия решений игроками в условиях меняющейся во времени информации. Процесс самой игры состоит в последовательных переходах от одного состояния игры к другому, которые осуществляются либо путем выбора игроками одного из возможных действий в соответствии с правилами игры, либо случайным образом. Формализация позиционной игры, как правило, представляется в виде дерева. Деревом называют связный граф без циклов (Рисунок 7.1). Исходная вершина называется корнем дерева. Рисунок 7.1 Основными свойствами дерева игры являются: - дерево содержит одну единственную начальную вершину (“корень” дерева), в которую не входит ни одна ветвь; 98 - дерево имеет не менее одной вершины, из которой не выходит ни одна ветвь (эти вершины называются конечными вершинами); - из корня дерева имеется единственный путь к каждой из остальных вершин дерева. Состояния игры (кружки) называются узлами или позициями (отсюда и название — позиционные игры), а возможные выборы в каждой позиции (дуги) — альтернативами. Окончательные позиции (черные кружки) называются вершинами (Рисунок 7.2). Рисунок 7.2. Символы в кружке указывают, кто из игроков (О, А или В) делает очередной ход в данной позиции. Символом О обычно обозначается ход в игре, осуществляемый не игроком, а каким-нибудь случайным механизмом (природой). Фактически процесс игры состоит в переходе от начальной позиции (корня дерева) к вершине через промежуточные позиции. Каждая вершина определяет единственную цепь (последовательность идущих друг за другом 99 дуг), связывающую начальную позицию с данной вершиной. Такая цепь называется партией. Число различных партий равно числу вершин. Каждая дуга обозначает ход из данного узла (позиции). В каждой вершине, обычно, задан числовой выигрыш игрока А. Партия начинается с корня. Каждый ход есть изменение позиции, соответствующее перемещению из одной вершины на какую-нибудь из примыкающих верхних вершин. Число ветвей у вершины равно числу вариантов хода. Партия заканчивается при достижении одной из конечных вершин. Различают позиционные игры с неполной и полной информацией. В позиционных играх с неполной информацией (например, домино) игрок, делающий ход, не знает точно, в какой именно позиции дерева игры он фактически находится. В позиционных играх с полной информацией (например, шашки, шахматы, крестики-нолики и пр.) каждый игрок при своем ходе знает ту позицию дерева игры, в которой он находится. На рисунке 7.3 изображено дерево одной партии известной игры «Крестики-нолики». В правом верхнем углу изображена сама партия. Игрок А играет крестиками. Игрок В – ноликами. Каждая ячейка игровой таблицы имеет адресацию, какая принята в MS-Excel. В самом начале игры у игрока А есть 9 вариантов поставить крести: А1, А2, А3, В1,В2,В3,С1,С2,С3. Он ставит крестик в позицию А3. Следующий ход игрока В. У него вариантов хода на один меньше, поскольку одна ячейка уже занята крестиком. Пусть он ставит нолик в позицию В1. Далее у игрока А ещё меньше вариантов хода и так далее. Пусть А поставит крестик в ячейку В2. Далее игрок В ставит нолик в ячейку А1, а игрок А следующим ходом в С1. А выиграл на пятом ходу. 100 Рисунок 7.3. В игре «Крестики-нолики» имеется 9! партий (362 880). Чистой стратегией в позиционной игре называется последовательность ходов игрока, выбранная им в зависимости от информации о ходах другого игрока и ходах игрока О (природы). Чистая стратегия в позиционной игре – это вектор размерности, равной числу позиций соответствующего игрока (числу узлов, в которых игрок осуществляет свой ход). Общее количество этих узлов зависит от вариантов хода игрока в позициях и количества ходов игры. Позиционную игру можно свести к матричной игре. Данный процесс называется нормализацией позиционной игры. Однако для многоходовых игр этот процесс очень трудный. Рассмотрим пример игры с полной информацией, состоящей из двух ходов. 101 1-й ход. Игрок А выбирает число х из множества двух чисел {1,2}. 2-й ход. Игрок В выбирает число у из множества двух чисел {1, 2}, зная, какое число х выбрал игрок А. После второго хода игрок А получает выигрыш за счет игрока В (смотри Рисунок 7.4). Рисунок 7.4 Функция Н(x, у) выплат игроку А за счет игрока В: Н(1, 1) = 1, (1) Н(2, 1) = -2, (2) Н(1, 2) = -1, (3) Н(2, 2) =2. (4) У игрока А две стратегии: – выбрать 1 – выбрать 2 У игрока В 4 стратегии: – выбрать 1 после выбора игроком А – 1 (1,1) – выбрать 2 после выбора игроком А – 1 (1,2) – выбрать 1 после выбора игроком А – 2 (2,1) – выбрать 2 после выбора игроком А – 2 (2,2) Чтобы привести данную позиционную игру к матричной необходимо как-то по-другому обозначить стратегии игрока В, поскольку его альтернативы зависят от выбора игрока А и в этом случае в игровой таблице будут не заполненные клетки. Например на пересечении стратегии игрока А 102 выбора 1 и стратегии игрока В выбора какого-либо числа после выбора игроком А числа 2. Стратегию игрока В удобно описывать упорядоченной парой [y1 ,y2 ]. y1 — альтернатива, выбираемая игроком В при условии, что игрок А выбрал первую свою альтернативу (1). y2 — альтернатива, выбираемая игроком В при условии, что игрок А выбрал вторую свою альтернативу (2). Таким образом альтернативы В получают следующую трактовку: В1– [1,1] игрок выбирает 1 при любом выборе игрока А (1,1) и (2,1). В2 - [1,2] игрок выбирает значение равное выбранному игроком А (1,1) и (2,2). В3 – [2,1] игрок выбирает значение отличное от выбранного игроком А (1,2) и (2,1). В4 – [2,2] - игрок выбирает 2 при любом выборе игрока А (1,2) и (2,2). Занесем функцию выигрыша в матрицу: Далее В1 В2 В3 В4 [1,1] [1,2] [2,1] [2,2] А1-1 Н(1, 1) Н(1, 1) Н(1, 2) Н(1, 2) А2-2 Н(2, 1) Н(2, 2) Н(2, 1) Н(2, 2) заменим выигрыш-функции конкретными указанными в (1), (2),(3),(4). В1 В2 В3 В4 [1,1] [1,2] [2,1] [2,2] А1-1 1 1 -1 -1 А2-2 -2 2 -2 2 значениями, 103 У игрока В есть заведомо не выгодная стратегия (В2). Она строго доминируется стратегиями В3 и В4. В игре есть седловая точка (А1;В3). Выигрыш игрока А – это -1. Нормализация двухходовой игры с неполной информацией. Изменим условие предыдущего примера. 1-й ход. Игрок А выбирает число х из множества двух чисел {1,2}. 2-й ход. Игрок В выбирает число у из множества двух чисел {1, 2}, при этом не зная, какое число х выбрал игрок А. У игрока А две стратегии: - выбрать 1 – выбрать 2 У игрока В тоже 2 стратегии, поскольку он не знает, какое число выбрал игрок А: – выбрать 1 – выбрать 2. В результате получаем матрицу: В1-1 В2-2 А1-1 1 -1 А2-2 -2 2 Седловой точки нет. Поэтому решение игры можно найти с помощью аналитического метода решения игры 2х2. p1o  V х22  х21 2  (2) 4   . ( х11  х22 )  ( х12  х21 ) (1  2)  (1  2) 6 1* 2  (1) * (2) 2  2 0    0. 6 6 6 104 Из этого видно, что отсутствие у игрока В сведений о выборе, сделанном игроком А, приводит к уменьшению количества его возможных стратегий, а также приводит к менее благоприятному исходу игры. Теорема. В любой конечно-шаговой игре с полной информацией на конечном древовидном графе существует ситуация абсолютного равновесия по Нэшу. Определение. Ситуация равновесия по Нэшу4 называется ситуацией абсолютного равновесия по Нэшу в игре, если данная ситуация, является ситуацией равновесия по Нэшу в подыгре. Подыгрой называется подграф дерева игры. В случае описанной выше игры «Крестики-нолики» подыгра – это ограниченный пунктирной линией часть дерева игры (Рисунок 7.5). 4 Равновесие по Нэшу – это тип решений игры двух и более игроков, в котором ни один участник не может увеличить выигрыш, изменив своё решение в одностороннем порядке, когда другие участники не меняют решения. 105 Рисунок 7.5. Согласно этого определения для нахождения равновесия достаточно проанализировать какой-нибудь подграф (подигру). Нахождение равновесной ситуации в конечно-шаговой игре с полной информацией на конечном древовидном графе может осуществляться разными методами: 1. Просчитать выигрыши по всем партиям и выбрать партию с наибольшими выигрышами для обоих игроков; 2. Методом динамического программирования. Первый способ не всегда применим, поскольку может не оказаться одной партии дающей максимальный выигрыш для обоих игроков. Второй способ даёт решение всегда. Динамическое программирование представляет собой математический аппарат, позволяющий быстро находить оптимальное решение в случае, 106 когда анализируемая ситуация не содержит факторов неопределенности, но имеется большое количество вариантов поведения, приносящих различные результаты, среди которых необходимо выбрать наилучший. Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы не было первоначальное поведение последующее решение относительно состояния, системы должно и первоначальное решение, оптимальное поведение определять полученного в результате первоначального решения. При решении задач методом динамического программирования весь многошаговый процесс проходится дважды: сначала от конца к началу (или наоборот), в результате чего формируются последовательности условных оптимальных управлений — альтернатив (определяющих оптимальные пути при условии попадания в конкретную позицию) и условные выигрыши. Затем от начала к концу, в результате чего формируется оптимальная партия игры. Во время первого прохода во всех позициях дерева игры определяем значение функции Беллмана (функции выигрыша). Пример 1. Две страховые компании оказывают в одном населенном пункте одинаковые страховые услуги. Тарифы устанавливаются и заключаются договорами на год. Каждая из них для повышения прибыли может на следующий год установить один из следующих страховых тарифов: 1000 руб – низкий тариф, 3000 – высокий тариф. Потребители страховых услуг разделены на бедное, среднее и богатое население: 107 Население 9000 Бедные Среднего достатка 10000 1000 Богатые Богатые выбирают тарифы повыше, считая, что там выше качество и всегда страхуются. Население со средним достатком обычно выбирает тариф пониже, но всегда страхуются. Бедное населения страхуется только по низкому тарифу, а в случае его отсутствия отказывается от страхования. Доход страховой компании вычисляется как произведение числа застрахованных на тариф. Если тарифы у компаний одинаковые, то население страхуется у них в равных количествах. Составим матрицы доходов: А В 1000 В 3000 А В 1000 3000 3 млн А 1000 10 млн 19 млн 1000 10 млн 3000 3 млн 16,5 млн 3000 19 млн 16,5 млн Допустим необходимо фирме – игроку А, выработать стратегию поведения на 3 года, дающую максимум прибыли. Учитывая, что каждый год одна из этих фирм может изменить тариф, подобная игра будет выглядеть как указано на Рисунке 7.6. В начале игры фирма В имеет высокий тариф. 108 В узлах дерева написана буква, обозначающая какой игрок ходит в этой позиции (А или В). На дугах, соответствующих разным альтернативам стоят соответствующие тарифы Н – низкий тариф, В – высокий тариф. Около вершин в скобках записаны выигрыши игроков, полученные в результате реализации выбранной альтернативы, сначала идет выигрыш игрока А, затем выигрыш игрока В. Красным цветом обозначены вершины дерева, то есть конечные позиции игры с выигрышами в этих позициях. Играем за игрока А. Пронумеруем все узлы (вершины, соответствующие ходам игроков) и конечные вершины. Узлы являются множеством очередности игроков. Они определяют размерность стратегии игроков. У игрока А стратегия представляет собой вектор размерности 5. У игрока В стратегия представляет собой вектор размерности 10 (см. Рисунок 7.7). Рисунок 7.6 109 Рисунок 7.7. 1. Просчитаем суммарный выигрыш во всех партиях. Партия 1. А:10+10+10+19=49 В: 10+10+10+3=33 Партия 2. А:19+10+10+19=58 В: 3+10+10+3=26 Партия 3. А: 3+3+10+19=35 В: 19+19+10+3=51 Партия 4. А:16,5+3+10+19=47,5 В: 16,5+19+10+3=47,5 Партия 5. А:10+19+19+19=67 В: 10+3+3+3= 19 Партия 6. А:19+19+19+19=76 В: 3+3+3+3= Партия 7. А: 3+19+19+19=60 В: 19+3+3+3= 28 Партия 8. А:16,5+19+19+19=73,5 В: 16,5+3+3+3= Партия 9. А:10+10+3+16,5=39,5 В:10+10+19+16,5=55,5 Партия 10.А:19+10+3+16,5=48,5 В: 3+10+19+16,5=48,5 Партия11.А:3+19+3+16,5=41,5 В:19+3+19+16,5=57,5 Партия12. А:16,5+19+3+16,5=64 В:16,5+3+19+16,5=64 Партия13.А:10+19+16,5+16,5=62 В:10+3+16,5+16,5= 46 Партия14.А:19+19+16,5+16,5=72 В: 3+3+16,5+16,5= 39 12 25,5 110 Партия15.А:3+16,5+16,5+16,5=55,5 В:19+16,5+16,5+16,5=68,5 Партия16. А:16,5+16,5+16,5+16,5=66 В:16,5+16,5+16,5+16,5=66 Из представленного выше списка партий видно, что одной партии, максимизирующей выигрыш сразу обоим игрокам, нет, поэтому решим игру методом динамического программирования. Начинаем с узла В3. Выбор делает игрок В. Если он выберет высокий тариф, то получит выигрыш 3 млн.руб., а если низкий, то 10. Он выбирает тариф Н FB(B3)=10; FA(B3)=10; Отмечаем ветвь Н. Опускаемся в узел А2. Выбор делает игрок А. При выборе Н А получает выигрыш=10+FA(B3)=10+10=20. Подсчитаем выигрыш А при выборе В. Для этого необходимо рассмотреть партии 3 и 4. Рассматриваем узел В4. Выбор делает игрок В. При выборе Н выигрыш 19, при выборе В – 16,5 FВ(В4)=19. FA(В4)=3. Отмечаем ветвь Н. Подсчитываем выигрыш игрока А в узле А2 при выборе В =3+FA(В4)=6. При выборе Н FA(А2)=20  FA(А2)=20 и отмечаем ветвь Н. FВ(А2)= FВ(В3)+10=20 Опускаемся в узел В1. Выбор делает игрок В. При выборе игроком В Н он получит выигрыш 10+ FВ(А2)=30. Чтобы вычислить выигрыш игрока В при выборе В необходимо рассмотреть партии 5, 6, 7, 8. В узле В5 выбор делает игрок В. При выборе Н он получит выигрыш 10, при выборе В – 3 FВ(В5)=10, FА(В5)=10. Отмечаем ветвь Н. В узле А3 выбор делает игрок А. При выборе Н он получит выигрыш 19+FА(В5)=19+10=29. Чтобы вычислить выигрыш при выборе В рассматриваем узел В6. В узле В6 выбор делает игрок В. При выборе Н он получит выигрыш 19, при выборе В – 16,5  FВ(В6)=19. FА(В6)=3. Отмечаем ветвь Н. 111 В узле А3 игрок А при выборе Н получит выигрыш 29, при выборе В FА(В6)+16,5=3+16,5=19,5  FА(А3)=29. Отмечаем ветвь Н. FВ(А3)= FВ(В5)+3=10+3=13. В узле В1 игрок В при выборе Н получит выигрыш 30, при выборе В FВ(А3)+3=13+3=16  FВ(В1)=30. Отмечаем ветвь Н. FА(В1)= FА(А2)+10=20+10=30. Опускаемся в узел А1. Выбор делает игрок А. При выборе Н А получает выигрыш=19+FA(B1)=19+30=49. Для подсчета выигрыша при выборе В необходимо рассмотреть партии с 9 по 16. Партия 9. Узел В7. Выбор делает игрок В. При выборе Н он получает выигрыш=10, при выборе В – 3 FВ(B7)=10. Отмечаем ветвь Н. FА(B7)=10. Опускаемся в узел А4. Выбор делает игрок А. При выборе Н он получает выигрыш= FА(B7)+10=20. Для подсчета выигрыша при выборе В рассматриваем узел В8. В узле В8 выбор делает игрок В. При выборе Н он получает выигрыш 19, при выборе В – 16,5  FВ(B8)=19. Отмечаем ветвь Н. FА(B8)=3. Подсчитываем выигрыш игрока А в узле А4. При выборе Н он получает выигрыш 20, при выборе В – FА(B8)+19=3+19=22  FА(А4)=22. Отмечаем ветвь В. FВ(А4)=22. Опускаемся в узел В2. Выбор делает игрок В. При выборе Н он получает выигрыш FВ(А4)+19=22+19=41. Для расчета выигрыша при выборе В необходимо рассмотреть партии 13,14,15,16. Рассматриваем узел В9. Выбор делает игрок В. При выборе Н он получает выигрыш 10, при выборе В – 3  FВ(В9)= 10, отмечаем ветвь Н. FА(В9)=10. 112 Опускаемся в узел А5. Выбор делает игрок А. При выборе Н он получает выигрыш FА(В9) +19=10+19=29. Далее рассматриваем партии 15 и 16. В узле В10 выбор делает игрок В. При выборе Н он получает выигрыш 19, при выборе В он получает 16,5 FВ(В10)=19. Отмечаем ветвь Н. FА(В10)=3. В узле А5. При выборе Н игрок А получает выигрыш 29, при выборе В он получает FА(В10) +16,5=3+16,5=19,5 FА(А5)=29. Отмечаем ветвь Н. FВ(А5)= FВ(В9)+ 3 =13. Возвращаемся в узел В2. При выборе Н игрок В получает выигрыш FВ(А4)+19=22+19=41. При выборе В он получает FВ(А5)+16,5=13+16,5=29,5 FВ(В2)=41. Отмечаем ветвь Н. FА(В2)= FА(А4)+ 3 =22+3=26. Возвращаемся в узел А1. При выборе Н игрок А получает выигрыш =49. При выборе В он получает FА(В2)+16,5=26+16,5=42,5 FА(А1)=49. Отмечаем ветвь Н. FВ(А1)= FВ(В1)+ 3 =30+3=33. Таким образом, оптимальная стратегия игрока А это: Позиция А1 А2 А3 А4 А5 Ход Н Н Н В Н Это интерпретируется следующим образом: если игрок А находится в позиции А1, то он должен сходить Н (выбрать низкий тариф); если он находится в позиции А2, то он должен сходить Н (выбрать низкий тариф); если он находится в позиции А3, то он должен сходить Н (выбрать низкий тариф); и т.д. 113 Оптимальная стратегия игрока В это: Позиция В1 В2 В3 В4 В5 В6 В7 В8 В9 В10 Ход Н Н Н Н Н Н Н Н Н Н Эти ходы максимизируют выигрыши игроков. Конкретное значение выигрышей игроков можно вычислить, точно зная ходы противника. Литература 1. Колобашкина Л. В. Основы теории игр : учебное пособие / Л. В. Колобашкина. — 3-е изд., испр. и доп. —М. : БИНОМ. Лаборатория знаний, 2016. — 195 с. 2. Шикин Е.В., Чхарчишвили А.Г. Математические мнтоды и модели в управлении: учебное пособие – 2-е издание., испр. — М. : Дело, 2002. — 440 с. 114 Лекция 8. Кооперативные игры. Определение. Кооперативной игрой нескольких игроков n≥2 называется неантагонистическая игра, в которой часть игроков может обсуждать перед игрой свои стратегии, образуя коалиции. Причиной возникновения кооперативной игры является стремление игроков к улучшению своих индивидуальных выигрышей. Это означает, что игроки могут образовывать коалиции из компаньонов. Объединение игроков в коалицию превращает их в «единого игрока», стратегиями которого являются все возможные комбинации стратегий игроков коалиции, а выигрышем — выигрыш коалиции. Кооперативная игра задается парой (N, v), где N— множество игроков, a v(Kj) — вещественная функция, называемая характеристической функцией игры. Кj  N –некоторая произвольная коалиция игроков. Каждой кооперативной игре можно поставить в соответствие игру «двух» игроков, причем: - «одним игроком» является коалиция КjN игроков множества N; — «другим игроком» являются остальные игроки из множества N, не вошедшие в коалицию Кj. Коалицией Kj игры N лиц называется любое непустое подмножество множества игроков N (включая N и все его одноэлементные подмножества). Мерами выигрышей игроков Кj и N\Кj являются их характеристические функции v(Kj) и v(N\Kj) (вещественная функция). Характеристическая функция игры удовлетворяет условиям: 1. v(0)=0 — коалиция без игроков ничего не может выиграть. 2. v(Кi) + v(KJ)v(Ki Kj) — игроки в коалиции не могут выиграть меньше, чем индивидуально, иначе коалиция будет экономически неустойчивой. 115 Здесь v(Ki Kj) — выигрыш коалиции игроков Кi и KJ, v(Кi) и v(KJ) — их индивидуальные выигрыши в некооперативной игре. Характеристическая функция называется простой, если она принимает только два значения: 0 и 1. Если характеристическая функция простая, то коалиции K, для которых v(K)=1, называются выигрывающими, а коалиции K для которых v(K)=0, - проигрывающими. Простые характеристические функции возникают в условиях голосования, когда коалиция является выигрывающей, если она собирает более половины голосов (простое большинство) или не менее двух третей голосов (квалифицированное большинство). Более сложным примером простой характеристической функции является оценка результатов голосования в Совете безопасности ООН, где выигрывающими коалициями являются все коалиции, состоящие из всех пяти постоянных членов Совета плюс ещё хотя бы один непостоянный член, и только они. Пример характеристической функции 1. Голосование. Характеристическая функция задается формулой:  0, | K | m v( K )    1, | K | m где m — некоторое фиксированное число, называемое критерием большинства (для простого большинства m =n/2+1). Коалиция, в состав которой вошло по крайней мере m игроков, выигрывает; коалиция, размер которой меньше, чем m, проигрывает. Пример характеристической функции 2. Игра “Сбросы в озеро”. Вокруг озера расположены n фабрик, которые используют для своих нужд чистую воду, а затем отработанную Использованная вода загрязнена. воду сбрасывают в озеро. 116 Перед сбросом воду можно очищать, а можно не очищать. Eсли хотя бы одна фабрика будет сливать загрязненную воду, то всем придется забирать из озера уже не чистую воду, поэтому перед использованием ее нужно будет очищать. Стоимость очистки собственной использованной воды C; стоимость очистки озерной воды, если в озеро неочищенную воду сбросили m фабрик, равна m · c. Пусть несколько фабрик, объединяясь в коалицию K, договариваются о том, чтобы одновременно очищать или не очищать свои отходы. Характеристической функцией будут издержки коалиции от очистки воды со знаком минус. Характеристическая функция vK(N) кооперативной игры с коалицией K определяется на основе решения биматричной игры: vK(N) = v(K) + v(N\K). Кооперативная игра (N,v), в которой задана коалиция Kj, называется существенной (или полезной), если выполняется условие групповой рациональности (групповой существенности) коалиции всех игроков: n v( N )   v( K k )  vK j ( N ) k 1 где v(N) = v(Kk) — сумма индивидуальных выигрышей игроков в некооперативной игре, vK j (N ) характеристическая функция кооперативной игры (суммарный выигрыш игроков в кооперативной игре). В несущественной игре коалиции экономически неустойчивы, поскольку объединение в эти коалиции не способствует увеличению индивидуальных выигрышей одного или нескольких игроков. Таким образом, для начала кооперативной удовлетворяться условия: — групповой существенности (игра существенна); игры должны 117 — коалиции должны обладать устойчивостью. Коалиция KjN является устойчивой, если не существует других коалиций, которые смогут обеспечить больший выигрыш для недовольных беглецов из коалиции Kj. Конфигурация кооперативной игры (т. е. разбиение N игроков по коалициям) с учетом выигрыша каждой коалиции является устойчивой, если характеристическая функция коалиции всех игроков принимает максимальное значение по сравнению с характеристическими функциями всех возможных конфигураций этой игры, для которых выполняется условие групповой рациональности. Прежде чем формировать коалиции и начинать процесс игры, игрокам следует договориться о принципах дележа выигрыша. Дележом кооперативной игры (N,v) с заданной коалицией Кj называется вектор ={к=({Fk})}, k=1,...,n, для которого одновременно выполняются два условия: n 1)   (F )  v k 1 k Kj ({N }) 2) ({Fk}) v(Fk), k=1,…,n. Дележ внутри коалиции чаще всего производится двумя способами: 1) с учетом индивидуальных вкладов игроков в выигрыш коалиции (в случае, когда решение биматричной игры может быть найдено исключительно с помощью применения отношений доминирования); 2) с учетом индивидуальных выигрышей игроков в некооперативной игре v(Fk) (это более общий способ дележа). В случае 2 дележ производится по формуле:  ({Fk })  v( Fk ) v({K j }) v Fk K j Kj ( Fk ) 118 где v(Fk), ({Fk}) — индивидуальные выигрыши игрока Fk соответственно в некооперативной и кооперативной играх, v({Kj}), — суммарный выигрыш игроков коалиции Kj, v Fk K j Kj ( Fk ) — сумма индивидуальных выигрышей в некооперативной игре игроков, составляющих коалицию Kj. Одним игрокам предпочтителен один дележ, другим — другой, поэтому договариваться о принципах дележа необходимо заранее. Алгоритм выделения экономически устойчивых коалиций в кооперативной игре 1. Решаются попарно некооперативные игры для всех N игроков методами теории биматричных игр. Например, если N=3, то решаются игры: первый против второго (I — II); первый против третьего (I — III) и второй против третьего (II — III). 2. Определяются индивидуальные выигрыши игроков в некооперативной игре v(Кk) как средние арифметические по всем партиям данного игрока. 3. Подсчитывается характеристическая функция некооперативной игры v(N) как сумма индивидуальных выигрышей всех игроков: n v( N )   v( K k ) k 1 4. Составляются всевозможные конфигурации коалиций для данной игры и рассчитываются для каждой коалиции характеристические функции выигрыша - Определяются матрицы выигрышей для каждой коалиций с учетом того, что стратегии коалиции являются комбинациями всех возможных стратегий игроков, входящих в данную коалицию. - Решаются биматричные игровые задачи для составленных кооперативных игр. 119 - Рассчитываются для каждой кооперации характеристические функции выигрыша. vK j (N ) 5. На основе условия групповой рациональности (существенности) vK j ( N )  v( N ) выделяются существенные игры, представляющие интерес для дальнейшего рассмотрения. 6. Производится дележ внутри коалиций в выбранной игре на основе индивидуальных вкладов игроков в выигрыш коалиции или на основе индивидуальных выигрышей в некооперативной игре. 7. Берется игра с максимальной характеристической функцией и для неё проверяется условие индивидуальной рациональности:({Fk})>v(Fk) к=1,...,n. При выполнении этого условия конфигурация игры является экономически устойчивой. Если условие рассматривается индивидуальной существенная рациональности игра с не выполняется, меньшим характеристической функции. Пример. Пусть задана игра трех лиц (n = 3) в биматричной форме. I-й против II-го (I — II): I-й против III-го (I — III): значением 120 II-й против III-го (II — III) 1. Решаем 3 биматричной игры. Считаем, что каждый игрок желает максимизировать свой выигрыш. I-й против II-го (I — II): У игрока I первая альтернатива доминирует вторую, поэтому первый игрок её применять не будет, вследствие этого последние строки из обеих матриц можно удалить. У второго игрока первая стратегия доминирует вторую, поэтому у обоих игроков матрицы принимают следующий вид: I-й против III-го (I — III): У игрока I первая альтернатива доминирует вторую, поэтому первый игрок её применять не будет, вследствие этого последние строки из обеих матриц можно удалить. I z1 z2 III z1 z2 x1 0,25 -0,75 x1 -0,75 -1 У второго игрока вторая стратегия доминирует первую, поэтому у обоих игроков матрицы принимают следующий вид: 121 II-й против III-го (II — III): У игрока II первая альтернатива доминирует вторую, поэтому первый игрок её применять не будет, вследствие этого последние строки из обеих матриц можно удалить. II z1 z2 III z1 z2 y1 -2,5 -3,75 y1 2 1,75 У третьего игрока вторая стратегия доминирует первую, поэтому у обоих игроков матрицы принимают следующий вид: 2. Вычисляем индивидуальные выигрыши. Для этого находим среднее арифметическое выигрышей каждого игрока в биматричных играх: v(I)=((-2,25)+(-0,75))/2=-1,5 v(II)=((-3,75)+(-3,75))/2=-3,75 v(III)=((-0,75)+2)/2=0,625 3. Вычисляем характеристическую функцию некооперативной игры: v(N)=v(I,II,III)=v(I)+v(II)+v(III)=-1,5-3,75+0,625=-4,625 4. Строим все возможные конфигурации коалиций (в комбинациях выигрыши складываются): 122 А. (I,II) против (III). Матрицы игры в данном случае имеют следующий вид: I,II z1 z2 III z z x1 y1 -2,25 -4,5 x1 y1 0,75 1,25 x1 y2 -2,5 -4,75 x1 y2 -0,25 0,25 x2 y1 -2,5 -4,75 x2 y1 -0,5 x2 y2 -2,75 -5 x2 y2 -1,5 -1 1 2 После удаления доминируемых строк и столбцов получаем v({I,II})=-4,5 v({III})=1,25 Характеристическая функция игры: vI,II-III({N})=v({I,II})+v({III})=-3,25>-4,625=v(N) следовательно, игра является существенной. Б. (I,III) против (II) Предварительно необходимо преобразовать II против III в III против II (это делается обычным транспонированием матриц): 123 Матрицы этой игры: I,III y1 y2 II y1 y2 x 1 z1 -0,5 -2 x 1 z1 -6,25 -6,75 x 1 z2 -0,25 -1,75 x 1 z2 -7,5 -8 x 2 z1 -0,75 -2,25 x 2 z1 -11,25 -11,75 x 2 z2 -0,5 -2 x 2 z2 -12,5 -13 После удаления доминируемых строк и столбцов получаем v({I,III})=-0,25 v({II})=-7,5. Характеристическая функция игры: vI,III-II({N})=v({I,III})+v({II})=-7,75<-4,625=v(N) игра не существенная. В. (I) против (II,III) Матрицы игры в данном случае имеют следующий вид: I y1z1 y1z2 y2z1 y2z2 II,III y1z1 x1 -2 -3 -2,5 -3,5 x1 x2 -2,5 -3,5 -3 -4 x2 y1z2 -4,75 -4,5 y2z1 y2z2 -5 -4,75 -11 -10,75 -11,25 -11 После удаления доминируемых строк и столбцов получаем: v({I})=-3 v({II,III})=-4,5. Характеристическая функция игры: vI-II,III({N})=v({I})+v({II,III})=-7,5<-4,625=v(N)  игра является существенной. 5. Из существенных игр выбирается игра с устойчивой конфигурацией. Для этого выбирается игра с максимальной характеристической функцией. В нашем случае существенная только одна игра {I,II} против {III}. не 124 6. Определяем делёж внутри коалиции {I,II}. А. Делёж с учетом индивидуальных вкладов I-го и II-го игрока. Характеристическая функция коалиции: v({I,II})=-0,75-3,75=-4,5. Вклад первого игрока -1,75  ({I})=-0,75. Индивидуальный выигрыш первого игрока в бескоалиционной игре v(I)=-1,5. В результате получаем ({I})>v(I), то есть первый игрок при таком дележе от коалиции выигрывает. Вклад второго игрока -3,75  ({II})=-3,75. Индивидуальный выигрыш второго игрока в бескоалиционной игре v(II)=3,75. Так как ({II})=v(II), то второй игрок не получает прибавки к выигрышу по сравнению с бескоалиционной игрой. Характеристическая функция коалиции третьего игрока при таком делении на коалиции :v({III})=1,25  ({III})=1,25. Индивидуальный выигрыш третьего игрока в бескоалиционной игре v(III)=0,625. У него как и у первого игрока тоже есть добавка по сравнению с бескоалиционной игрой:({III})=1,25>0,625=v(III). Таким образом, при таком способе дележа выигрыш получают I-й и IIIй игроки. Для II-го игрока экономические предпосылки для организации кооперативной игры отсутствуют, поэтому необходимо использовать другой способ дележа. Б. Дележ с учетом индивидуальных выигрышей игроков в некооперативной игре. Индивидуальных выигрыши игроков в некооперативной игре: v(I)=-1,5, Вычисляем v(II)=-3,75, характеристическую v(III)=0,625. функцию v(N)=v(I)+v(II)+v(III)=-1,5-3,75+0,625=-4,625. Подсчитаем выигрыши игроков по формуле: некооперативной игры: 125 v({K j })  ({Fk })  v( Fk )  vK j ( Fk ) , Fk K j Получаем при заданном дележе выигрыши игроков:  ({I })  v( I ) v( I , II )  4.5  1.5  -1,2857 , v( I )  v( II )  1.5  3.75  ({II})  v( II ) v( I , II )  4.5  3.75  -3,2143 , v( I )  v( II )  1.5  3.75 ({III})= v({III})=1,25 . В итоге получаем: ({I})>v(I) (-1,2857>-1,5), ({II})>v(II) (-3,21423>-3,75), ({III})>v(III) (1,25>0,625). Таким образом, при таком способе дележа выигрыш получают все игроки. Рассчитаем прирост выигрыша от коалиции. vI,II-III({I}) = ({I}) - v(I) =-1,2857-(-1,5) =0,21429. vI,II-III({II}) = ({II}) -v(II) = -3,21423-(-3,75)=0,53577. vI,II-III({III})= ({III})-v(III)= 1,25-0,625 Данная конфигурация является =0,625. экономически устойчивой при рассмотренном способе дележа. Причем игрок III, не участвовавший в коалиции, имеет наибольший выигрыш от такой коалиции. Принцип оптимальности кооперативных игр. Вектор Шепли. Определение. Вектором Шепли называется дележ игры (N,v), определяемый следующим образом: i  (k  1)!(n  k )! (v({K i })  v({K i \ i}), i  1,...,n n ! ki  N  (1) где суммирование производится по всем коалициям Ki, содержащим i-го игрока, k — число членов коалиции Ki, n — общее число участников кооперативной игры (N, v). 126 В формуле (1) (k  1)!(n  k )! - Вероятность формирования коалиции Кi по n! всему множеству N. Следовательно (k  1)!(n  k )! (k  1)!(n  k )!  0.  1 , при этом n! n! ki  N  v({Ki })  v({Ki \ i}) - гарантированный выигрыш, который привносит игрок i в игру. Функция I является усреднённым вкладом игрока I в игру. Таким образом Вектор Шепли – это n-компонентный вектор, i-я компонента которого понимается как справедливый выигрыш, назначаемый игроку i в соответствии с его «вкладом» в игру (самый справедливый делёж). Пример. Комитет из трех человек принимает различные решения простым большинством (два «за»), но один его член (председатель) имеет право вето. Определить вектор Шепли для соответствующей игры. Решение. Составим характеристическую функцию, считая выигрыш коалиции при принятии предлагаемого ею решения равным 1, а при отклонении — 0 (игроку, имеющему право вето, присвоим номер I). Имеем несколько коалиций. Коалиции из двух игроков с игроком 1 и коалиция из трех игроков выигрышные. Остальные коалиции проигрышные. v({I,II}) = v({I,III}) = v({I,II,III})=1; v({I}) = v({II}) = v({III}) = v({II,III}) =0. Рассчитаем вектор Шепли: i  (k  1)!(n  k )! (v({K i })  v({K i \ i}), n! ki  N 1  (2  1)!(3  2)! (2  1)!(3  2)! (v({I , II })  v({II })  (v({I , III})  v({III})  3! 3!  (3  1)!(3  3)! 1 1 2 4 (v({I , II , III})  v({II , III})  (1  0)  (1  0)  (1  0)  3! 6 6 6 6 127 2  (3  1)!(3  3)! (2  1)!(3  2)! (v({I , II })  v({I })  (v({I , II , III})  v({I , III})  3! 3! 1 2 1 (1  0)  (1  1)  . 6 6 6 3  (2  1)!(3  2)! (3  1)!(3  3)! (v({I , III})  v({I })  (v({I , II , III})  v({I , II })  3! 3! 1 2 1 (1  0)  (1  1)  6 6 6 4 1 1 6 6 6 Ответ: ( ; ; ) Пример. Совет директоров акционерного общества состоит из четырех акционеров, имеющих акции соответственно в следующих количествах: 1-й 10 шт., 2-й 20 шт., 3-й 30 шт., 4-й 40 шт. Любое решение утверждается акционерами, имеющими в сумме большинство акций. Построить вектор Шепли игроков. Данная ситуация может рассматриваться как простая игра четырех игроков. Строим характеристические функции всевозможных выигрышных коалиций: v({I,II,III}) = v({I,II,IV}) = v({I,III,IV}) = v({I,II,III,IV})= v({II,IV}) = v({II,III,IV}) = =v({III,IV}) =1. Согласно формуле i  (k  1)!(n  k )! (v({K i })  v({K i \ i}), n! ki  N  вычисляем компоненты вектора Шепли. 1  (3  1)!(4  3)! (3  1)!(4  3)! (v({I , II , III})  v({II , III}))  (v({I , II , IV })  v({II , IV }))  4! 4! (3  1)!(4  3)! (v({I , III , IV })  v({III , IV }))  4! (4  1)!(4  4)! 1 (v({I , II , III , IV })  v({II , III , IV }))  . 4! 12 2  (3  1)!(4  3)! (3  1)!(4  3)! (v({I , II , III})  v({I , III}))  (v({I , II , IV })  v({I , IV }))  4! 4! (4  1)!(4  4)! (2  1)!(4  2)! (v({I , II , III , IV })  v({I , III , IV }))  (v({II , IV })  v({IV }))  4! 4! 128 (3  1)!(4  3)! 3 (v({II , III , IV })  v({III , IV }))  . 4! 12 (3  1)!(4  3)! (v({I , II , III})  v({I , II }))  4! (4  1)!(4  4)! (3  1)!(4  3)! (v({I , II , III , IV })  v({I , II , IV }))  (v({I , III , IV })  v({I , IV }))  4! 4! 3  (3  1)!(4  3)! (2  1)!(4  2)! 3 (v({II , III , IV })  v({II , IV }))  (v({III , IV })  v({IV }))  . 4! 12 4! (3  1)!(4  3)! (v({I , II , IY })  v({I , II }))  4! (4  1)!(4  4)! (3  1)!(4  3)! (v({I , II , III , IV })  v({I , II , III}))  (v({I , III , IV })  v({I , III}))  4! 4! 4  (3  1)!(4  3)! (2  1)!(4  2)! (v({II , III , IV })  v({II , III}))  (v({II , IV })  v({II }))  4! 4! (2  1)!(4  2)! 5 (v({III , IV })  v({IV }))  . 4! 12 1 3 3 5 ; ; ; ). 12 12 12 12 Ответ ( 1 2 3 4 ; ; ). 10 10 10 10 Для сравнения доли акций: ( ; Литература 1. Колобашкина Л. В. Основы теории игр : учебное пособие / Л. В. Колобашкина. — 3-е изд., испр. и доп. —М. : БИНОМ. Лаборатория знаний, 2016. — 195 с. 129 Разбиение матрицы на подматрицы Иногда матрица игры Х бывает такой, что ее горизонтальными и вертикальными линиями можно разбить на подматрицы, в каждой из которых суммы элементов в строках равны между собой и суммы элементов в столбцах равны между собой. Если чистые стратегии игроков А и В, на пересечении которых образованы подобные подматрицы, входят в решение игры, т.е. входят в оптимальные смешанные стратегии с положительными вероятностями, то они входят в эти оптимальные смешанные стратегии с равными вероятностями. Однако, если чистые стратегии, входящие в смешанную стратегию (с положительными вероятностями), входят в нее с равными вероятностями, то отсюда еще не следует, что эта смешанная стратегия будет оптимальной. Пример. Пусть дана матрица: В1 В2 В3 В4 В5 3 -1 2 1 3 А1 -2 4 -4 8 2 А2 2 8 -3 1 А3 4 4 4 А4 Её можно разбить на подматрицы как указано в таблице ниже: В6 5 5 5 7 В1 В2 В3 В4 В5 В6 3 -1 2 1 3 5 А1 -2 4 -4 8 2 5 А2 2 8 -3 1 5 А3 4 4 4 7 А4 В результате можно заменить чистые стратегии на смешанные по этим подматрицам: Q1 Q2 Q3 В1 В2 В3 В4 В5 В6 А1 3 -1 2 1 3 5 А2 -2 4 -4 8 2 5 130 А3 2 8 -3 1 5 А4 4 4 4 7 При этом выигрыши будут равны: Q1=0,5B1+0,5B2+0B3 +0B4+0B5 +0B6 – В1 и В2 используются с равными вероятностями по 0,5, остальные с нулевыми. Q2=0B1 +0B2 +1/3B3+1/3B4+1/3B5+0B6 – В3, В4 и В5 используются с равными вероятностями по 1/3, остальные с нулевыми. Q3=0B1+0B2 +0B3 +0B4 +0B5 +1B6 – в этой подматрице только один столбец, поэтому соответствующая чистая стратегия используется с вероятностью 1, остальные с нулевой. Таким образом получаем матрицу: Q1 1 1 1 А1 А2 А3 А4 Q2 2 2 2 4 Q3 5 5 5 7 После преобразований у нас получилось, что стратегии А1, А2 и А3 стали дублирующими, поэтому две из них можно убрать: Q1 Q2 Q3 P1 1 2 5 P2 4 7 Выигрыши смешанных стратегий игрока А получены из выражений: P1=А1+0*А2+0*А3 +0*А4- то есть взята только стратегия А1. Р2= 0*А1+0*А2+0*А3 + А4- то есть взята только стратегия А4. Литература 131 1. Исследование операций в экономике: учеб. Пособие /Н.Ш.Кремер, Б.А.Путко, И.М. Тришин, М. Н. Фридман; под ред. проф. Н. Ш. Кремера. – 2-е Изд., перераб. и доп.- М. : Издательство Юрайт: ИД Юрайт, 2010. - 430 с. (Глава 12) . 2. Кремер Н.Ш., Путко Б.А., Тришин И.М. Математика для экономистов: от Арифметики до Эконометрики: учеб-справоч. пособие / под ред. проф. Н. Ш. Кремера. – 2-е изд., перераб. и доп. – М.: Издательство Юрайт: ИД Юрайт, 2010. – 646 с. (Параграфы 10.1 и 10.2). 3. Шапкин А. С. Математические методы и модели исследования операций: Учебник / А. С. Шапкин, В. А. Шапкин — 5-е изд — М: Издательско-торговая корпорация «Дашков и К», 2012. — 400 с. 4. Лабскер Л.Г. Теория игр в экономике (практикум с решения задач): учебное пособие / Л.Г. Лабскер, Н.А. Ященко ; под ред. Л.Г. Лабскера. – 2-е изд., стер. – М. : КНОРУС, 2013. – 264 с.