Теория игр

1. Основные понятия  теории матричных игр

Теория игр – это совокупность математических методов анализа и оценки конфликтных ситуаций.

Содержание теории игр: установление принципов оптимального поведения в условиях неопределенности (конфликта), доказательство существования решений, удовлетворяющих этим принципам, указание алгоритмов нахождения решений, их реализация.

Моделями теории игр можно  описать экономические, правовые, классовые, военные конфликты, взаимодействие человека с природой.

Все такие модели в теории игр принято называть играми.

Игры можно классифицировать по различным признакам: стратегические и чисто случайные, бескоалиционные  и коалиционные, игры 1, 2, …, n лиц (по числу игроков), конечные и бесконечные (по числу стратегий), игры в нормальной форме и динамические, с нулевой суммой («антагонистические») и с ненулевой суммой.

Рассмотрим простейшую модель – игру, в которой участвуют два игрока, множество стратегий каждого игрока конечно, а выигрыш одного игрока равен проигрышу другого (бескоалиционная, конечная, антагонистическая игра двух лиц). Такую игру (Г) называют матричной. Она определяется тройкой Г=(X,Y,K), где Х – множество стратегий 1-го игрока, Y – множество стратегий 2-го игрока,K=K(x,y) – функция выигрыша (выигрыш 1-го игрока и соответственно проигрыш 2-го при условии, что 1-й игрок выбрал стратегию  , а 2-й – стратегию  ). Пару (x,y) называют ситуацией в игре Г.

Пусть 1-й игрок имеет  всего m стратегий, а 2-й – n стратегий: Х=М={1,2, …, m}, Y=N={1,2, …, n}. Тогда игра Г полностью определяется заданием матрицы  , где a_ij=K(i,j) – выигрыш 1-го игрока при условии, что он выбрал стратегию (т.е. строку) i, а 2-й игрок – стратегию (т.е. столбец) j (эти стратегии называют чистыми).

Матрица А называется матрицей игры или платежной матрицей.

Пусть матрица  игры  . Цель каждого игрока – получить как можно больший выигрыш. Но 1-му игроку нет смысла выбирать стратегию i=1 в надежде выиграть 5 ед., так как 2-й игрок, действуя разумно, не станет выбирать стратегию j=2, чтобы не проиграть максимальную сумму 5 ед. Игрокам удобнее выбрать «осторожные» стратегии.

Пусть  – платежная матрица игры Г. Если 1-й игрок выбрал стратегию i, то в худшем случае он выиграет  . Поэтому он всегда может гарантировать себе выигрыш  , обозначим его  – нижняя цена игры, или максимин, соответствующая стратегия 1-го игрока называется максиминной.

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

Схема:

Например, 

Соответствующие стратегии: i₀=1 (максиминная), j₀=1,2 (минимаксная).

Справедливо неравенство:  .

В игре Г естественно считать оптимальной такую ситуацию (i,j), от которой ни одному из игроков невыгодно отклоняться.

Ситуация (i^*,j^*) называется ситуацией равновесия, или седловой точкой, если для любых  ,   выполняется неравенство  . Соответствующие стратегии i^*, j^* называются оптимальными чистыми стратегиями 1-го и 2-го игроков, а число   называется ценой игры. Элемент   является одновременно минимумом в своей строке и максимумом в своем столбце.

Ситуация равновесия существует тогда и только тогда, когда   (это значение и является ценой игры v).

Например, 

(2,3)-ситуация равновесия, v=4 – цена игры, i^*=2, j^*=3 – оптимальные стратегии 1-го и 2-го игроков. Выбрав их, 1-й игрок обеспечит себе выигрыш не менее 4 ед., а 2-й игрок проиграет не более 4 ед. при любом выборе другого игрока.

Наряду с чистыми стратегиями  игроков рассматривают также смешанные стратегии.

Смешанной стратегией для 1-го игрока называется упорядоченная система m действительных чисел x=(x₁, x₂, …, x_m),  ,  , которые можно рассматривать как относительные частоты (вероятности), с которыми 1-й игрок выбирает чистые стратегии i=1, 2, …, m.

