Матричные игры 2×n

Матричные игры 2×n Рассмотрим многоразовую игру с матрицей выигрышей . В такой игре игрок A имеет две стратегии A1 и A2, а игрок B – n стратегий B1, B2,…, Bn. Пусть смешанные стратегии игроков A и B имеют вид . Предполагаем, что седловая точка в игре отсутствует. Имеем где . Для нахождения используем графический метод. Для этого в плоскости построим прямые : , . Здесь – независимая переменная, а – переменная, зависящая от . Далее построим ломаную , огибающую снизу все эти прямые для . Тогда ордината y верхней точки ломаной L даст значение , в которой и достигается . Это значение и будет ценой игры. В качестве примера рассмотрим случай . Построим три прямые: и их нижнюю огибающую (рис. 1). Из рисунка находим точку , которая и будет являться решением игры. Найдем теперь оптимальную стратегию игрока B. Для этого снова используем теорему об активных стратегиях. При нахождении оптимальной стратегии игрока B необходимо учитывать как расположение точки на плоскости, так и ее единственность (или неединственность). Рассмотрим возможные варианты. 1. Точка единственна. В этом случае точка максимума огибающей L является точкой пересечения двух прямых. Например, на рисунке 1 такими прямыми являются прямые и , которые соответствуют первому и второму столбцу матрицы выигрышей . По теореме об активных стратегиях активными будут только стратегии B1 и B2, а их вероятности войдут в уравнение для нахождения оптимальной смешанной стратегий игрока B. 2. Точка не является единственной, то есть нижняя огибающая L содержит целый горизонтальный участок, например, как на рис. 2. Тогда для игрока B оптимальной является стратегия соответствующая прямой , а для игрока A существует бесконечно много оптимальных смешанных стратегий, в которых вероятности находятся между значениями и (см. рис. 2). Доминирующие и доминируемые стратегии Иногда платежная матрица , , имеет такую структуру, что игра может быть упрощена отбрасыванием в этой матрице некоторых строк (столбцов). Рассмотрим матричную игру двух игроков A и B. Пусть игрок A имеет стратегии A1, A2,…, Am, а игрок у игрока B имеются стратегии B1, B2,…, Bn. Определение. Будем говорить, что стратегия Ai доминирует стратегию Ak (стратегия Ak доминируется стратегией Ai), если для элементов платёжной матрицы C выполняются неравенства то есть элементы k-й строки матрицы C не превосходят соответствующих элементов ее i-й строки и хотя бы для одного значения j неравенство является строгим. Будем говорить, что стратегия Bj доминирует стратегию Bl (стратегия Bl доминируется стратегией Bj), если то есть элементы j-го столбца матрицы C не превосходят соответствующих элементов ее l-го столбца и хотя бы для одного значения i неравенство является строгим. Справедливо следующее очевидное утверждение. Утверждение 1. Если платежная матрица C имеет доминируемые стратегии (строки или столбцы), то оптимальное решение такой игры совпадает с оптимальным решением игры с платежной матрицей C*, полученной из матрицы C отбрасыванием доминируемых строк (столбцов). Замечание. 1. При отбрасывании доминируемых строк (столбцов) размер матрицы C уменьшается. Этот процесс упрощения игры можно продолжать до тех пор, пока не останется доминируемых стратегий. 2. Если платежная матрица содержит несколько одинаковых строк (столбцов), то оставляют только одну из таких строк (столбцов), а остальные отбрасывают. Утверждение 2. Если элементы двух платежных матриц и , где , , связаны соотношениями где , γ – произвольное число, то оптимальные стратегии этих игр совпадают, а цены игр связаны равенством (1) Будем искать оптимальные смешанные стратегии и игроков A и B. Для решения используем графический метод. Построим прямые: и нижнюю огибающую (рис. 3). Из рис. 3 видно, что оптимальная точка – это точка пересечения прямых и , то есть она определяется из системы Решив систему, получим , , . Таким образом, оптимальная стратегия игрока A имеет вид . Теперь найдем цену игры D. Заметим, что элементы матриц C и D связаны соотношением: , , . Тогда по формуле (1) находим цену второй игры: Применение методов линейного программирования при решении матричных игр Рассмотрим игру двух лиц с платежной матрицей (матрицей выигрышей игрока A) , , . Не ограничивая общности, можем считать, что матрица C положительна. В противном случае к элементам матрицы C следует добавить одно и то же положительное число, применяя утверждение 2. Пусть смешанная стратегия игрока A имеет вид Тогда средний выигрыш игрока A при использовании игроком B чистой стратегии Bj составит . Обозначим через минимальный средний выигрыш игрока A при любой чистой стратегии игрока B, т. е . Тогда выполняются неравенства (2) Введем новые переменные и перепишем неравенства (2) в виде (3) Задача игрока A – максимизировать свой выигрыш, то есть . Введем в рассмотрение функцию , где . В силу (3) . Следовательно, функцию надо минимизировать. Таким образом, приходим к следующей задаче линейного программирования. Найти минимум функции (4) при следующих ограничениях (5) Рассмотрим теперь игру игрока B. Его смешанная стратегия обеспечит ему средний проигрыш, не больший чем , при любой чистой стратегии игрока A, то есть (6) Вводя новые переменные преобразуем систему (6) к виду (7) Рассмотрим функцию , где . В силу (7) . Так как для игрока B его проигрыш надо минимизировать, то функцию надо, напротив, максимизировать. Приходим к задаче линейного программирования: найти максимум функции (8) при следующих ограничениях (9) Из курса линейного программирования известно, что задачи (4)–(5) и (8)–(9) представляют собой пару двойственных задач и эти задачи имеют оптимальные решения и . Таким образом, приходим к следующему результату. Теорема 1. Решение матричной игры с положительной матрицей выигрышей , , , равносильно решению двойственных задач линейного программирования (4)–(5), (8) – (9). При этом цена игры удовлетворяет равенству а оптимальные вероятности и определяются формулами , . Алгоритм решения матричной игры с помощью решения двойственных задач линейного программирования следующий. 1. Ко всем элементам платежной матрицы C прибавим одно и то же положительное число γ так, чтобы все ее элементы стали положительными. 2. Составим пару двойственных задач линейного программирования (4)–(5) и (8)–(9) и найдем их решения , . В качестве контроля правильности решения задач можно использовать равенство 3. Построим оптимальные смешанные стратегии игроков: , , , . (10) 4. Вычислим цену игры: (11)