Игра в смешанных стратегиях

Если платежная матрица не имеет седловой точки, то цена игры V определяется условием (1) §2, т.е. первый игрок обеспечит выигрыш не меньше α, а второй игрок обеспечит проигрыш не больше β. Так как α<β, то первый игрок стремится увеличить выигрыш, а второй – уменьшить проигрыш.

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

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

Теорема 2. (Дж. фон Неймана.Основная теорема теории игр) Каждая конечная матричная игра имеет, по крайней мере, оптимальное решение в смешанных стратегиях.

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

Смешанные стратегии для соответствующих игроков 1 и 2 будут и :

(3)

(4)

где и – чистые стратегии игроков

(5)

Вероятности применения соответствующих стратегий игроками 1 и 2

(6)

Зная платежную матрицу A можно определить средний выигрыш (математическое ожидание):

M(A,X,Y)= (7)

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

Рассмотрим конечную игру, матрица которой имеет размер 2х2

(8)

Определить оптимальные стратегии первого и второго игроков и соответствующие им вероятности для матрицы (8), т.е.

(9)

Для игрока 1 получаем систему уравнений:

(10)

Для игрока 2 система имеет вид:

(11)

Если V≠0 и игроки имеют только оптимальные смешанные стратегии, то определитель матрицы A не равен нулю. Следовательно системы (10) и (11) имеют единственные решения.

Решая системы уравнений (10) и (11) находим вероятности X и Y в следующем виде:

(12)

При решении игровых задач платежные матрицы в большинстве случаев имеют размерность mхn, в которой m˃2 и n˃2, т.е. исходная матрица является сложной. Размерность матрицы можно сократить, исключаяв них дублирующие и заведомо не выгодные доминирующие стратегии игроков.

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

Первому игроку не выгодно применять стратегии, которым соответствуют доминируемые строки, а игроку 2 не выгодно применять стратегии, которым соответствуют доминирующие столбцы.

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

Теорема 3. Если x’,y’,v’являются решением платежной матрицы A, то решением игры с платежной матрицей является тройка чисел x’;y’;kv’+b;k≥0, где b – любое действительное число.