Аналогично определяется смешанная стратегия для 2-го игрока: y=(y₁, y₂, …, y_n),  ,  .

Множества всех смешанных  стратегий 1-го и 2-го игроков будем  обозначать соответственно S_m и S_n.

Чистые стратегии можно  рассматривать как частный случай смешанных стратегий. Например, чистую стратегию j=2 можно рассматривать как смешанную y=(0,1,0,…,0), чистую стратегию i=1 – как смешанную x=(1,0,…,0).

Пару смешанных стратегий (x,y) называют ситуацией в смешанных стратегиях.

Функция выигрыша K(x,y) в ситуации (x,y) определяется как математическое ожидание выигрыша 1-го игрока при условии, что 1-й и 2-й игроки выбрали соответственно стратегии x=(x₁, x₂, …, x_m) и y=(y₁,y₂, …, y_n):  .

Если для некоторых   и   и для всех   и   выполняется неравенство  , то x^*, y^* называются оптимальными смешанными стратегиями игроков, число  называется ценой игры, пара (x^*, y^*) – стратегической седловой точкой, а тройка x^*, y^*, v – решением игры.

Основная теорема  теории матричных игр, или теорема о минимаксе. Если  – матрица игры Г и для всех   и    , то величины   и   существуют и равны между собой (эта величина и является ценой игры v).

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

Свойства оптимальных  стратегий

1. Пусть K(x,y) – математическое ожидание выигрыша в игре Г_А с ценой v. Тогда, для того чтобы элемент   был оптимальной стратегией 1-го игрока, необходимо и достаточно, чтобы для каждого элемента   выполнялось неравенство  . Аналогично, для того чтобы   был оптимальной стратегией 2-го игрока, необходимо и достаточно, чтобы для каждого   выполнялось неравенство  .

2. Пусть K(x,y) – математическое ожидание выигрыша в игре Г_А, v – действительное число,  ,  . Тогда, для того чтобы v было ценой игры, а x^* и y^* были оптимальными стратегиями соответственно 1-го и 2-го игроков, необходимо и достаточно, чтобы для любых   и   выполнялось неравенство  .

3. Пусть K(x,y) – математическое ожидание выигрыша в игре Г_А с ценой v. Тогда, для того чтобы элемент   был оптимальной стратегией 1-го игрока, необходимо и достаточно, чтобы для каждого   выполнялось неравенство  . Аналогично, для того чтобы   был оптимальной стратегией 2-го игрока, необходимо и достаточно, чтобы для каждого   выполнялось неравенство  .

4. Если x^*, y^* – решение  -игры Г_А, то  .

5. Пусть  ,  , v – решение игры Г_А. Тогда для любого  , при котором  , выполняется неравенство x_i=0, а для любого  , при котором  , выполняется неравенство y_j=0.

6 (Лемма о масштабе). Если Г_А – игра с матрицей  , а   – игра с матрицей  , где  , где α,b=const, α>0, то множества оптимальных стратегий игроков в играх Г_А и   совпадают, а  . Иначе говоря, две игры, отличающиеся лишь началом отсчета выигрышей и масштабом их измерения, стратегически эквивалентны.

2. ( ) – игры

Пусть   – платежная матрица игры Г. Если она не имеет седловой точки, то единственное решение игры Г можно найти

1) решив две системы:

2) по формулам:

;   (или  );

;   (или  );

;

3) в матричном виде:

,          ,       ,

где   – определитель матрицы А, А^* – присоединенная к А матрица,  ,  ,  , J^T и y^T – транспонированные матрицы J и y.

Найдем, например, решение  игры с платежной матрицей  , которая не имеет седловой точки.

1) Составим системы:

Решив системы, получим:

,  ,  ,  ,  , то есть  ,  ,   – решение игры.

2) Найдем решение по  формулам:

;                 ;

;  ;  .

