Элементы теории матричных игр

Определения процесс принятия решений в конфликтных ситуациях… игры 2 (парные) и n 3 лиц. участники игры - игроки. Игра состоит из последовательности действий (ходов), среди кот. могут быть как личные ходы, так и случайные. Выбор личных ходов основан на стратегии игрока. Стратегия игрока – это набор правил для определения варианта действий, используемых при выборе каж. личного хода. Результат ходов игроков оценивается платежными функциями участников игры, кот. можно интерпретировать как их выигрыши. Если сумма выигрышей всех игроков = 0, то такую игру наз. игрой с нулевой суммой.

Определения Стратегия игрока является opt, если при многократном повторении игры его средний выигрыш max. Будем считать, что игроки ведут себя разумно (без риска и азарта)… Матричная игра – это парная игра, в кот. заданы: {1, …, m} – мн. стратегий 1 игрока, {1, …, n} – мн. стратегий 2 игрока, пары стратегий i {1,…,m} и j {1,…,n} определен выигрыш 1 игрока = a ij. Mat A=(a ij, i=1,…,m, j=1,…,n) наз. платежной. цель 1-го игрока – max своего выигрыша, цель 2-го игрока – min выигрыша 1-го игрока.

Принцип осторожности Предположим, что 2-й игрок знает все ходы 1-го игрока заранее. Тогда на каждый ход 1-го игрока i он отвечает лучшей стратегией j(i): a i,j(i) a ij Лучшая чистая стратегия 1 игрока i 0 : С др. стороны, если предположить, что 1-й игрок отвечает на стратегию j 2-го игрока своей лучшей стратегией i(j), то

Принцип осторожности Стратегии i 0 и j 0 определяются игроками по принципу осторожности, т.к. каж. игрок при выборе хода учитывает самый плохой для себя вариант развития событий. 0 – нижняя цена игры 0 – верхняя цена игры Если 1 игрок придерживается принципа осторожности, то его выигрыш 0. Если 2 игрок придерживается принципа осторожности, то выигрыш 1 игрока 0.

Лемма о minmax и maxmin Лемма. функции f(x, y), x X, y Y справедливо неравенство: Доказательство. Пусть и Тогда 0 0 случай 0 = 0 удовлетворяет обоих игроков, и выбор стратегий i 0, j 0, на которых достигается =, является opt (решением mat игры в чистых стратегиях).

Седловая точка Седловой точкой mat A наз. пара номеров строка-столбец (i 0, j 0 ) : min в строке & max в столбце

Теорема. Необходимым и достаточным условием = нижней и верхней цен игры является седловой точки в платежной mat A. Доказательство. ) Пусть 0 = 0. По def: Теорема о седловой точке ) Пусть (i 0, j 0 ) – седловая точка. По def : С др. стороны

Решение mat игр в смешанных стратегиях Не всякая mat имеет седловую точку… Смешанная стратегия – это вероятностное распределение на мн. чистых стратегий: p i – вероятность использования 1-м игроком чистой стратегии i, q j – вероятность использования 2-м игроком чистой стратегии j. Применение смешанных стратегий – это чередование чистых стратегий согласно их вероятностям при многократном повторении игры.

Принцип осторожности пары смеш. стратегий (p, q) определим платежную функцию как мат. ожидание величины выигрыша 1-го игрока: Принцип осторожности в данном сл. приводит к определению след. характеристик: где нижняя, а верхняя цены игры в смеш. стратегиях.

Теорема Фон Неймана Теорема. В mat игре пара смеш. стратегий (p *, q * ): 1. E(p, q * ) E(p *, q * ) E(p *, q), p P, q Q; 2. = = = E(p *, q * ) цена игры. Доказательство. Сформулируем задачи 1 и 2 игроков в виде задач ЛП. Добавив достаточно большое число ко всем элементам платежной матрицы > 0. Задача 1-го игрока: Обозначим Разделив на (p), получим Задача 1 игрока

Доказательство теоремы Фон Неймана Задача 2 игрока Пусть u * и v * opt реш. дв. задач Согласно принципу дополняющей нежесткости: Просуммируем последние = по j и по i и разделим на f(u * ) (v * )

Доказательство теоремы Фон Неймана и утв. 1 доказано. Из E(p, q * ) E(p *, q * ) E(p *, q), p P, q Q С др. стор. (по лемме о maxmin и minmax) = (p * ) = E(p *, q * ) = = (q * ).

Методы решение матричных игр Если платежная mat имеет седловую точку, то решение игры в чистых стратегиях, кот. определяется седловой точкой mat. Предположим, что седловой точки в платежной mat нет. Тогда mat игру следует решать в смешанных стратегиях. Строка i доминирует строку k, если a ij a kj, j и такой столбец d, что a id > a kd Столбец j доминирует столбец k, если a ij a ik, i и такая строка d, что a dj < a dk Подмн. доминируемых строк и столбцов могут быть исключены из платежной mat

Активные стратегии Чистая стратегия i является активной, если она используется в некоторой opt стратегии с >0 вероятностью. Другими словами, если opt стратегия p (q) такая, что p i > 0 (q j > 0), то чистая стратегия i (j) является активной для 1 (2) игрока. Теорема (об активных стратегиях). Если один игрок придерживается opt стратегии, то его соперник достигает цены игры, применяя любую свою смешанную стратегию, в которой используются только активные стратегии. Доказательство. Пусть 1 игрок использует opt ст. p *, а 2 смеш. ст. q, в кот. q j > 0, j J, где J подмн. активных ст. 2 игрока. Необходимо доказать, что цена игры = E(p *, q). Пусть j = E(p *, q j ), где q j = (0, …, 0, 1, 0, …, 0). Очевидно, j, j. Покажем, что для активной ст. j j =.

