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

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

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

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

I j

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

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

J i

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

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

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

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

Для игрока А это Р=(р1,….рm), а для игрока В – это Q=(q1,…….,qn), при этом

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

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

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

НА(Р,Q0)=< НА(Р0,Q0)=< НА(Р0,Q)

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

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

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

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

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

правилам:

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

2. Каждый из игроков обладает конечным набором стратегий (для игрока А — это стратегии А1, А2, …… Аm, а для игрока В — это стратегии В1, В2,…….Вn);

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

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

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

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

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

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

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

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

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

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

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

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

Σ аij pi>= ν

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

xi= pi/ ν

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

Σ аij хi>=1и Σ хi>=1/ν

ii

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

Σ хi→ min

Σ аij хi>=1

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

yi= qi/ ν

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

Σ yi→ max, Σ аij