3) Найдем решение в  матричном виде:

,  ,  ,  ,  ;

,  ,  .

Результаты совпадают.

3.  и  – игры

Рассмотрим игру с платежной  матрицей  .

Если 1-й игрок применит смешанную стратегию  , а 2-й игрок – чистую стратегию  , то  . (1)

Аналогично при выборе 2-м игроком чистых стратегий  , ,

По формулам решения  – игры получим:

,  ;

,  ;  .

Тогда решение исходной игры имеет вид  ,   (номерам столбцов, не вошедших в матрицу  , соответствуют нулевые

координаты вектора  ),  .

Аналогично решаются  - игры. Пусть, например,  ,  – смешанная стратегия 2-го игрока, 1-й игрок выбирает чистые стратегии i=1,2,3.

;                                                                          (1)

;                                                                          (2)

.                                                         (3)

Построим прямые (1),(2),(3) по двум точкам, придавая y значения 0 и 1 (рис. 2). Оптимальная стратегия 2-го игрока – его минимаксная стратегия, которая соответствует самой низкой точке B выделенной на рис. 2 верхней границы. Абсцисса этой точки – искомой значение y, ордината точки – значение v.

Тогда решение исходной игры:

,  , .

Рассмотрим еще один пример. Пусть платежная матрица игры  . Построим соответствующие прямые (1), (2), (3) (рис.3). На выделенной нижней границе есть горизонтальный участок AB, все точки которого имеют одну и ту же (максимальную) ординату.

Решение исходной игры:  , где  ,  ,  , то есть 1-й игрок имеет множество оптимальных стратегий, 2-й игрок – единственную оптимальную стратегию, это чистая стратегия j=2 (только она участвует в образовании отрезка AB), цена игры v – ордината точек отрезка AB. Значения v и y^* можно было получить также, используя формулы решения  –игр для матрицы  или   (проверьте!).

4. Доминирование  стратегий

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

Например, в игре с платежной  матрицей   1-му игроку не стоит выбирать стратегию i=3, лучше выбрать i=2 (какую бы стратегию ни выбрал 2-й игрок), а 2-ому игроку не стоит выбирать j=3, лучше выбрать j=1 (почему?). В результате вместо игры Г_А с матрицей А можно рассмотреть игру   с матрицей  . Легко найти решение игры  :  ,  ,  . Можно предположить, что решение игры Г_А будет иметь вид:  ,  ,  .

Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если   для всех   и хотя бы для одного j  . В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая.

Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех     и хотя бы для одного i  . В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой.

В предыдущем примере 2-я  стратегия 1-го игрока доминирует его 3-ю  стратегию, 1-я стратегия 2-го игрока доминирует его 3-ю стратегию. Доминируемые стратегии исключаются из матрицы игры.

Стратегия может доминироваться также выпуклой линейной комбинацией других стратегий. Так, i-я стратегия 1-го игрока доминируется выпуклой линейной комбинацией остальных стратегий, если  ; j-я стратегия 2-го игрока доминируется выпуклой линейной комбинацией остальных стратегий, если  .

Например, в матрице   3-я строка строго доминируется выпуклой линейной комбинацией 1-ой и 2-ой строк с коэффициентами   и  :   (проверьте!), поэтому вместо игры Г_Аможно рассмотреть игру  ,  . Найдя ее решение, получим решение игры Г_А:  ,  , v=6.

Если   – некоторая смешанная стратегия, то ее расширением на i-ом месте будем называть стратегию вида  .

Справедлива теорема: пусть Г_А –  – игра, в которой i-я строка доминируема,   – игра с матрицей  , полученной из А вычеркиванием i-ой строки. Тогда

1)  ;

2) всякая оптимальная  стратегия 2-го игрока в игре   является оптимальной и в игре Г_А;

3) если x^* – оптимальная стратегия 1-го игрока в игре  , то   – его оптимальная стратегия в игре Г_А.

Аналогичная теорема имеет  место для доминируемого столбца.

