2. Теоремы теории игр.

Теорема 1. Всякая конечная игра имеет цену, и у каждого игрока

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

(основная теорема теории игр)

Терема 2. Нижняя цена игры всегда не превосходит верхней цены игры, .

Рассмотрим два случая.

1. Пусть .

Игра, для которой, , называется игрой с седловой точкой. Если , то С является ценой игры, а стратегии игроков, обеспечивающие им выигрыш или проигрыш, равный С, являются опти­мальными. Если игра с седловой точкой имеет С = 0, то она является справедливой, если С0, - несправедливой.

2. Пусть. В этом случае трудно определить цену игры и оптимальные стратегии игроков. Вернемся к рассмотренному приме­ру.= 3, а= 5. Значит, первый игрок может гарантировать себе выигрыш, равный 3, а второй - ограничить свой проигрыш 5. Область междуиявляется, как бы, ничейной, и каждый игрок может попы­таться улучшить свой результат за счет этой области. Каковы в этом случае оптимальные стратегии игроков? Если каждый игрок будет при­менять стратегию, соответствующую его максимальному гарантированному выигрышу или проигрышу, противник может догадаться о его намерениях и улучшить свой результат. Например, первый игрок использует х₃, а второй - y₂. Второй игрок заметил, что первый все время применяет x₃, и решил применить y₁, сведя свой проигрыш к меньшему числу. Таким образом, чтобы иметь успех, каждый игрок должен хранить свой выбор в секрете. Это трудно сделать, если игра повторяется многократно.

Секретность можно сохранить, если каждый раз выбирать страте­гию случайным образом (бросая монету, кость и т.п.). При этом вы­игрыш и проигрыш будут случайными величинами. Результат можно оце­нить средней величиной проигрыша или выигрыша. Так, в нашем случае, если второй игрок использует свои стратегии y₁, y₂, y₃случайным образом, например, с вероятностями 1/3; 1/3; 1/3, соответственно, то среднее значение его проигрыша может быть:

- если первый использует х₁:

С_ср= 1/3 а₁₁+ 1/3 а₁₂ + 1/3 а₁₃= 7/3 + 2/3 + 5/3 = 14/3;

- если первый использует х₂:

С_ср = 1/3 а₂₁ + 1/3 а₂₂ + 1/3 а₂₃= 2/3 + 2/3 + 3/3 = 7/3;

- если первый использует х₃:

С_ср = 1/3 а₃₁ + 1/3 а₃₂ + 1/3 а₃₃= 3/3 + 5/3 + 4/3 = 4.

Таким образом, второй игрок может ограничить свой проигрыш уже не 5, а 14/3, независимо от стратегии первого игрока. Следователь­но, в ряде случаев оказывается целесообразным не намечать заранее стратегии, а выбирать ту или иную случайным образом. Стратегия, основанная на случайном выборе, называется смешанной стратегией.

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

Пусть u=(u₁,...,u_m)иz=(z₁,...,z_n), соответственно, вероятности отдельных исходов механизма случайного выбора 1-го и 2-го игроков.

Из теории вероятностей должно быть известно, что

1) u_i 0,i=;z_j 0,j=; (т.к. 0р 1);

2) и (т.к. р(U) = 1, U- достоверное событие).

Если u^*- оптимальная стратегия 1-го игрока, z^*- оптималь­ная стратегия 2-го игрока, то числоявляется ценой игры.

Определение оптимальных стратегий и цены игры составляет процесс решения игры.

Теорема 3.Всякая матричная игра с нулевой суммой имеет решение в смешанных стратегиях. Для того, чтобы число С было ценой игры, а u^* и z^* - оптимальными стратегиями игроков, необ­ходимо и достаточно выполнения неравенств:

и.

Теорема о цене игры дает ответ на вопрос о существовании решения игры и определяет путь решения.

В частном случае, когда, по крайней мере, у одного из игроков имеется только 2 стратегии, справедлива теорема.

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

3. Способы решения задач теории игр.

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

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

Решение

Чтобы решить игру необходимо определить цену игры и оптимальные смешанные стратегии игроков.

1.

Другой способ решения игр ,,основан на геометрической интерпретации игры.

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

Решение

Если первые два способа имеют ограничения на использование, то следующий способ решения не имеет этого недостатка. Способ решения представляет сведение задачи теории игр к ЗЛП (теорема 3).

Пусть игра имеет матрицу . Согласно теореме 3:

и

Пусть для определённости С > 0. Разделим все неравенства на С.

и

Обозначим ,, при этом,,,.

и

Кроме того, так как и , тои . Так как первый игрок стремится получитьmaxвыигрыш, то, а, и. Второй игрок стремится получить минимальный проигрыш, поэтому.

Имеем пару двойственных задач линейного программирования.

Пример. Решить игру, заданную матрицей .

№	Б.п.	y1	y2	y3	y4	y5	y6	b
0	y5*	3	2	5	7	1	0	1
	y6	1	4	3	2	0	1	1
	Z	-1*	-1	-1	-1	0	0	0
1	y1	1	2/3			1/3	0	1/3
	y6*	0	10/3			-1/3	1	2/3
	Z	0	-1/3*	2/3	4/3	1/3	0
2	y1	1	0			2/5	-1/5	1/5
	y2	0	1			-1/10	3/10	1/5
	Z	0	0	4/5	13/10	3/10	1/10	-2/5

, , .

,

, .

Ответ: , , .