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

 

Содержание

Введение2

1. Матричная игра 2
2. Равновесная ситуация5
3. Смешанные стратегии7
4. Методы решения матричных игр10
1. Решение 2 2-игры 10
2. m n – игры 11
3. Решение игр 213
4. Решение игр симплекс-методом16

Заключение18

    Список литературы19

 

 

Введение

В процессе целенаправленной человеческой деятельности возникают  ситуации, в которых интересы отдельных  лиц (участников, групп, сторон) либо прямо противоположны,  либо, не будучи непримиримыми, все же не совпадают. Простейшими и наиболее наглядными примерами таких ситуаций являются спортивные игры, арбитражные споры, военные учения (маневры), борьба между блоками избирателей за своих кандидатов, в международных отношениях - отстаивание интересов своего государства и т. п. Здесь каждый из участников сознательно стремится добиться наилучшего результата за счет другого участника. Подобного рода ситуации встречаются и в различных сферах производственной деятельности.

Игра (в математике) - это  идеализированная математическая модель коллективного поведения: несколько игроков влияют на исход игры, причем их интересы различны

Один из самых простых, но одновременно и наиболее изученных  и продвинутых классов игр, на так называемых матричных играх. Матричной игрой (при двух участниках) называется игра, в которой выигрыши первого игрока (проигрыши второго игрока) задаются матрицей. Исследование матричных игр интересно потому, что к ним могут быть приближенно сведены многие игры более общего вида.

1. Матричная игра

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

Предположим, что игрок А имеет m стратегий: , , …, а игрок В – n стратегий: , , …,

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

Последнее условие показывает, что в рассматриваемых обстоятельствах  выигрыш одного из игроков равен  выигрышу другого, взятому с противоположным  знаком. Поэтому при анализе такой  игры можно рассматривать выигрыши только одного из игроков. Пусть это  будет, например, выигрыши игрока А.

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

			…
			...
			...
…	...	...	...	...
			...

 

Рис. 1.1. Общий вид платёжной  матрицы матричной игры

Полученная матрица имеет  размер m n и называется матрицей игры или платежной матрицей.

Матричной игрой (при двух участниках) называется игра, в которой  выигрыши первого игрока (проигрыши  второго игрока) задаются матрицей. Матричные игры относятся к разряду так называемых антагонистических игр, т. е. игр, в которых интересы игроков прямо противоположны.

2. Равновесная ситуация

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

Величина выигрыша игрока A равна, по определению матричной игры, величине проигрыша игрока B. Поэтому для игрока B необходимо определить значение Vв=.

Или найти максимальные значения по каждому из столбцов платёжной  матрицы, а затем определить минимальное  из этих значений. Величина Vв называется минимаксом матрицы или верхней ценой игры.

В случае, если значения Vн и Vв не совпадают, при сохранении правил игры (коэффициентов ) в длительной перспективе, выбор стратегий каждым из игроков оказывается неустойчивым. Устойчивость он приобретает лишь при равенстве Vн = Vв = V. В этом случае говорят, что игра имеет решение в чистых стратегиях, а стратегии, в которых достигается V - оптимальными чистыми стратегиями. Величина V называется чистой ценой игры.

Цена игры совпадает с  элементом  матрицы игры A, расположенным на пересечении -й строки (стратегия игрока A) и -го столбца (стратегия игрока B), - минимальным в своей строке и максимальным в своем столбце.

Этот элемент называют седловой точкой матрицы A или точкой равновесия, а про игру говорят, что она имеет седловую точку.

Стратегии и , соответствующие седловой точке, называют оптимальными, а совокупность оптимальных ситуаций и цена игры – решением матричной игры с седловой точкой.

Седловых точек в матричной  игре может быть несколько, но все  они имеют одно и то же значение.

Матричные игры с седловой точкой важны и интересны, однако более типичным является случай, когда  применение описанного алгоритма приводит к неравенству Vн < Vв.

3. Смешанные стратегии

 

      В играх без седловых точек любые стратегии игроков, в том числе максиминная и минимаксная, в известном смысле, являются ненадежными. В этих играх среди имеющихся у игроков стратегий нет таких, которые гарантировали бы получение возможно большего выигрыша: как бы ни рассуждал игрок при выборе своей стратегии, его противник может восстановить ход его мыслей и наказать его. Оказывается, наилучшим способом сохранения тайны является случайный выбор стратегии. В этом случае противник не может догадаться о том, какая стратегия будет выбрана, поскольку даже сам игрок не знает, каков будет результат случайного выбора. Больше того, и это главное, оказалось, что разумно построенный случайный выбор стратегии гарантирует игрокам определенный исход игры, как это имело место в играх с седловой точкой. Такой способ выбора, предложенный французским математиком Э.Борелем, получил название смешанной стратегии. Суть смешанной стратегии заключается в одновременном задействовании или "смешивании" нескольких стратегий, каждой из которых предписывается определенный вес.

Приведем простой пример смешивания стратегий.  

Арбитр футбольного матча, чтобы  определить первую атакующую команду, бросает монету, т.е. вместо того, чтобы  принять определенное решение, выбирает пару чисел (1/2, 1/2), где первое число  – есть вероятность того, что  атакующей будет первая команда, второе - вероятность для второй команды.  
        Четыре студентки, проживающие в одной комнате, тянут четыре спички, одна из которых короче остальных. Та "неудачница", которой достанется короткая спичка, должна вымыть пол. Поступая так, студентки добавляют к своим четырем стратегиям: "моет пол Галя", "поет пол Вера", "моет пол Наташа", "моет пол Лена" еще одну, а именно, вектор х=(1/4, 1/4, 1/4, 1/4). Дополнительная стратегия х состоит в смешивании четырех стратегий, каждой с вероятностью 1/4.     

