Решение игры в смешанных стратегиях. Теорема фон Неймана

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

Решение игры связано с матрицей (а_ij) и следующими понятиями:

Нижняя цена игры α=maxmin а_ij (сначала находится минимум в каждой строке, а

I j

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

Верхняя цена игры β=minmax а_ij (сначала находится максимум в каждом столбце,

J i

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

Очевидно α<= β. В случае α=β говорят о цене игры ν=α=β. Соответствующие цене игры стратегии являются оптимальными, а сама игра есть игра с седловой точкой.

В случае, когда α<β седловой точки не существует. В этом случаерешение игры ищестся в смешанных стратегиях. Доказано (Дж. Фон Нейман), что конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно в смешанных стратегиях.

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

Для игрока А это Р=(р₁,….р_m), а для игрока В – это Q=(q₁,…….,q_n), при этом

Σ pi=1 и Σ q_j=1, средний выигрыш игрока А равен Н_А(Р,Q)=Σ Σ а_ij pi q_j

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

Оптимальными смешанными стратегиями Р⁰ и Q⁰ называются стратегии, если выполняется неравенство:

Н_А(Р,Q⁰)=< Н_А(Р⁰,Q⁰)=< Н_А(Р⁰,Q)

В этом случае Н_А(Р⁰,Q⁰) называется ценой игры и обозначается α=<ν=< β

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

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

Решение матричных игр МхN (сведение к задаче линейного программирования).

Матричной игрой называется парная игра, осуществляемая по следующим

правилам:

1. В игре участвуют два игрока - А и В;

2. Каждый из игроков обладает конечным набором стратегий (для игрока А - это стратегии А₁, А₂, …..А_m, а для игрока В - это стратегии В₁,В₂,…….В_n);

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

6. И выигрыш, и проигрыш выражаются числами а_ij,которые являютсяэлементами, так называемой платежной матрицы. В частности, выигрыш для игрока А при выборе стратегии А_i, и игроком В – стратегии В_j равен а_ij, а для игрока В – он равен в_ij =-а_ij, то есть является проигрышем.

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

Если условие в_ij =-а_ij не выполняется, то есть каждый из игроков имеет свою платежную матрице, тогдаэтапарная игра является игрой с ненулевой суммой и называется биматричной игрой.

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

Решение игры связано с матрицей (а_ij) и следующими понятиями:

Нижняя цена игры α=max_imin_j а_ij (сначала находится минимум в каждой строке, а

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

Верхняя цена игры β=min_imax_j а_ij (сначала находится максимум в каждом столбце,

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

Сведение матричной игры к задаче линейного программирования

Из свойств оптимальных смешанных стратегий игроков вытекает, что при любой стратегии игрока В для игрока А имеет место неравенство:

Σ а_ij p_i>= ν

Обозначая далее

x_i= p_i/ ν

исходное неравенство можно переписать следующим образом

Σ а_ij х_i>=1 и Σ х_i>=1/ν

^{i i}

Поскольку игрок А стремиться максимально увеличить свой гарантированный выигрыш, то задача отыскания решения матричной игры сводится к следующей задаче линейного программирования:

Σ х_i → min

Σ а_ij х_i>=1

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

y_i= q_i/ ν

и учитывая, что Σ а_ij y_i<=1 получаем двойственную по отношению к рассмотренной следующую задачу линейного программирования:

Σ y_i → max, Σ а_ij