Активные стратегии По def цены игры имеем: j J имеет место j =. Из

Решение игр 2 2 Седловой точки нет! В силу теоремы об активных стратегиях, если 1 игрок использует opt стратегию, то 2 достигает цены игры при любой своей смеш. стратегии, в которой используются только активные чистые стратегии, например при

Решение игр 2 n и m 2 Рассм. игру 2 n и найдем opt смеш. стр. 1 игрока Положим и f(x)= (p) Тогда по теореме об активных стратегиях Получаем з. max миноранты семейства лин. ф. в (0, 1): Посколькуи миноранта семейства лин. ф. вогнута, непрерывна и кусочно-линейная, то ее max на (0, 1) достигается в 1 из внутренних точек излома и может быть найден за время O(n 2 )

Решение игр 2 n Пусть max миноранты достигается на пересечении прямых и Тогда для решения игры достаточно рассмотреть mat игру 2 2 с mat

Пример решения игры 2 n

Пример решения игры 3 3 взяв q 1 = (1,0,0), q 2 = (0,1,0) и q 3 = (0,0,1), получим Выразим p 3 = 1– p 1 – p 2 и запишем задачу 1 игрока: Пусть D = {(p 1, p 2 ) | 0 p 1 + p 2 1; p 1, p 2 0} доп. область. Определим в D подобласти, где max зн. принимает 1 из величин f i, i =1,2,3. Для этого рассмотрим следующие случаи.

Пример решения игры 3 3 а) Сравним f 1 и f 3. Если f 1 = f 3, то 7p 2 – 4 = 11p 2 – 6 p 2 = 1/2. В области D 1 = {(p 1, p 2 ) | p 2 [1/2, 1], p 1 [0, 1 – p 2 ]} f 1 f 3 В области D 2 = {(p 1, p 2 ) | p 2 [0, 1/2], p 1 [0, 1 – p 2 ]} f 1 f 3 б) Сравним f 1 и f 2. Если f 1 = f 2, то 2p 1 + 7p 2 – 4 = 5 – 2p 1 – 9p 2 4p p 2 = 9 Если (p 1, p 2 ) R 1 ={(p 1, p 2 ) | p 1 [0,7/12], p 2 [(9 – 4p 1 )/16,1 – p 1 ]}, то f 2 f 1. В случае (p 1, p 2 ) R 2 ={(p 1,p 2 ) | p 1 [0,7/12], p 2 [0,(9 – 4p 1 )16]; p 1 [7/12, 1], p 2 [0, 1 – p 1 ]} имеем f 2 f 1

Пример решения игры 3 3 f1f1 f3f3 f2f2 f1f1

в) Сравним f 2 и f 3. Если f 2 = f 3, то 5 – 2p 1 – 9p 2 = 2p p 2 – 6 4p p 2 = 11. Значит, Если (p 1,p 2 ) S 1 ={(p 1,p 2 ) | p 1 [0,9/16], p 2 [(11 – 4p 1 )/20, 1 – p 1 ]}, то f 2 f 3. В случае (p 1,p 2 ) S 2 ={(p 1,p 2 ) | p 1 [0,9/16], p 2 [0,(11– 4p 1 )/20]; p 1 [9/16, 1], p 2 [0, 1 – p 1 } имеем f 2 f 3 Итак, область D делится прямыми p 2 = 1/2, 4p 1 +16p 2 =9 и 4p 1 +20p 2 =11 на 6 подобластей K j, j = 1, …, 6

Пример решения игры если (p 1, p 2 ) K 2 K 3, то min{f 1, f 2, f 3 } = f 1 ; - если (p 1, p 2 ) K 1 K 4, то min{f 1, f 2, f 3 } = f 2 ; - если (p 1, p 2 ) K 5 K 6, то min{f 1, f 2, f 3 } = f 3. f2f2 f3f3

Пример решения игры 3 3 Т.к. лин. ф. принимает экстремальные зн. на границе области, то

Пример решения игры 3 3 Нижняя цена игры, по т. об акт. стр. является ценой игры, = Чтобы найти opt смеш. стратегию 2 игрока достаточно еще раз воспользоваться теоремой об активных стратегиях. Получим Для решения mat игры с произвольными n и m можно применять как метод ЛП (см. теорему Фон Неймана), так и итеративный метод Брауна-Робинсон

Итеративный метод Брауна-Робинсон Идея метода заключается в поочередном выборе каждой стороной наилучшей чистой стратегии против наблюдаемого эмпирического распределения чистых стратегий противника. На 1 шаге противники выбирают произвольные чистые стратегии. Пусть на первых N шагах последовательно выбирались стратегии и – кол. шагов, на кот. 1 и 2 игроками выбирались стр. i и j

Итеративный метод Брауна-Робинсон На шаге (N+1) выбираются такие чистые стратегии, что

Пример решения mat игры методом Брауна-Робинсон Шаг 1. Шаг 2. Шаг 3. Шаг 4.

Пример решения mat игры методом Брауна-Робинсон Остановка по критериюне корректна…