Теория игр

 

Теория игр – это математическая дисциплина, исследующая методы принятия решений в конфликтных ситуациях, когда сталкиваются интересы конфликтующих сторон. Обычно в игре участвуют 2 лица, преследующие противоположные цели. К конфликтным ситуациям относятся почти все ситуации, возникающие при планировании военных операций, охране объектов, преследовании и перехвате цели, при рассмотрении экономического поведения, арбитражных споров, выборы в парламент, работе аукционов.

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

Игроки – это конфликтующие стороны.

Допустимые действия каждого игрока направлены на достижение некоторой цели – это правило игры. Элементы игры называются ходами.

Личный ход – это выбор игроком одного варианта из заданного множества. Решение, принятое игроком при личном ходе это выбор.

Случайный ход – это выбор одного варианта из множества при помощи некоторого случайного механизма.

Стратегия игрока – это система правил однозначно определяющих выбор поведения игрока на каждом ходе в зависимости от ситуации сложившейся в процессе игры. При выборе стратегии S_j S игрок получает выигрыш h_ij в зависимости от сложившейся ситуации i. Для формализации игры применяют матрицу игры или платежную матрицу, элементы которой a_ij – это выигрыш 1-го игрока при выборе своей i-ой стратегии и встречной стратегии j 2-го игрока.

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

Пусть X и Y пространства всевозможных стратегий x и y, которыми могут пользоваться участники игры: 1-й и 2-й игрок соответственно. Обозначим L_x(x,y,h) и L_y(x,y,h) - проигрыш 1-го и 2-го игроков соответственно в конкретной партии игры. Тогда общая сумма проигрышей называется функцией потерь L_x +L_y=L

Далее будем рассматривать игры с нулевой суммой, т.е. игры в которых L_x(x,y,h) = -L_y(x,y,h) (проигрыш одного игрока = выигрышу другого) – антагонистические игры.

С учетом случайности h можно найти средние потери.

Укажем, что в общем виде игра задается следующей моделью:

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

Если первый игрок применяет стратегию X_k, то он обеспечивает для себя гарантированный выигрыш A(X_k)= min L(X_k,Y) (наименьший элемент в k-ой строке).

Число называется нижней ценой игры,

а соответствующая чистая стратегия 1-го игрока называется максиминной.

Гарантированный проигрыш 2-го игрока B(y_k) равен наибольшему элементу из L(x,y_k) max в k-ом столбце. Выбор наименьшего из этих чисел обеспечивает уменьшение проигрыша 2-го игрока, тогда число - верхняя цена игры.

Теорема:

в игре с матрицей : A(x)≤L(x.y)≤B(y) и α<β.

Теорема:

Если α=β=υ, то игра имеет седловую точку, а соответствующие стратегии игроков являются оптимальными:

Максиминная стратегия оптимальна для первого игрока

Минимаксная стратегия оптимальна для 2-го игрока.

υ – цена игры: означает выигрыш первого и проигрыш 2-го игрока.

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

Если матрица игры имеет седловую точку, то игра называется игрой с седловой точкой. При υ=0 игра называется справедливой, при υ<>0 несправедливой.

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

Вектор, каждая координата которого равна относительной частоте или вероятности использования игроком соответствующей чистой стратегии, называется смешанной стратегией игрока. При использовании смешанных стратегий функция потерь зависит от распределения вероятностей и применения игроками №1 и №2 своих чистых стратегий x и y примет вид:

Теорема:

Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях.

Гарантированное значение выигрыша 1-го игрока при стратегии :

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

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

Гарантированное значение проигрыша 2-го игрока при стратегии :

;

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

Стратегия η₀ определяющая верхнюю цену игры называется минимаксной стратегией 2-го игрока.

Чистые стратегии, входящие в состав оптимальной смешанной стратегии называются полезными стратегиями.

Стратегия i₀ для первого игрока называется доминируемой, если существует стратегия i₁ первого игрока / a_i1,j≥a_i0,j a_ij – элементы матрицы игры или существует μ_i≥0, i≠i₀ /

Стратегия j₀ 2-го игрока называется доминирующей, если существует стратегия j₁ 2-го игрока / a_i,j1≥a_i,j0 или существует ν_j≥0, j≠j₀ /

Теорема:

Неполезными стратегиями 1-го игрока являются его доминируемые стратегии. Неполезными стратегиями 2-го игрока являются его доминирующие стратегии.

 

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

