Нижняя и верхняя цены игры. Седловая точка

Пусть дана игра с помощью матрицы:

(3.1.4)

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

Определение 6. Нижней ценой игры называется число .

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

Определение 7. Верхней ценой игры называется число .

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

Пример 3.1.3.Пусть игра дана матрицей:

; ; (3.1.5)

Первый игрок выбирает осторожный ход и гарантирует себе выигрыш 0, а второй осторожный ход – и проигрыш 2. На самом деле, в случае осторожного поведения игроков, первый получит 2.

Нетрудно доказать, что .

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

Пример 3.1.4. Пусть игра дана матрицей:

; ;

В этой игре осторожная стратегия первого игрока - , второго игрока - .

Смешанные стратегии. Основная теорема теории игр

Рассмотрим случай, когда и розыгрыши проводятся многократно. Тогда для первого игрока возникает вопрос: можно ли каким-либо образом чередовать ходы таким образом, чтобы суммарный средний выигрыш был больше .

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

Определение 9. Вектор , , называется смешанной стратегией первого игрока ( означает вероятность (при бесконечном количестве розыгрышей), либо частоту (при конечном числе розыгрышей), с которой он выбирает свои ходы , i= ).

Определение 10. Вектор , , называется смешанной стратегией второго игрока ( означает вероятность либо частоту, с которой второй игрок выбирает свой ход , j= ).

Определение 11. Пусть – множество смешанных стратегий первого игрока, – множество смешанных стратегий второго игрока.

Определение 12: Пусть . Тогда, если , то ход A_i называется активным ходом, а, если , то он называется пассивным в для первого игрока. Аналогично, если и , то ход активный, а если , то этот ход пассивный в для второго игрока.

Замечание: Если в некоторой игре первый игрок все время выбирает ход A_i, то это соответствует смешанной стратегии . Аналогично, если второй игрок все время выбирает , то тогда . Тогда Ai и называют чистыми стратегиями игроков.

Теорема 4 (основная теорема теории игр). В любой матричной игре существует – оптимальная смешанная стратегия первого игрока и – оптимальная смешанная стратегия второго игрока такие, что: , , .

При этом называется ценой игры. .

Можно доказать, что .