8.2. Теория игр.
Принятия решений в условиях определенности, риска и неопределенности, в которой внешняя среда (природа) предполагалась пассивной, в конфликтных ситуациях имеются противодействующие стороны, интерес которых противоположны. При конфликтных ситуациях решений принимаются в условиях неопределенности двумя и более разумными противниками, каждый из которых стремится оптимизировать свои решения за счет других. Теория, занимающаяся принятием решений и условиях конфликтных ситуаций, называется теорией игр. Математическая модель конфликтной ситуации представляет собой игру.
Игра - это совокупность правил, описывающих сущность конфликтной ситуации. Эти правила устанавливают:
• выбор образа действия игроков на каждом этапе игры;
• информацию, которой обладает каждый игрок при осуществлении таких выборов;
• плату для каждого игрока после завершения любого этапа игры.
Игру можно определить следующим образом:
• имеются n конфликтующих сторон (игроков), принимающих решения, интересы которых не совпадают;
• сформулированы правила выбора допустимых стратегий, известные игрокам;
• определен набор возможных конечных состояний игры (например, выигрыш, ничья, проигрыш);
• всем игрокам (участникам игры) заранее известны платежи, соответствующие каждому возможному конечному состоянию. Платежи задаются в виде матрицы
В зависимости от числа конфликтующих сторон игры делятся на парные (с двумя игроками) и множественные (имеющие не менее трех игроков). Каждый игрок имеет некоторое множество (конечное или бесконечное) возможных выборов, т. е. стратегий.
Стратегией игры называется совокупность правил, определяющих поведение игрока от начала игры до ее завершения. Стратегии каждого игрока определяют результаты или платежи в игре. Игра называется игрой с нулевой суммой, если проигрыш одного игрока равен выигрышу другого, в противном случае она называется игрой с ненулевой суммой.
Игра называется конечной, если у каждого игрока имеется конечное число стратегий. Результаты конечной парной игры с нулевой суммой можно задавать матрицей, строкой столбцы которой отсутствуют различным стратегиям, а ее элементы - выигрышам одной стороны (равные проигрышам другой). Эта матрица называется платежной матрицей или матрицей игры.
Если первый игрок имеет m стратегий, а второй - n стратегии, то говорят, что мы имеем дело с игрой mхn. Рассмотрим игру mхn. Пусть заданы множество стратегий: для первого игрока для второго игрокаплатежная матрица, где- выигрыш первого игрока или проигрыш второго игрока при выборе ими стратегий Аi, и Dj соответственно. Каждый из игроков выбирает однозначно с вероятностью I некоторую стратегию, т.е. пользуется при выборе решения чистой стратегией. При этом решение игры будет в чистых стратегиях. Поскольку интересы игроков противоположны, то первый игрок стремится максимизировать свой выигрыш, а второй игрок, наоборот, минимизировать свой проигрыш.
Решение игры состоит в определении наилучшей стратегии каждым игроком. Выбор наилучшей стратегии одним игроком проводится при полном отсутствии информации о принимаемом решении вторым игроком. Следует отметить, что и первый, и второй ток являются разумными противниками, которые, находятся в состоянии конфликта. Поэтому для решения игры двух лиц с нулевой суммой используется очень «пессимистичный» критерий, так называемый критерий минм-макса-максимина. Так еслй первый игрок применяет стратегию Аj, то второй будет стремиться к тому, чтобы выбором соответствующей стратегии Bj свести выигрыш первого игрока к минимуму, что равнозначно сведению своего проигрыша к минимуму. Величина этого минимума
(8.1)
Первый игрок (при любых ответах противника) будет стремиться найти такую стратегию, при которой а, обращается в максимум:
(8.2)
Величина называется нижней ценой игры. Ей соответствует максиминная стратегия, придерживаясь которой первый игрок при любых стратегиях противника обеспечит себе выигрыш, не меньший а. Другими словами, нижняя цена игры является гарантированным выигрышем первого игрока при любых стратегиях игрока.
Аналогично определим по каждому столбцу матрицы; найдем минимальное значение :
(8.3)
Величина называется верхней ценой игры. Ей соответствует минимаксная стратегия второго игрока. Величинапредставляет собой гарантированный проигрыш второго игрока при любой стратегии первого игрока.
Пример 8.4. Дана платежная матрица 3x4, которая определяет выигрыши игрока А. Вычислить нижнюю и верхнюю цены заданной игры.
Решение
Представим кашу игру в виде следующей таблицы:
Стратегии первого игрока, Аi | Стратегии второго игрока, Вj | Значение, | ||||
В1 | В2 | В3 | В4 | |||
А1 А2 А3 Значение | 10 7 6 10 - | 4 6 2 6 6 | 11 8 1 11 - | 7 20 11 20 - | 4 6 1 - - | - 6 -
- |
Если игрок А выбирает первую стратегию, он может полупить выигрыш в размере 10, 4, 1 или 7 д. е. в зависимости от выбранной стратегии игроком В. При этом выигрыш игрока будет не меньше д. е. независимо от поведения игрокаВ. Аналогично при выборе игроком А второй стратегии гарантированный выигрыш д. е. При выборе игроком А третьей стратегии выигрыш д.е.
Таким образом, минимальные значения аi, i = 1,3 определяют минимально гарантированный выигрыш для игрока A, если он выбирает соответствующую стратегию i. Величина max аi = max{4; 6; l}= 6 д.е. будет гарантированным выигрышем игрока А при любых стратегиях игрока В. Выбранная игроком А вторая стратегия называется максиминной стратегией, а соответствующее ее значение выигрыша а2 = 6 д. е. будет нижней ценой игры.
Второй игрок стремится минимизировать свой проигрыш. Выбрав первую стратегию , игрокВ может проиграть не более чем =max{10; 7; 6} = 10 д. е. независимо от выбора стратегии игроком А. Аналогично рассуждая, получим следующие результаты (д. е.):
Игрок В выбирает стратегию , которая минимизирует его максимальные проигрыши:
д.е.
Величина = 6 д. е. будет гарантированным проигрышем игрока В при любых стратегиях игрока А. Выбранная игроком В вторая стратегия называется минимаксной стратегией, а соответствующее ее значение проигрыша= 6 д. е. будет верхней ценой игры.
Следует отметить, что для любой матрицы выполняется неравенство
(8.5)
Если , т. е. верхняя цена равна нижней цене игры, то соответствующие чистые стратеги называются оптимальными, а про игру говорят, что она имеет седловую точку. Седловая точка является минимальным элементом соответствующей строки и максимальным элементом соответствующего столбца. Эта точка есть точка равновесия игры, определяющая однозначно оптимальные стратегии. Оптимальность здесь означает, что ни один игрок не стремится изменить свою стратегию, так как его противник может на это ответить выбором другой стратегии, дающей худший для первого игрока результат.
Величина С =называется ценой игры. Она определяет средний выигрыш игрока А и средний проигрыш игрока В при использовании ими оптимальных стратегий. В нашем примере цена игры С = 6 д. е., оптимальная пара стратегий - А2 и В2.
Если в платежной матрице А все элементы строки А1 = (аi1, аi2, ..,, аin) не меньше соответствующих элементов строки Аk = {аk1 аk2,…,akn), а по крайней мере один строго больше, то строка А является доминирующей, а строка Аk - доминируемой
Аналогичны понятия «доминирующий столбец» и «доминирующая строка»
Первому игроку невыгодно применять стратегии которые соответствуют доминируемые строки; второму игроку невыгодно менять стратегии, которым соответствуют доминирующие строки. Поэтому при решении игры можно уменьшить размеры платежей матрицы путем удаления из нее доминирующих столбцов и доминируемых строк.
Пример 8.2. Для игры с платежной матрицей
найдите стратегии игроков и цену игры.
Решение.
Элемент а32 = -1 является наименьшим в третьей строке и наибольшим во втором столбце, т.е. он является седловой точкой. Поэтому цена игры С= - 1, а оптимальные стратегии игрока первого – А3, а второго – В2.
Используя понятия доминирующих строк и доминирующих столбцов, задачу можно решить следующим образом.
В матрице А третья строка доминирует над второй, поэтому вторую можно изъять из платежной матрицы. В результате получится матрица
В матрице А1 первый и третий столбцы доминируют над вторым, следовательно, их можно изъять. В результате платежная матрица принимает вид
В матрице А2 вторая строка доминирует. После вычеркивания получится матрица А3, состоящая из одного элемента:
А3=(-1)
Элемент матрицы А3 и определяет решение нашей задачи.
Отдельные игры могут не иметь седловых точек, т. е. у каждого игрока не существует единственной, наиболее надежной стратегии. В этом случае используют смешанную стратегию. Смешанная стратегия состоит в том, что в ходе игры происходит случайный выбор стратегии из некоторого множества смешанных стратегий и для каждой, смешанной стратегии указывается вероятность ее выбора. Смешанная стратегия для игрока А представляет собой вектор
(8.6)
где Рi- — вероятность выбора i-Й стратегии игроком и удовлетворяет следующим условиям:
(8.7)
Аналогично смешанная стратегия игрока В представляет собой вектор
(8.8)
где qj — вероятность выбора j-й стратегии игроком В - удовлетворяет следующим условиям;
(8.9)
Платежная матрица игры имеет следующий вид: (8.10)
А В | q1 | q2 | q3 | … | qn |
P1 P2 P3 Pm | a11 a21 a31 am1 | a12 a22 a32 am2 | a13 a23 a33 am3 | … … …
… | a1n a2n a3n amn |
Игрок А выбирает стратегию Рi, так, чтобы максимизировать наименьший ожидаемый выигрыш по столбцам платежной матрицы, тогда как игрок В выбирает стратегию qj с целью минимизировать наибольший ожидаемый проигрыш подстрокам. Математический критерии минимакса при смешанных стратегиях может быть описан следующим образом. Игрок А выбирает стратегию Рi , дающая
(8.10)
Игрок В выбирает стратегию qj дающую
(8.11)
Когда стратегии иоптимальны, то выполняется строгое равенство между максиминным ожидаемым выигрышем и минимаксным проигрышем, а результирующее значение равно оптимальному (ожидаемому) значению игры.
Теорема утверждает, что выражения (8.10 и 8.11) имеют одно и то же значение M(P0,Q0), называемое ценой игры. Если и- оптимальные решения для обоих игроков, каждому элементу платежной матрицы аij соответствует вероятность *. Следовательно, оптимальное ожидлаемое значение игры
(8.12)
Цена игры заключена между нижней и верхней ценами, т. е.
Решить конечную игру - это значит нужно найти векторы Р и Q (оптимальные стратегии), удовлетворяющие теореме о минимаксе, а следовательно, получить, величину ожидаемого платежа М(Р0,Q0) - цену игры.
Свойство оптимальности означает, что любое отступление одного из игроков от оптимальной стратегии (при условии, что второй игрок продолжает придерживаться своей оптимальной страте-1ии) при многократном повторении игры может только уменьшить его средний выигрыш (увеличить средний проигрыш).
Решение игры обладает одним важным свойством: если игрок А использует свою оптимальную стратегию, а игрок В смешивает свои стратегии в любых пропорциях, то средний выигрыш игрока А не уменьшается. Стратегии, которые смешиваются для получения оптимальной стратегии, будем называть полезными. Доказано, что у игры m х n существует такое оптимальное решение, что число полезных стратегий с каждой стороны не превосходит минимального из чисел тип. Известно несколько методов нахождения оптимальных стратегий в играх двух лиц с нулевой суммой. Рассмотрим один из методов - метод линейного программирования для нахождения решения игр.
Пусть игра m х n не имеет оптимального решения непосредственно в чистых стратегиях, т. е. отсутствует седловая точка (). Оптимальное решение необходимо искать в области смешанных стратегий. Предположим, что всеm стратегий игрока А полезные. Определим вероятности их применения в смешанной оптимальной стратегии. Обозначим эти вероятности через Pi, i = , а цену игры - через М. Оптимальная смешанная стратегия игрока А определяется из условия (8.10)
Пусть
Поскольку при оптимальной стратегии средний выигрыш не меньше М при любой стратегии противника, то справедлива система n неравенств:
(8.14)
или
(8.15)
Тогда задача отыскания оптимальной смешанной стратегии игрока А может быть сформулирована в виде задачи линейного граммирования.
Для этого необходимо максимизировать Z = М при граммированиях
(8.16)
Введем новые неизвестные:
Чтобы исключить возможность деления на нуль, увеличим цену игры на положительное число С. Для этого достаточно ко всем элементам матрицы прибавить одно и то же положительное число С, при этом все элементы аij сделать положительными. Следует отметить, что эта операция не меняет искомых оптимальных стратегий.
Поскольку
Разделим левую и правую части неравенств (9.48) и (9.49) на М,
(8.17)
(8.18)
В силу того что
задача принимает вид
(8.19)
при ограничениях
(8.20)
Для игрока В оптимальная стратегия определяется из условия (8.11)
(8.21)
при ограничениях
(8.22)
Эта задача записывается как симметричная двойственная задача линейного программирования к задаче игрока А(9.52), (9.53): максимизировать
(8.23)
при ограничениях
(8.24)
где
Задачи игроков А и В решают обычным симплекс-методом.
Пример 8.3. Рассмотрим игру 3x4:
В | ||||||
|
| 1 | 2 | 3 | 4 | |
А | 1 2 3 | 4 -2 -3 | 3 5 2 | 2 -1 -3 | -5 4 6 | -5 -2 -3 |
| 4 | -5 | 2 | 6 |
|
Определим и,
где - минимум вi-й строке;
- максимум в i-м столбце.
Нижняя цена игры равна максимину = -2, верхняя цена игры равна минимаксу= 2. Так как, то седловая точка игры отсутствует, задача должна решаться в смешанных стратегиях.
Нижняя цена игры - число отрицательное (= -2), поэтому, возможно, значение игры М не будет положительным. Число С, которое необходимо прибавить ко всем элементам матрицы, должно быть не меньше 2. Пусть С = 6. Тогда матрица принимает вид
В | |||||
|
| 1 | 2 | 3 | 4 |
А | 1 2 3 | 10 4 3 | 9 11 8 | 8 5 3 | 1 10 12 |
Задача игрока В записывается в форме задачи линейного программирования
при ограничениях:
Решая задачу симплекс-методом, получим:
Таким образом, решением исходной задачи будет следующее:
В нашем примере первая и вторая стратегий игрока В бесполезны, так как . При случайном чередовании третьей и четвертой стратегий с относительными частотами = 0,75 и= 0,25 соответственно игроку В обеспечен средний выигрыш в размере М = 0,25.
Оптимальные стратегии игрока А получаются из решения двойственной задачи.
В настоящее время развитие теории игр вышло далеко за пределы рассмотренного нами простейшего случая парных игр с нулевой суммой. Однако ограниченный объем книги не позволяет дать представление о более сложных разделах современной теории игр, таких, как множественные коалиционные игры, дифференциальные игры и др.
Контрольные вопросы.
Объясните что такое неопределенность внешней среды.
Объясните, что следует понимать под ситуацией риска.
Объясните, что подразумевается под определением теория игр.
Объясните понятия: стратегия игры, матрица игры, критерий мини-макса-максимена.
Дайте характеристику методу линейного приграммирования.
- Э.Н.Медведев основы научных исследований Учебное пособие
- Медведев э.Н.
- Введение к курсу «основы научных исследований»
- 1.1. Необходимость и важность изучения курса «Основы научных исследований»
- Контрольные вопросы
- 2. Организация. Виды и формы научной работы студентов
- 2.1. Организация научно-исследовательской работы студентов
- 2.2. Реферат – как первая научная работа
- 2.3 Курсовая работа
- 2.4. Дипломная работа
- 2.5. Магистровская работа
- Науковедение и классификация наук
- 3.4.Основные направления исследований
- Контрольные вопросы
- 4.Информационное обеспечение научно-исследовательского процесса
- 4.1.Основные термины и понятия
- 4.2. Экономическая информация
- 4.3. Типы научных документов и их классификация.
- 4.4.Закономерности роста и старения научных документов
- 4.5.Информационное обеспечение научно-исследовательского процесса
- 4.6.Особенности научно-исследовательского процесса в условиях
- 4.7.Глобальная сеть «Internet»
- 5.Методология научных исследований
- 5.1.Цель и задачи науки
- 5.2.Объекты научных исследований и их классификация
- 5.3.Методологические приёмы в исследовании вопросов экономики
- 5.4.Методологические приёмы в исследовании маркетинга
- 5.5.Гипотеза в научных исследованиях
- 5.6.Эксперимент в научных исследованиях
- 6. Статистические и вероятностные методы исследований
- 6.3. Средние величины и способы их вычисления
- 6.4.Дисперсия, среднее квадратичное отклонение
- 6.5.Вероятность события
- Среднее значение
- Параметры распределения
- 6.7.Прогноз значений случайной величины
- Контрольные вопросы
- 7.Анализ результатов наблюдений
- 7.1.Корреляционный анализ
- 7.3. Ранговый коэффициент корреляции
- 7.4.Регрессионный анализ
- 7.5.Способ выравнивания эмпирических рядов
- 7.6. Определение показателей при отсутствии аналитических зависимостей
- Контрольные вопросы
- 8. Линейное програмирование
- 8.1. Общие понятия
- 8.2. Теория игр.
- 9.Организация и проведение научных исследований
- 9.1. Научно-исследовательский процесс
- 9.2.Научная организация труда в исследовательской деятельности
- 9.3.Организационная стадия научно-исследовательского процесса
- 9.4.Выбор научно-исследовательской темы
- 9.5 Исследовательская стадия научного процесса
- 9.6.Завершающая стадия исследовательского процесса.
- Контрольные вопросы
- 10.Психология научного творчества
- 10.1.Научное мышление
- 10.2. Методы активизации творческого мышления
- 10.3.Влияние внешних факторов на мышление
- 10.4. О возрастном цензе в науке и о „научном старении”
- 10.6. Методика использования литературных источников
- Контрольные вопросы
- 11. Правовые основы в сфере науки. И научно-технической деятельности
- 11.1. О научной и научно-технической деятельности
- 11.2 Правовой статус субъектов научной и научно-технической деятельности
- 11.3.Авторское право
- 11.4 Право на открытие и изобретение
- Контрольные вопросы
- Приложение а оформление реферата и курсовой работы а.1.Оформленике реферата
- Министерство образования и науки Украины
- А.2.Постановка, оформление и защита курсовой работы
- Приложение б порядок написания литературньіх источников
- Приложение в Подготовка, оформление и защита дппломной и магистровской работ
- В.1 Организация подготовки дипломной или магистровской работы
- В.1.2.Назначение научного руководителя
- В.2. Организация написания работы
- Міністерство освіти і науки України
- В.3.2.Нумерация
- В.3.3.Иллюстрации
- В.3.4.Таблицы
- В.3.5.Формулы
- В.3.6.Правила использования цитат
- В.3.7.Оформление списка использованных материалов
- В.3.8.Приложения
- В.4. Защита научной работы
- В.5.Отчет о научно-исследовательской работе
- Приложение г
- Розділ і Загальні положення
- Розділ II Правовий статус суб'єктів наукової і науково-технічної діяльності
- Державні гарантії діяльності наукових працівників