Моделирование конфликтных ситуаций. Принцип минимакса. Понятие седловой точки.

При проектировании возникают ситуации, характеризуемые противоположностью интересов двух (или более) сторон, и тогда результат действия одной из сторон зависит от образа действия других. Такие ситуации называются конфликтными и изучаются теорией игр, позволяющей формализовать и анализировать количественно конфликтные ситуации и дающей рекомендации о наилучшем поведении объекта в таких ситуациях.

Остановимся на некоторых определениях. Игра - это упрощенная формализованная модель реальной конфликтной ситуации. Формализация конфликтных ситуаций заключается в том, что действия сторон подчинены определенным правилам, которые называют правилами игры. Правила игры предопределяют возможные варианты действия, или стратегии, сторон.

Рассмотрим парные игры, т. е. игры двух сторон (игроков) А и В. Результаты игры, т. е. выигрыш или проигрыш, характеризуется числом (ценой игры). Джон фон Нейман исследовал игры с "нулевой суммой", когда выигрыш стороны А есть проигрыш стороны В, т. е. результат от реализации принятого решения распределяется между сторонами. Или, точнее, алгебраическая сумма выигрышей сторон равна нулю. Поскольку в игре с нулевой суммой интересы сторон прямо противоположны, достаточно рассматривать выигрыш одной стороны. Согласно основной теореме теории игр игрок В может выиграть в среднем сумму, равную К за одну игру, а игрок А может ему помешать выиграть большую сумму. Утверждается также, что для игрока В существует оптимальная стратегия, обеспечивающая выигрыш этой суммы, а при применении оптимальной стратегии игроком А он может проиграть не более чем К. это так называемый принцип (теорема) минимакса, который запишем в виде:

где a и b - соответственно характеристики действия игроков А и В; – функция потерь, или платежная функция. В случае если имеет место равенство:

то соответствующее значение функции называется седловой точкой игры, которая является точкой пересечения оптимальных стратегий игроков А и В.

В этой точке минимум максимума потерь одного игрока совпадает с максимумом минимума потерь другого. На рис. 2.5.1. представлена поверхность, имеющая седловую форму, где точка К – седловая точка игры.

Например, при проектировании системы управления летательного аппарата игроком А можно считать конструктора. Его цель заключается в том, чтобы путем выбора соответствующего алгоритма управления получить наибольший эффект, например, минимизировать средний квадрат ошибки управления. Природа – игрок В в наименее благоприятном случае имеет прямо противоположную цель – максимизировать средний квадрат ошибки управления для чего располагает выбором характеристик входных воздействий. В нашем примере стратегия игрока А – выбор оптимального алгоритма управления, а стратегия игрока В – выбор реализации входного сигнала. Ограничимся рассмотрением конечной игры, т. е. такой игры, в которой игроки А и В располагают только конечным числом стратегий (в отличие от бесконечных игр). Игрок А располагает стратегиями Игрок В располагает стратегиями Это так называемая игра m x n. Выигрыш игрока А при стратегиях и обозначим через

В общем случае выигрыш является случайной величиной, т. е. обозначает средний выигрыш. Значения образуют платежную матрицу, иначе называемую матрицей игры или эффективности. Назовем меру выигрыша показателем эффективности варианта стратегии в условиях . Матрица эффективности в этом случае аналогична табл. 3.2, в которой вместо варианта решения записывают вариант стратегии и заменяют на

Решить игру m x n, значит найти для каждого игрока такую стратегию, чтобы его средний выигрыш за большое число игр был наибольшим.

Рис.2.5.1. Геометрическая интерпретация теоремы минимакса.

Таблица 3.2

			…	i
			…
			…
…	…	…		…
j			…

Теория игр рекомендует каждому игроку выбирать такую стратегию, при которой получается максимально возможный выигрыш при наименее благо­приятном действии противника. Такую стратегию называют стратегией мини­макса. Оптимальная стратегия игрока А определяется из матрицы эффективно­сти путем отыскания такого ее элемента, который удовлетворяет условию

– выигрыш,

иными словами, такой элемент выбран как максимальный по строкам i из ми­нимальных в каждой строке по столбцам j. Оптимальная стратегия игрока В оп­ределяется по элементу

– проигрыш,

иными словами, по такому элементу матрицы, который является минимальным по столбцам j из максимальных по строкам i каждого столбца.