Тема 3. Лекция 8. Антагонистические игры. Смешанные стратегии.

Теорема фон Неймана.

Пусть задана антагонистическая игра с платежной матрицей A (m, n) = (|a_ij|)

Определение. Смешанной стратегией игрока А называется дискретная случайная величина, принимающая значения 1,2,3,…m с определенной вероятностью; . смешанной стратегией игрока В называется дискретная случайная величина, принимающая значения 1,2,3,… n с определенной вероятностью.

					m
P1	P2				pm

P = (p₁, p₂ … p_m), p_i ≥ 0 , ∑p_i = 1. Q = (q₁, q₂ … q_n) (аналогично для Q).

Чистые стратегии игроков являются частными случаями смешанных, при этом

А1=(1,0,0,……0), А2=(0,1,0,……0) ….. Аm=(0,0,….0,1);

В1=(1,0,0,……0), В2=(0,1,0,……0) ….. Вn=(0,0,….0,1);

Тогда смешанные стратегии можно представить в виде

, Ai - базисные векторы

Проанализируем структуру множества смешанных стратегий. Пусть у игрока А есть две чистые стратегии.

- это множество называется одномерным симплексом.

Для трех чистых стратегий имеем 2-мерный симплекс смешанных стратегий – треугольник с вершинами (1,0,0), (0,1,0), (0,0,1) (концы векторов P принадлежат треугольнику) и т.д.

Определение. Пара (P, Q) – образует исход игры (или игровую ситуацию). В которой выигрыш игрока A, равный a_ij , достигается с вероятностью p_iq_j. H(P,Q) есть математическое ожидание выигрыша (средний выигрыш) при избранных стратегиях игроков - средний выигрыш A (проигрыш B) при (P,Q). В матричном виде:

Пример. Пусть задана платежная матрица и стратегии игроков:

, . Считаем векторы P, Q столбцами.

- нижняя цена игры.

Определение. - показатель эффективности стратегии P игрока A относительно смешанной стратегии Q игрока B. (S_B - множество смешанных стратегий игрока B.)

- показатель неэффективности стратегии Q игрока B.

Теорема. Показатели α и β достижимы.Т.е.

Доказательство:

Рассмотрим функцию α(P,S_B). Для фиксированной стратегии P H(P,Q) - есть функция одной векторной переменной Q на ограниченном замкнутом контуре.

Ограниченность:

, ∑q_i = 1, q_i≥ 0

Замкнутость.

Вспомним, что множество называется замкнутым, если оно содержит все свои предельные точки

. Если каждый элемент сходящейся числовой последовательности неотрицателен, то и ее предел (очевидно) также неотрицателен, т.е. Далее: . Это доказывает, что симплекс – замкнутое множество.

Теорема.

- множество чистых стратегий является подмножеством смешанных стратегий.

Верно для H(P, Q⁰) = α(P, S_B)

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

Верхней ценой игры в смешанных стратегиях называется величина:

Теорема.

где α, β - цены игры в чистых стратегиях.

Доказательство:

Докажем, что : Для произвольных стратегий P и Q имеем:

Определение. Если , то игра имеет цену в смешанных стратегиях => Максиминная и минимаксная стратегии тогда являются оптимальными.

Теорема. (Основная теорема антагонистических игр.) Для любой матричной игры существует решение в смешанных стратегиях ( , минимаксные стратегии оптимальны).

Без доказательства.

Тема 3. Лекция 9. Антагонистические игры.