ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. Платжная матрица Нижняя и верхняя цена игры Рассмотрим парную конечную игру. Пусть игрок А располагает m личными стратегиями, которые обозначим А1, А2 Аm. Пусть у игрока В имеется n личных стратегий, обозначим их B1, B2 Вn. Говорят, что игра имеет размерность mn. В результате выбора игроками любой пары стратегий Аi и Вj i 1, 2 m j 1, 2 n однозначно определяется исход игры, т.е. выигрыш аij игрока А положительный или отрицательный и проигрыш -аij игрока В. Предположим, что значения аij известны для любой пары стратегий Аi, Bj. Матрица Р аij, i 1, 2 m j 1, 2 n, элементами которой являются выигрыши, соответствующие стратегиям Аi и Вj, называется платжной матрицей или матрицей игры. Общий вид такой матрицы представлен в табл. 1 Таблица 1 Bi Аj В1 В2 Вn А1 а11 а12 а1n А2 а21 а22 а2n Аm аm1 аm2 аmn Строки этой таблицы соответствуют стратегиям игрока А, а столбцы стратегиям игрока В. Рассмотрим игру mn с матрицей Р аij, i 1, 2 m j 1, 2, ,n и определим наилучшую среди стратегий А1, А2 Аm. Выбирая стратегию Аi, игрок А должен рассчитывать, что игрок В ответит на не той из стратегий Вj, для которой выигрыш для игрока А минимален игрок В стремится навредить игроку А. Обозначим через i наименьший выигрыш игрока А при выборе им стратегии Аi для всех возможных стратегий игрока В наименьшее число в i-й строчке платжной матрицы, т.е Среди всех чисел i i 1, 2, ,m выберем наибольшее. Назовм нижней ценой игры, или максимальным выигрышем максимином.
Это гарантированный выигрыш игрока А при любой стратегии игрока В. Следовательно Стратегия, соответствующая максимину, называется максиминной стратегией.
Игрок В заинтересован в том, чтобы уменьшить выигрыш игрока А выбирая стратегию Вj, он учитывает максимально возможный при этом выигрыш для А. Обозначим. Среди всех чисел j выберем наименьшее и назовм верхней ценой игры или минимаксным выигрышем минимаксом.
Это гарантированный проигрыш игрока В. Следовательно Стратегия, соответствующая минимаксу, называется минимаксной стратегией.
Принцип, диктующий игрокам выбор наиболее осторожных минимаксной и максиминной стратегий, называется принципом минимакса. Этот принцип следует из разумного предположения, что каждый игрок стремится достичь цели, противоположной цели противника.
Любая стратегия игрока В является минимаксной. Дополнив таблицу 1 строкой j и столбцом i, получим таблицу 2. На пересечении дополнительных строки и столбца будем записывать верхнюю и нижнюю цены игр. Таблица 2 Bi Aj B1 B2 i A1 - 1 1 - 1 A2 1 - 1 - 1 j 1 1 -1 1 Если верхняя и нижняя цены игры совпадают, то общее значение верхней и нижней цены игры называется чистой ценой игры, или ценой игры. Минимаксные стратегии, соответствующие цене игры, являются оптимальными стратегиями, а их совокупность оптимальным решением, или решением игры. В этом случае игрок А получает максимальный гарантированный не зависящий от поведения игрока В выигрыш, а игрок В добивается минимального гарантированного вне зависимости от поведения игрока А проигрыша. Говорят, что решение игры обладает устойчивостью, т.е. если один из игроков придерживается своей оптимальной стратегии, то для другого не может быть выгодным отклоняться от своей оптимальной стратегии.
Пара чистых стратегии Ai и Bj дат оптимальное решение игры тогда и только тогда, когда соответствующий ей элемент aij является одновременно наибольшим в свом столбце и наименьшим в своей строке.
Такая ситуация, если она существует, называется седловой точкой по аналогии с поверхностью седла, которая искривляется вверх в одном направлении и вниз в другом. Обозначим А и В - пару чистых стратегий, на которых достигается решение игры в задаче с седловой точкой. Введм функцию выигрыша первого игрока на каждой паре стратегий PAi, Bj aij. Тогда из условия оптимальности в седловой точке выполняется двойное неравенство PAi, B PA, B PA, Bj, которое справедливо для всех i 1 m j 1 n. Действительно, выбор стратегии А первым игроком при оптимальной стратегии В второго игрока максимизирует минимальный возможный выигрыш PA, B PAi, B, а выбор стратегии В вторым игроком при оптимальной стратегии первого минимизирует максимальный проигрыш PA, B PA, B.