Теория игр

Лекция 5. ТЕОРИЯ ИГР 5.1. Понятие об игровых моделях На практике часто приходится сталкиваться с задачами, в которых необходимо принимать решения в условиях неопределенности, т. е. возникают ситуации, в которых две (или более) стороны преследуют различные цели, а результаты любого действия каждой из сторон зависят от мероприятий партнера. Такие ситуации относятся к конфликтным: результат каждого хода игрока зависит от ответного хода противника, цель игры – выигрыш одного из партнеров. В экономике конфликтные ситуации встречаются очень часто и имеют многообразный характер. К ним относятся, например, взаимоотношения между поставщиком и потребителем, покупателем и продавцом, банком и клиентом. Теория игр – раздел математики, изучающий конфликтные ситуации на основе их математических моделей. Игра – математическая модель конфликтной ситуации. Игроки – стороны, участвующие в конфликте. Выигрыш – исход конфликта. Для того чтобы решить игру, или найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т. е. один из игроков должен получать максимальный выигрыш, когда второй придерживается своей стратегии. В то же время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии. Такие стратегии называются оптимальными. Оптимальные стратегии должны также удовлетворять условию устойчивости, т. е. любому из игроков должно быть невыгодно отказаться от своей стратегии в этой игре.  5.2. Платёжная матрица. Нижняя и верхняя цена игры  Рассмотрим парную конечную игру. Пусть игрок А располагает m личными стратегиями, которые обозначим A1, A2, …, Аm. Пусть у игрока В имеется n личных стратегий, обозначим их B1, B2, …, Bm. Таким образом, игра имеет размерность m × n. В результате выбора игроками любой пары стратегий  однозначно определяется исход игры, т. е. выигрыш аij игрока А (положительный или отрицательный) и проигрыш (–аij) игрока В. Предположим, что значения аij известны для любой пары стратегий (Ai, Bj). Матрица , элементами которой являются выигрыши, соответствующие стратегиям Ai и Bj, называется платежной матрицей, или матрицей игры. Общий вид такой матрицы представлен в табл. 5.1. Таблица 5.1 - Платёжная матрица               Вj Аi                  В1 В2 … Вn А1 а11 а12 … а1n А2 а21 а22 … а2n … … … … … Аm аm1 аm2 … аmn Рассмотрим игру m × n с матрицей  и определим наилучшую среди стратегий A1, A2, …, Аm. Выбирая стратегию Аi игрок А должен рассчитывать, что игрок В ответит на нее той из стратегий Bj, для которой выигрыш для игрока А минимален (игрок В стремится «навредить» игроку А). Обозначим через α наименьший выигрыш игрока А при выборе им стратегии А; для всех возможных стратегий игрока В (наименьшее число в i-й строке платежной матрицы). Назовем α нижней ценой игры, или максимальным выигрышем (максимином). Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно, .                                         (5.1) Стратегия, соответствующая максимину, называется максиминной стратегией. Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А; выбирая стратегию Bj, он учитывает максимально возможный при этом выигрыш для А. Назовем В верхней ценой игры, или минимаксным  выигрышем (минимаксом). Это гарантированный проигрыш игрока В. Следовательно, .                                       (5.2) Стратегия, соответствующая минимаксу, называется минимаксной стратегией. Принцип, диктующий игрокам выбор наиболее «осторожных» минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника. Если верхняя и нижняя цены игры совпадают, то общее значение верхней и нижней цены игры α = β = ν называется чистой ценой игры, или ценой игры. Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность – оптимальным решением, или решением игры. В этом случае игрок А получает максимальный гарантированный (не зависящий от поведения игрока В) выигрыш ν, а игрок В добивается минимального гарантированного (вне зависимости от поведения игрока А) проигрыша ν. Говорят, что решение игры обладает устойчивостью, т. е. если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии. Пара чистых стратегий Ai и Bj дает оптимальное решение игры тогда и только тогда, когда соответствующий ей элемент аij является одновременно наибольшим в своем столбце и наименьшим в своей строке. Такая ситуация, если она существует, называется седловой точкой (по аналогии с поверхностью седла, которая искривляется вверх в одном направлении и вниз – в другом). Обозначим А* и В* – пару чистых стратегий, на которых достигается решение игры в задаче с седловой точкой. Введем функцию выигрыша первого игрока на каждой паре стратегий: P(Ai Bj) = аij. Тогда из условия оптимальности в седловой точке выполняется двойное неравенство: P(Ai, B*) ≤ Р(А*, В*) ≤ P(A*, Bj), которое справедливо для всех . Действительно, выбор стратегии А* первым игроком при оптимальной стратегии В* второго игрока максимизирует минимальный возможный выигрыш: Р(А*, В*) ≥ P(Ai, B*), а выбор стратегии В* вторым игроком при оптимальной стратегии первого минимизирует максимальный проигрыш: Р(А*, В*) ≤ P(A*, Bj). 5.3. Решение игр в смешанных стратегиях. Приведение матричной игры к задаче ЛП Если игра не имеет седловой точки, то применение чистых стратегий не дает оптимального решения игры. В таком случае можно получить оптимальное решение, случайным образом чередуя чистые стратегии. Смешанной стратегией игрока А называется применение чистых стратегий A1, A2, …, Аm с вероятностями р1, р2, …, рm, причем сумма вероятностей равна: . Смешанные стратегии игрока А записываются в виде . Аналогично смешанные стратегии игрока В обозначаются как , где сумма вероятностей появления стратегий . Чистые стратегии можно считать частным случаем смешанных и задавать строкой, в которой 1 соответствует чистой стратегии. На основании принципа минимакса определяется оптимальное решение (или решение) игры: это пара оптимальных стратегий S*A, S*В, в  общем  случае смешанных, обладающих следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то другому не может быть выгодно отступать от своей. Выигрыш, соответствующий оптимальному решению, называется ценой игры ν. Цена игры удовлетворяет неравенству α ≤ v ≤ β, где α и β – нижняя и верхняя цены игры. Пусть  и  – пара оптимальных стратегий. Решение задачи линейного программирования (ЛП) определяет оптимальную стратегию . При этом цена игры .                                     (5.3) Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности. 5.4. Примеры решения задач систем массового обслуживания Пример 1. Предприятие может выпускать три вида продукции (А1, A2 и А3), получая при этом прибыль, зависящую от спроса, который может быть в одном из трёх состояний (В1, В2 и В3). Дана матрица (табл. 5.2), ее элементы аij характеризуют прибыль, которую получит предприятие при выпуске i-й продукции с j-м состоянием спроса. Таблица 5.2 - Платежная  матрица игры                        Вj   Аi                  В1 В2 В3 pi α А1 3 6 8 p1 3 А2 9 4 2 p2 2 А3 7 5 4 p3 4 qj q1 q2 q3     β 9 6 8   α = 4,  β = 6   Определить оптимальные пропорции в выпускаемой продукции, гарантирующие среднюю величину прибыли при любом состоянии спроса, считая его неопределенным. Решение. Задача сводится к игровой модели, в которой игра предприятия А против спроса В задана платежной матрицей (табл. 5.3). Определим нижнюю и верхнюю цены игры в табл. 5.2. Так как α ≠ β, то седловая точка отсутствует, и оптимальное решение следует искать в смешанных стратегиях игроков:  и . Обозначив xi = pi/v, yj = qj/v, составим две взаимно-двойственные задачи линейного программирования. Задача 1. Игрок А. Задача 2. Игрок В. Рекомендуется решать задачу на максимум, как, например, задача 2, поскольку первое базисное решение для нее будет допустимым. Введем добавочные переменные и перейдем к уравнениям, т. е. приведём задачу линейного программирования к каноническому виду. Учитывая соответствие между переменными задач (вторая теорема двойственности), получим: Свободные (первоначальные) переменные Базисные (дополнительные) переменные x1  x2  x3 x4  x5  x6 ↕    ↕    ↕ ↕    ↕    ↕ y4  y5  y6 y1  y2  y3 Базисные (дополнительные)переменные Свободные (первоначальные) переменные т. е.: x* = (0,074; 0; 0,111), у* = (0,037; 0,148; 0). При решении задачи линейного программирования с помощью надстройки MS Excel «Поиск решения» решение двойственной задачи содержится в отчёте Устойчивость: основные переменные – в столбце «Результ. значение», а дополнительные – в столбце «Теневая цена». Используя первую теорему двойственности, получим: Zmin = Z´max = 0,185. По формуле (5.3): ν = 1/0,185 = 5,4. Учитывая, что xi = pi/v,  yj = qj/v, получим: pi = xi ∙ v, p1 = 0,074 ∙ 5,4 = 0,4, p2 = 0 ∙ 5,4 = 0, p3 = 0,111 ∙ 5,4 = 0,6. qj = yj ∙ v, q1 = 0,037 ∙ 5,4 = 0,2, q2 = 0,148 ∙ 5,4 = 0,8, q3 = 0. Оптимальная стратегия игрока А – SA = (0,4; 0; 0,6), игрока В – SВ = = (0,2; 0,8; 0). Решение двойственной задачи линейного программирования представлено на рис. 5.1–5.3.   Рис. 5.1. Решение задачи теории игр с помощью надстройки MS Excel «Поиск решения»   Рис. 5.2. Данные для решения задачи в надстройке MS Excel «Поиск решения»   Рис. 5.3 Использование отчёта «Устойчивость» для поиска дополнительных переменных   Ответ: Предприятие должно выпустить 40 % продукции А1 и 60 % продукции А3, а продукцию А2 не выпускать. Оптимальный спрос в 20 % времени находится в состоянии В1, и в 80 % – в состоянии В2, при этом математическое ожидание прибыли составит 5,4 ден. ед. При решении произвольной конечной игры размера m × n рекомендуется придерживаться следующей схемы. 1. Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока А (игрока В) являются те, которым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов). 2. Определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадает с верхней (нижней) ценой. 3.  Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. 5.5. Исходные данные Методика решения задач по теории игр включает следующие этапы: 1) составление платёжной матрицы игры в соответствии с выбранными вариантами; 2) определение верхней и нижней цены игры; 3) если α ≠ β, то следует составить две взаимно-двойственные задачи; 4) решение задачи линейного программирования. Рекомендуется решать задачу на максимизацию целевой функции с ограничениями «меньше либо равно»; 5) формулирование выводов по задаче. Задача 1. Предположим, что ОАО «РЖД» осуществляет только три вида деятельности: грузовые перевозки; пассажирские перевозки в дальнем следовании; пассажирские перевозки в пригородном сообщении:  (А1, A2 и А3) – стратегии игрока А, получая при этом прибыль, зависящую от спроса, который может быть в одном из четырёх состояний (В1, В2, В3 и В4) – стратегии игрока В. Определить оптимальные пропорции в видах деятельности, гарантирующие среднюю величину прибыли при любом состоянии спроса, считая его неопределенным. Игровая модель задаётся платежной матрицей с элементами аij, характеризующими прибыль, которую получит ОАО «РЖД»  при выпуске i-й продукции с j-м состоянием спроса. Указания. Вывод сделать по образцу: «Следовательно, ОАО "РЖД" должно осуществлять виды деятельности в следующих пропорциях __ % грузовые перевозки – А1, __ % пассажирские перевозки в дальнем следовании – А2, а, допустим (условный пример!), пассажирские перевозки в пригородном сообщении – А3 не осуществлять. Оптимальный спрос в __ % времени находится в состоянии В1, и в __ % – в состоянии В2» и т. д. Задачи линейного программирования необходимо решать с помощью надстройки MS Excel «Поиск решения». Выбор вариантов. Стратегия игрока В имеет четыре стратегии – их оценки остаются неизменными. Для стратегия игрока А выбираются три стратегии по трём последним цифрам номера зачётной книжки. Например, три последние цифры зачётной книжки студента равны 285, таким образом, выбираем строки 2, 8, 5. Если три последние цифры номера зачётной книжки содержат два одинаковых числа, например, 055, то выбираются строки 0, 5, *(1) – одно совпадение (табл. 5.4); если номер содержит три одинаковые цифры, например, 555, то выбираются строки 5, *(1), **(1) – два совпадения (табл. 5.4). В случае, если платежная матрица содержит седловую точку, то строка, её содержащая, заменяется на значения строки ***(с.т.). Например, три последние цифры номера зачётной книжки 026, таким образом, платёжная матрица выглядит следующим образом (табл. 5.3).   Таблица 5.3 - Платёжная матрица игры по варианту 026                  Вj  Аi                   В1 В2 В3 В4 α А1 4 6 1 7 1 А2 5 8 10 6 5* А3 5 1 10 5 1 β 5* 8 10 7   Поскольку α = β = 5, то имеется седловая точка; игра имеет решение в чистых стратегиях. Заменяем строку с набором стратегий А2 на строку ***(с.т.).    Таблица 5.4 - Варианты для решения задачи по теории игр Стратегии игроков Номера зачетной книжки Стратегии игрока В В1 В2 В3 В4 Стратегии игрока А 4 6 1 7 1 8 7 9 4 2 5 8 10 6 3 10 8 9 2 4 2 8 3 8 5 7 9 6 2 6 5 1 10 5 7 2 1 8 1 8 9 3 7 9 9 1 2 3 8 *(1) 3 8 5 4 **(2) 2 9 7 6 ***(с.т.) 10 5 8 1   В задаче следует привести доказательство существования (α = β) или отсутствия (α ≠ β) седловой точки (см. табл. 5.3).