Матричные игры

Графический метод можно применять  при решении игры 2 × п и m × 2.

2.1.4. Приведение матричной игры к задаче линейного программирования

Игра m×n в общем случае не имеет наглядной геометрической интерпретации. Её решение достаточно трудоёмко при больших m и п, однако принципиальных трудностей не имеет, поскольку может быть сведено к решению задачи линейного программирования. Покажем это. Пусть игра m×n задана платёжной матрицей р= ( ), i = 1, 2, …, m; j = 1, 2, …, n. Игрок  А обладает стратегиями , игрок В – стратегиями . Необходимо определить оптимальные стратегии и , где – вероятности применения соответствующих чистых стратегий ;

, .

Оптимальная стратегия  удовлетворяет следующему требованию. Она обеспечивает игроку А средний выигрыш, не меньший, чем цена игры v, при любой стратегии игрока В и выигрыш, равный цене игры v, при оптимальной стратегии игрока В. Без ограничения общности полагаем v > 0; этого можно добиться, сделав все элементы 0. Если игрок А применяет смешанную стратегию против любой чистой стратегии игрока В, то он получает средний выигрыш, или математическое ожидание выигрыша , 1, 2, …, п (т.е. элементы j-го столбца матрицы почленно умножаются на соответствующие вероятности стратегий результаты складываются).

Для оптимальной стратегии  все средние выигрыши не меньше цены игры v, поэтому получаем систему неравенств:

                                    (3)

Каждое из неравенств можно  разделить на число v > 0. Введём новые переменные:

/v, /v, …, /v.

Тогда система примет вид:

                                    (4)

Цель игрока А – максимизировать свой гарантированный выигрыш, т.е. цену игры v.

Разделив на 0 равенство , получаем, что переменные (i =1, 2, …, т) удовлетворяют условию: 1/v. Максимизация цены игры v эквивалентна минимизации величины 1/v, поэтому задача может быть сформулирована следующим образом: определить значения переменных 0, i =1, 2, …, т, так чтобы они удовлетворяли линейным ограничениям и при этом линейная функция

                                           (5)

 обращалась  в минимум. Это задача линейного   программирования. Решая задачу (3)-(4), получаем оптимальное решение и оптимальную стратегию .

Для определения оптимальной стратегии  следует учесть, что игрок В стремится минимизировать гарантированный выигрыш, т.е. найти . Переменные удовлетворяют неравенствам

                                   (6)

которые следуют из того, что средний проигрыш игрока В не превосходит цены игры, какую бы чистую стратегию не применял игрок А.

Если обозначить

/v, 1, 2, …, п,                                        (7)

то получим систему неравенств:

                                   (8)

Переменные  (j= 1, 2, …, n,) удовлетворяют условию .

Игра  свелась к следующей задаче.

Определить  значения переменных 0, j=1, 2, …, n, которые удовлетворяют системе неравенств и максимизируют линейную функцию

                                          ₍₉₎

Решение задачи линейного программирования определяет оптимальную стратегию  . При этом цена игры

v =1/max =1/min .                                      (10)

Составив расширенные матрицы  для задач (4), (5) и (8), (9), убеждаемся, что  одна матрица получилась из другой транспортированием:

 

                                                 ≥                                            ≤

Таким образом, задачи линейного программирования (4), (5) и (6), (9) являются взаимно-двойственными. Очевидно, при определении оптимальных  стратегий в конкретных задачах  следует выбрать ту из взаимно-двойственных задач, решение которой менее  трудоёмко, а решение второй задачи найти с помощью теорем двойственности.

При решении произвольной конечной игры размером рекомендуется придерживаться следующей схемы:

1. Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока A (игрока B) являются те, которым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов).
2. Определить верхнюю и нижнюю цены игры и проверить имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадет с верхней (нижней) ценой.
3. Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размером рекомендуется симплексный метод, для игр размером 2х2, 2хn, nх2 возможно геометрическое решение.

На практике реализация оптимального решения  в смешанных стратегиях может происходить несколькими путями. Первый состоит в физическом смешении чистых стратегий A_i в пропорциях, заданных вероятностями p_i.