5. Множество решений  матричной игры

Можно доказать, что множества  оптимальных стратегий 1-го и 2-го игроков (Т₁ и Т₂) – непустые ограниченные выпуклые и замкнутые подмножества соответственно m-мерного и n-мерного пространств. Из выпуклости следует, что если Т₁ (Т₂) имеет более одного элемента, то оно имеет бесконечное число элементов, то есть матричная игра имеет либо только одно, либо бесконечное множество решений.

Чтобы найти множество  всех решений игры с платежной  матрицей А, нужно рассмотреть все квадратные подматрицы матрицы А. Найдя решения игр, заданных подматрицами, нужно составить их расширения на соответствующих местах и проверить, являются ли полученные стратегии оптимальными для игры Г_А. Множество всех решений каждого игрока является выпуклой линейной комбинацией найденных решений.

Решение игры, заданной квадратной подматрицей В, можно найти в матричном виде по формулам  ,  ,  .

Найдем, например, множество  всех решений игры Г_А с платежной матрицей  .

Подматрицы   не дадут решений, так как матрица А не имеет седловых точек. Рассмотрим подматрицы  :

,          ,         .

Для В:   – является решением игры Г_А (убеждаемся в этом проверкой).

Для С:  ,  ,    ,  ,   – является решением игры Г_А.

Для D получим такое же решение, как для В.

Таким образом, в игре Г_А 1-й игрок имеет единственную оптимальную стратегию  , 2-й игрок имеет множество оптимальных стратегий  , где  ,  , цена игры v=1.

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

Пусть матрица игры имеет  вид  , K=K(x,y)– функция выигрыша,  ,  ,  .

Тогда по свойству 2 оптимальных  стратегий для любых  ,   должно выполняться условие  , то есть 

Разделив все уравнения  и неравенства обеих систем на v, обозначим  ,  . Заметим, что цена игры v при этом должна быть положительна, в противном случае нужно предварительно к матрице А применить лемму о масштабе. Учитывая, что цель 1-го игрока – максимизировать, а цель 2-го – минимизировать величину v, приходим к двойственной задаче линейного программирования с целевой функцией  :

Решив задачу симплексным  методом и вернувшись к переменным xi, yj, получим решение матричной игры.

Пример. Найти решение игры с матрицей  .

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

Решим задачу симплексным  методом.

Получаем решение двойственной задачи:  ,  ,  .

Тогда решение игры с матрицей  :  ,  ,  .

Решение исходной игры:  ,  ,  .

7. Приближенное  решение матричных игр

Для матриц большой размерности  применение методов линейного программирования приводит к громоздким вычислениям, поэтому удобнее использовать приближенные методы решения. Одним из таких методов  является итеративный метод Брауна-Робинсона, или метод фиктивного разыгрывания. Идея метода – многократное фиктивное разыгрывание игры. В первой партии каждый игрок выбирает произвольную чистую стратегию, в k-ой партии каждый выбирает ту стратегию, которая принесла максимальный суммарный выигрыш (для первого игрока) или минимальный суммарный проигрыш (для второго игрока) в (k-1)-ой партии.

Можно доказать, что  , где v – цена игры, k– номер партии,   – максимальное значение суммарного выигрыша 1-го игрока в k-ой партии при выборе различных стратегий,   – минимальное значение суммарного проигрыша 2-го игрока в k-ой партии при выборе различных стратегий.

За приближенные оптимальные  стратегии игроков принимают  векторы, координатами которых являются относительные частоты выбора соответствующих  чистых стратегий.

Преимущество метода – его простота, недостаток – малая скорость сходимости вследствие немонотонности последовательностей   и  .

Пример. Найти приближенное решение игры, заданной матрицей 

Решение. Обозначим чистые стратегии 1-го игрока a, b, c, 2-го игрока – α, b, g. Пусть в первой партии игроки выбрали стратегии a и α.  ;    . Приближенное решение игры за 12 партий: v=1,45,  ,  .

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