Чтобы отличить от стратегий вида х первоначальные стратегии игроков будем называть их чистыми стратегиями. Мы переходим теперь к формальному определению смешанных стратегий.

Пусть дана игра A= ,

в которой у игрока A - m, а у игрока B - n чистых стратегий.  
        Смешанной стратегией игрока называется вероятностное распределение на множестве его чистых стратегий.

Смешанная стратегия игрока A в игре есть вектор , где (i=1,...,m) - вероятность выбора i-й чистой стратегии. Так как - вероятность, то 0 и, поскольку одна из m чистых стратегий обязательно будет выбрана, то представляет собой вероятность полной группы событий. Значит,=1.

Аналогично, смешанная стратегия игрока B есть вероятностный вектор Y, где (j=1,...,n) выбора j-й чистой стратегии, 0 и =1.

В этих условиях каждая обычная ситуация по определению является случайным событием и ввиду независимости X и Y реализуется с вероятностью . Поскольку в этой ситуации игрок A получает выигрыш , то математическое ожидание выигрыша в условиях ситуации в смешанных стратегиях равно = .

Это число принимается за средний  выигрыш игрока A в ситуации в смешанных стратегиях .

Стратегии и называются оптимальными смешанными стратегиями игроков A и B соответственно, если выполнено следующее соотношение: .

Последнее равносильно тому, что

 .

Величина V=, определяемая последней формулой называется ценой игры.

Набор , состоящий из оптимальных смешанных стратегий игроков A и B и цены игры, называется решением матричной игры.

Не всякая матричная игра имеет решение в чистых стратегиях. Благодаря введению смешанных стратегий становится возможным следующее важнейшее в теории игр утверждение.

Теорема 1 (о минимаксе). Любая матричная игра имеет решение в смешанных стратегиях.

Теорема о минимаксе, или основная теорема для матричных игр, впервые  была доказана Дж. фон Нейманом.

 

существуют и равны между  собой:

.

Более того, существует хотя бы одна ситуация в смешанных стратегиях , для которой выполняется соотношение

 

 

 

 

 

4. Методы решения матричных игр

Сравнительно просто решаются игры, в которых хотя бы один игрок  имеет всего две чистых стратегии: игры 2 2, 2 n, m n. Когда m, n>2 теория игр не имеет собственного точного метода. Такие игры сводятся к задачам линейного программирования и решаются методом симплекс-таблиц. Нужно заметить, что применение симплекс метода приводит к громоздким вычислениям уже для игры 3x3. Для игр больших размеров применяются приближенные методы.

1. Решение 2 2-игры

 

В общем случае игра 2 2 определяется матрицей

.

Прежде всего, необходимо проверить, есть ли у данной игры седловая точка. Если да, то игра имеет решение  в чистых стратегиях, причём оптимальными стратегиями игроков A и B соответственно будут чистая максиминная и чистая минимаксная стратегии. Если же игра с матрицей выигрышей А не имеет решения в чистых стратегиях, то оба игрока имеют только такие оптимальные стратегии, которые используют все свои чистые стратегии с положительными вероятностями.

Пусть U = (x, 1 - x) – оптимальная стратегия игрока A. Тогда

;    .

Аналогично, если W = (h, 1 – h) – оптимальная стратегия игрока B, то

.

 

2. m n – игры

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

Пусть дана m n - игра А. Говорят, что i-я стратегия игрока A доминирует его k-ю стратегия, если для всех j = 1,2,…,n. Говорят, что j-я стратегия игрока B доминирует его l-и стратегию, если для всех i = 1,2,…,m. .  
        Из определения видно, что доминирующая стратегия дает игроку выигрыш не хуже, чем доминируемая. Отсюда следует, что игрок всегда может обойтись без доминируемых стратегий, в частности, если есть одинаковые стратегии, то он может применять только одну из них. Поэтому в матрице А доминируемые стратегии (строки или столбцы) могут быть отброшены, а это приводит к матрице малых размеров. В результате выполнения доминирования получается игра, эквивалентная первоначальной, в смысле следующего утверждения.

Теорема 2. Пусть (x,y) - седловая точка m n - игры А, а () - седловая точка - игры A' (), полученной из А в результате исключения доминируемых стратегий. Тогда , для всех недоминируемых i, j: =0, для всех доминируемых i:

Пример 1. Рассмотрим игру

Стрелками показаны доминируемые стратегии. Получили 2х2-игру, в которой все  стратегии недоминируемы. Игра эквивалентна первоначальной игре А, т.е. оптимальные стратегии в игре А имеют вид x=(0,),         

В результате вместо игры А мы можем решить более простую 2х2-игру .

Теперь мы можем указать общий  порядок решения матричной игры:

1. проверить, существует ли решение в чистых стратегиях; если есть, то игра решена;
2. если нет решения в чистых стратегиях, то выполнить доминирование;
3. найти решение в смешанных стратегиях.

 

3. Решение игр 2

Для построения решений 2 - игр существует эффективный метод, основанный на простых геометрических соображениях. Этот метод называют графическим.

Рассмотрим игру 2 n: .

Задача игрока A состоит в максимизации функции .Так как , мы имеем .

Таким образом, v является минимумом n линейных функций одной переменной ; можно вычертить графики этих функций и затем максимизировать их минимум g( ) графическими методами. Покажем на примере игры 2 3.