Методы решения задач теории игр с нулевой суммой

 

1-й метод: Матрица игры имеет седловую точку, тогда решение сводится к поиску седловой точки матрицы, координаты которой (i₀,j₀) определяют элемент a_i0,j0 – цену игры, i₀ – чистая оптимальная стратегия 1-го игрока, j₀ – чистая оптимальная стратегия 2-го игрока.

Пример: Игра имеет матрицу

α₁=2; α₂=5; α₃=4; - min элемент в строке.→ max=5=α – верхняя цена игры.

β₁=10; β₁=10; β₁=5; β₁=14; β₁=12; - max элемент столбца→ min=5=β – нижняя цена игры.

a_2,3=5=α=β=υ – цена игры, т.е. оптимальная стратегия 1-го игрока №2, 2-го игрока № 3.

2-й метод: Матрица А имеет размер 2 x n (m x 2) или сводима к этим размерам, тогда задача может быть решена графически. Рассмотрим ситуацию 2 x n, тогда 1-й игрок имеет 2 стратегии и его искомая смешанная стратегия U(x₁,x₂), где x_i – это вероятности с которыми игрок применяет свои i стратегии, тогда средний выигрыш игрока 1-го, если 2-й игрок применяет свою стратегию y_j, равен: L(x,y_j)=x₁*a_1j+x₂*a_2j. Это может быть интерпретировано графически как прямая. Изобразив все стратегии 2-го игрока, как ответы на ход 1-го, определим максиминную стратегию, оптимальную для 1-го игрока. Аналогично, если матрица имеет размер m x 2, изображаем стратегии 1-го как ответы на ход второго. Найдем минимаксную стратегию, оптимальную для 2-го и находят его оптимальную смешанную стратегию.

Пример:

решаем систему.

 

В результате получим: х₁=2/3; х₂=1/3; U^*=(2/3; 1/3)

10 υ=8 (цена игры)

9 9

7 6

 

х₁ 1/3 х₂
y₁=y₂=1/2; y₃=0; υ=8;

X^*(2/3;1/2)→ 67% времени 1-й игрок применяет свою стратегию №1 и 33% времени стратегию № 2.

Пример 2:

Т.к. 2-й игрок имеет 2 стратегии, то решаем задачу для 2-го игрока, изображая стратегии 1-го как ответ на ход 2-го.

 

8

6

5

 

 

y₁₌3/8; y₂=5/8; υ=43/8

 

x₁=7/8; x₂=0; x₃=0; x₄=1/8 X^*(7/8;0;0;1/8)

 

 

Пример 3:

доминируемая стратегия

 

доминирующие

 

, т.е. седловой точки нет, но матрица после упрощения примет вид:

, и решаем задачу графически:

 

 

8

7 7

 

 

x₁=x₃=1/2; x₂=0; υ=4,5

 

y₄=y1=0; y₂=7/12; y₃=0; y₅=5/12

 

X^*(1/2;0;1/2);

Y^*(0;7/12;0;0;5/12);

υ=4,5;

 

3 метод. Матрица А имеет размер m x n, не имеет седловой точки и не может быть решена графически. Тогда задача теории игр сводится к задаче линейного программирования, а именно к паре взаимодвойственных задач для 1-го и 2-го игрока соответственно.

Задача 1-го игрока: Задача 2-го игрока:

F=υ→max Ф=U→min

y_j≥0

x_i≥0

 

От этих задач переходят к вспомогательным задачам, рассматривая переменные

 

I игрока II игрока

 

Примечание: При составлении ЗЛП важно, что все элементы матрицы a_ij≥0, если это не так, то рассматриваем матрицу:

, где , υ^/=υ+С.

Решив вспомогательные задачи 1-го и 2-го игрока, найдем оптимальные стратегии и основных задач.

 

Заметим, что при реализации симплекс-метода целесообразно сразу составлять задачу 2-го игрока.

Пример:

Составляем вспомогательную задачу 2-го игрока.

 

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

Базис	B
Оценки		-1	-1	-1

 

В результате решения получим конечную симплекс-таблицу вида:

Базис	B
	1/2				1/2
	1/2				-1/2
Оценки	3/2	1/2			1/2

 

Решение вспомогательной задачи 1-го игрока, т.е. решение двойственной задачи для задачи 2-го

 

→