Матричные игры (стр. 2 из 3)

Игра состоит из двух ходов: игрок A выбирает одну из своих возможных стратегий

( i = 1, 2, …, m), а игрок B выбирает стратегию ( j = 1, 2, .., n), причем каждый участник делает выбор в полной ситуации незнании выбора другого игрока. В результате выигрыши и каждого из игроков удовлетворяют соотношению

, откуда если , имеем .

Цель игрока

– максимизировать функцию , а игрока В – минимизировать эту же функцию. Каждый из игроков может выбирать одну из переменных, от которых зависит значение функции. Если игрок А выбирает некоторую из стратегий , то это может влиять на значение функции . Влияние на величину значения является неопределенным, а определенность имеет место только после выбора, например, игроком B переменной (при этом определяется другим игроком).

Пусть

, тогда составим матрицу:

.

Строки матрицы соответствуют стратегиям

, столбцы – стратегиям . Матрица А называется матрицей игры, а элемент матрицы – выигрыш игрока А, если он выбрал стратегию , а игрок B выбрал стратегию .

Пусть игрок А выбрал некоторую стратегию

, тогда в худшем случае он получит выигрыш, равный . Поэтому предвидя такую возможность, игрок А должен выбрать ту стратегию, которая позволит максимизировать его минимальный выигрыш : . Величина - гарантированный выигрыш игрока А – называется нижней ценой игры, а стратегия , обеспечивающая получение - максиминной.

Игрок В, выбирая стратегию, исходит из следующего принципа: при выборе некоторой стратегии

его проигрышнее превысит максимального из значений элементов -го столбца матрицы, т.е. меньше или равен . Рассматривая множество для различных значений , игрок В выбирает такое значение , при котором его максимальный проигрыш минимизируется: . Величина называется верхней ценой игры, а соответствующая выигрышу стратегия - минимаксной.

Фактический выигрыш игрока А при разумных действиях обоих участников ограничен нижней и верхней ценой игры. Если эти выражения будут равны, т.е.

, то выигрыш игрока А – вполне определенное число, значит игра называется вполне определенной, а выигрыш – значением игры и равен элементу матрицы .

Вполне определенные игры называют играми с седловой точкой. Элемент

в матрице такой игры является одновременно минимальным в строке , максимальным в столбце и называется седловой точкой.

Седловой точке соответствуют оптимальные стратегии игроков, их совокупность – это решение игры, которое обладает следующим свойством: если один из игроков придерживается своей оптимальной стратегии, то для другого отклонение от его оптимальной стратегии не может быть выгодно.

Точка называется седловой из-за формы графика функции выигрыша в точке

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

Необходимо отметить, что в случае, если цена антагонистической игры равна 0, игра называется справедливой.

Задача: определить верхнюю и нижнюю цены для игр, заданных платежными матрицами А и В:

и .

Решение: минимальное значение

в строках матрицы А равны соответственно 2,3,1. Максимальное значение из них равно 3. Следовательно, - нижняя цена игры, которой соответствует матрица , равна 3.

Для определения (верхней цены игры) найдем максимальные значения элементов в столбцах матрицы. По столбцам имеем: 4, 5, 6, 5. Следовательно, .

Для матрицы

составляем аналогично и :

и .

Таким образом,

- цена игры. Решение данной игры состоит в выборе игроком стратегии , при этом выигрыш составит не меньше 4, а для игрока стратегия , позволяющая ограничить проигрыш числом 3.

Игровые системы, содержащие седловую точку, имеют заранее известное решение, т.к. каждый из игроков применяет свою оптимальную стратегию. Решение игры, матрицы которой не содержат седловой точки (т.е.

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