ТЕОРИЯ ИГР

Литература 1.Петросян Л.А., Зенкевич Н.А., Семина Е.А. Теория игр. – М., Воробьев Н.Н. Теория игр для экономистов- кибернетиков. – М.: Наука, Дюбин Г.Н., Суздаль В.Г. Введение в прикладную теорию игр.– М.: Наука, 1981.

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-го игрока называется максиминной.

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

Схема:

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

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

Ситуация (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 1, x 2, …, x m ),,, которые можно рассматривать как относительные частоты (вероятности), с которыми 1-й игрок выбирает чистые стратегии i=1, 2, …, m. Аналогично определяется смешанная стратегия для 2-го игрока: y=(y 1, y 2, …, y n ),,.

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

Если для некоторых и и для всех и выполняется неравенство, то x*, y* называются оптимальными смешанными стратегиями игроков, число называется ценой игры, пара (x*, y*) – стратегической седловой точкой тройка x*, y*, 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 (Лемма о масштабе). Если Г А – игра с матрицей, а – игра с матрицей, где, где α, =const, α>0, то множества оптимальных стратегий игроков в играх Г А и совпадают, а. Иначе говоря, две игры, отличающиеся лишь началом отсчета выигрышей и масштабом их измерения, стратегически эквивалентны.

2. ( ) - игры

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

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

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

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

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

1) Составим системы: Решив системы, получим: то есть -решение игры.

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

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

3. и – игры

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

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

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

1 A Рис.1 (1) x 0 x (3) (2) (4)

Точка A является точкой пересечения прямых (2) и (3), поэтому решение исходной игры можно найти, решив игру

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

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

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

(1) (2) (3)

(1) y 0 y (3) (2) 1 B Рис.2

Точка B является точкой пересечения прямых (2) и (3). Найдем решение игры

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

Пусть платежная матрица игры (3) x 0 x2x2 (2) (1) Рис.3 1 BA x1x1

A – точка пересечения прямых (2) и (3), ее абсциссу найдем, решая игру

B – точка пересечения прямых (1) и (2), ее абсциссу найдем, решая игру

Решение исходной игры:, где,, то есть 1-й игрок имеет множество оптимальных стратегий, 2-й игрок – единственную оптимальную стратегию, это чистая стратегия j=2.

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

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

В результате вместо игры Г А с матрицей А можно рассмотреть игру с матрицей

Легко найти решение игры Можно предположить, что решение игры Г А будет иметь вид:

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

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

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

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

теорема: пусть Г А – -игра, в которой i-я строка доминируема, – игра с матрицей, полученной из А вычеркиванием i-ой строки. Тогда 1) ; 2) всякая оптимальная стратегия 2-го игрока в игре является оптимальной и в игре Г А ; 3) если x* – оптимальная стратегия 1-го игрока в игре, то – его оптимальная стратегия в игре Г А. Аналогичная теорема имеет место для доминируемого столбца.

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

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

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

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

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

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

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

Для С: – является решением игры Г А. Для D получим такое же решение, как для В.

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

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

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

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

То есть

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

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

Составим двойственную задачу линейного программирования:

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

Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 1-я итерация q4q q5q q6q

Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 2-я итерация q4q4 02/301/37/310-1/3 q5q5 02/3 0 7/3 4/301-1/3 q1q1 11/3 1 2/3 001/ /3 001/3

Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 3-я итерация q4q4 04/70015/71-1/7-2/7 q2q2 12/7 0 14/703/7-1/7 q1q1 11/7 10 2/70-2/73/ /701/72/7

Базис С0С0 P0P q1q1 q2q2 q3q3 q4q4 q5q5 q6q6 4-я итерация q3q3 14/150017/15-1/15-2/15 q2q2 12/ /157/15-1/15 q1q1 11/ /15-4/157/ /152/154/15

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

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

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

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

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

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

партии k выбор 1-го игрока выбор 2-го игрока суммарный выигрыш 1-го игрока при выборе стратегии суммарный проигрыш 2-го игрока при выборе стратегии abcαβ 1 aα bβ bβ cβ cβ cβ ,8331,167

партии k выбор 1-го игрока выбор 2-го игрока суммарный выигрыш 1-го игрока при выборе стратегии суммарный проигрыш 2-го игрока при выборе стратегии abcαβ 7 cβ ,8571,286 8 c ,751,25 9 c ,6671, c ,71,2 11 a ,8181, a ,9171,417

Приближенное решение игры за 12 партий: v =1,45, ;,