Решение матричных игр в смешанных стратегиях

Однако не все матрицы имеют седловую точку. Тогда решение находят, применяя смешанные стратегии, то есть, чередуя случайным образом несколько чистых стра­тегий (гибкая тактика). Согласно основному неравенству теории игр нижняя цена игры никогда не может быть больше верхней цены игры, т.е. Решение матричных игр в смешанных стратегиях - student2.ru . Следовательно, если нижняя цена игры – это то, что игрок А согласен получить в результате игры, а верхняя цена игры – это то, что игрок В согласен отдать игроку А в процессе игры, тогда в случае отсутствия седловой точки Решение матричных игр в смешанных стратегиях - student2.ru возникает желание у обоих игроков рискнуть, чтобы получить больший выигрыш в игре.

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

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

Обычно смешанную стратегию первого игрока обо­значают как вектор

U = Решение матричных игр в смешанных стратегиях - student2.ru ,

где рi – вероятность выбора игроком А i-ой стратегии.

а второго игрока – как вектор

Z = Решение матричных игр в смешанных стратегиях - student2.ru ,

где qj, ≥ 0 – вероятность выбора игроком B j-ой стратегии

Решение матричных игр в смешанных стратегиях - student2.ru .

Если рo – оптимальная стратегия первого игрока, q° - оптимальная стратегия второго игрока, то число

Решение матричных игр в смешанных стратегиях - student2.ru - называют ценой игры.

Для того чтобы число υ – было ценой игры, а po и q° – оптимальными стратегиями, необходимо и до­статочно выполнение неравенств:

Решение матричных игр в смешанных стратегиях - student2.ru , где (j = 1,...,n),

Решение матричных игр в смешанных стратегиях - student2.ru , где (i = 1,...,m).

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

Пример. Найти решение игры, заданной матрицей Решение матричных игр в смешанных стратегиях - student2.ru .

Решение

Сначала, проверяется наличие седловой точки.

Таблица 3.

  В1 В2 Решение матричных игр в смешанных стратегиях - student2.ru
А1 А2 2(Т1) 4(Т2)
Решение матричных игр в смешанных стратегиях - student2.ru  

Для этого определяются минимальные элементы в каж­дой из строк (2 и 4) и максимальные элементы в каждом из столбцов (6 и 5) (Табл. 3).

Значит, нижняя цена игры

Решение матричных игр в смешанных стратегиях - student2.ru ,

верхняя цена игры

Решение матричных игр в смешанных стратегиях - student2.ru .

Так как α = 4 ≠ β = 5, то игра седловой точки не имеет и ее решение – смешан­ные оптимальные стратегии, а цена игры Решение матричных игр в смешанных стратегиях - student2.ru лежит в пределах 4≤ Решение матричных игр в смешанных стратегиях - student2.ru ≤5.

Пусть для игрока А стратегия задается вектором U = (p1, p2). Тогда при применении игроком В чистой стратегии В1 или В2 игрок А получит средний выигрыш, равный цене игры, то есть

Решение матричных игр в смешанных стратегиях - student2.ru

Из решения трех уравнений с тремя неизвестными оптимальная стратегия игрока А1: Решение матричных игр в смешанных стратегиях - student2.ru ; Решение матричных игр в смешанных стратегиях - student2.ru ; v = Решение матричных игр в смешанных стратегиях - student2.ru .

Пусть для игрока В стратегия задается вектором Z = (q1, q2). Тогда:

Решение матричных игр в смешанных стратегиях - student2.ru

Отсюда оптимальная стратегия игрока В: Решение матричных игр в смешанных стратегиях - student2.ru Следовательно, решением игры будут смешанные стратегии Решение матричных игр в смешанных стратегиях - student2.ru , Решение матричных игр в смешанных стратегиях - student2.ru с оценкой игры v = Решение матричных игр в смешанных стратегиях - student2.ru . Таким образом, если, например, имеется многоходовая игра, то из пяти партий игрок А два раза выбирает первую стратегию и три раза выбирает вторую стратегию, а игрок В один раз использует первую стратегию, и четыре раза – вторую стратегию. В этом случае выигрыш является оптимальным для двух сторон.

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

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

