[ Федеральное государственное образовательное бюджетное учреждение
высшего профессионального образования
Московский технический университет связи и информатики
Кафедра теории вероятностей и прикладной математики
Методические указания и контрольные задания
по дисциплине
ТЕОРИЯ ИГР
для студентов-заочников 2 курса,
специальности: 080100
семестр 4 Москва 2014 План УМД на 2013/2014 уч.год Методические указания и контрольные задания по дисциплине "Теория игр" 2014 год Составитель: Демин Д.Б., к.ф.-м.н., доцент каф. ТВиПМ В предлагаемых методических указаниях приведены теоретические сведения и практические навыки общего характера по курсу «теория игр».
Дана рабочая программа, тематика лекций и упражнений, основные вопросы к экзамену. Приведены задания по контрольной работе в вариантах.
Издание утверждено на заседании кафедры «Теории вероятностей и прикладной математики» (протокол № ).
Рецензент: Кюркчан А.Г., проф, зав каф. ТВиПМ
ВВЕДЕНИЕ
Предлагаемые методические указания относятся к курсу «Теория игр», изучаемого студентами-заочниками в четвертом семестре. В этом курсе студенты знакомятся с основными моделями и методами теории игр – теории принятия решений в неопределенных ситуациях. Приводятся примеры принятия решения в области экономики и менеджмента. По курсу выполняется контрольная работа, которая приведена в конце данных указаний.Методические указания не заменяют учебников, а содержат только основные моменты изучаемого материала, краткий обзор отдельных вопросов, а также решения некоторых типовых задач вопросы по предмету.
Основная литература по курсу «Теория игр» приведена ниже.
ОБЩИЕ УКАЗАНИЯ
1. Самостоятельная работа с учебником Самостоятельная работа с учебником является основным видом работы студента-заочника. Читая основную литературу по курсу, студент может и должен обращаться к указанной дополнительной литературе. Это необходимо в тех случаях, когда основной учебник не дает полного ответа на некоторые вопросы программы. Кроме того в дополнительной литературе приведено много вспомогательного теоретического и практического материала, облегчающего усвоение основных тем курса.2. Решение задач Приступая к решению задач, следует после изучения очередного раздела по учебнику внимательно изучить примеры решения типовых задач по данному пособию, а затем переходить к самостоятельному решению рекомендованных задач. В тех случаях, когда это необходимо, следует дать рисунок, поясняющий решение задачи. Решение следует сопровождать краткими, но исчерпывающими пояснениями. Решение каждой задачи должно содержать окончательный ответ, содержащий перечисление оптимальных стратегий игроков с указанием их выигрыша (проигрыша). Промежуточные вычисления следует проводить в целых числах и рациональных дробях без приближенного их округления в виде десятичной дроби.
3. Выбор варианта Вариант выбирается в соответствии с двумя последними цифрами студенческого билета. Например, если номер студенческого билета 11021, то вариант будет иметь номер 21. Если номер варианта больше 39, то из последних двух цифр нужно отнять число 40. Например, если ваши последние две цифры 54, то ваш вариант будет 54–40=14.
руководствоваться следующим:
1. Не следует приступать к выполнению контрольных работ до изучения всех примеров, приведенных в данном пособии.
2. Контрольные работы выполняются по УМД одного года издания.
Замена издания другим в процессе изучения курса теории игр не допускается.
3. Контрольная работа выполняется в обычной ученической тетради.
Она должна быть аккуратно и четко написана. Для замечаний преподавателей на каждой странице оставляются поля шириной 2 см. Все страницы нумеруются. На обложку тетради наклеивается заполненный адресный бланк, а на первую страницу тетради – титульный бланк.
4. Решения задач и контрольных работ сопровождаются исчерпывающими, но краткими объяснениями. Задачи располагают в порядке номеров, указанных в заданиях; перед решением задачи выписывается полностью ее условие.
5. На рецензию одновременно высылается не более одной работы.
6. После получения прорецензированной работы из университета студент должен выполнить указания, сделанные рецензентом. Если контрольная работа не зачтена, студент обязан в той же тетради (после заключения рецензента) внести все исправления, решить заново задачи, указанные рецензентом, и представить работу на повторную рецензию.
7. Контрольная работа выполняется самостоятельно. В случае, если у рецензента возникает сомнение в самостоятельности выполнения работы, студент вызывается на консультацию для устной защиты контрольной работы.
8. В конце работы указывается использованная литература.
9. Контрольная работа подписывается с указанием даты выполнения.
10. Контрольные работы, выполненные без соблюдения изложенных правил или по чужому варианту, не засчитываются и возвращаются.
К сдаче экзамена допускаются студенты, имеющие на руках выполненные и зачтенные работы. Экзамен сдается в письменной и устной формах.
При сдаче экзамена студент должен знать определения, теоремы, формулы и иметь навыки решения задач по данному курсу.
Студенты, успешно выполняющие учебный план, приглашаются в университет для проведения лабораторных работ, сдачи экзаменов и очной работы с преподавателями. В это время для студентов читаются обзорные лекции и проводятся упражнения в объеме учебного плана.
Следует иметь в виду, что обзорные лекции не являются систематическим чтением курса. Они охватывают лишь узловые моменты программы. Обзорные лекции, упражнения и консультации будут полезны студентам, которые проработали курс по полной программе и выполнили контрольные задания.
РАБОЧАЯ ПРОГРАММА
1. Задачи теории игр. Примеры, виды игровых задач.2. Антагонистические матричные игры. Примеры игр. Максимин и минимакс. Выигрыши двух игроков.
3. Ситуации равновесия в игре. Понятие седловой точки. Чистые стратегии двух игроков.
4. Смешанные стратегии двух игроков в матричной игре. Выигрыши игроков.
5. Теорема Дж. фон Неймана о ситуации равновесия. Аналитическое решение игры 22.
6. Геометрическое решение игры 22.
7. Лемма о масштабе. Условия эквивалентности смешанных стратегий двух игр.
8. Свойства оптимальных смешанных стратегий в матричной игре.
9. Графический метод решения матричной игры (2m).
10.Графический метод решения матричной игры (n2).
11.Активные (существенные) стратегии игроков. Теоремы об активных стратегиях.
12.Принцип доминирования стратегий двух игроков. Теоремы о доминируемых стратегиях.
13.Вполне смешанная игра. Решение матричной игры nn методом обратной матрицы.
14.Сведение матричной игры nm к двойственной задаче линейного программирования. Общий подход.
15.Постановка задач линейного программирования.
16.Множества решений неравенств, уравнений и их систем в задачах линейного программирования. Допустимые решения. Допустимые базисные решения. Сведения из теории выпуклых множеств.
17.Задача линейного программирования в канонической форме. Основные теоремы о множествах оптимальных решений этой задачи.
18.Аналитический метод решения задачи линейного программирования nm (симплекс-метод).
19.Симплекс-таблицы в симплекс-методе для задач на максимум и минимум.
20.Метод искусственного базиса в симплекс-методе.
21.Взаимосвязь решений двух двойственных задач линейного программирования.
22.Решение матричной игры nm симплекс-методом. Получение решения при помощи использования принципа двойственности.
23.Принципы доминирования в биматричных играх. Пример для матриц размера 33.
24.Ситуация равновесия по Нэшу в биматричной игре произвольной размерности. Свойства ситуаций равновесия. Теорема Дж. Нэша.
25.Ситуация равновесия по Нэшу в биматричной игре 22. Поиск смешанных стратегий для двух игроков.
26.Графическая интерпретация решения в биматричной игре 22 по Нэшу.
27.Поиск оптимальных стратегий по Парето в биматричной игре 22.
Множество Парето. Точка утопии. Идеальная точка.
СПИСОК ЛИТЕРАТУРЫ
1. Исследование операций в экономике. Под ред. Н.Ш. Кремера. М.:ЮНИТИ, 2000.
2. Шикин Е.В., Шикина Г.Е. Исследование операций. М.: ТК Велби, Издво «Проспект», 2006.
3. Колобашкина Л.В. Основы теории игр. М. Бином. Лаборатория знаний, 2012.
4. Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. М.:
Высш.школа, Книжный дом «Университет», 1998.
5. А.А. Васин, В.В. Морозов. Теория игр и модели математической экономики. М.: МАКС Пресс, 2005.
6. Грачева М.В., Фадеева Л.Н., Черемных Ю.Н. Количественные методы в экономических исследованиях. М.: Юнити, 2004.
7. Вентцель Е.С. Исследование операций: задачи, принципы, методология.
М.: Дрофа, 2004.
В дальнейшем при ссылках на литературу указанные учебники обозначаются заключенными в квадратные скобки номерами по этому списку. Например, [1] означает учебник Кремера и т.п.
ТЕМЫ ЛЕКЦИЙ
1. Матричные антагонистические игры. Смешанные стратегии двух игроков в матричной игре. Теорема Дж. фон Неймана.2. Свойства оптимальных смешанных стратегий в матричной игре.
Решение в смешанных стратегиях матричных игр вида: 2 2, n 2 и 2 m.
3. Лемма о масштабе. Активные стратегии игроков. Теоремы об активных стратегиях. Принцип доминирования стратегий двух игроков. Теоремы о доминируемых стратегиях.
4. Сведение матричной игры n m к двойственной задаче линейного программирования. Аналитический метод решения задачи линейного программирования n m (симплекс-метод). Симплекс-таблицы в симплекс-методе для задач на максимум и минимум.
5. Метод искусственного базиса в симплекс-методе. Решение двойственной задачи линейного программирования симплекс-методом.
6. Биматричные игры. Ситуация равновесия по Нэшу в биматричной игре произвольной размерности и в игре 2 2. Ситуация оптимальности по Парето в биматричной игре.
ТЕМЫ УПРАЖНЕНИЙ
1. Примеры матричных игр. Решение игр в чистых стратегиях. Решение игры вида 2 2 в смешанных стратегиях.2. Решение в смешанных стратегиях матричных игр вида n 2 и 2 m.
Метод обратной матрицы.
3. Решение матричной игры n m симплекс-методом.
4. Определение ситуации равновесия по Нэшу и оптимальной ситуации по Парето в биматричной игре 2 2.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО РАЗДЕЛАМ КУРСА «ТЕОРИЯ ИГР»
ВВЕДЕНИЕ
[1, гл.9, § 1], [2, гл.5], [3, гл.1, § 1], [4, гл.1, § 1], [5, введение], [6, гл.5, § 1], [7, гл.8, § 25].В практической деятельности, в том числе и в экономике, приходится сталкиваться с задачами, в которых необходимо принимать решения в условиях неопределенности, т.е. возникают ситуации, в которых сталкиваются две и более враждующие стороны, преследующие различные цели. Причем результат любого действия каждой из сторон зависит от того, какие действия предпримет противоположная сторона.
Такие ситуации принято называть конфликтными. В экономике конфликтные ситуации возникают очень часто. К ним относятся, например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом, фирмами, захватывающими определенную часть рынка и др. Во всех этих примерах конфликтная ситуация порождается различием интересов партнеров и стремлением каждого из них принимать оптимальные решения, которые максимально реализуют поставленные цели.
В реальной жизни конфликтные ситуации довольно сложны. Их изучение осложнено наличием различных факторов, часть из которых может оказывать слабое влияние на развитие конфликта и на его исход.
Поэтому для анализа конфликтной ситуации необходимо отвлечься от второстепенных факторов и построить ее упрощенную, формализованную модель, которую принято называть игрой. От реальной конфликтной ситуации игра отличается лишь тем, что ведется по определенным правилам.
Для изучения и анализа конфликтов, представленных в виде упрощенных математических моделей (игр), был создан специальный математический аппарат – теория игр.
Теория игр – математическая теория конфликтных ситуаций или, другими словами, это раздел математики, в котором изучаются математические модели принятия решений в условиях неопределенности.
В игре могут сталкиваться интересы двух (парная игра) и более сторон (игроков) (множественная игра). Целью каждого из них является получение как можно большего выигрыша. В дальнейшем мы будем сталкиваться преимущественно с парной игрой.
Математическое описание игры сводится к перечислению всех участвующих в ней игроков, указанию для каждого игрока всех его стратегий, а также численного выигрыша, который он получит после того, как игроки выберут свои стратегии. В результате игра становится формальной моделью, поддающейся математическому описанию.
Выбор и осуществление одного из предусмотренных правилом игры действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход – это сознательный выбор игроком одного из возможных действий (ход в шашках, в шахматах). Случайный ход – это случайно выбранное действие (выбор карты из перетасованной колоды).
Случайные ходы в теории игр не рассматриваются, они являются предметом изучения другой дисциплины – теории вероятностей.
Задача теории игр – рекомендовать игрокам определенные стратегии при выборе их личных ходов.
Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации. Игрок может выбирать стратегию либо в процессе самой игры в зависимости от конкретной ситуации, либо он может выбрать ее заранее до начала игры.
Для того, чтобы решить игру, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получить максимальный выигрыш, когда второй придерживается своей стратегии. В то же время второй игрок должен иметь минимальный проигрыш, когда первый игрок придерживается своей стратегии. Такие стратегии называются оптимальными.
Если игра повторяется много раз, оптимальной стратегией игрока называется такая стратегия, которая обеспечивает ему максимально возможный средний выигрыш в игре.
Целью теории игр является определение оптимальной стратегии и выигрыша для каждого игрока.
Игры классифицируются по целому ряду признаков:
– по количеству игроков: парные игры (игры двух лиц) и игры n лиц (множественные игры);
– по количеству стратегий: конечные (число возможных стратегий конечно) и бесконечные игры;
– по характеру взаимоотношений: бескоалиционные, коалиционные, кооперативные игры;
– по характеру выигрышей: игры с нулевой суммой (антагонистические) и игры с ненулевой суммой (неантагонистические);
– по количеству ходов: одношаговые и многошаговые игры (позиционные, стохастические, дифференциальные);
– в зависимости от состояния информации: игры с полной информацией (все стратегии игроков известны заранее; примеры:
крестики-нолики, шашки, шахматы) и игры с неполной информацией (игра в карты (когда все карты розданы), домино);
непрерывные.
РАЗДЕЛ 1: МАТРИЧНЫЕ ИГРЫ
[1, гл.9, § 2], [2, гл.5, § 1], [3, гл.1, § 1-2], [4, гл.1, § 1], [5, гл.1], [6, гл.5, § 2], [7, гл.8, § 26].Матричная игра – это конечная игра двух игроков с нулевой суммой.
Фактически она является конечной парной антагонистической бескоалиционной игрой с полной информацией о стратегиях обоих игроков. Обозначим для удобства одного игрока через А, а другого через Предположим, что игрок А имеет m стратегий А1,..., Am, а игрок B – n стратегий B1,..., Bn. Выбор игроками А и B стратегий Аi и B j однозначно определяет исход игры – выигрыш a ij игрока А и выигрыш bij игрока B, причем bij aij (т.е. выигрыш игрока А – это проигрыш игрока B, и наоборот).
Если значения выигрышей a ij игрока А известны при каждой паре i 1, m, j 1, n, то их удобно записать в виде прямоугольной таблице, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока B :
или в виде матрицы Полученная матрица P имеет размерность m n и называется матрицей игры, или – платежной матрицей. Рассматриваемую игру часто называют матричной (m n) игрой.
Так как в данной игре игрок А выигрывает именно столько, сколько проигрывает игрок B, то сумма выигрышей двух игроков здесь равна нулю. Такие игры принято называть играми с нулевой суммой или антагонистическими играми, так как интересы игроков здесь прямо противоположны.
Ценой (значением) игры называется средний выигрыш игрока А.
Пример 1. (игра в орлянку) Играют два игрока. Каждый игрок держит в кулаке свою монету, затем игроки одновременно разжимают пальцы.
Если монеты повернуты одинаковой стороной (герб или решка), то первый игрок ( А ) выигрывает 1 руб., если же монеты повернуты разными сторонами, то тогда второй игрок ( B ) выигрывает 1 рубль.
Итак, в этой игре у обоих игроков есть по две стратегии. У игрока А :
выигрыши нам известны, то платежная матрица P выигрышей игрока А будет иметь следующий вид:
Если эту игру повторять много раз, то можно говорить о среднем выигрыше игрока А в данной игре. Ниже будет дано решение этой игры.
1.2. СИТУАЦИИ РАВНОВЕСИЯ В МАТРИЧНОЙ ИГРЕ
[1, гл.9, § 2], [2, гл.5, § 1], [3, гл.1, § 3], [4, гл.1, § 2-3], [5, гл.1, § 1], [6, гл.5, § 2], [7, гл.8, § 26].Рассмотрим в целом логику матричной игры глазами двух игроков.
Каждый из игроков стремится максимизировать свой выигрыш.
Логика игры глазами игрока А : если я выберу свою стратегию Аi, то игрок B (будучи не очень глупым) ответит на нее такой стратегий B j, для которой мой выигрыш будет минимальным (т.е. игрок B стремится минимизировать свой возможный проигрыш и навредить игроку А ).
Отсюда следует, что игрок А при любой своей стратегии получит 1 j n aij.
Тогда среди всех таких чисел игрок А выберет максимально возможное, т.е. v max 1 j n aij. Величина v называется нижней ценой игры (максимином) и является гарантированным выигрышем игрока А. При этом, принцип выбора игроком А стратегии, основанной на максимизации минимального выигрыша, называется принципом минимакса, а соответствующая стратегия – максиминной стратегий игрока А.
Для игрока B можно провести аналогичные рассуждения. Пусть он выбрал стратегию B j, тогда в худшем случае он проиграет max aij.
Поэтому второй игрок ( B ) всегда может себе гарантировать проигрыш, равный v min max aij. Величина v называется верхней ценой игры (минимаксом) и является гарантированным проигрышем игрока B.
Сделаем вывод. В матричной игре выигрыш v игрока A всегда больше или равен максимину v, а выигрыш игрока B (т.е. величина v ) всегда больше или равна max min (aij ). Тогда Лемма. В любой матричной игре максимин всегда меньше или равен минимакса, т.е.
Рассмотрим вопрос об оптимальном поведении игроков в антагонистической игре. Естественно считать оптимальной в игре такую ситуацию ( Ai, B j ), от которой не выгодно отклоняться ни одному из игроков. Такая ситуация ( Ai, B j ) называется равновесной, а принцип оптимальности, построенный на равновесной ситуации, – принципом равновесия. Ситуацию ( Ai, B j ) или, в других обозначениях, – (i, j ) принято еще называть седловой точкой. Номера i и j обозначают оптимальные стратегии игроков A и B.
Теорема. Если в матричной игре существует седловая точка (i, j ), то говорят, что она имеет решение в чистых стратегиях. Причем Ai – оптимальная стратегия игрока A, а B j – оптимальная стратегия игрока B. В этом случае тогда Вообще, матричная игра может и не иметь седловых точек, либо иметь, по крайней мере, одну из них.
Так, в примере 1, седловой точки нет. В этом случае говорят, что игра не имеет решения в чистых стратегиях. Рассмотрим другой пример.
Пример 2. Пусть имеется платежная матрица P. Найти все седловые точки в этой игре:
образом, в данной игре есть две седловые точки: ( A2, B3 ) и ( A2, B5 ), а
1.3. СМЕШАННОЕ РАСШИРЕНИЕ МАТРИЧНОЙ ИГРЫ
[1, гл.9, § 3], [2, гл.5, § 1.2], [3, гл.1, § 4], [4, гл.1, § 4-5], [5, гл.1, §2], [6, гл.5, § 3-4], [7, гл.8, § 26].Если в матричной игре не существует ситуации равновесия (т.е.
v v ), то применение игроками A и B своих чистых максиминных и минимаксных стратегий не дает оптимального решения игры, так как они могут получить и больший выигрыш. Однако сообщение о выборе стратегии противнику может привести к еще большим потерям, чем в случае максиминной или минимаксной стратегии.
Оказывается, что компромиссного распределения разности v v между игроками и уверенного получения игроками своего выигрыша можно достичь путем случайного применения ими своих чистых стратегий. В этом случае обеспечивается наибольшая скрытность выбора стратегии (результат выбора не может быть известен противнику, поскольку до реализации случайного механизма он не известен самому игроку).
Определение. Случайная величина, значениями которой являются стратегии игрока, называется его смешанной стратегией.
Так, в матричной (m n) игре смешанной стратегией игрока A является m мерная случайная величина x ( p1, p2,..., pm ), у которой случайная величина y (q1, q2,..., qn ), у которой В (4)-(5) величины p i, q j – это вероятности выбора игроками A и B своих стратегий Аi и B j. Если pi 1, то это означает, что игрок A выбрал свою «чистую» стратегию Аi, тогда x (0,...,1,...,0) (i).
Аналогичные рассуждения можно провести и для игрока B.
Пара ( x, y ) смешанных стратегий игроков в игре называется ситуацией в смешанных стратегиях.
В условиях смешанных стратегий ситуация Аi, B j (в чистых стратегиях) является случайным событием и в виду независимости наборов вероятностей ( p1, p2,..., pm ) и (q1, q2,..., qn ) вероятность его появления равна p i q j. В такой ситуации игрок A получает выигрыш, равный a ij. Тогда выигрыш v игрока A в ситуации ( x, y ) в смешанных стратегиях для матричной (m n) игры можно определить как математическое ожидание H A ( x, y ) (среднее значение) его выигрыша при условии, что игроки используют смешанные стратегии x и y соответственно:
В векторно-матричной форме записи формула (6) примет вид:
при этом функция H A ( x, y ) является непрерывной по x и y.
Определение. Ситуация ( x, y ) является ситуацией равновесия в матричной (m n) игре, а число v H A ( x, y ) – ценой игры, если при любых x и y :
Ситуацию равновесия ( x, y ), удовлетворяющую соотношению (8), принято называть оптимальной ситуацией в смешанных стратегиях.
Приведенное условие оптимальности (8) означает, что Теорема (Дж. фон Нейман). В любой матричной игре существует хотя бы одна ситуация равновесия в смешанных стратегиях.
Основные свойства оптимальных смешанных стратегий 1. Пусть x ( p1,..., pm ) и y (q1,..., q n ) – оптимальные смешанные стратегии игроков A и B, и v H A ( x, y ) – цена игры.
Оптимальная смешанная стратегия x игрока A смешивается только из тех стратегий Аi i 1, m, т.е. отличными от нуля будут только те вероятности p i, для которых выполнены равенства:
Аналогично для игрока B : оптимальная смешанная стратегия y игрока A смешивается только из тех стратегий B j j 1, n, т.е.
отличными от нуля будут только те вероятности q j, для которых выполнены равенства:
В формулах (10)-(11) знак i в аргументе функции H A ( x, y ) означает, что игрок A выбрал свою чистую стратегию Аi, и, соответственно, j означает, что игрок B выбрал свою чистую стратегию B j.
Кроме того, выполняются соотношения:
Соотношение (12) можно переписать и в такой форме:
2. Для того, чтобы ситуация ( x, y ) была ситуацией равновесия в матричной (m n) игре, и число v H A ( x, y ) – ценой игры, необходимо и достаточно, чтобы выполнялись следующие неравенства:
3. Для того, чтобы ситуация ( x, y ) была ситуацией равновесия в матричной (m n) игре, необходимо и достаточно выполнения следующего равенства (см. равенство (12а)):
4. В матричной игре множества оптимальных смешанных стратегий игроков A и B являются выпуклыми многогранниками [4, гл.1, § 5].
5. Пусть платежная матрица P матричной игры является кососимметрической, т.е. aij a ji для i j. Тогда, если x – оптимальная смешанная стратегия игрока A, то такую же оптимальную стратегию имеет и игрок B : y x, при этом цена игры v 0.
На этих свойствах основаны методы решения матричных игр.
1.4. РЕШЕНИЕ МАТРИЧНОЙ ИГРЫ [1, гл.9, § 3-4], [2, гл.5, § 5.1], [3, гл.1, § 5], [6, гл.5, § 3-4].
Рассмотрим матричную игру размера 2 2, которая является простейшим случаем конечной игры. Пусть платежная матрица P игры имеет вид:
Пусть игра не имеет решения в чистых стратегиях, т.е. v v. Это означает, что решение следует искать в смешанных стратегиях.
Рассмотрим аналитический способ решения.
игрока A (если p 0, то это означает, что игрок A выбрал свою чистую стратегию A2 ; если p 1, то это означает, что игрок A выбрал свою чистую стратегию A1, что в данном случае недопустимо). Таким образом, обе стратегии игрока A являются активными (определение приведено в разделе 1.5.2). Тогда из свойства 1 и равенства (11) (см. также (12в) в 1.5.2) следует, что какую бы чистую стратегию не выбрал игрок B, если x ( p,1 p) – оптимальная стратегия игрока A, то цена игры v будет определяться из следующих равенств:
Отсюда получим следующее решение:
Аналогичные рассуждения можно провести и для игрока B : если y q1, q2 (q,1 q), 0 q 1 – оптимальная смешанная стратегия игрока B, то из свойства 1 и равенства (10) следует, что Отсюда имеем:
Так, решение игры из примера 1 будет иметь следующий вид:
Таким образом, оптимальной стратегией игрока A будет x ;, а цена игры v 0.
Аналогично для игрока B :
Значит, игрокам A и B при многократном проведении игры следует применять обе свои стратегии в пропорции 1:1.
Приведем геометрическое решение игры 2 2.
Отложим по оси абсцисс Ox единичный отрезок A1 A2 : точка A ( x 0 ) изображает стратегию A1, а все промежуточные точки этого отрезка – смешанные стратегии x ( p1, p2 ) игрока A, причем расстояние от x до правого конца A2 – это вероятность p1 выбора стратегии A1, а расстояние до левого конца A1 – вероятность p 2 выбора стратегии A2. На перпендикулярных осях I-I и II-II откладываются выигрыши при стратегиях A1 и A2.
Если игрок B выберет стратегию B1, то она даст игроку A выигрыши a11 и a21 на осях I-I и II-II, соответствующие стратегиям A1 и A2. Обозначим эти точки на осях I-I и II-II буквой B1. Средний выигрыш v1, соответствующий смешанной стратегии x ( p1, p2 ), определяется тогда по формуле: v1 a11 p1 a21 p2, и равен ординате точки M 1, принадлежащей отрезку B1 B1 и имеющей абсциссу x (см. рис.1а).
Аналогично, строим отрезок B2 B2, соответствующий применению игроком B его стратегии B2. При этом средний выигрыш v определяется по формуле: v2 a12 p1 a22 p2, и равен ординате точки M 2, принадлежащей отрезку B2 B2 (см. рис.1б).
Объединим рис.1а и рис.1б и покажем графическое решение на рис.2.
В соответствии с принципом максимина оптимальная стратегия x такова, что минимальный выигрыш игрока A (при наихудшем поведении игрока B ) обращается в максимум. Ординаты точек, лежащих на выделенной ломаной B1MB2, на рис.2 показывают минимальный выигрыш игрока A при использовании им любой смешанной стратегии (участок B1M – против стратегии B1, участок MB2 – против стратегии B2 ). Оптимальную стратегию определяет точка M, в которой минимальный выигрыш достигает максимума, а ее ордината равна цене игры v.
Пример 3. Применим данный геометрический метод к нахождению оптимальной стратегии игрока A в игре с платежной матрицей P Найдем сначала максимин v и минимакс v : v max{ 2,1} 2, v min{ 3, 5} 3. Итак, решение нужно искать в смешанных стратегиях.
На рис.3 приведено геометрическое решение примера 3. Используя рис.3, вычислим точку пересечения прямых B1 B1 и B2 B2. Уравнение прямой B1 B1, проходящей через точки (0; 2) и (1; 3):
Уравнение прямой B2 B2, проходящей через точки (0; 5) и (1; 1):
Тогда координаты точки пересечения M прямых B1 B1 и B2 B определяются из системы:
Аналогичным способом, приведенным выше, можно определить оптимальную стратегию игрока B, если поменять местами игроков A и B, и вместо максимума нижней границы B1MB2 (рис.2) в соответствии с принципом минимакса рассмотреть минимум верхней границы A1 NA (рис.4). Абсцисса точки N на ломаной A1 NA2 определяет значение q 2 в оптимальной стратегии y (q1, q2 ) игрока B, а ордината этой точки – цену игры v.
Итак, на рис.4 показан графический способ отыскания оптимальной стратегии игрока B в примере 3. Найдем координаты точки N пересечения прямых A1 A1 и A2 A2. Для этого составим уравнения этих прямых.
Уравнение прямой A1 A1, проходящей через точки (0; 2) и (1; 5):
Уравнение прямой A2 A2, проходящей через точки (0; 3) и (1; 1):
Значит, координаты точки пересечения N прямых A1 A1 и A2 A определяются из системы:
Сделаем проверку полученного решения. Используем формулу (6):
Таким образом, решение найдено Оптимальные смешанные стратегии игроков A и B следующие: x ; ; y ;.
Отметим, что графический способ решения годиться и в том случае, если игра имеет решение в чистых стратегиях (подробнее см. [1 гл.9, § 4]).
Если платежная матрица P содержит отрицательные числа, то при графическом решении удобнее перейти к новой матрице, содержащей только положительные числа. Для этого нужно ко всем элементам матрицы P добавить подходящее положительное число. Ответ на вопрос о том, как при этом изменится решение игры с новой матрицей, дает следующая лемма.
Лемма (о масштабе, аффинное правило). Пусть x и y – оптимальные стратегии двух игроков, а v – цена игры в матричной m n игре с платежной матрицей P, причем где и – некоторые числа, 0. Тогда в матричной игре с платежной матрицей P оптимальные стратегии будут такими же, как и в матричной игре с платежной матрицей P, а цена игры Лемма о масштабе показывает стратегическую эквивалентность двух игр, отличающихся только началом отсчета выигрышей и масштабом их измерения.
1.5. ГРАФИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ МАТРИЧНЫХ ИГР
[2, гл.5, § 1.3], [3, гл.1, § 6], [4, гл.1, § 6-7], [5, гл.1, § 4], [6, гл.5, § 6].Рассмотрим матричные игры, число стратегий в которых у одного из игроков равно двум. В этом случае, как и для матричной (22)-игры, решение можно получить геометрически.
1.5.1. РЕШЕНИЕ МАТРИЧНОЙ (2n)-ИГРЫ В этом случае платежная матрица P игры имеет вид:
Согласно указанным выше свойствам оптимальных стратегий 1- нахождение цены игры v и оптимальной стратегии x ( p, 1 p ) игрока A равносильно разрешению уравнения (см. ф.(11)-(12)):
где x ( p,1 p) ( p1, p2 ) – произвольная смешанная стратегия игрока A. В формуле (20) фактически записан выигрыш H A ( x, j ) игрока A, когда игрок B применяет одну из своих n чистых стратегий ( j ) :
Наша задача определить максимум в формуле (20). Проще всего это сделать, построив график функции v a1 j p a2 j (1 p) на плоскости pOv. Указанное уравнение описывает на данной плоскости прямую линию, т.е. каждой чистой стратегии ( j ) игрока B соответствует своя прямая. Поэтому сначала нужно нанести на плоскость pOv все прямые вида v a1 j p a2 j (1 p), j 1, n. Затем для каждого значения p ( 0 p 1 ) путем визуального сравнения соответствующих ему значений v на каждой из построенных прямых определяется и отмечается минимальное из них. В результате описанной процедуры получается ломаная, которая и является графиком функции 1 j n a1 j p a2 j (1 p) (выделена жирной линией на рис.5). Эта ломаная как бы огибает снизу все семейство построенных n прямых, и поэтому ее называют нижней огибающей этого семейства. Верхняя точка построенной нижней огибающей определяет цену игры v и оптимальную стратегию игрока A :
x ( p, 1 p ) (на рис.5. эта точка есть пересечение прямых, отвечающих Bl и Bk стратегиям игрока B ).
Описанная процедура решения может рассматриваться как некоторый аналог максиминного подхода для игрока A при отсутствии седловой точки.
Утверждение. Лучшая стратегия игрока A против чистых стратегий Пример 4. Решить матричную игру с платежной матрицей Сначала исследуем матрицу P на наличие седловой точки.
v max{ 2, 2} 2, v min{ 7, 5, 11} 5, т.е. седловой точки нет. Значит решение игры нужно искать в смешанных стратегиях.
Вычисляем средние выигрыши игрока A по формуле (21), когда игрок B применяет одну из своих трех чистых стратегий:
Приведенные выше три уравнения фактически можно получить при помощи умножения строки ( p, 1 p) слева на столбцы матрицы P.
Далее, строим все три полученные выше прямые на координатной плоскости pOv (см. рис.6), и находим их нижнюю огибающую. На выделенной огибающей находим аналитически координаты наивысшей точки. Из рис.6, видно, что эта точка является пересечением 2-ой и 3-ей прямых, поэтому оптимальное значение p ищем из системы уравнений:
В результате получаем решение: p Таким образом, оптимальная смешанная стратегия x игрока A будет следующая: x ;.
Опишем далее процедуру отыскания оптимальной смешанной стратегии игрока B. В зависимости от формы нижней огибающей здесь может представиться несколько случаев.
1. Нижняя огибающая имеет ровно одну наивысшую точку ( p, v ).
а) Если p 0, то это означает, что игрок A придерживается своей чистой стратегии А2 (см. рис.7а). Тогда игроку B выгодно применять чистую стратегию, соответствующую номеру прямой (на рис.7а это прямая ( j ) ), проходящей через точку (0, v ) и имеющей наибольший отрицательный наклон.
б) Если p 1, т.е. игрок A выбрал чистую стратегию А1, то оптимальной для игрока B является чистая стратегия, соответствующая номеру прямой, проходящей через точку (1, v ) и имеющей наименьший положительный наклон (см. рис.7б).
в) Если 0 p 1, то в наивысшей точке нижней огибающей пересекаются как минимум две прямые, одна из которых (k-ая) имеет положительный наклон, а другая (l-ая) – отрицательный (см. рис.7в), и оптимальная смешанная стратегия игрока B получается, если положить:
смешанная стратегия игрока B, а величина q есть решение уравнения:
2. Нижняя огибающая содержит горизонтальный участок, соответствующий чистой стратегии ( j ) игрока B, которая и является оптимальной для него (см. рис.7г).
Вернемся к решению примера 4. Здесь игрок B обладает тремя стратегиями, поэтому его смешанная стратегия будет: y (q1, q2, q3 ). Так как прямые линии (2) и (3) на рис.6 определяют наивысшую точку нижней огибающей, то, используя пункт 1в), следует принять: q1 0, q2 q, q3 1 q ( q1 q2 q3 1 ). Далее, из формулы (22) следует, что Отсюда получаем следующее оптимальное решение: y 0,,.
Проверка:
Пусть теперь игрок B имеет две стратегии B1 и B2, и его смешанная стратегия определяется вектором y (q1, q2 ), q1 q2 1 ; а игрок A имеет m стратегий A1, …, Am. Тогда платежная матрица P имеет вид:
Анализ такой игры во многом напоминает рассуждения, описанные для игры (2 n).
Пусть y (q1, q2 ) – произвольная смешанная стратегия игрока B.
Тогда выигрыш игрока B в ситуации (i, y ), т.е. когда игрок A придерживается своей чистой стратегии Ai ( i 1, m ), равен:
Графиком функций H A (i, y), определяемых формулой (23), являются m прямых линий на плоскости qOv. Рассмотрим верхнюю огибающую этих прямых, т.е. функцию H A (q) maxai1q ai 2 (1 q). Эта функция будет выпуклой (как верхняя огибающая семейства выпуклых функций).
Точка минимума q функции H A (q) дает оптимальную смешанную стратегию y (q, 1 q ), а цена игры v будет определяться как:
Таким образом, на координатной плоскости qOv точка q будет абсциссой нижней точки полученной верхней огибающей (ломаной линии) (см. рис.8а), которое и определяет оптимальную стратегию игрока B, а ординатой этой точки будет цена игры v.
Отыскание оптимальной смешанной стратегии игрока A проводится по той же схеме, которая позволяет найти оптимальную стратегию игрока B в игре (2 n). Рассмотрим пример.
Пример 5. Пусть платежная матрица P имеет следующий вид:
Сначала проанализируем игру на наличие седловой точки:
точки нет. Итак, решение будем искать в смешанных стратегиях.
Вычисляем средние выигрыши игрока B по формуле (23), когда игрок A применяет одну из своих четырех чистых стратегий:
Приведенные выше четыре уравнения могут быть также получены при помощи умножения строк матрицы P справа на столбцы Далее, наносим найденные прямые на координатную плоскость qOv (см. рис.8б). Из рис.8б видно, что нижняя точка верхней огибающей (выделена жирной линией) является точкой пересечения прямых (2) и (4).
Решая систему образом, оптимальной стратегией игрока B будет y,.
Ищем далее оптимальную стратегию игрока A. Так как нижняя точка верхней огибающей лежала на пересечении (2)-ой и (4)-ой прямых, то смешанная стратегия игрока A будет иметь следующий вид:
средние выигрыши игрока A, когда игрок B придерживается одной из своих двух чистых стратегий:
оптимальной смешанной стратегией игрока A будет x 0; ; 0;.
Приведем еще некоторые свойства (теоремы), полезные при отыскании решения игры.
Теорема 1.5.1. Пусть x ( p1, p2,..., p m ) и y (q1, q2,..., qn ) – оптимальные стратегии игроков A и B. Тогда для любого i ( i 1, m ), при котором H A (i, y ) v, имеет место равенство pi 0, а для любого j ( j 1, n ) такого, что v H A ( x, j ), имеет место равенство q j 0.
H A ( x, j ) v (сравните со свойством 2 для оптимальных смешанных стратегий двух игроков).
B ) называется существенной или активной стратегией, если существует оптимальная стратегия x ( p1, p2,..., p m ) (или y (q1, q2,..., qn ) ) этого игрока, для которой pi 0 ( q j 0 ).
Из этого определения и предыдущей теоремы следует, что для любой существенной стратегии ( i ) игрока A и любой оптимальной стратегии y игрока B выполняется равенство в игре (см. равенства (11) и (12а)):
где a i – i -ая строка матрицы P.
Аналогичное равенство имеет место для любой существенной стратегии ( j ) ( j 1, n ) игрока B и оптимальной стратегии x игрока A :
где a j – j -ый столбец матрицы P.
[3, гл.1, § 3-6], [4, гл.1, § 8], [6, гл.5, § 4].
Сложность решения матричной игры возрастает с увеличение размеров матрицы платежей P. Поэтому следует проанализировать матрицу P с целью сокращения ее размерности. При анализе платежной матрицы сразу же можно выделить стратегии, являющиеся дублирующими или заведомо невыгодными для сторон.
Определение 1. Говорят, что смешанная стратегия x игрока A доминирует его стратегию x в (m n)-игре, если для всех чистых стратегий игрока B выполняются неравенства:
Определение 2. Говорят, что чистая стратегия Ai (или i ) игрока A доминирует его чистую стратегию Al (или l ), если aij alj, j 1, n.
Если указанное неравенство выше выполняется строго, то в этом случае стратегия Ai доминирует строго стратегию Al. Тогда стратегию Al игроку A использовать не нужно и необходимо удалить соответствующую l -ую строку из платежной матрицы P.
Определение 3. Аналогично, смешанная стратегия y игрока B доминирует его смешанную стратегию y, если для всех чистых стратегий игрока A имеем:
Определение 4. Говорят, что чистая стратегия B j (или j ) игрока B доминирует его чистую стратегию Bk (или k ), если aij aik, i 1, m.
Если указанное неравенство выполняется строго, то в этом случае стратегия B j доминирует строго стратегию Bk. Тогда стратегию Bk игроку B нет необходимости использовать и необходимо удалить соответствующий k -ый столбец из платежной матрицы P.
Формулы (24) и (25) означают, что строка (столбец) матрицы P должны быть не больше (не меньше) некоторой выпуклой линейной комбинации остальных строк (столбцов).
Определение 5. Говорят, что в (m n)-игре i -ая стратегия дублирует j -ую стратегию, если Все дублирующие стратегии, кроме одной из них, нужно удалять из игры, и считать, что вероятности их выбора равны нулю.
Определение 6. Стратегии x и x игрока A называются эквивалентными в игре, если для всех j 1, n : xa j xa j, т.е. x x.
При этом выполняется равенство: H A ( x, y ) H A ( x, y ).
Аналогично для игрока B.
Определение 7. Стратегии y и y игрока B называются эквивалентными в игре, если для всех j 1, m : ai y ai y, т.е. y y.
При этом выполняется равенство: H A ( x, y) H A ( x, y).
Определение 8. Стратегия x ( y ) игрока A ( B ) доминируема, если существует стратегия x ( y ) этого игрока, которая доминирует x ( y ).
Игроки A и B не должны использовать свои доминируемые стратегии в игре. Укажем здесь несколько теорем.
Теорема 1. Если в игре стратегия x одного из игроков доминирует оптимальную стратегию x, то стратегия x также оптимальна.
Теорема 2. Если в игре стратегия x одного из игроков оптимальна, то x – доминируема строго (т.е. для нее формулы (24)-(25)не выполняются).
Теорема 3. Пусть в (m n)-игре i -ая строка ( j -ый столбец) матрицы P доминируема (доминируем) и пусть P – матрица, получаемая из матрицы P вычеркиванием i -ой строки ( j -го столбца). Тогда справедливы следующие утверждения:
1. v A v A (цены обоих игр совпадают).
2. Всякая оптимальная стратегия y игрока B (оптимальная стратегия x игрока A ) в игре с матрицей P является оптимальной и в игре с матрицей P.
3. Если x ( y ) – оптимальная смешанная стратегия игрока A ( B ) в игре с матрицей P, то оптимальная смешанная стратегия x ( y ) игрока A ( B ) в игре с матрицей P получается из стратегии x ( y ) добавлением на i -ое ( j -ое) место в x ( y ) нуля.
Приведем примеры, поясняющие указанные здесь определения и теоремы.
Пример 6. Пусть платежная матрица P имеет следующий вид:
Сначала проанализируем игру на наличие седловой точки:
точки нет. Значит ищем решение в смешанных стратегиях.
Стратегии A2 и A4 являются дублирующими, так как 2-ая и 4-ая строки матрицы P совпадают. Следовательно нужно удалить одну из этих строк, например 4-ую. В результате из P получим матрицу P :
Далее, видим, что стратегия A2 доминирует стратегию A1, т.к. для всех элементов второй и первой строки выполнено: a 2 j a1 j, j 1,3.
Поэтому первую строку матрицы P нужно вычеркнуть, что приводит к В матрице P третья строка доминируется выпуклой линейной комбинацией первой и второй строк вида: a3 a1 a 2, поэтому третью строку нужно отбросить.
Линейная комбинация строк a i матрицы P вида 1 a1... k a k является выпуклой, если коэффициенты i этой линейной комбинации удовлетворяют свойствам: i 0, i 1, k и 1... k 1. Аналогично для столбцов этой матрицы.
Итак, от матрицы P приходим к матрице P :
Видно, что третий столбец матрицы P строго доминируется вторым столбцом, поэтому третий столбец нужно отбросить и перейти к В матрице P IV третий столбец доминируем как выпуклая линейная комбинация первого и второго столбцов вида: a a a, поэтому третий столбец нужно отбросить. В результате приходим к матричной игре V с матрицей PV у которой нет доминириуемых строк и столбцов. Решая эту игру аналитически, получим: v 7 p (1 p) 3 p 5(1 p) p 1 2, т.е.
оптимальной стратегией игрока A в игре V будет ( x ),.
Аналогично для игрока B имеем: v 7q 3(1 q) q 5(1 q) q 1 4, т.е. его оптимальной стратегией будет ( y ),. Цена игры здесь v 4.
Проведем графическое решение игры IV с матрицей P IV и покажем его совпадение с предыдущим решением. По формуле (21) имеем:
Полученные три прямые отображены на координатной плоскости pOv на рис.9. Далее, выделяем нижнюю огибающую данного семейства прямых и находим аналитически координаты наивысшей точки. Из рис.9, видно, что эта точка является пересечением 1ой и 2-ой прямых, поэтому оптимальное значение p ищем из системы уравнений:
Отсюда получим: ( x ),, что совпадает с ( x ). Используя здесь только первую и вторую стратегии игрока B, получим такое же решение как и для матрицы PV : ( y ),, 0.
Таким образом, оптимальными стратегиями исходной игры будут следующие (на места удаленных (доминируемых) стратегий добавлены [2, гл.5, § 1], [3, гл.1, § 7], [4, гл.1, § 9].
Пусть все стратегии обоих игроков или хотя бы у одного из них будут активными (существенными) и при этом ни одна из существенных стратегий не является строго доминируемой. Такую ситуацию равновесия ( x, y ) в игре принято называть вполне смешанной (т.е. хотя бы у одного из игроков все вероятности pi ( q j ) ненулевые по i, j ).
Теорема. Если матричная (m n)-игра является вполне смешанной и цена игры v 0, то игра имеет единственное решение и квадратную матрицу ( m n ). При этом, оптимальные стратегии x, y и цена игры v определяются по следующим формулам:
где u (1,1 1).
Комментарий к теореме: если матрица P содержит отрицательные элементы, то ее цена игры может оказаться равной нулю. Тогда, чтобы использовать формулы (26), нужно изменить матрицу P, прибавив к ее элементам любое положительное число, такое, чтобы все элементы стали положительными. Этим мы гарантируем выполнение условия:
v 0. В соответствии с леммой о масштабе, оптимальные стратегии для игры с новой матрицей P P будут такими же, как и в игре с матрицей P.
Пример 7. Рассмотрим игру с матрицей вида Убедимся, что здесь отсутствует седловая точка:
искать решение в смешанных стратегиях.
Так как не все элементы матрицы P положительны, перейдем к новой матрице P P 1, тогда В этой матрице отсутствуют доминируемые строки и столбцы, и она является квадратной, поэтому для поиска оптимальных стратегий применим формулы (26). Для этого найдем обратную матрицу ( P ), применяя метод Гаусса (при помощи элементарных преобразований строк исходную матрицу приводим к единичной, а единичная матрица тем же преобразованиями приводится к обратной):
1.8. РЕШЕНИЕ МАТРИЧНЫХ ИГР МЕТОДАМИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ
[1, гл.9, § 5], [2, гл.5, § 1], [3, гл.1, § 8], [4, гл.1, § 6], [6, гл.1, § 5].Рассмотрим матричную (m n)-игру с матрицей P (aij ) mn. Будем полагать, что цена игры v 0. Это предположение всегда выполняется, если элементы a ij матрицы P неотрицательны, т.е. aij 0. Если в исходной матрице P есть отрицательные числа, всегда можно прибавить такое максимальное положительное число, при котором aij 0, i, j. При этом цена игры также увеличиться на это число (лемма о масштабе).
Итак, пусть v 0, что возможно если все элементы aij 0.
Посмотрим сначала на игру глазами игрока A.
Из свойств оптимальных смешанных стратегий игроков следует, что при оптимальном поведении игрока A (т.е. когда он выбирает свою оптимальную стратегию x ( p1,..., pm ) ) и любом поведении противника (игрока B ) сумма его выигрыша не меньше, чем цена игры v, поэтому в случае выбора игроком B его чистых стратегий B j, j 1, n можно записать следующие уравнения:
Иными словами выполняются соотношения:
Из (27а) следует, что где xi. Так как игрок A стремится максимизировать свой выигрыш, то задача поиска оптимального решения для игрока A в матричной игре сводится к решению следующей задачи: найти величины xi 0, i 1, m удовлетворяющие системе ограничений такие, что их сумма минимальна:
Рассмотрим теперь игру глазами игрока B. Если игрок B использует свою оптимальную стратегию y (q1,..., q n ), а игрок A – одну из своих чистых стратегий Ai, i 1, m, то средний выигрыш H A (i, y ) в игре будет не больше, чем цена игры, т.е. выполняются соотношения Так как игрок B стремится минимизировать свой проигрыш v, то задача поиска оптимального решения для игрока B сводится к решению следующей задачи: найти величины y j 0, j 1, n, удовлетворяющие системе ограничений такие, что их сумма максимальна:
Задача (29)-(30) называется прямой задачей линейного программирования, а задача (33)-(34) – двойственной задачей линейного программирования в матричной (m n)-игре. Решение этих задач может быть получено аналитически при помощи так называемого симплексметода.
Итак, матричная (m n)-игра свелась к решению двух двойственных задач линейного программирования (29)-(30), (33)-(34), в которых min F ( x) max G( y), где v – это цена исходной матричной игры.
Сформулируем кратко алгоритм симплекс-метода с использованием симплекс-таблиц.
Симплекс-метод основан на утверждении о том, что линейная функция F (x) (или G ( y ) ) задачи линейного программирования достигает своего оптимума (максимума или минимума) в одной из угловых точек многогранника решений, который определяется неравенствами (29) или (33). Идея симплекс-метода состоит в направленном переборе угловых точек с последующим уменьшением значений целевой функции F (x) для задачи на минимум (или увеличением значений целевой функции G ( y ) для задачи на максимум).
Рассмотрим реализацию симплекс-метода для следующей общей задачи линейного программирования: найти максимум (минимум) линейной функции F ( x) c j x j относительно n неизвестных x1, …, x n, удовлетворяющих системе ограничений, состоящей из m уравненийнеравенств вида:
В векторно-матричной форме это выглядит так:
при ограничениях ограничений (35) (или (37)) встречаются в задачах на максимум, а знаки – в задачах на минимум. Возможны также и случаи, когда в системе ограничений типа (37) встречаются как знаки неравенств и, так и знаки равенства "".
Симплекс-метод применяется к канонической задаче линейного программирования, т.е. когда все ограничения на неизвестные являются ограничениями-равенствами. Чтобы перейти от ограничений вида (35), (37) к ограничениям-равенствам, нужно в каждое уравнение системы ограничений добавить по одной положительной переменной x n i, i 1, m либо с коэффициентом 1 (в случае неравенства ), либо с коэффициентом 1 (в случае неравенства ). В результате этого задача линейного программирования примет следующий канонический вид:
при ограничениях-равенствах Таким образом, система ограничений вида (39) состоит из m уравнений с n m неизвестными.
Для реализации симплекс-метода необходимо установить три основных элемента:
1. способ определения начального допустимого базисного решения;
2. правило перехода к лучшему (по сравнению с предыдущим) 3. критерий проверки оптимальности найденного решения.
Не теряя общности, будем считать, что система ограничений типа равенств для канонической задачи (38) имеет следующий вид:
Будем полагать, что ранг матрицы системы ограничений (40) совпадает с рангом расширенной матрицы этой системы, т.е.
являются линейными комбинациями предыдущих уравнений и их можно отбросить. В случае, если r 2 или n 2, решение задачи (38) можно найти геометрически. Подробнее об этом можно почитать в [1]-[2].
Пусть r m. При этом считаем, что r n. Выберем какие-либо m базисных переменных x j, j 1, m в системе (40) и будем считать их главными (это можно определить через базисный ненулевой минор матрицы A ). Если рассматривать систему ограничений вида (39), то в этой системе в качестве базисных переменных можно взять новые дополнительные переменные x n i, i 1, m, т.к. базисный минор при этих переменных совпадает с определителем единичной матрицы. Дальнейшие рассуждения будут касаться системы ограничений вида (40). Оставшиеся переменные в этой системе, а именно x m 1, …, x n будут тогда свободными. Выразим базисные (основные) переменные x j, j 1, m через свободные переменные, т.е. запишем их в виде:
где свободные переменные x m 1, …, x n могут принимать любые значения.
Положив их равными нулю, получим частное решение системы (40):
Отсюда получаем нулевое (начальное) базисное решение:
Решение (42) будет допустимым базисным решением, если все коэффициенты i 0, i 1, m, иначе это решение будет недопустимым, и тогда нужно заново выбирать другие базисные переменные.
Пусть решение (42) допустимо. Функцию F (x) в (38) нужно преобразовать так, чтобы базисные переменные были выражены через свободные. В результате этого функция F (x) примет следующий вид:
где знак "" будет для задачи на минимум, а знак ”–” для задачи на максимум. При этом для задачи на минимум:
а для задачи на максимум:
Здесь вектор C б состоит из коэффициентов ci при базисных переменных X б ( 1( 0 ), 2( 0 ),..., m0 ) ), т.е. состоит из значений допустимых базисных переменных x i (на начальном шаге); вектор X j – это столбец, состоящий ограничений (41). Все коэффициенты системы (41), а также ci, 0 и j удобно свести в так называемую симплекс-таблицу, которая отражает ход решения, достигнутое решение и признак оптимальности на каждом шаге алгоритма симплекс-метода.
Итак, начальная симплекс-таблица может принять следующий общий вид:
Симплекс-таблица 1 (0-й шаг):
В первом столбце "б" симплекс-таблицы перечислены базисные переменные, во втором столбце " C б " указаны коэффициенты ci при базисных переменных в функции F (x), в третьем столбце " X б " приведены значения базисных переменных, что соответствует достигнутому решению x ( 0 ) (на начальном нулевом шаге) для исходной задачи. На пересечении строк и столбцов, в которых выписаны базисные переменные x i ( i 1, m ), можно заметить единичную матрицу. Это правило сохраняется для всех симплекс-таблиц. Далее идут столбцы " X j " ( j m 1, n ): в них выписаны коэффициенты ij, i 1, m при остальных переменных (свободных или небазисных) в системе (41). Последний столбец (1,..., m ) определяет базисную переменную, которую нужно вывести из базиса. Прокомментируем последнюю строку таблицы.
Здесь значение 0 F ( x ), а значения j, j m 1, n определяют оптимальность достигнутого решения. Отметим, что у базисных переменных j 0, j 1, m.
Укажем признак оптимальности достигнутого решения: если на некотором шаге s все j 0, j 1, n, то полученное допустимое базисное решение будет оптимальным и максимум (минимум) функции F (x) равен числу (0s ), т.е. F * F ( x * ) (0s ) max(min) F ( x).
отрицательны. В этом случае достигнутое решение x (s ) не является оптимальным, поэтому следует перейти к новому допустимому базисному решению x ( s1), при котором значение функции F (x) увеличится (для задачи на максимум) или уменьшится (для задачи на минимум). Укажем здесь алгоритм перехода к новой симплекс-таблице.
Итак, из множества отрицательных коэффициентов j выбираем максимальный по модулю (если таких будет несколько, то берем первый из них). Пусть это будет l. Индекс l тогда определяет некую свободную переменную x l, которую нужно сделать базисной.
Соответствующий столбец X l в симплекс-таблице принято называть разрешающим столбцом.
Далее, для каждой строки симплекс-таблицы определим ограничения на новую базисную переменную x l, чтобы выяснить за счет какой старой базисной переменной в базис вводится новая переменная x l. Ограничения i( s ), i 1, m (по каждой базисной переменной) вычисляем по следующему правилу:
1) если i и i,l имеют разные знаки, то i (вместо знака ” ” в самом правом столбце симплекс-таблицы можно ставить знак ” – ”);
5) если i и i,l имеют одинаковые знаки, то Далее, определяется k min i. Индекс k здесь указывает базисную переменную x k, которая выводится из базиса, и ее место займет новая переменная x l. Соответствующая этой переменной k -ая строка симплекс-таблицы называется разрешающей строкой. Элемент k,l, стоящий на пересечении разрешающей строки и разрешающего столбца называется разрешающим элементом симплекс-таблицы.
При переходе к новой симплекс-таблице поступаем следующим образом: 1) все элементы разрешающей строки (кроме коэффициента с k ) делим на разрешающий элемент k,l ; 2) в столбцах X j, соответствующих базисным переменным, ставим 0 и 1, причем значение 1 – напротив своей базисной переменной, а значение 0 – напротив остальных базисных переменных; 3) остальные элементы новой симплекс-таблицы вычисляются по следующему правилу (правило Гаусса):
Получив на шаге s +1 новую симплекс-таблицу, вычисляем коэффициенты ее последней строки по формулам (44)-(46) (верхний индекс «0» в коэффициентах заменить на s +1). Далее, повторяем рассуждения относительно оптимальности достигнутого решения.
Рассмотрим пример решения матричной игры при помощи указанного выше алгоритма симплекс-метода. По ходу решения укажем способ отыскания решения для двойственной задачи линейного программирования.
Пример 8. Определить при помощи линейного программирования решение игровой задачи с платежной матрицей:
Определим верхнюю и нижнюю цены игры:
Значит, решение ищем в смешанных стратегиях игроков:
Так как не все элементы матрицы P положительны, перейдем к новой матрице P P 1, тогда и v v A 1 – цена игры с новой матрицей P.
взаимно-двойственные задачи линейного программирования (см. (29)-(30) и (33)-(34)):
задача 1. Найти минимум линейной функции F ( x ) x1 x2 x3 1 v min при ограничениях:
После приведения системы ограничений к каноническому виду, получим:
Если переменные x 4, x 5, x 6 принять в качестве базисных, а переменные x1, x 2, x 3 – свободными, то при x1 x2 x3 0 получим первое базисное решение x (0, 0, 0, 1, 1, 1), которое не является допустимым. Укажем здесь один из универсальных подходов исправления такой ситуации. Этот подход получил название метод искусственного базиса (или М-метод).
Суть М-метода состоит в следующем (подробнее см. в [1], раздел 5.7). В каждое уравнение системы ограничений, дающее отрицательное значение компоненты в базисном решении, вводим новую искусственную переменную x k ( k 1, l, l m ), которая имеет тот же знак, что и свободный коэффициент в правой части уравнения (см. (39)). Далее, все искусственные переменные делаем базисными. При этом линейная функция F (x ) (см. (36) и (38)) преобразится в функцию T ( x, ~), которая для задачи на максимум имеет вид: T ( x, ~ ) F ( x ) M ( ~1... ~l ) ( M – произвольное большое положительное число, заведомо большее всех Пусть в ходе решения ЗЛП для функции T ( x, ~) с искусственным базисом симплекс-методом было получено оптимальное решение и в этом решении все искусственные переменные оказались равными нулю, тогда исходная ЗЛП для функции F (x) имеет оптимальное решение (потому что min M ( ~1... ~l ) 0 ). В противном случае исходная ЗЛП не имеет оптимального решения.
Итак, используя М-метод, переходим от системы ограничений (49а) к системе (49б):
где переменные x 7, x 8, x 9 – это искусственные переменные. Делаем эти переменные базисными, а остальные xi, i 1,6 – свободными. Тогда при xi 0, i 1,6 получим начальное (нулевое) допустимое базисное решение x ( 0) (0, 0, 0, 0, 0, 0,1,1,1). В окончательном оптимальном решении x * нас будут интересовать только первые три компоненты вектора x. Функция F (x ) здесь также преобразится и примет следующий вид:
Из (49в) следует, что коэффициенты ci при искусственных переменных равны числу M ( M 0 очень большое число).
На основании (49б-в) построим первую симплекс-таблицу.
Симплекс-таблица 1 (нулевое решение):
Коэффициенты j вычислялись по формулам (44)-(45):
Фактически F ( x ) 0 3M, т.е. это большое положительное число, которое желательно уменьшить. Здесь три отрицательных коэффициента j : 1, 2, 3, значит решение x оптимальным (точкой минимума), поэтому нужно, используя алгоритм симплекс-метода, перейти к другому более оптимальному решению.
Наибольшим по модулю отрицательным коэффициентом j здесь будет (30 ) (смотрим по наибольшему числу при коэффициенте M ). Поэтому переменную x 3 следует ввести в базис ( X 3 – это разрешающий столбец).
Столбец показывает, за счет какой базисной переменной это можно сделать (см. (47)): 7 1 / 4, 8 1 / 1, 9 1 / 0. Наименьшим из этих чисел является 7, поэтому искусственную переменную x 7 следует вывести из базиса (первая строка таблицы x 7 – разрешающая строка). В таблице квадратом выделен разрешающий элемент. Далее переходим к новой симплекс-таблице, проделывая преобразования элементов таблицы по формулам (48). В результате получим таблицу 2.
Симплекс-таблица 2 (первое решение):
Таким образом, допустимое базисное решение будет следующим:
x (1) (0, 0,1 / 4, 0, 0, 0, 0, 3 / 4,1). Здесь для (1) имеем:
Отрицательными коэффициентами j здесь будут: 1, 2 и 4.
Из них выбираем 2 как наибольший по модулю, тогда столбец X становится разрешающим и соответствующую переменную x 2 нужно ввести в базис. Вычисляем ограничения на x 2 : 3 1 / 4 : 0, 8 3 / 4 : 3 1 / 4, 9 1 / 1 1. Таким образом, из базиса следует вывести переменную x8, и на ее место ввести переменную x 2. Далее, проделывая преобразования элементов таблицы 2 по формулам (48), приходим к новой симплекс-таблице 3.
Симплекс-таблица 3 (второе решение):
x ( 2) (0,1 / 4,1 / 4, 0, 0, 0, 0, 0,3 / 4). Здесь для ( 2 ) имеем:
Отрицательными коэффициентами j являются: 1 и 5, при этом наибольшим по модулю из них будет 1. Значит, столбец X становится разрешающим и переменную x1 необходимо ввести в базис.
Т.к. 9 3, то переменную x 9 следует вывести из базиса. Далее, проделывая преобразования элементов таблицы 3 по формулам (48), приходим к новой симплекс-таблице 4.
Симплекс-таблица 4 (третье решение):
Итак, допустимое базисное решение x ( 3) имеет вид:
x (3) (9 / 25, 7 / 25, 4 / 25, 0, 0, 0, 0, 0,0).
Для коэффициентов j имеем:
учитывается), то достигнутое решение x ( 3) является оптимальным (в данном случае – минимальным), т.е. x (9 / 25, 7 / 25, 4 / 25 ) (здесь учтены только исходные переменные x1, x2, x3, остальные переменные были либо дополнительными, либо искусственными), при этом имеем: v A v 1 1/ 4. Из решения x * можно легко получить оптимальную стратегию для игрока A : x A x v (9 / 20, 7 / 20, 4 / 20 ).
Оптимальную стратегию для игрока B можно найти двумя способами: либо составить и решить двойственную задачу линейного программирования (см. (33)-(34)), либо, исходя из принципа двойственности, получить решение из последней симплекс-таблицы предыдущего решения.
Подробнее о принципе двойственности и свойствах двойственных задач линейного программирования можно почитать в [1, глава 6] и [2, глава 4]. Итак, составим вторую (двойственную к первой) задачу линейного программирования для нахождения оптимальной стратегии игрока B. По формулам (33)-(34) и матрице P получим следующее.
задача 2. Найти максимум линейной функции После приведения системы ограничений к каноническому виду, получим:
переменные, и при y1 y 2 y3 0 получим начальное базисное решение y ( 0 ) (0, 0, 0,1,1,1). Это решение допустимо, поэтому, используя (50а), можно решить задачу 2 симплекс-методом точно также как и предыдущую задачу 1. Отметим, что в этой задаче не нужно вводить искусственные переменные, но это не означает, что она будет легче решаться, чем задача 1.
Укажем сначала решение задачи 2, исходя из свойств взаимно двойственных задач линейного программирования. Так, если была получена последняя симплекс-таблица предыдущей задачи 1, то решение задачи 2 ищется из последней строки этой таблицы. Именно, y1 4 (т.е.
коэффициенты j соответствуют оптимальному решению второй двойственной задачи), y 2 (53), y 3 (63). Тогда отсюда имеем: y * (1 / 5, 1 / 5, 2 / 5).
Теперь решим задачу 2 непосредственно, используя двойственный симплекс-метод и таблицы.
На основании (50)-(50а) и начального решения y составим первую симплекс-таблицу:
симплекс-таблица 1 (нулевое решение):
Приведем расчеты коэффициентов j (см. (44), (46)) Есть три одинаковых максимальных по модулю отрицательных коэффициента j : 1, 2 и 3. Выбираем из них первый, т.е. 1, что означает, что переменную y1 нужно ввести в базис. Далее находим ограничения на переменную y1, т.е. коэффициенты i (см. (47)).
Результат приведен в столбце " " симплекс-таблицы 1. Видно, что переменную y 6 нужно выводить из базиса и заменить ее на y1.
Используя общие правила перехода к новой симплекс-таблице и формулы (48), получим следующую таблицу:
симплекс-таблица 2 (первое решение):
Опустим подробные вычисления коэффициентов j и приведем остальные симплекс-таблицы.
симплекс-таблица 3 (второе решение):
симплекс-таблица 4 (третье решение):
В четвертой таблице все коэффициенты j поэтому достигнутое решение y является оптимальным (в данном случае – максимальным) и y y (1 / 5, 1 / 5, 2 / 5) (такое же решение получилось выше из предыдущей задачи на основании принципа y B y v (1 / 4, 1 / 4,1 / 2). По четвертой таблице, исходя из принципа двойственности, можно также определить и решение первой задачи с ограничениями (49). Именно, x1 4 9 / 25 (т.е. коэффициенты j дополнительных переменных y 4, y 5, y 6 соответствуют оптимальному решению второй двойственной задачи), x2 5 7 / 25, x3 6 4 / 25.
Поэтому: x (9 / 25, 7 / 25, 4 / 25 ), что соответствует решению задачи 1.
РАЗДЕЛ 2. БИМАТРИЧНЫЕ ИГРЫ
[2, гл.5, § 2], [3, гл.3, § 1-2], [4, гл.3, § 1-3], [5, гл.2, § 8-9], [6, гл.1, § 7Предыдущие рассмотрения касались игр двух лиц, интересы игроков в которых были противоположны. Однако, на практике чаще встречаются ситуации, хотя интересы игроков не совпадают, но уже не являются противоположными (антагонистическими). Например, при встрече двух боевых единиц двух воюющих сторон их обоюдное стремление уничтожить друг друга не выражает антагонистического конфликта.Биматричной игрой называется конечная бескоалиционная игра двух лиц, т.е. когда каждый из двух игроков имеет конечное число стратегий.
Пусть игрок A имеет m стратегий, а игрок B – n стратегий. Тогда биматричную игру можно описать двумя матрицами выигрышей A и B для игроков A и B :
Здесь a ij – выигрыш игрока A, если он применит свою стратегию Ai, а игрок B – стратегию B j ; bij – выигрыш игрока B в ситуации Ai, B j.
Таким образом, если интересы игроков A и B не совпадают, но не обязательно противоположны, получаются две платежные матрицы:
матрица A – матрица выплат игроку A, другая матрица B – матрица выплат игроку B. Поэтому название игры здесь совершенно естественно – биматричная.
Матричную игру можно считать частным случаем биматричной игры, когда матрица выплат игроку B противоположна матрице выплат игроку A :
В общем случае биматричная игра – это игра с ненулевой суммой.
Рассмотрим некоторые типичные конфликтные ситуации, приводящие к биматричным играм. Сначала укажем формализацию этих конфликтов, а позднее дадим рекомендации по их разрешению.
Пример 1. «Борьба за рынки». Небольшая фирма (игрок A ) намерена сбыть партию товара на одном из двух рынков, контролируемых другой, более крупной фирмой (игрок B ). Для этого фирма A готова предпринять на одном из рынков определенные действия (например.
провести рекламную кампанию). Господствующая на этих рынках фирма B может попытаться воспрепятствовать этому, приняв на одном из рынков предупредительные меры. Если фирма A не встречает противодействия на рынке, то она его захватывает; при наличии препятствий – терпит поражение.
Будем считать для определенности, что проникновение фирмы A на первый рынок более выгодно, чем на второй. Естественно также считать, что борьба за первый рынок потребует вложения больших средств.
Например, победа фирмы A на первом рынке принесет ей вдвое больший выигрыш, чем победа на втором рынке, но зато и поражение полностью ее разорит, а фирму B избавит от конкурента. Что касается второго рынка, то при поражении фирмы A ее потери будут не столь значительны, но и победа принесет немного.
Таким образом, у фирмы A две стратегии: A1 – выбор первого рынка, A2 – выбор второго рынка. Такие же стратегии и у фирмы B : B1 – выбор первого рынка, B2 – выбор второго рынка.
Чтобы составить платежные матрицы игрок, нужны расчетные количественные показатели, которые мы приведем здесь в условных единицах:
Из выписанных матриц видно, что если игроки выберут один и тот же рынок, то победа останется за игроком B.
Пример 2. «Дилемма узников». Игроками являются два узника, находящихся в камере предварительного заключения по подозрению в совершении преступления. При отсутствии прямых улик возможность их осуждения в большей степени зависит от того, заговорят они или будут молчать.
Если оба будут молчать, то наказание им обоим составит ровно 1 год.
Если оба сознаются, то получат срок 6 лет (признание учитывается как смягчающее обстоятельство). Если заговорит только один, а другой будет молчать, то заговоривший будет выпущен на свободу, а промолчавший получит максимально возможное наказание 9 лет.
В этой биматричной игре каждый из игроков имеет две стратегии:
молчать (стратегии A1 и B1 ) или говорить (стратегии A2 и B2 ). При этом их выигрыши описываются так:
Пример 3. «Семейный спор». Два партнера (муж и жена) договариваются совместно провести одно из двух мероприятий: пойти на футбол (Ф) или в театр (Т). В случае осуществления первого из этих двух мероприятий (пойти на футбол) выигрыш первого партнера (игрок A ) вдвое больше выигрыша второго (игрок B ). Наоборот, в случае осуществления второго из этих двух мероприятий выигрыш игрока A будет вдвое меньше выигрыша игрока B.
В этой биматричной игре у каждого из игроков имеется по две стратегии (Ф, Т), при этом они заранее не договариваются, куда им пойти.
Если они не встретятся, то это будет огорчением для обоих. Матрицы выигрышей здесь имеют такой вид:
Пример 4. «Студент-преподаватель». Пусть студент (игрок A ) готовится сдать зачет (например, по теории игр). Игрок B – это преподаватель, который его принимает. У студента две стратегии:
подготовиться к сдаче зачета (+) и не подготовиться (–). У преподавателя также две стратегии: поставить зачет (+) и не поставить зачет (–). В основу функций выигрышей положим следующие соображения:
Количественно это можно выразить, например, так:
2.2. СМЕШАННЫЕ СТРАТЕГИИ. РАВНОВЕСИЕ ПО НЭШУ.
В приведенных выше примерах описаны ситуации, в которых интересы игроков не совпадают. Поэтому необходимо найти такое компромиссное решение, которое в том или ином виде удовлетворяло бы обоих игроков. Таким образом, необходимо найти такую равновесную ситуацию, явное отклонение от которой одного из игроков уменьшило бы его выигрыш. Такая ситуация ранее была найдена в матричных играх: она определялась седловой точкой (если, конечно, она существует).
Рассмотрим биматричную игру в нормальной форме. Пусть игрок A имеет m стратегий Ai ( i 1, m ), а игрок B – n стратегий B j ( j 1, n ).
Ситуация (i, j ) биматричной игры называется ситуацией равновесия (равновесной по Нэшу) в чистых стратегиях, если Для того чтобы найти ситуацию равновесия по Нэшу в чистых стратегиях, необходимо найти в каждом столбце матрицы выигрышей игрока A максимальный элемент и подчеркнуть его. Аналогично, в каждой строке матрицы выигрышей игрока B нужно подчеркнуть максимальный элемент. Если в обеих матрицах будет подчеркнут элемент, стоящий на одном и том же месте, то его положение и определит ситуацию равновесия в игре. Заметим, что в биматричной игре (в отличие от матричной) выигрыши игроков, при наличии нескольких ситуаций равновесия, могут различаться.
Пример. Найти все ситуации равновесия в биматричной игре В матрицах A и B подчеркнуты максимальные элементы, стоящие в столбцах и строках соответственно. Видно, что общий подчеркнутый элемент стоит в позиции (3, 3), т.е. здесь единственная ситуация равновесия: Ai A3, B j B3 и выигрыши игроков следующие: v A 5, В биматричных играх, как и в матричных, можно использовать принцип (строгого) доминирования для удаления заведомо невыгодных стратегий у игроков A и B. Как это делается, подробно описано в соответствующей литературе.
Остановимся теперь на случае, когда игра не имеет ситуаций равновесия в чистых стратегиях. В матричных играх эта трудность была преодолена при помощи перехода к смешанному расширению игры, т.е. к возможности е многократного повторения и такому поведению игроков, при котором они чередуют свои чистые стратегии с определенными вероятностями:
для игрока A : x ( p1, p2,..., pm ) – его смешанная стратегия, где для игрока B : y (q1, q2,..., qn ) – его смешанная стратегия, причем Смешанное расширение матричной игры привело к расширению возможности выплат в том смысле, что вычисляется средний выигрыш игроков A и B :
В биматричных играх также можно перейти к смешанному расширению игры, предполагая, что каждая игра может быть повторена в неизменных условиях. При этом средние выигрыши игроков A и B определяются по их платежным матрицам A и B :
Ситуация {x*, y*} называется ситуацией равновесия (по Нэшу) в смешанных стратегиях биматричной игры, если для любых x и y выполняются неравенства:
Эти неравенства означают, что если один из игроков отклонится от своей равновесной стратегии, то его выигрыш не увеличится.
Теорема (Джон Нэш, 1950). Всякая биматричная игра имеет хотя бы одну ситуацию равновесия, возможно, в смешанных стратегиях.
Рассмотрим далее решение биматричной игры размерности 22.
В этом случае платежные матрицы игроков имеют вид:
формул (57) получим:
Определим ситуацию равновесия, т.е. найдем пару чисел ( p, q ), 0 p *, q * 1, для которой одновременно выполняются неравенства:
Так как величины p и q могут принимать любые значения, то выполнение указанных неравенств равносильно выполнению неравенств:
Таким образом, для определения равновесной ситуации достаточно проверить неравенства (58а) для двух чистых стратегий игроков A и B.
Запишем средние выигрыши игроков в более удобной форме:
Положим:
Используя эти обозначения, из формул (60)-(61) получим:
Из неравенств (58б) и формул (60а)-(61а) следует, что:
Из неравенств (62) для игрока A имеем три случая:
Если C 0, то решением будет являться весь единичный квадрат p [0,1], q [0,1], т.к. условия 1)-3) выполняются при всех p и q.
Если C 0, 0, то выполняется либо условие 1), либо условие 2), т.е. решением является либо p 0, либо p 1.
Если C 0, то получим следующие решения:
Если C 0, то решения будут следующие:
Графическая интерпретация множества решений игрока A :
Решением игры является пересечение множеств решений для игроков A и B. Графически решение будет выглядеть как пересечение двух зигзагов, варианты которых приведены на рисунках выше. При этом эти зигзаги могут быть как противоположными, так и одинаковой направленности. В первом случае мы получим три точки пересечения, т.е.
три состояния равновесия, а во втором – одну.
Укажем решения конкретных примеров.
Пример 1. Рассмотрим игру «борьба за рынки». Платежные матрицы игроков A и B имеют следующий вид:
Так как C 0, то решения для игрока A будут следующие:
Так как D 0, то решения для игрока B будут следующие:
Нанесем полученные решения на график.
Точка пересечения построенных зигзагов – это точка равновесия. Она имеет координаты ( p, q ) 2 / 9; 3 / 14. Тогда оптимальной смешанной стратегией игрока A будет x A 2 / 9; 7 / 9, а у игрока B : y B 3 / 14; 11 / 14.
Средние выигрыши игроков вычисляем по формулам (60а)-(61а):
Разобьем данную биматричную игру на две матричные с нулевой суммой и найдем их решения.
1. Игра с матрицей PA (15)-(16)): x A 1 7 ; 6 7 (оптимальная стратегия игрока A ), y B 3 / 14 ; 11 / (оптимальная стратегия игрока B ), v A 4 7 (цена игры).
2. Игра с матрицей PB (оптимальная стратегия игрока A ), y B 1 / 3; 2 / 3 (оптимальная стратегия игрока B ), v B 1 / 3 (цена игры).
Сравнивая полученные решения с решением биматричной игры, видим, что:
1. оптимальный средний выигрыш игрока в матричной игре совпадает с его выигрышем при равновесной ситуации в биматричной;
2. по своей матрице игрок может определить только оптимальную стратегию (равновесную по Нэшу) другого игрока, но не свою, а для определения своей стратегии нужна матрица противника.
Полученные выводы можно использовать для решения биматричных игр большей размерности, чем 22. Для этого нужно всего лишь решить две матричные игры той же размерности.
В биматричных играх принцип равновесия по Нэшу не всегда приводит к ситуации, выгодной обоим игрокам.
Рассмотрим в связи с этим второй пример "дилемма узников".
Пример 2. В игре "дилемма узников" выигрыши игроков описываются матрицами:
Решаем эту игру как биматричную: C 1 (9) 0 6 2, Так как C 0, то решения для игрока A будут следующие:
q 3 2.
Так как D 0, то решения для игрока B будут следующие:
p 3 2.
Нанесем полученные решения на график (см. рис.13).
Однако при одновременном отклонении обоих игроков каждый из них может получить больший выигрыш, чем в равновесной ситуации.
Именно, в ситуации ( p, q) (1, 1), когда каждый из игроков A и B выбирает первую чистую стратегию "молчать", они теряют лишь 1 (год). При этом очевидно, что ситуация (1, 1) неустойчива, так как любой из игроков, изменяя свою стратегию, может увеличить свой выигрыш (избежать наказания). Решим данную биматричную игру как две матричные с нулевой суммой.
1. Для игры с матрицей PA 0 6 получим следующее решение:
y B 1; 0, v B 1 (цена игры).
Т.е. игроку B рекомендуется придерживаться второй стратегии, а игроку A – первой, но тогда H A 9, H B 0. Такая ситуация хуже для игрока A, чем для игрока B.
Таким образом, в биматричной игре ситуация равновесия обоих игроков определяется не столько стремлением увеличить собственный выигрыш, сколько стремлением минимизировать выигрыш другого игрока.
2.4. ОПТИМАЛЬНОСТЬ ПО ПАРЕТО Дадим определение другого способа определения оптимальности в биматричных играх, который основан на принципе оптимальности по Парето.
Ситуация ( p, q ) в биматричной игре двух лиц A и B называется оптимальной по Парето, если из того, что следуют равенства: p p, q q, т.е. не существует ситуации p, q, для которой имеют место неравенства (63). Среди этих неравенств по крайней мере одно должно быть строгим.
В оптимальной по Парето ситуации, все игроки, действуя совместно, не могут увеличить выигрыш каждого, не уменьшив при этом выигрыш одного из них. В отличие от этого, в ситуации равновесия по Нэшу ни один из игроков, действуя в одиночку, не может увеличить своего собственного выигрыша.
Покажем, как на практике отыскать оптимальную по Парето ситуацию в биматричной игре 22. Введем обозначения и рассмотрим плоскость (U, V ). На плоскости (U, V ) найдем целевую точку, в качестве координат которой часто выбирается сочетание наилучших значений U и V. В данном случае это будет точка Вследствие того, что обычно такая точка T при заданных ограничениях не реализуется, ее называют точкой утопии.
Далее, строим множество точек, отвечающее соотношениям (64), определяем на нем множество Парето, отвечающее заданным условиям на переменные p, q, и находим на нем точку, ближайшую к точке утопии T.
Именно такая точка и будет идеальной точкой P(U П, VП ), отвечающей принципу оптимальности по Парето. Найдя идеальную точку P, можно определить (используя соотношения (64)) и значения p П, q П, при которых она достигается. Здесь ( p П, q П ) – это оптимальная ситуация по Парето.
Vmax Найдем границы множества точек, удовлетворяющих (65). Для этого можно рассматривать крайние значения переменных p и q :
т.е. U П 1, VП 1. Решая систему уравнений H A ( p П, q П ) 1, оптимальной ситуацией по Парето будет ситуация ( p П, q П ) (1, 1) (т.е.
игроки A и B применяют свои первые чистые стратегии). Заметим, что точка D(6; 6) соответствует точке равновесия по Нэшу в данном примере, но при этом эта точка намного дальше от точки утопии, чем точка P. Ясно, что оптимальная ситуация по Парето здесь лучше, чем по Нэшу.
В заключение укажем оптимальные ситуации по Парето в других рассмотренных примерах. Так, в примере 1 "борьба за рынки" оптимальной ситуацией по Парето будет ситуация ( p П, q П ) (0, 0), т.е.
U П 1, VП 1. В примере 3 "семейный спор" есть две оптимальные ситуации по Парето, именно: ( pП1, qП1 ) (1, 0) и ( pП 2, qП2 ) (0, 1), при этом они одновременно являются и ситуациями равновесия по Нэшу (есть также одна ситуация равновесия по Нэшу в смешанных стратегиях, но она хуже указанных выше двух). В примере 4 "студент-преподаватель" оптимальной ситуацией по Парето будет ситуация ( p П, q П ) (1, 1), она же будет и равновесной по Нэшу.
СПИСОК ВОПРОСОВ ПО КУРСУ «ТЕОРИЯ ИГР»
Задачи теории игр. Примеры, виды игровых задач.Антагонистические матричные игры. Примеры игр. Максимин и минимакс. Выигрыши двух игроков.
Ситуации равновесия в игре. Понятие седловой точки. Чистые стратегии двух игроков.
Смешанные стратегии двух игроков в матричной игре. Выигрыши игроков в игре.
Теорема Дж. фон Неймана о ситуации равновесия. Аналитическое решение игры 22.
Геометрическое решение игры 22.
Лемма о масштабе. Условия эквивалентности смешанных стратегий двух игр.
Свойства оптимальных смешанных стратегий в матричной игре.
Графический метод решения матричной игры (2n).
10. Графический метод решения матричной игры (m2).
11. Активные (существенные) стратегии игроков. Теоремы об активных стратегиях.
12. Принцип доминирования стратегий двух игроков. Теоремы о доминируемых стратегиях.
13. Вполне смешанная игра. Решение матричной игры nn методом обратной матрицы.
14. Сведение матричной игры nm к двойственной задаче линейного программирования. Общий подход.
15. Постановка задач линейного программирования. Примеры, различные формы задач и подходы решения.
16. Задача линейного программирования в канонической форме.
Основные теоремы о множествах оптимальных решений этой задачи.
Допустимые базисные решения.
17. Аналитический метод решения задачи линейного программирования mn (симплекс-метод). Симплекс-таблицы.
18. Метод искусственного базиса в симплекс-методе.
19. Двойственные задачи линейного программирования.
Решение матричной игры симплекс-методом. Сведение к 20.
двойственной задаче линейного программирования.
21. Биматричные неантагонистические игры. Постановка задачи.
Функции выигрышей.
22. Примеры биматричных игр: борьба за рынки, дилемма узников, семейный спор, студент-преподаватель.
23. Ситуация равновесия по Нэшу в чистых стратегиях в биматричной игре. Пример поиска ситуаций равновесия для игры 22.
24. Ситуация равновесия по Нэшу в смешанных стратегиях в биматричной игре. Теорема Нэша. Свойства ситуаций равновесия.
25. Ситуация равновесия по Нэшу в смешанных стратегиях для игры 22. Поиск решений для двух игроков.
26. Графическая интерпретация решения биматричной игры 22 по Нэшу.
27. Принцип оптимальности по Парето в биматричной игре. Пример для игры 22.
28. Поиск оптимальных стратегий по Парето в биматричной игре 22.
Множество Парето. Точка утопии.
КОНТРОЛЬНАЯ РАБОТА ПО ДИСЦИПЛИНЕ «ТЕОРИЯ ИГР»
1. В матричной игре с платежной матрицей P найти: 1) верхнюю и нижнюю цены игры; 2) седловую точку (если она существует) и оптимальные чистые стратегии игроков.2. Применить графический и аналитический методы поиска оптимальных стратегий для игры 2x2.
3. Используя принцип доминирования, свести матричную игру к игре с матрицей либо n 2, либо 2 m и найти ее решение графическим методом:
4. Найти оптимальные стратегии для игры 3 3 при помощи: 1) метода обратной матрицы; 2) симплекс-метода:
5. В биматричной игре с матрицами A и B найти: 1) ситуации равновесия по Нэшу (в смешанных стратегиях); 2) оптимальные ситуации по Парето (в чистых и в смешанных стратегиях):
1. В матричной игре с платежной матрицей P найти: 1) верхнюю и нижнюю цены игры; 2) седловую точку (если она существует) и оптимальные чистые стратегии игроков.
2. Применить графический и аналитический методы поиска оптимальных стратегий для игры 2x2.
3. Используя принцип доминирования, свести матричную игру к игре с матрицей либо n 2, либо 2 m и найти ее решение графическим методом:
4. Найти оптимальные стратегии для игры 3 3 при помощи: 1) метода обратной матрицы; 2) симплекс-метода:
5. В биматричной игре с матрицами A и B найти: 1) ситуации равновесия по Нэшу (в смешанных стратегиях); 2) оптимальные ситуации по Парето (в чистых и в смешанных стратегиях):
1. В матричной игре с платежной матрицей P найти: 1) верхнюю и нижнюю цены игры; 2) седловую точку (если она существует) и оптимальные чистые стратегии игроков.
2. Применить графический и аналитический методы поиска оптимальных стратегий для игры 2x2.
3. Используя принцип доминирования, свести матричную игру к игре с матрицей либо n 2, либо 2 m и найти ее решение графическим методом:
4. Найти оптимальные стратегии для игры 3 3 при помощи: 1) метода обратной матрицы; 2) симплекс-метода:
5. В биматричной игре с матрицами A и B найти: 1) ситуации равновесия по Нэшу (в смешанных стратегиях); 2) оптимальные ситуации по Парето (в чистых и в смешанных стратегиях):
1. В матричной игре с платежной матрицей P найти: 1) верхнюю и нижнюю цены игры; 2) седловую точку (если она существует) и оптимальные чистые стратегии игроков.
2. Применить графический и аналитический методы поиска оптимальных стратегий для игры 2x2.
3. Используя принцип доминирования, свести матричную игру к игре с матрицей либо n 2, либо 2 m и найти ее решение графическим методом:
4. Найти оптимальные стратегии для игры 3 3 при помощи: 1) метода обратной матрицы; 2) симплекс-метода:
5. В биматричной игре с матрицами A и B найти: 1) ситуации равновесия по Нэшу (в смешанных стратегиях); 2) оптимальные ситуации по Парето (в чистых и в смешанных стратегиях):
«