Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011

Определим матрицы A1 и B1 как матрицы размером m × n , (i, j) элементы которых есть aij и bij . Игра полностью определена, ко-

гда заданы матрицы выигрышей A1 и B1 .

Смешанная стратегия игрока A есть столбец X из неотрицательных элементов xi , которые представляют собой относитель-

ную частоту, с которой A будет выбирать свою i -ю чистую стратегию. Таким образом,

Аналогично смешанная стратегия игрока B есть столбец Y , неотрицательные элементы y j которого в сумме равны 1. Если A и

B всегда выбирают чистую стратегию случайным образом в соответствии с распределением вероятностей, заданным векторами X и Y , то ожидаемые выигрыши игроков A и B получаются

Вэтих соотношениях выражение в скобках означает скалярное произведение соответствующих векторов.

Вотличие от матричных игр, где существует единственный критерий оптимальности поведения игроков, в неантагонистических играх вообще и в биматричных в частности, таких критериев не-

сколько. Различают ситуации равновесия по Нэшу, сильно равновесные ситуации и ситуации, оптимальные по Парето. Каждый из этих подходов к оценке оптимальности поведения игроков имеет свои достоинства и свои недостатки [40].

Далее пойдет речь только о ситуациях равновесия по Нэшу. Ситуация равновесия в игре есть пара смешанных стратегий

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

106

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

Теорема Нэша гарантирует существование ситуаций равновесия в биматричных играх [40], но не дает никаких средств для их нахождения.

Наиболее эффективным из всех известных алгоритмов для практических вычислений ситуации равновесия является алгоритм, предложенный Лемке и Хоусоном в 1963 г. [59]. По своей сути этот алгоритм тесно связан с методами нелинейного программирования, изложенными в п. 1.3. Следует особо подчеркнуть то обстоятельство, что данный алгоритм может быть без особых затруднений реализован на ЭВМ.

Докажем, прежде всего, две теоремы, на основании которых можно сформулировать постановку задачи.

Теорема 2.1. Ситуация (X 0 ,Y 0 ) является ситуацией равновесия в биматричной игре с матрицами выигрышей A1 и B1 в том и только в том случае, когда

где Lm и Ln – векторы размерности m и n соответственно, со-

ставленные из единиц (знаки неравенств используются для покоординатного сравнения векторов).

Доказательство. Пусть (X 0 ,Y 0 ) – ситуация равновесия, т.е.

Возьмем в качестве X и Y векторы, у которых одна из компонент равна единице, а остальные – нулю. Получим m + n соотношений

Наоборот, пусть выполняются указанные условия.

107

Вектор

является произвольным вектором. Представим его в базисе единичных векторов f1, f2 ,..., fm следующим образом:

что и требовалось доказать.

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

где d – достаточно большая положительная константа, такая, что A > 0 и B > 0 , E – матрица размерности (m × n) , составленная из

(2.24) изменяются и условия (2.20).

108

Это соотношение можно использовать при вычислении цены

Используя полученный в начале доказательства результат, при-

109

Согласно теореме 2.1 выполнение этих условий является необ-

матрицы B , есть эквивалентная форма записи условий теоремы.

2.1.4.2.Нахождение ситуации равновесия

вбиматричных играх

Доказав теоремы 2.1 и 2.2, получили критерий, с помощью которого удобно определять, является ли пара (X 0 ,Y 0 ) ситуацией

равновесия.

Действительно, если исходить только из определения ситуации равновесия, то для проверки пары (X 0 ,Y 0 ) необходимо переби-

рать все векторы X и Y из множества смешанных стратегий. Сделать это невозможно. Вот почему потребовалось найти необходимое и достаточное условие, в записи которого фигурируют только векторы X 0 и Y 0 .

Постановка задачи нахождения ситуации равновесия. Пусть

A и B > 0 . Задача состоит в том, чтобы найти пару (X * ,Y * ) , для которой выполняются условия:

Будем называть любую пару (X * ,Y * ) ситуацией равновесия.

Допустимое множество для поиска смешанных стратегий игрока 1 определяется в соответствии с соотношениями (2.40) и (2.41) следующим образом:

110