15. Основные теоремы матричных игр

Теорема о максимине. В конечной игре двух игроков (коалиций) с нулевой суммой (матричной игре) при  имеет место равенство

. (2.9)

Теорема о максимине указывает на существование равновесия для случая v_А=v_B, при   и, следовательно, существования оптимальных смешанных стратегий.

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

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

Обе эти теоремы эквивалентны. Из этих теорем следует, что любая матричная игра имеет цену v. Цена игры v - средний выигрыш, приходящийся на одну партию, - всегда удовлетворяет условию

, (2.10)

т.е. лежит между нижней  и верхней  ценами игры.

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

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

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

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

Теорема об активных стратегиях. Если один из участников матричной игры G (mxn), придерживается своей оптимальной смешанной стратегии, то это обеспечивает ему максимальный средний выигрыш, равный цене игры , независимо от того, какие действия предпринимает другой игрок, если только он не выходит за пределы своих активных стратегий (т.е. пользуется любой из них в чистом виде или смешивает их в любых пропорциях), причем число активных стратегий каждого игрока, входящих в их оптимальные смешанные стратегии, не превосходит L, где L = min(m, n).

Использование данной теоремы позволяет в частности, упрощать решение матричных игр 2xn и mx2.

16. Понятие смешанной стратегией. Теорема Фон–Неймана

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

Смешанная стратегия игрока - это полный набор примене­ния его чистых стратегий при многократном повторении игры в одних и тех же условиях с заданными вероятностями.

Совокупность (комбинация) чистых стратегий A₁, A₂, …A_mи B_1, B_2, …B_n в сочетании с векторами вероятностей выбора каждой из них называются смешанными стратегиями.

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

Из этой теоремы следует, что не вполне определённая игра имеет хотя бы одно оптимальное решение в смешанных стратегиях. В таких играх решением будет пара оптимальных смешанных стратегий P^* и Q^*, таких, что если один из игроков придерживается своей оптимальной стратегии, то и другому игроку не выгодно отклоняться от своей оптимальной стратегии.

Средний выигрыш игрока A определяется математическим ожиданием:

Если вероятность (относительная частота) применения стратегии отлична от нуля, то такая стратегия называется активной.

Стратегии P^*, Q^* называются оптимальными смешанными стратегиями, если

M_A(P, Q^*) ≤ M_A(P^*, Q^*) ≤ M_A(P^*, Q) (1)

В этом случае M_A(P^*, Q^*) называется ценой игры и обозначается через V (V_* ≤ V ≤ V^*). Первое из неравенств (1)означает, что отклонение игрока A от своей оптимальной смешанной стратегии при условии, что игрок B придерживается своей оптимальной смешанной стратегии, приводит к уменьшению среднего выигрыша игрока A. Второе из неравенств означает, что отклонение игрока B от своей оптимальной смешанной стратегии при условии, что игрок A придерживается своей оптимальной смешанной стратегии, приводит к увеличению среднего проигрыша игрока B.