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

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

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

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

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

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

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

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

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

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

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