методичка Теория игр 2014. Методические указания и контрольные задания по дисциплине теория игр для студентовзаочников 2 курса, специальности 080100 семестр 4 Москва 2014
 Скачать 1.28 Mb.
|
|
Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования Московский технический университет связи и информатики Кафедра теории вероятностей и прикладной математики Методические указания и контрольные задания по дисциплине ТЕОРИЯ ИГР для студентов-заочников 2 курса, специальности 080100 семестр 4 Москва 2014 План УМД на 2013/2014 уч.год Методические указания и контрольные задания по дисциплине "Теория игр" 2014 год Составитель Демин ДБ, к.ф.-м.н., доцент каф. ТВиПМ В предлагаемых методических указаниях приведены теоретические сведения и практические навыки общего характера по курсу теория игр. Дана рабочая программа, тематика лекций и упражнений, основные вопросы к экзамену. Приведены задания по контрольной работе в 40 вариантах. Издание утверждено на заседании кафедры Теории вероятностей и прикладной математики (протокол № ). Рецензент Кюркчан А.Г., проф, зав каф. ТВиПМ ВВЕДЕНИЕ Предлагаемые методические указания относятся к курсу Теория игр, изучаемого студентами-заочниками в четвертом семестре. В этом курсе студенты знакомятся с основными моделями и методами теории игр – теории принятия решений в неопределенных ситуациях. Приводятся примеры принятия решения в области экономики и менеджмента. По курсу выполняется контрольная работа, которая приведена в конце данных указаний. Методические указания не заменяют учебников, а содержат только основные моменты изучаемого материала, краткий обзор отдельных вопросов, а также решения некоторых типовых задач вопросы по предмету. Основная литература по курсу Теория игр приведена ниже. ОБЩИЕ УКАЗАНИЯ 1. Самостоятельная работа с учебником Самостоятельная работа с учебником является основным видом работы студента-заочника. Читая основную литературу по курсу, студент может и должен обращаться к указанной дополнительной литературе. Это необходимо в тех случаях, когда основной учебник не дает полного ответа на некоторые вопросы программы. Кроме того в дополнительной литературе приведено много вспомогательного теоретического и практического материала, облегчающего усвоение основных тем курса. 2. Решение задач Приступая к решению задач, следует после изучения очередного раздела по учебнику внимательно изучить примеры решения типовых задач поданному пособию, а затем переходить к самостоятельному решению рекомендованных задач. В тех случаях, когда это необходимо, следует дать рисунок, поясняющий решение задачи. Решение следует сопровождать краткими, но исчерпывающими пояснениями. Решение каждой задачи должно содержать окончательный ответ, содержащий перечисление оптимальных стратегий игроков с указанием их выигрыша проигрыша. Промежуточные вычисления следует проводить в целых числах и рациональных дробях без приближенного их округления в виде десятичной дроби. 3. Выбор варианта Вариант выбирается в соответствии с двумя последними цифрами студенческого билета. Например, если номер студенческого билета 11021, то вариант будет иметь номер 21. Если номер варианта больше 39, то из последних двух цифр нужно отнять число 40. Например, если ваши последние две цифры 54, то ваш вариант будет 54–40=14. 4. Выполнение контрольных работ При выполнении контрольных работ студент должен руководствоваться следующим 1. Не следует приступать к выполнению контрольных работ до изучения всех примеров, приведенных в данном пособии. 2. Контрольные работы выполняются по УМД одного года издания. Замена издания другим в процессе изучения курса теории игр не допускается. 3. Контрольная работа выполняется в обычной ученической тетради. Она должна быть аккуратно и четко написана. Для замечаний преподавателей на каждой странице оставляются поля шириной 2 см. Все страницы нумеруются. На обложку тетради наклеивается заполненный адресный бланка на первую страницу тетради – титульный бланк. 4. Решения задачи контрольных работ сопровождаются исчерпывающими, но краткими объяснениями. Задачи располагают в порядке номеров, указанных в заданиях перед решением задачи выписывается полностью ее условие. 5. На рецензию одновременно высылается не более одной работы. 6. После получения прорецензированной работы из университета студент должен выполнить указания, сделанные рецензентом. Если контрольная работа не зачтена, студент обязан в той же тетради (после заключения рецензента) внести все исправления, решить заново задачи, указанные рецензентом, и представить работу на повторную рецензию. 7. Контрольная работа выполняется самостоятельно. В случае, если у рецензента возникает сомнение в самостоятельности выполнения работы, студент вызывается на консультацию для устной защиты контрольной работы. 8. В конце работы указывается использованная литература. 9. Контрольная работа подписывается с указанием даты выполнения. 10. Контрольные работы, выполненные без соблюдения изложенных правил или по чужому варианту, не засчитываются и возвращаются. 5. Сдача экзамена К сдаче экзамена допускаются студенты, имеющие на руках выполненные и зачтенные работы. Экзамен сдается в письменной и устной формах. При сдаче экзамена студент должен знать определения, теоремы, формулы и иметь навыки решения задач поданному курсу. 6. Очная учеба студентов Студенты, успешно выполняющие учебный план, приглашаются в университет для проведения лабораторных работ, сдачи экзаменов и очной работы с преподавателями. В это время для студентов читаются обзорные лекции и проводятся упражнения в объеме учебного плана. Следует иметь ввиду, что обзорные лекции не являются систематическим чтением курса. Они охватывают лишь узловые моменты программы. Обзорные лекции, упражнения и консультации будут полезны студентам, которые проработали курс по полной программе и выполнили контрольные задания. Бюджет времени (в часах) Аудиторная работа Самостоятельная работа лекции упражнения итого изучение курса выполнение контрольной работы итого 12 8 20 100 24 124 РАБОЧАЯ ПРОГРАММА Задачи теории игр. Примеры, виды игровых задач. Антагонистические матричные игры. Примеры игр. Максимин и минимакс. Выигрыши двух игроков. Ситуации равновесия в игре. Понятие седловой точки. Чистые стратегии двух игроков. Смешанные стратегии двух игроков в матричной игре. Выигрыши игроков. Теорема Дж. фон Неймана о ситуации равновесия. Аналитическое решение игры 2 2. Геометрическое решение игры 2 2. Лемма о масштабе. Условия эквивалентности смешанных стратегий двух игр. Свойства оптимальных смешанных стратегий в матричной игре. Графический метод решения матричной игры (2 m). Графический метод решения матричной игры (n 2). Активные (существенные) стратегии игроков. Теоремы об активных стратегиях. Принцип доминирования стратегий двух игроков. Теоремы о доминируемых стратегиях. Вполне смешанная игра. Решение матричной игры n n методом обратной матрицы. Сведение матричной игры n m к двойственной задаче линейного программирования. Общий подход. Постановка задач линейного программирования. Множества решений неравенств, уравнений и их систем в задачах линейного программирования. Допустимые решения. Допустимые базисные решения. Сведения из теории выпуклых множеств. Задача линейного программирования в канонической форме. Основные теоремы о множествах оптимальных решений этой задачи. Аналитический метод решения задачи линейного программирования n m (симплекс-метод). 19. Симплекс-таблицы в симплекс-методе для задач на максимум и минимум. Метод искусственного базиса в симплекс-методе. Взаимосвязь решений двух двойственных задач линейного программирования. Решение матричной игры n m симплекс-методом. Получение решения при помощи использования принципа двойственности. Принципы доминирования в биматричных играх. Пример для матриц размера 3 3. Ситуация равновесия по Нэшу в биматричной игре произвольной размерности. Свойства ситуаций равновесия. Теорема Дж. Нэша. Ситуация равновесия по Нэшу в биматричной игре 2 2. Поиск смешанных стратегий для двух игроков. Графическая интерпретация решения в биматричной игре 2 2 по Нэшу. Поиск оптимальных стратегий по Парето в биматричной игре 2 2. Множество Парето. Точка утопии. Идеальная точка. СПИСОК ЛИТЕРАТУРЫ Основная 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. Решение в смешанных стратегиях матричных игр вида n 2 и 2 m. Метод обратной матрицы. 3. Решение матричной игры n m симплекс-методом. 4. Определение ситуации равновесия по Нэшу и оптимальной ситуации по Парето в биматричной игре 2 2. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО РАЗДЕЛАМ КУРСА ТЕОРИЯ ИГР ВВЕДЕНИЕ [1, гл, § 1], [2, гл, [3, гл, § 1], [4, гл, § 1], [5, введение, [6, гл, § 1], [7, гл, § 25]. В практической деятельности, в том числе ив экономике, приходится сталкиваться с задачами, в которых необходимо принимать решения в условиях неопределенности, те. возникают ситуации, в которых сталкиваются две и более враждующие стороны, преследующие различные цели. Причем результат любого действия каждой из сторон зависит оттого, какие действия предпримет противоположная сторона. Такие ситуации принято называть конфликтными. В экономике конфликтные ситуации возникают очень часто. К ним относятся, например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом, фирмами, захватывающими определенную часть рынка и др. Во всех этих примерах конфликтная ситуация порождается различием интересов партнеров и стремлением каждого из них принимать оптимальные решения, которые максимально реализуют поставленные цели. В реальной жизни конфликтные ситуации довольно сложны. Их изучение осложнено наличием различных факторов, часть из которых может оказывать слабое влияние на развитие конфликта и на его исход. Поэтому для анализа конфликтной ситуации необходимо отвлечься от второстепенных факторов и построить ее упрощенную, формализованную модель, которую принято называть игрой. От реальной конфликтной ситуации игра отличается лишь тем, что ведется по определенным правилам. Для изучения и анализа конфликтов, представленных в виде упрощенных математических моделей (игр, был создан специальный математический аппарат – теория игр. Теория игр – математическая теория конфликтных ситуаций или, другими словами, это раздел математики, в котором изучаются математические модели принятия решений в условиях неопределенности. В игре могут сталкиваться интересы двух (парная игра) и более сторон (игроков) (множественная игра. Целью каждого из них является получение как можно большего выигрыша. В дальнейшем мы будем сталкиваться преимущественно с парной игрой. Математическое описание игры сводится к перечислению всех участвующих в ней игроков, указанию для каждого игрока всех его стратегий, а также численного выигрыша, который он получит после того, как игроки выберут свои стратегии. В результате игра становится формальной моделью, поддающейся математическому описанию. Выбор и осуществление одного из предусмотренных правилом игры действий называется ходом игрока. Ходы могут быть личными и случайными. Личный ход – это сознательный выбор игроком одного из возможных действий (ход в шашках, в шахматах. Случайный ход – это случайно выбранное действие (выбор карты из перетасованной колоды. Случайные ходы в теории игр не рассматриваются, они являются предметом изучения другой дисциплины – теории вероятностей. Задача теории игр – рекомендовать игрокам определенные стратегии при выборе их личных ходов. Стратегией игрока называется совокупность правил, определяющих выбор его действия при каждом личном ходе в зависимости от сложившейся ситуации. Игрок может выбирать стратегию либо в процессе самой игры в зависимости от конкретной ситуации, либо он может выбрать ее заранее до начала игры. Для того, чтобы решить игру, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, те. один из игроков должен получить максимальный выигрыш, когда второй придерживается своей стратегии. В тоже время второй игрок должен иметь минимальный проигрыш, когда первый игрок придерживается своей стратегии. Такие стратегии называются оптимальными. Если игра повторяется много раз, оптимальной стратегией игрока называется такая стратегия, которая обеспечивает ему максимально возможный средний выигрыш в игре. Целью теории игр является определение оптимальной стратегии и выигрыша для каждого игрока. Игры классифицируются по целому ряду признаков – по количеству игроков парные игры (игры двух лиц) и игры n лиц множественные игры – по количеству стратегий конечные (число возможных стратегий конечно) и бесконечные игры – по характеру взаимоотношений бескоалиционные, коалиционные, кооперативные игры – по характеру выигрышей игры с нулевой суммой антагонистические) и игры с ненулевой суммой (неантагонистические); – по количеству ходов одношаговые и многошаговые игры позиционные, стохастические, дифференциальные – в зависимости от состояния информации игры с полной информацией (все стратегии игроков известны заранее примеры крестики-нолики, шашки, шахматы) и игры с неполной информацией игра в карты (когда все карты розданы, домино – по виду функций выигрыша матричные, биматричные, непрерывные. РАЗДЕЛ 1: МАТРИЧНЫЕ ИГРЫ 1.1. ОПРЕДЕЛЕНИЕ МАТРИЧНОЙ ИГРЫ [1, гл, § 2], [2, гл, § 1], [3, гл, § 1-2], [4, гл, § 1], [5, гл, [6, гл, § 2], [7, гл, § 26]. Матричная игра – это конечная игра двух игроков с нулевой суммой. Фактически она является конечной парной антагонистической бескоалиционной игрой с полной информацией о стратегиях обоих игроков. Обозначим для удобства одного игрока через А, а другого через Предположим, что игрок А имеет m стратегий А ,..., 1 , а игрок B – n стратегий n B B ,..., 1 . Выбор игроками Аи стратегий Аи однозначно определяет исход игры – выигрыш ij a игрока Аи выигрыш ij b игрока B , причем ij ij a b (те. выигрыш игрока А – это проигрыш игрока B , и наоборот. Если значения выигрышей ij a игрока А известны при каждой паре стратегий А , (такие пары принято называть ситуациями, n j m i , 1 , , 1 , то их удобно записать в виде прямоугольной таблице, строки которой соответствуют стратегиям игрока А, а столбцы – стратегиям игрока B : 1 B 2 B n B А 11 a 12 a А 21 a 22 a А 1 m a или в виде матрицы mn m m n n a a a a a a a a a P 2 1 2 22 21 1 12 Полученная матрица P имеет размерность n m и называется матрицей игры, или – платежной матрицей. Рассматриваемую игру часто называют матричной игрой. Так как в данной игре игрок А выигрывает именно столько, сколько проигрывает игрок B , то сумма выигрышей двух игроков здесь равна нулю. Такие игры принято называть играми с нулевой суммой или антагонистическими играми, так как интересы игроков здесь прямо противоположны. Ценой (значением) игры называется средний выигрыш игрока А Пример 1. игра в орлянку) Играют два игрока. Каждый игрок держит в кулаке свою монету, затем игроки одновременно разжимают пальцы. Если монеты повернуты одинаковой стороной (герб или решка, то первый игрок (А) выигрывает 1 руб, если же монеты повернуты разными сторонами, то тогда второй игрок ( B ) выигрывает 1 рубль. Итак, в этой игре у обоих игроков есть по две стратегии. У игрока А Г Г А , 1 , Р Р А , 2 , у игрока B : Р , 1 Г B , ГР. Так как выигрыши нам известны, то платежная матрица P выигрышей игрока А будет иметь следующий вид 1 1 1 Если эту игру повторять много раз, то можно говорить о среднем выигрыше игрока А в данной игре. Ниже будет дано решение этой игры. 1.2. СИТУАЦИИ РАВНОВЕСИЯ В МАТРИЧНОЙ ИГРЕ [1, гл, § 2], [2, гл, § 1], [3, гл, § 3], [4, гл, § 2-3], [5, гл, § 1], [6, гл, § 2], [7, гл, § 26]. Рассмотрим в целом логику матричной игры глазами двух игроков. Каждый из игроков стремится максимизировать свой выигрыш. Логика игры глазами игрока А если я выберу свою стратегию А , то игрок B (будучи не очень глупым) ответит на нее такой стратегий j B , для которой мой выигрыш будет минимальным (те. игрок B стремится минимизировать свой возможный проигрыши навредить игроку А. Отсюда следует, что игрок А при любой своей стратегии получит Тогда среди всех таких чисел игрок А выберет максимально возможное, те. ij n j m i a v 1 1 min max . Величина v называется нижней ценой игры (максимином) и является гарантированным выигрышем игрока А. При этом, принцип выбора игроком А стратегии, основанной на максимизации минимального выигрыша, называется принципом минимакса, а соответствующая стратегия – максиминной стратегий игрока А Для игрока B можно провести аналогичные рассуждения. Пусть он выбрал стратегию j B , тогда в худшем случае он проиграет Поэтому второй игрок ( B ) всегда может себе гарантировать проигрыш, равный ij m i n j a v 1 1 max min . Величина v называется верхней ценой игры минимаксом) и является гарантированным проигрышем игрока Сделаем вывод. В матричной игре выигрыш v игрока A всегда больше или равен максимину v , а выигрыш игрока B (те. величина v ) всегда больше или равна ) ( min max ij i j a . Тогда v А выигрыш v v ) ( (1) Лемма В любой матричной игре максимин всегда меньше или равен минимакса, те. v v (2) Так, в примере 1, 1 v , а 1 v , те. Рассмотрим вопрос об оптимальном поведении игроков в антагонистической игре. Естественно считать оптимальной в игре такую ситуацию ) , ( j i B A , от которой невыгодно отклоняться ни одному из игроков. Такая ситуация ) , ( j i B A называется равновесной, а принцип оптимальности, построенный на равновесной ситуации, – принципом равновесия. Ситуацию ) , ( j i B A или, в других обозначениях, – принято еще называть седловой точкой. Номера i и j обозначают оптимальные стратегии игроков A и Теорема Если в матричной игре существует седловая точка ) , ( j i , то говорят, что она имеет решение в чистых стратегиях. Причем i A – оптимальная стратегия игрока A , а j B – оптимальная стратегия игрока B . В этом случае тогда v v (максимин равен минимаксу. (3) Вообще, матричная игра может и не иметь седловых точек, либо иметь, по крайней мере, одну из них. Так, в примере 1, седловой точки нет. В этом случае говорят, что игра не имеет решения в чистых стратегиях. Рассмотрим другой пример. Пример 2. Пусть имеется платежная матрица P . Найти все седловые точки в этой игре 2 0 0 2 4 4 6 4 5 5 3 20 1 3 5 P Здесь 4 } 4 , 4 , 5 max{ v , 4 } 4 , 20 , 4 , 5 , 5 min{ v , те. v v . Таким образом, в данной игре есть две седловые точки ) , ( 3 2 B A и ) , ( 5 2 B A , а цена игры 4 v v v 1.3. СМЕШАННОЕ РАСШИРЕНИЕ МАТРИЧНОЙ ИГРЫ [1, гл, § 3], [2, гл, § 1.2], [3, гл, § 4], [4, гл, § 4-5], [5, гл, §2], [6, гл, § 3-4], [7, гл, § 26]. Если в матричной игре не существует ситуации равновесия (те. v v ), то применение игроками A и B своих чистых максиминных и минимаксных стратегий не дает оптимального решения игры, так как они могут получить и больший выигрыш. Однако сообщение о выборе стратегии противнику может привести к еще большим потерям, чем в случае максиминной или минимаксной стратегии. Оказывается, что компромиссного распределения разности между игроками и уверенного получения игроками своего выигрыша можно достичь путем случайного применения ими своих чистых стратегий. В этом случае обеспечивается наибольшая скрытность выбора стратегии (результат выбора не может быть известен противнику, поскольку до реализации случайного механизма он неизвестен самому игроку. Определение Случайная величина, значениями которой являются стратегии игрока, называется его смешанной стратегией. Так, в матричной игре смешанной стратегией игрока является мерная случайная величина ) ..., , , ( 2 1 m p p p x , у которой m i i p 1 1, 0 i p , m i , 1 (4) Аналогично, смешанная стратегия игрока B есть мерная случайная величина ) ..., , , ( 2 1 n q q q y , у которой n j j q 1 1 , 0 j q , n j , 1 (5) В (4)-(5) величины i p , j q – это вероятности выбора игроками A и B своих стратегий Аи. Если 1 i p , то это означает, что игрок выбрал свою чистую стратегию А , тогда Аналогичные рассуждения можно провести и для игрока Пара ) , ( y x смешанных стратегий игроков в игре называется ситуацией в смешанных стратегиях. В условиях смешанных стратегий ситуация А , (в чистых стратегиях) является случайным событием ив виду независимости наборов вероятностей ) ..., , , ( 2 1 m p p p и ) ..., , , ( 2 1 n q q q вероятность его появления равна j i q p . В такой ситуации игрок A получает выигрыш, равный ij a . Тогда выигрыш v игрока A в ситуации ) , ( y x в смешанных стратегиях для матричной игры можно определить как математическое ожидание ) , ( y x H A (среднее значение) его выигрыша при условии, что игроки используют смешанные стратегии x и соответственно m i n j j i ij A q p a y x H 1 1 ) , ( (6) В векторно-матричной форме записи формула (6) примет вид n mn m n m T A q q a a a a p p xAy y x H ) , ( 1 1 1 11 1 , (7) при этом функция ) , ( y x H A является непрерывной пои Определение. Ситуация ) , ( y x является ситуацией равновесия в матричной игре, а число ) , ( y x H v A – ценой игры, если при любых x и y : ) , ( ) , ( ) , ( y x H y x H y x H A A A (8) Ситуацию равновесия ) , ( y x , удовлетворяющую соотношению (8), принято называть оптимальной ситуацией в смешанных стратегиях. Приведенное условие оптимальности (8) означает, что ) , ( max min ) , ( ) , ( min max y x H y x H y x H v A y x A A y x (9) Теорема (Дж. фон Нейман). В любой матричной игре существует хотя бы одна ситуация равновесия в смешанных стратегиях. Основные свойства оптимальных смешанных стратегий |