Другой путь - при многократном повторении игры - в каждой партии чистые стратегии применяются в виде случайной последовательности, причём каждая из них с частотой, равной ее вероятности в оптимальном  решении.

2.2. Практические основы изучаемой  темы

Задача  №1.

Найти решение игры, предварительно упростив её.

 

 

_{Вторая  стратегия явно невыгодна  для игрока А, по сравнению с первой.}

 

  и  .

Обозначив, , i = 1,2,3 и , j = 1,2,3,4,5 составим две взаимно-двойственные задачи линейного программирования.

                   

             

Решаем  симплексным методом задачу 2. Введем добавочные переменные и перейдём к  уравнениям.

I шаг.  Основные переменные –

Неосновные  переменные –

Базисное решение  допустимое. Переводим в основные переменные , а в неосновные.

II шаг.  Основные переменные –

Неосновные  переменные –

Базисное решение  допустимое. Переводим в основные переменные , а в неосновные.

III шаг.  Основные переменные –

Неосновные  переменные –

Базисное решение  является оптимальным, так как отсутствуют положительные коэффициенты при неосновных переменных и .

Делаем  переход:

Оптимальное базисное решение задачи 1: , причём , а .

Оптимальная стратегия 

                 

Оптимальная стратегия 

                  

Здесь учтено, что третий столбец  исходной матрицы отброшен.

 

Задача  № 2.

Дать геометрическую интерпретацию  игры:

_{Перейдём  к новой матрице  добавив +2.}

 

 

                                  _y

                                   I                                       II

                                                                                         

                                           

 _N

                                                                   

                                                 v                              

                                                                                 

 

x

 

Нижняя  цена игры – 

Верхняя цена игры – 

 

Точка N точка пересечения прямых и

Составим уравнение прямой , проходящей через точки (0;3) и (1;5)

 

Составим уравнение прямой , проходящей через точки (0;4) и (1;1)

 

Решаем  систему уравнений:

 

Откуда получаем, что x=0,2; y=3,4; то есть т.N(0,2;3,4)

Мы получили, что оптимальная  стратегия игрока А равна:

  

 

Теперь  будем искать оптимальную стратегию  игрока

 

 

 

                                  _y

                                   I                                       II

 

                                                                             

                                             

       _M

                                                                   

                                                          v                      

                                                                                

 

 

 

 

 

 

Точка M точка пересечения прямых и

Составим уравнение прямой , проходящей через точки (0;3) и (1;4)

 

Составим уравнение прямой , проходящей через точки (0;5) и (1;1)

 

Решаем  систему уравнений:

 

Откуда получаем, что x=0,4; y=3,4; то есть т.M(0,4;3,4)

Мы получили, что оптимальная  стратегия игрока B равна:

  

 

Задача  № 3.

Для платёжной матрицы определить нижнюю и верхнюю цены игры.

 

 

 

_{Для удобства составим таблицу:}

 

 

	2	5	3	2
	6	4	5	4
	3	7	6	3
	2	3	4	2
	6	7	6	6                  4

 

Из  таблицы видно, что нижняя цена игры , а верхняя цена игры

 

 

 

 

 

 

 

                    3.        Заключение.

 

   В курсовой работе были рассмотрены  основные понятия и элементы  теории игр: парная конечная  игра и её платёжная матрица,  способ нахождения нижней цены  игры (максимина) и верхней цены  игры (минимакса), а также соответствующие  им стратегии (принцип минимакса), наличие Седловой точки в игре  и цена игры.

   В смешанных стратегиях игр  была изучена теорема Неймана  и теорема об активных стратегиях. Была показана геометрическая  интерпретация игры 2´2 для игр, имеющих и не имеющих Седловой точки; нахождение по графикам оптимальных стратегий игроков и цена игры. Также была приведена матричная игра к задаче линейного программирования, с помощью которой определяются оптимальные стратегии игры m´n и цена игры.

   В практической части  были решены задания по отысканию  платёжной матрицы, верхней и  нижней цены игры, существованию  Седловой точки. Также была  показана геометрическую интерпретацию  игры 2´2 и решена экономическая задача по нахождению оптимального спроса и предложения.   

 

 

 

 

 

 

 

 

 

 

 

 

4.         Список использованной литературы