Методы и модели игры

 

Пример 7. Рассмотрим игру с матрицей

.

Сравнивая строки матрицы, видим, что 1-я строка совпадает с 4-й строкой, или, что то же, стратегия А₄ дублирует стратегию А₁. Тем самым, одну из этих, строк можно вычеркнуть, не нанося ущерба решению

.

Поэлементна сравнивая 1-ю и 2-ю строки, замечаем, что 1-я строка доминирует 2-ю строку, или, что то же, стратегия А₁ доминирует стратегию А₂. Это вновь позволяет уменьшить число строк матрицы

Замечая, что 4-й столбец  полученной матрицы доминирует ее 3-й  столбец, приходим к игре с 2 х 3-матрицей

Решая эту 2 х 3 игру графическим методом, находим ее решение – цену игры и оптимальные смешанные стратегии игроков А и В:

.

Возвращаясь к исходной 4 x 4 игре, получаем окончательный ответ:

 

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

 

Аффинное правило

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

Допустимые преобразования матрицы игры и ее цена. Оптимальные стратегии у матричных игр, элементы матриц А и С которых связаны равенствами

с_ik = λа_ik + μ,    i = 1, 2, ... , m;    k = l, 2, ... , n,

 где λ > 0, a μ – произвольно, имеют одинаковые равновесные ситуации (либо в чистых  
либо в смешанных стратегиях), а их цены удовлетворяют следующему условию

.

 

Пример 8. Элементы матриц

 и 

связаны равенством

с_ik = 3а_ik + 5,      i= 1, 2;      k = 1, 2, 3.

Поэтому цена игры с матрицей С  легко вычисляется

(см. пример 7).

 

 

Основные этапы поиска решения  матричной игры

 

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

2-й этап – поиск доминирующих стратегий (в случае успеха этого поиска – отбрасывание доминируемых строк и столбцов в исходной матрице игры).

3-й этап – замена игры на ее смешанное расширение и отыскание оптимальных  смешанных стратегий и цены игры.

 Итерационный метод решения матричных игр

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

Проиллюстрируем этот метод на примере  игры, заданной матрицей

(здесь maxmin = 0, minmax = 2 → седловой  точки нет).

Опишем правила выбора ходов игроками, предположив, для определенности, что начинает игрок А:

ход игрока А — стратегия А₁ — (2   0   3);

игрок В выбирает свою стратегию так, чтобы выигрыш игрока А был минимален (отмечен полужирным шрифтом)

ход игрока В — стратегия В₂ —

игрок А выбирает свою стратегию так, чтобы его выигрыш при стратегии B₂ игрока В был максимален (отмечен полужирным шрифтом):

ход игрока А — стратегия А₂ — (1   3 - 3);

игрок В выбирает свою стратегию так, чтобы «накопленный» выигрыш игрока А при стратегиях А₁ и А₂,

(2   0   3) + (1   3  -3) = (3   3   0),

был минимален:

ход игрока В — стратегия В₃ —

;

игрок А выбирает свою стратегию так, чтобы его «накопленный» выигрыш при стратегиях B₂ и B₁ игрока В,

был максимален:

ход игрока А — стратегия А₁ — (2   0   3);

игрок В выбирает свою стратегию так, чтобы «накопленный» выигрыш игрока А при стратегиях A₁, A₂ и A₁,

(3   3   0) + (2   0   3) = (5   3   3),

был минимален:

ход игрока В — стратегия B₂ —

и т.д.

Разобьем последовательные ходы игроков А и В на пары

(ход игрока А, ход игрока В)

и запишем результаты в таблице

n	i	B1	B2	B3	ν*(n)	k	A1	A2	ν*(n)	ν(n)
1	1	2	0	3	0,00	2	0	3	3,00	1,50
2	2	3	3	0	0,00	3	3	0	1,50	0,75
3	1	5	3	3	1,00	2	3	3	1,00	1,00
4	1	7	3	6	0,75	2	3	6	1,50	1,12
5	2	8	6	3	0,60	3	6	3	1,20	0,90
6	1	10	6	6	1,00	2	6	6	1,00	1,00
7	1	12	6	9	0,86	2	6	9	1,44	1,15
8	2	13	9	6	0,75	3	9	6	1,13	0,93
9	1	15	9	9	1,00	2	9	9	1,00	1,00
10	1	17	9	12	0,90	2	9	12	1,20	1,05
11	2	18	12	9	0,82	3	12	9	1,09	0,96
12	1	20	12	12	1,00	2	12	12	1,00	1,00
…………………………………………………………………………………………………..

требующей некоторых пояснений.

 

Описание таблицы

