Глава 3. Матричные игры
Постановка задачи.
2 игрока. Многократное повторение партий. Ходы выбирают одновременно из определенного для них набора ходов. Все, что выигрывает 1-й, проигрывает 2-й – игра с нулевой суммой. Вычисляются или задаются выигрыши 1-го игрока (они же проигрыши 2-го) при всевозможных сочетаниях ходов – они известны по условию задачи.
Пусть у 1-го m ходов s1, s2,…, sm, у 2-го n ходов t1, t2,…, tn. Если выбрана пара ходов si, tj, то ей соответствует выигрыш 1-го aij (выигрыш 2-го будет –aij). Выигрыши 1-го игрока образуют платежную матрицу А.
В общем случае вектор P(p1, p2,…, pm), который определяет частоты (вероятности) применения 1-м игроком своих ходов (åpi = 1, 0£ pi £1), называется вектором стратегии 1-го игрока. Q(q1, q2,…, qn) – вектор стратегии 2-го игрока (åqj = 1, 0£ qj£1).
Стратегия Р = (0,…, 1,…, 0) – чистая. Смешанная
Средний выигрыш 1-го игрока за одну игру (математическое ожидание)
- функция выигрыша.
Пусть даны P*, Q* и некоторое число v. Если для любых стратегий P и Q выполняется неравенство
E(P, Q*) £ v £ E(P*, Q), то стратегии P* и Q* называются оптимальными, а число v - ценой игры.
v = E(P*, Q*). Решение игры – 2 вектора оптимальных стратегий и цена игры.
Решение игры 2х2.
Аналитическое решение Р(х, 1 – х), Q(у, 1 – у).
Графическое решение (можно решать 2 x n и m x 2)
Основная теорема теории игр.
Теорема 1 (основная). Любая матричная игра имеет решение.
Лемма 1. Если ко всем элементам платежной матрицы добавить одно и то же число к (быть может, отрицательное), то оптимальные стратегии игроков не изменятся, а цена игры возрастет на к.
Лемма 2. Любая матричная игра с положительной платежной матрицей имеет решение.
Она сводится к паре двойственных задач линейного программирования (задача 1-го игрока – к задаче на минимум, задача 2-го игрока – к задаче на максимум)
, 
, 
Теорема 2. P* и Q* оптимальны Û E(Pi, Q*) £ v £ E(P*, Qj), Pi и Qj – чистые стратегии.
О сокращении матриц. Общий порядок решения игры.
Седловая точка. Мин. эл-т строки = макс. эл-т столбца.
Теорема 3. P* и Q* - чистые Û $! седловая точка
Вычеркивают доминируемые строки и доминирующие столбцы
1-2. Сокращение матрицы
1-2. Приведение матрицы к неотрицательной
3. Решение пары двойственных задач.
4. Возвращение к первоначальной матрице
Примеры.
1. Фермер может засеять свое поле четырьмя сортами пшеницы. Затраты на все семена, а также на обработку почвы одинаковы. Год может быть засушливым, нормальным и дождливым. Известны урожайности культур в зависимости от погоды и цена центнера для каждого сорта.
| Погода | Урожайность пшеницы в центнерах | |||
| П - 1 | П - 2 | П - 3 | П - 4 | |
| Сухая | ||||
| Нормальная | 7,5 | |||
| Дождливая | ||||
| Цена (ц / у. е.) |
Составьте матрицу выигрышей фермера и определите его оптимальную стратегию. Что вы ему порекомендуете делать?
2. Фирма А производит сезонный товар, который имеет спрос в течение n дней. Товар поступает на рынок ежедневно. Фирма В производит аналогичный товар, она хочет минимизировать доходы фирмы А (с целью разорения). Известно, что чем позже товар поступает на рынок, тем его качество выше. Реализуется только товар более высокого качества. Пусть ежедневный доход равен 6 (ден. ед.). Составить платежную матрицу при n = 6, n = 9, n = 12 и вычислить оптимальные стратегии фирм А и В. Описать поведение фирм (согласно полученным стратегиям), а также изменение стратегии фирм при увеличении числа дней торговли.
3. Cоставить платежную матрицу и определить оптимальные стратегии фирм А и В с целью привлечения наибольшего числа покупателей. Каждая из этих фирм может устанавливать свои магазины в любом из 4 заданных пунктов, расположенных в вершинах четырехугольника. Число жителей каждого из населенных пунктов, а также расстояния между ними даны на рисунках. Кроме того, задаются числа K (%) и L (%) - доли населения данного пункта, которые пользуются магазином фирмы А в случае, когда он расположен ближе (K) или дальше (L),чем магазин фирмы В. Если магазины находятся на равном расстоянии от данного пункта, то в каждый из них обращается половина жителей этого пункта.
Составить пару двойственных задач и решить их.
Составить платежную матрицу и сократить ее.
Решить другим способом, если возможно, и сравнить результаты.
| 14 тыс. | 4 км | 12 тыс. | ||||
| 6 км | 5 км | |||||
| 4 тыс. | 7 км | 8 тыс. |
K = 65, L = 45
4. Двое одновременно называют «1», «2» или «3».
Приближенное решение игры.
Численный метод решения матричных игр (Брауна-Робинсон)
Идея этого метода состоит в том, что разыгрывается «мысленный эксперимент». Оба игрока (А и В) поочередно применяют друг против друга свои стратегии, стараясь выиграть (проиграть) больше (меньше).
Эксперимент состоит из ряда партий. Один из игроков произвольно делает ход, второй игрок отвечает ему ходом, который хуже всего для первого, т.е. дает первому наименьший выигрыш. В свою очередь первый выбирает ход, который даст ему наибольший выигрыш при применении вторым игроком выбранного им предыдущего хода. Далее свой следующий ход выбирает второй игрок и т.д. На каждом шаге итерации игрок выбирает ход, худший для противника. При этом игроки вычисляют накопленный выигрыш, что позволяет находить на каждом шаге средний выигрыш за одну партию, т.е. дать оценку цены игры.
Доказано, что данный итерационный процесс является сходящимся. Средний выигрыш за одну партию будет стремиться к цене игры, а частоты применения ходов – к вероятностям оптимальных стратегий.
