МАТРИЧНЫЕ ИГРЫ ОСНОВНЫЕ ПОНЯТИЯ Игра – упрощенная модель конфликта, имеющая четкие правила: варианты действий игроков, объем информации о действиях противника, выигрыш (исход конфликта), к которому приводит совокупность действий игроков. Игроки – стороны, участвующие в игре: 2 игрока – парная игра, более 2 – множественная игра (рассматриваются парные игры). Игра с нулевой суммой (антагонистическая игра) – выигрыш одного из игроков равен проигрышу другого. Стратегия игрока – совокупность правил, определяющих действия игрока при каждом личном ходе в зависимости от сложившейся ситуации. Решение антагонистической игры – выбор стратегий, удовлетворяющих условию оптимальности (игрок А должен получать максимальный выигрыш,когда игрок В придерживается своей стратегии, а игрок В должен получать минимальный проигрыш, когда игрок А придерживается своей стратегии). Устойчивость оптимальных стратегий – ни одному из игроков не выгодно отклоняться от своей оптимальной стратегии. Игра с полной информацией – перед каждым ходом каждый игрок знает все предшествующие ходы и выигрыши. Кооперативная игра – допускается возможность предварительных переговоров между игроками (рассматриваются некооперативные игры). МАТРИЦА ИГРЫ (платежная матрица) Пусть у игрока есть возможных ходов (стратегий) , а у игрокаестьвозможных ходов (стратегий). Если игроксделает ход, а игроксделает ход, то эти ходы однозначно определяют исходы игрыдля игрокаидля игрока. Эти числа записывают в виде платежных матриц
(Стратегии игрока указаны по строкам, стратегии игрока– по столбцам ) Биматричная игра – у каждого из игроков своя платежная матрица. Матричная игра – интересы игроков противоположны (выигрыш игрока является и проигрышем игрока), т.е.. В этом случае можно ограничиться одной матрицей – матрицей игрока . СЕДЛОВАЯ ТОЧКА МАТРИЦЫ ИГРЫ Нижняя цена игры(гарантированный выигрыш игрока А при любой стратегии игрока В). Верхняя цена игры(гарантированный проигрыш игрока В при любой стратегии игрока А). Очевидно, что . Если, то говорят оцене игры . Соответствующие цене игры стратегии – оптимальные чистые стратегии, а сама игра – игра с седловой точкой.
Если седловой точки не существует. СМЕШАННЫЕ СТРАТЕГИИ – применение своих чистых стратегий с частотами, задаваемыми векторами и соответственно. Средний выигрыш игрока :. Оптимальные смешанные стратегии и, если(отклонение любого из игроков от своей оптимальной смешанной стратегии риводит в уменьшению его среднего выигрыша). ТЕОРЕМА (Дж.ф. Нейман): Каждая конечная матричная игра имеет, по крайней мере, одно оптимальное решение, возможно, среди смешанных стратегий. |
ПРИМЕРЫ
1. Пример игры Игроки А и В одновременно и независимо друг от друга записывают натуральные числа.Если их сумма четна, то единицу выигрывает игрок А (игрок В проигрывает единицу), если нечетна, то столько же выигрывает игрок В (игрок А единицу проигрывает). Матрица игры имеет вид:
B1 B2 A1 1 -1 A2 -1 1
– первая стратегия игрока (он записывает четное число) – вторая стратегия игрока (он записывает нечетное число) – первая стратегия игрока (он записывает четное число) – вторая стратегия игрока (он записывает нечетное число) 2. Седловая точка платежной матрицы.
B1 B2 B3
A1 4 5 3 3 A2 6 7 4 4 A3 5 2 3 2
6 7 4
Нижняя цена игры Верхняя цена игры
Цена игры –оптимальная чистая стратегия игрока –оптимальная чистая стратегия игрока 3. Смешанные стратегии Для игры из 1.
q 1-q p 1 -1 1-p -1 1
–оптимальная смешанная стратегия игрока –оптимальная смешанная стратегия игрока
|
Теория игр матричные игры (продолжение)
ДУБЛИРОВАНИЕ И ДОМИНИРОВАНИЕ СТРАТЕГИЙ Дублирование стратегий – из одинаковых строк (столбцов) оставляем одну (один). Доминирование стратегий – если одна строка поэлементно больше либо равна другой, удаляем меньшую. Это же правило (со знаком ) применяем к столбцам.(Если игра имеет седловую точку, то после всех описанных преобразований получим игру). СВЕДЕНИЕ МАТРИЧНОЙ ИГРЫ К ЗАДАЧЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Р ассмотрим матричную игру с матрицей
Припишем строкам вероятности . Умножая этот вектор на столбцы матрицы, получаем выражения для среднего проигрыша игрока, который не превосходит цены игры:
Вводя новые переменные сумма которых равна, и учитывая, что игрокстремится понизить цену игры (минимизировать свой проигрыш), получаем (после деления каждого неравенства на)задачу линейного программирования (ЗЛП-I):
Аналогично,приписывая столбцам матрицы вероятности , получим(ЗЛП-II), двойственную к (ЗЛП-I):
Любую из этих задач можно решить одним из алгоритмов симплекс-метода, а затем, на основание теории двойственности, найти решение другой задачи. В частности при игре с матрицей или , одна из вышеприведенной пары двойственных задач будет содержать две переменные и может быть решена графическим способом. Затем, используя соотношения дополняющей нежесткости, решается другая задача.
|
ПРИМЕРЫ
4 .Дублирование и доминирование стратегий У простим игру. 4-я строка дублирует первую. Вторая строка доминирует над третьей. Оставшиеся две строки несравнимы
П олучим матрицу. Второй столбец доминирует над третьим. Оставшиеся строки и столбцы несравнимы. Таким образом, игру свели к игре
5. Графический способ решения игр и Игра : Приписав 1-й строке вероятность p, а 2-й – вероятность (1- p), получим n линейных сооношений, по графикам которых выберем их нижнюю огибающую. Максимум этой огибающей даст нам точку, координатами которой являются: значения вероятности p и цены игры v. Пусть эта точка является пересечением i-й и j-й прямых. Приписываем i-му столбцу вероятность q, а j-му столбцу – вероятность (1- q). Из получившейся системы уравнений находим q и (1- q).Найдем решение матричной игры:
Решая уравнения (1) и(3) получаем p =2/5, (1- p) =3/5 и v = w(2/5)= –2/5. Оптимальная стратегия игрока А: .Цена игры (выигрыш) – v = –2/5. Первому столбцу припишем ненулевую вероятность q, а третьему – (1- q). Второму столбцу будет соответствовать нулевая вероятность. Решая систему
находим q = 4/5 и (1- q) = 1/5. Оптимальная стратегия игрока В: . И гра : Решается аналогично с той лишь разницей, что сначала решается задача для игрока В в которой ищется минимум верхней огибающей. q =3/4, (1- q) =1/4 Ненулевые вероятности p и (1-p) припишем 1-й и 2-й строке. Решая полученную систему, находим p =5/8, (1- q) =3/8 Оптимальные стратегии: Игрок А – Игрок В – Цена игры – 7/4 |