Решение матричных игр в смешанных стратегиях - student2.ru .

Для оптимальной стратегии первого игрока Решение матричных игр в смешанных стратегиях - student2.ru и цены игры Решение матричных игр в смешанных стратегиях - student2.ru выполняется неравенство:

Решение матричных игр в смешанных стратегиях - student2.ru , где (j = 1,...,n),

Разделив обе его части на Решение матричных игр в смешанных стратегиях - student2.ru получим:

Решение матричных игр в смешанных стратегиях - student2.ru 1.

Обозначив, Решение матричных игр в смешанных стратегиях - student2.ru получим:

Решение матричных игр в смешанных стратегиях - student2.ru

Так как первый игрок стремится получить макси­мальный выигрыш, то он должен обеспечить минимум величине 1/ Решение матричных игр в смешанных стратегиях - student2.ru . С учетом этого определение оптимальной стратегии первого игрока сводится к нахождению минимума функции:

Решение матричных игр в смешанных стратегиях - student2.ru

при условиях:

Решение матричных игр в смешанных стратегиях - student2.ru .

Аналогично определение оптимальной стратегии вто­рого игрока сводится к нахождению максимума функции:

Решение матричных игр в смешанных стратегиях - student2.ru

при условиях:

Решение матричных игр в смешанных стратегиях - student2.ru ,

где Решение матричных игр в смешанных стратегиях - student2.ru .

Таким образом, чтобы найти решение данной игры по матрице А, нужно составить следующую пару двой­ственных задач и найти их решение.

Прямая задача (задача второго игрока) Двойственная задача (задача первого игрока)
Целевая функция
Z(x) = x1 + x2 + … + xn → max U(y) = y1 + y2 + … + ym → min
Функциональные ограничения
а11х1 + а12х2 + … + а1nхn ≤ 1 a21х1 + а22х2 + … + а2nхn ≤ 1 … … … am1х1 + аm2х2 + … + аmnхn ≤ 1 а11у1 + а21у2 + … + аm1уm ≥ 1 а12у1 + а221у2 + … + аm2уm ≥ 1 … … … а1nу1 + а2nу2 + … + аmnуm ≥ 1
Прямые ограничения
x1 ≥0, x2 ≥0, … , xn≥0 y1 ≥0, y2 ≥0, … , ym≥0

Используя решения пары задач, можно выявить оп­тимальные стратегии и цену игры:

Решение матричных игр в смешанных стратегиях - student2.ru ; Решение матричных игр в смешанных стратегиях - student2.ru ; Решение матричных игр в смешанных стратегиях - student2.ru .

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

1) составляют пару двойственных задач, эквивалент­ных данной игре;

2) определяют оптимальные планы двойственных задач;

3) находят решение игры по соотношениям между планами задач, оптимальными стратегиями и ценой игры.

Замечание: Т.к. в задачах линейного программирования существует требование неотрицательности переменных, то для приведения матричной игры к задаче линейного программирования необходимо, чтобы элементы платежной матрицы были бы положительными Решение матричных игр в смешанных стратегиях - student2.ru . Если Решение матричных игр в смешанных стратегиях - student2.ru , то ко всем элементам платежной матрицы необходимо добавить некоторое число Решение матричных игр в смешанных стратегиях - student2.ru так, чтобы новые элементы платежной матрицы были бы положительны Решение матричных игр в смешанных стратегиях - student2.ru . Тогда после нахождения оптимального решения Решение матричных игр в смешанных стратегиях - student2.ru ; Решение матричных игр в смешанных стратегиях - student2.ru необходимо исправить цену игры: Решение матричных игр в смешанных стратегиях - student2.ru .

Наши рекомендации