Повторяющиеся игры: принцип минимакса
Минимаксная теорема Джона фон Неймана (иногда называемая фундаментальной теоремой теории игр для двух игроков), продемонстрированная в 1926 году, является важным результатом в теории игр.
Вернёмся к играм с нулевой суммой. В них на пересечениях стратегий в платёжной матрице записаны не пары чисел, а одно число – сумма, которую получает первый игрок от второго. Такое представление игры называется «матричной игрой».
Можно показать, что седловая точка является точкой наибольшей целесообразности для обоих игроков. Почему? Пусть первый игрок выбрал i-ю стратегию. Тогда элементы строки i в матрице будут означать его возможные выигрыши. Если второй игрок применит оптимальную для него стратегию, то выигрыш первого игрока, очевидно, будет равен минимальному элементу в i-й строке. Таким образом, первому игроку требуется выбрать такую строку, чтобы минимальный элемент в ней был наибольшим среди всех минимальных элементах в строках.
Число α=max1≤i≤m min1≤j≤n a_ij (то есть, такое число, которое является максимумом из всех минимальных значений по строкам) называется нижней ценой игры, стратегия первого игрока, приводящая к нему, называется максиминной.
Максиминная стратегия позволяет первому игроку получить гарантированный выигрыш, не меньший α вне зависимости от действий второго игрока.
Второй игрок заинтересован в том, чтобы первый игрок выиграл как можно меньше. Если он выберет j-ю стратегию (это будет соответствовать j-му столбцу платёжной матрицы), то при выборе первым игроком стратегии i выигрыш первого составит a_ij. Первый игрок, очевидно, выберет строку с наибольшим значением в столбце j и, следовательно, второму игроку требуется выбрать такой столбец, в котором такое наибольшее значение минимально. Выигрыш второго игрока при его наилучшей стратегии будет равен -max 1≤i≤m a_ij.
Число β=min 1≤i≤m max1≤j≤n a_ij является верхней ценой игры, а стратегия второго игрока, приводящая к нему, называется минимаксной.
Такая стратегия позволяет получить гарантированный выигрыш не меньший -β вне зависимости от действий первого игрока.
Эти стратегии, минимаксная и максиминная, являются осторожными стратегиями (они носят обобщённое название «минимаксные» стратегии), а сам принцип называется «принципом минимакса».
Если нижняя и верхняя цены игры совпадают, то игра называется игрой с седловой точкой, а это совпадающее значение носит название «цена игры».
Давайте выполним небольшое упражнение – найдём верхнюю и нижнюю цену игры с заданной платежной матрицей.
Решение. Давайте для каждой строки матрицы найдём наименьший элемент. Запишем справа от соответствующей строки. Для каждого столбца найдём наибольший элемент. Запишем его под соответствующим столбцом.
Тогда нижняя цена данной игры равна max(1; −1; 3; −1) = 3 ; верхняя цена игры равна min(3; 3; 5; 4; 5) = 3.
Есть ли у данной матрицы седловые точки? Да, причем их две, других нет – это точки на пересечении третьей строки с первым и вторым столбцами. Значит, оптимальной стратегией первого игрока будет выбрать третью строку, а второму без разницы, выбирать первый или второй столбец. Хотя я бы на месте второго игрока выбрала вторую стратегию, потому что в соответствующем ей столбце в целом поменьше числа. То есть, в равноценных ситуациях можно выбирать ту, куда выгоднее сходить, если есть шанс, что оппонент не настолько рационален, как вы. =)
Существуют игры, в которых можно явным образом откинуть заведомо нецелесообразные стратегии. Например, подобное мы наблюдали в рассмотренных ранее задачах.
Введём более формальное определение:
Убирание всех доминируемых строк из матрицы не приведёт к изменению решения. Этот принцип полезен для уменьшения размера платёжной матрицы. Подобное определение и метод уменьшения размера матрицы существует и для столбцов.