1-й столбец	номер n шага (пары последовательных ходов игроков А и В)
2-й столбец	номер i стратегии, выбранной игроком А
3-й столбец	«накопленный» суммарный выигрыш  игрока А за первые n шагов при стратегии В1 игрока В	Минимальный из этих выигрышей выделяется полужирным шрифтом
4-й столбец	«накопленный» суммарный выигрыш  игрока А за первые n шагов при стратегии В2 игрока В
5-й столбец	«накопленный» суммарный выигрыш  игрока А за первые n шагов при стратегии В3 игрока В
6-й столбец	минимальный средний выигрыш игрока А, равный, минимальному накопленному им выигрышу за первые n шагов, деленному на число этих шагов
7-й столбец	номер k стратегии, выбранной игроком В
8-й столбец	«накопленный» суммарный выигрыш игрока А за первые n шагов при стратегии А1	Максимальный из этих выигрышей выделяется полужирным шрифтом
9-й столбец	«накопленный» суммарный выигрыш  игрока А за первые n шагов при стратегии А2
10-й столбец	максимальный средний выигрыш  игрока А, равный максимальному накопленному им выигрышу за первые n шагов, деленному на число этих шагов
11-й столбец	среднее арифметическое минимального среднего выигрыша и максимального  среднего выигрыша игрока A

 

Решение игры определяется приближенно  по окончании любого из шагов.

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

После 9-го шага имеем

ν(9) = l,00.

При этом игрок А 6 раз использовал стратегию А₁ и 3 раза стратегию А₂. В свое очередь игрок B 6 раз применял стратегию В₂, 3 раза стратегию В₃, а стратегией В₁ не пользовался вообще. Отсюда получаем, что

,  

Соответственно, после 10-го шага получаем —

.

Данная игра легко решается графически. Вот точный ответ:

.

Сравнивая результаты, полученные на 9-м, 10-м, а также 11-м и 12-м шагах:

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

 

Сделаем несколько замечаний.

 

Замечание 1. При увеличении числа шагов все три величины v_*(n), v*(n) и v(n) будут приближаться к цене игры v, но среднее арифметическое v(n) будет приближаться к v сравнительно быстрее.

Замечание 2. Хотя сходимость итераций весьма медленна, тем не менее, даже такой небольшой расчет всегда дает возможность находить ориентировочное значение цены игры и доли чистых стратегий.

Замечание 3. Сравнительно медленная скорость сходимости можно объяснить целым рядом причин. Укажем одну из них, психологически наиболее интересную. Если, к примеру, игрок А уже получил оптимальную смешанную стратегию, то он не склонен останавливаться на ней.  Отнюдь нет — он продолжит попытки выиграть у противника В побольше, особенно если последний еще не достиг оптимальной смешанной стратегии. Тем самым, игрок А может невольно ухудшить свое положение.

Замечание 4. Отметим два основных преимущества описанного метода:

1) итерационный метод прост и одновременно универсален (при его помощи можно легко найти приближенное решение любой матричной игры),

2) объем и сложность вычислений  сравнительно слабо растут по  мере увеличения числа стратегий  игроков (размеров матрицы игры).

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

 

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

A = (a_ik).

Без ограничения общности будем  считать, что все элементы матрицы А положительны (этого всегда можно добиться, пользуясь аффинным правилом, преобразующим заданную матрицу игры, но не изменяющим оптимальных смешанных стратегий игроков). Тем самым, искомая цена игры v — положительное число.

 

Интересы игрока А

Из теоремы о свойствах оптимальных  смешанных стратегий игроков  вытекает, что при любой чистой стратегии В_k игрока В, k = 1, 2, ... , n, оптимальная смешанная стратегия Р = {p₁, p₂, … , p_m} игрока А обеспечивает его средний выигрыш, не меньший v. Иными словами, выполняются соотношения

которые с учетом обозначений

можно записать так

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

найти неотрицательные величины х₁, x₂, ... , х_m, удовлетворяющие неравенствам

и такие, что их сумма минимальна

.

Интересы игрока B

Аналогичным образом заключаем, что  оптимальная смешанная стратегия Q = {q₁, q₂, … , q_n} игрока В при любой чистой Стратегии А₁ игрока A, i = 1, 2,... , m, обеспечивает его средний проигрыш, не больший v. Иными словами, выполняются соотношения

которые с учетом обозначений

можно записать так

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

найти неотрицательные  величины у₁,у₂, ... , у_n, удовлетворяющие неравенствам

и такие, что их сумма максимальна

Тем самым, мы получаем следующий важный результат.

Теорема 3. Решение матричной игры с положительной платежной матрицей (а_ik) равносильно решению двойственных задач линейного программирования

(A)                ,     

(B)                ,    

При этом цена игры

,

где Θ — величина, обратная общему значению оптимальных сумм,

а оптимальные значения и связаны с оптимальными и посредством равенств

 

Алгоритм решения матричной  игры

1-й шаг. Ко всем элементам исходной матрицы игры прибавляется одно и то же положительное число γ так, чтобы все элементы новой матрицы были строго положительны.

2-й шаг. Решаются двойственные задачи линейного программирования (А) и (В) (например, симплекс-методом, или как-нибудь иначе). Находятся наборы , и число Θ.

3-й шаг. Строятся оптимальные смешанные стратегии игроков А и В соответственно

4-й шаг. Вычисляется цена игры

 

Пример 9. Рассмотрим 2 x 2 игру с матрицей

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