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

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

(4.2.1)

Смешанные стратегии и, удовлетворяющие равенству (4.2.1) называютоптимальными (они образуютситуацию равновесия), а величинуγ―средний результат игры при использовании оптимальных смешанных стратегий называютценой игры.

Если оба игрока используют свои оптимальные смешанные стратегии, то

(4.2.2)

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

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

В частности, средний выигрыш игрока 1 (средний проигрыш игрока2) остается неизменным и равным цене игрыγпри использовании игроком2(игроком1) любой чистой стратегии.

Докажем это для игры m×n. Пустьрешение игры,. Обозначимγ₁, γ₂,…, γ_nвыигрыши игрока1при использовании игроком 2чистых стратегий y₁,y₂,…,y_n.

Из определения оптимальной стратегии следует, что любое отклонение игрока 2от стратегиине может быть ему выгодно, поэтому его проигрышиγ₁ ≥γ,γ₂ ≥γ,…,γ_n ≥γ. Но возможно ли это? Поскольку в стратегиичистые стратегии y₁,y₂,…,y_nприменяются с частотами q₁,q₂,…,q_n, то средний проигрыш игрока B(цена игры)

(4.2.3)

Очевидно, что если хотя бы одна из величин γ₁,γ₂,…,γ_nбольшеγ, то есть равнаγ+∆γ, а другие равныγ, то это противоречит системе (4.2.3). Таким образом, доказано свойство оптимальных смешанных стратегий.

Итак, все сказанное справедливо, если игровая ситуация повторяется многократно в сходных условиях и осреднение результатов игр допустимо; каждый игрок не имеет информации о конкретном, хотя и случайном выборе стратегии другим игроком. Если же игрок 2информирован о действиях игрока1, то есть знает его конкретную стратегиюx_iв каждом повторении игры, то средний выигрыш игрока1при использовании им смешанной стратегии может оказаться меньше гарантированной при максиминной чистой стратегии нижней цены игры α. В этом случае игрок 2наказывает игрока1за отклонение от максиминной чистой стратегии.

Лекция 5 методы решения Матричных игр в смешанных стратегиях

5.1. Решение матричной игры

Решением игры называют также нахождение оптимальных смешанных стратегий и цены игры.

Рассмотрим простейшую игру 2×2.

	y1	y2
x1	a11	a12
x2	a21	a22

Здесь возможны 2 варианта.

Если игра имеет седловую точку, то решение игры―две чистые стратегии (максиминная для игрока 1и минимаксная для игрока 2), которые ее содержат.

Если игра не имеет седловой точки, то решение игры―две оптимальные смешанные стратегии и.

Найдем оптимальную смешанную стратегию игрока 1

(5.1.1)

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

(5.1.2)

Отсюда

(5.1.3)

(5.1.4)

(5.1.5)

(5.1.6)

(5.1.7)

Найдем теперь оптимальную смешанную стратегию игрока 2

(5.1.8)

Для этого достаточно уравнений

(5.1.9)

Отсюда

(5.1.10)

Решению игры 2×2 можно дать геометрическую интерпретацию. Средний выигрыш игрока1при стратегии y₁равен. Нижняя граница выигрыша показана пунктиром, ее максимум ― цена игры и ее

решение.